History
On 4 March 2006 the working group posted 802.1aq draft 0.1. In March 2012 the IEEE approved the 802.1aq standard. In May 2013, the first public multivendor interoperability was demonstrated as SPB served as the backbone for Interop 2013 in Las Vegas. In 2013 and 2014 SPB was used to build the InteropNet backbone with only one-tenth the resources of prior years. DuringAssociated protocols
* IEEE 802.1Q-2014 - Bridges and Bridged Networks - This standard incorporates Shortest Path Bridging (IEEE 802.1aq) with the following: IEEE Std 802.1Q-2011, IEEE Std 802.1Qbe-2011, IEEE Std 802.1Qbc-2011, IEEE Std 802.1Qbb-2011, IEEE Std 802.1Qaz-2011, IEEE Std 802.1Qbf-2011, IEEE Std 802.1Qbg-2012, IEEE Std 802.1Q-2011/Cor 2–2012, and IEEE Std 802.1Qbp-2014, and much functionality previously specified in 802.1D. * IEEE 802.1ag - Connectivity Fault Management (CFM) * IEEE 802.1Qbp - Equal Cost Multiple Paths in Shortest Path Bridging * IEEE P802.1Qcj - Automatic Attachment to Provider Backbone Bridging (PBB) services * RFC 6329 - IS-IS Extensions Supporting IEEE 802.1aq Shortest Path BridgingRFC 6329
TheProtocol extensions
The IS-IS extensions defined in RFC 6329 that deliver standardized support for 802.1aq SPB are: * IS-IS Hello (IIH) Protocol Extensions * Node Information Extensions * Adjacency Information Extensions * Service Information Extensions= IS-IS Hello (IIH) protocol extensions
= 802.1aq has been designed to operate in parallel with other network layer protocols such as IPv4 and IPv6; therefore, failure of two nodes to establish an SPB adjacency will not cause network layer protocols to also reject an adjacency. RFC 6328 assigns 802.1aq the Network Layer Protocol ID (NLPID) value 0xC1. This NLPID is used by SPB Bridges to indicate their ability to form adjacencies and operate as part of an 802.1aq domain. 802.1aq frames flow on adjacencies that advertise this NLPID in both directions, and nodes regard an adjacency that has not been advertised in both directions as non-existent (with infinite link metric). 802.1aq augments the normal IIH PDU with three new TLVs, which like all other SPB TLVs, travel within ''Multi-Topology TLV''s, therefore allowing multiple logical instances of SPB within a single IS-IS protocol instance. SPB can use many VIDs, agreeing on which VIDs are used for which purposes. The IIH PDUs carry a digest of all the used VIDs, referred to as the ''Multiple Spanning Tree Configuration TLV'' which uses a common and compact encoding reused from IEEE 802.1Q. For the purposes of loop prevention SPB neighbors may also support a mechanism to verify that the contents of their topology databases are synchronized. Exchanging digests of SPB topology information, using the optional ''SPB-Digest sub-TLV'', allows nodes to compare information and take specific action where a mismatch in topology is indicated. Finally, SPB needs to know which shortest path tree (SPT) sets are being used by which VIDs, and this is carried in the ''Base VLAN Identifiers TLV''.= Node information extensions
= All SPB nodal information extensions travel within a new ''Multi-Topology (MT) capability TLV''. There can be one or many MT-Capability TLVs present, depending on the amount of information that needs to be carried. The ''SPB Instance sub-TLV'' gives the Shortest Path Source ID (SPSourceID) for this node or topology instance. This is used in the formation of multicast destination addresses (DAs) for frames originating from this node or instance. There are multiple ECT algorithms defined for SPB and additional algorithms may be defined in the future including but not limited to ECMP- or hash-based behaviors and (*,G)=Adjacency information extensions
= The ''SPB Link Metric sub-TLV'' occurs within the Multi-Topology Intermediate System Neighbor TLV or within the Extended IS Reachability TLV. ''SPB Adjacency Opaque Equal Cost Tree Algorithm TLV'' also occurs within the Multi-Topology Intermediate System TLV or the Extended IS Reachability TLV. Where this sub-TLV is not present for an IS-IS adjacency, that adjacency will not carry SPB traffic for the given topology instance.= Service information extensions
= The '' SPBM Service Identifier and Unicast Address TLV'' is used to introduce service group membership on the originating node or to advertise an additional B-MAC unicast address present on, or reachable by the node. The '' SPBV MAC Address TLV'' is the IS-IS sub-TLV used for advertisement of group MAC addresses in SPBV mode.Benefits
Shortest Path Bridging-VID (SPBV) and Shortest Path Bridging-MAC (SPBM) are two operating modes of 802.1aq. Both inherit key benefits of link state routing: * the ability to use all available physical connectivity, because loop avoidance uses a control plane with a global view of network topology * fast restoration of connectivity after failure, again because of link state routing's global view of network topology * under failure, the property that only directly affected traffic is impacted during restoration * rapid restoration of broadcast and multicast connectivity, because IS-IS floods all of the required information in the SPB extensions to IS-IS, thereby allowing unicast and multicast connectivity to be installed in parallel, with no need for a second phase signaling process to run over the converged unicast topology to compute and install multicast trees. SPBM offers emulation of a transparent Ethernet LAN segment. It implements VLANs with scoped multicast trees, which means no egress discard of broadcast, unknown-unicast and multicast traffic, a feature common to approaches that use a small number of shared trees, hence the network does not simply degrade with size as the percentage of frames discarded goes up. The carrier-space equivalent of this application is the delivery of Ethernet VPN services to Enterprises over common carrier infrastructure. The required attributes are fundamentally the same; complete transparency for customer Ethernet services (both point-to-point and LAN), and complete isolation between one customer's traffic and that of all other customers. A further consequence of SPBM's transparency in both data plane and control plane is that it delivers the MEF 6.1 service set. It also provides the carrier with the toolkit to support geo-redundant broadband backhaul; in these applications, many DSLAMs or other access equipment must be backhauled to multiple Broadband Remote Access Server (BRAS) sites, with application-determined binding of sessions to a BRAS. However, DSLAMs must not be allowed to communicate with each other, because carriers then lose the ability to control peer-to-peer connectivity. MEF E-TREE does just this, and further provides an efficient multicast fabric for the distribution ofOperations and management
802.1aq builds on all existing Ethernet operations, administration and management (OA&M). Since 802.1aq ensures that itsHigh level
802.1aq is the IEEE-sanctioned link state Ethernet control plane for all IEEE VLANs covered in IEEE 802.1Q. The Shortest Path Bridging virtual local area network identifier (VLAN ID) or Shortest Path Bridging VID (SPBV) provides a capability that is backward compatible withShortest Path Bridging-VID
A primary feature of Shortest Path Bridging is the ability to use link state IS-IS to learn network topology. In SPBV the mechanism used to identify the tree is to use a different Shortest Path VLAN ID (SPVID) for each source bridge. The IS-IS topology is used both to allocate unique SPVIDs and to enable shortest path forwarding for individual and group addresses. Originally targeted for small, low-configuration networks, SPB grew into a larger project encompassing the latest provider control plane for SPBV and harmonizing the concepts of Ethernet's data plane. SPB defines a shortest path ''region'' which is the boundary of the shortest path topology and the rest of the VLAN topology, which may be any number of legacy bridges. SPB operates by learning the SPB-capable bridges and growing the ''region'' to include the SPB-capable bridges that have the same Base VID and MSTID configuration digest (Allocation of VIDs for SPB purposes). SPBV builds shortest-path trees that support loop prevention and optionally support loop mitigation on the SPVID. SPBV still allows learning of Ethernet MAC addresses but it can distribute multicast addresses that can be used to prune the shortest path trees according to the multicast membership either through Multiple MAC Registration Protocol (MMRP) or directly using IS-IS distribution of multicast membership. SPBV builds shortest-path trees but also interworks with legacy bridges running Rapid Spanning Tree Protocol and Multiple Spanning Tree Protocol (MSTP). SPBV uses techniques from MSTP regions to interwork with non-SPT regions behaving logically as a large distributed bridge as viewed from outside the region. SPBV supports shortest path trees but SPBV also builds a spanning tree which is computed from the link state database and uses the Base VID. This means that SPBV can use this traditional spanning tree for computation of the common and internal spanning tree (CIST). The CIST is the default tree used to interwork with other legacy bridges. It also serves as a fallback spanning tree if there are configuration problems with SPBV. SPBV has been designed to manage a moderate number of bridges. SPBV differs from SPBM in that MAC addresses are learned on all bridges that lie on the shortest path and shared VLAN learning is used since destination MACs may be associated with multiple SPVIDs. SPBV learns all MACs it forwards even outside the SPBV region.Shortest Path Bridging-MAC
Shortest Path Bridging-MAC (SPBM) reuses the PBB data plane which does not require that the Backbone Core Bridges (BCB) learn encapsulated client addresses. At the edge of the network the C-MAC (client) addresses are learned. SPBM is very similar to Provider Link State Bridging (PLSB) using the same data and control planes but the format and contents of the control messages in PLSB are not compatible. Individual MAC frames ofFailure recovery
Failure recovery is as per normal IS-IS with the link failure being advertised and new computations being performed, resulting in new FDB tables. Since no Ethernet addresses are advertised or known by this protocol, there is no re-learning required by the SPBM core and its learned encapsulations are unaffected by a transit node or link failure. Fast link failure detection may be performed using IEEE 802.1ag Continuity Check Messages (CCMs) which test link status and report a failure to the IS-IS protocol. This allows much faster failure detection than is possible using the IS-IS hello message loss mechanisms. Both SPBV and SPBM inherit the rapid convergence of a link state control plane. A special attribute of SPBM is its ability to rebuild multicast trees in a similar time to unicast convergence, because it substitutes computation for signaling. When an SPBM bridge has performed the computations on a topology database, it knows whether it is on the shortest path between a root and one or more leaves of the SPT and can install state accordingly. Convergence is not gated by incremental discovery of a bridge's place on a multicast tree by the use of separate signaling transactions. However, SPBM on a node does not operate completely independently of its peers, and enforces agreement on the current network topology with its peers. This very efficient mechanism uses exchange of a single digest of link state covering the entire network view, and does not need agreement on each path to each root individually. The result is that the volume of messaging exchanged to converge the network is in proportion to the incremental change in topology and not the number of multicast trees in the network. A simple link event that may change many trees is communicated by signaling the link event only; the consequent tree construction is performed by local computation at each node. The addition of a single service access point to a service instance involves only the announcement of the I-SID, regardless of the number of trees. Similarly the removal of a bridge, which might involve the rebuilding of hundreds to thousands of trees, is signaled only with a few link state updates. Commercial offerings will likely offer SPB over multi-chassis lag. In this environment multiple switch chassis appear as a single switch to the SPB control plane, and multiple links between pairs of chassis appear as an aggregate link. In this context a single link or node failure is not seen by the control plane and is handled locally resulting in sub 50ms recovery times.Animations
Following are three animated GIFs which help to show the behavior of 802.1aq. The first of these gifs, shown in Figure 5, demonstrates the routing in a 66 node network where we have created a 7-member E-LAN using ISID 100. In this example we show the equal cost tree (ECT) created from each member to reach all of the other members. We cycle through each member to show the full set of trees created for this service. We pause at one point to show the symmetry of routing between two of the nodes and emphasize it with a red line. In each case the source of the tree is highlighted with a small purple V. The second of these animated gifs, shown in Figure 6, demonstrates 8 ECT paths in the same 66 node network as Figure 4. In each subsequent animated frame the same source is used (in purple) but a different destination is shown (in yellow). For each frame, all of the shortest paths are shown superimposed between the source and destination. When two shortest paths traverse the same hop, the thickness of the lines being drawn is increased. In addition to the 66 node network, a small multi level Data Center style network is also shown with sources and destinations both within the servers (at the bottom) and from servers to the router layer at the top. This animation helps to show the diversity of the ECT being produced. The last of these animated gifs, shown in Figure 7, demonstrates source destination ECT paths using all 16 of the standard algorithms currently defined.Details
Equal cost multi tree
Sixteen equal cost multi tree (ECMT) paths are initially defined, however there are many more possible. ECMT in an IEEE 802.1aq network is more predictable than with internet protocol (IP) or multiprotocol label switching (MPLS) because of symmetry between the forward and reverse paths. The choice as to which ECMT path will be used is therefore an operator assigned head end decision while it is a local / hashing decision with IP/MPLS. IEEE 802.1aq, when faced with a choice between two equal link cost paths, uses the following logic for its first ECMT tie breaking algorithm: first, if one path is shorter than the other in terms of hops, the shorter path is chosen, otherwise, the path with the minimum Bridge Identifier is chosen. Other ECMT algorithms are created by simply using known permutations of the BridgePriority, , SysIds. For example, the second defined ECMT algorithm uses the path with the minimum of the inverse of the BridgeIdentifier and can be thought of as taking the path with the maximum node identifier. For SPBM, each permutation is instantiated as a distinct B-VID. The upper limit of multipath permutations is gated by the number of B-VIDs delegated to 802.1aq operation, a maximum of 4094, although the number of useful path permutations would only require a fraction of the available B-VID space. Fourteen additional ECMT algorithms are defined with different bit masks applied to the BridgeIdentifiers. Since the BridgeIdentifier includes a priority field, it is possible to adjust the ECMT behavior by changing the BridgePriority up or down. A service is assigned to a given ECMT B-VID at the edge of the network by configuration. As a result, non-participating packets associated with that service are encapsulated with the VID associated with the desired ECMT end to end path. All individual and group address traffic associated with this service will therefore use the proper ECMT B-VID and be carried symmetrically end to end on the proper equal cost multi path. Essentially the operator decides which services go in which ECMT paths, unlike a hashing solution used in other systems such as IP/MPLS. Trees can supportTraffic engineering
802.1aq does not spread traffic on a hop-by-hop basis. Instead, 802.1aq allows assignment of a Service ID (ISID) to a VLAN ID (VID) at the edge of the network. A VID will correspond to exactly one of the possible sets of shortest path nodes in the network and will never stray from that routing. If there are 10 or so shortest paths between different nodes, it is possible to assign different services to different paths and to know that the traffic for a given service will follow exactly the given path. In this manner traffic can easily be assigned to the desired shortest path. In the event that one of the paths becomes overloaded it is possible to move some services off that shortest path by reassigning those service's ISID to a different, less loaded, VID at the edges of the network. The deterministic nature of the routing makes offline prediction/computation/experimentation of the network loading much simpler since actual routes are not dependent on the contents of the packet headers except for the VLAN identifier. Figure 4 shows four different equal-cost paths between nodes 7 and 5. An operator can achieve a relatively good balance of traffic across the cut between nodes and 2and and 3by assigning the services at nodes 7 and 5 to one of the four desired VIDs. Using more than 4 equal cost tree (ECT) paths in the network will likely allow all 4 of these paths to be used. Balance can also be achieved between nodes 6 and 4 in a similar manner. In the event that an operator does not wish to manually assign services to shortest paths it is a simple matter for a switch vendor to allow a simple hash of the ISID to one of the available VIDS to give a degree of non-engineered spreading. For example, the ISID modulo the number of ECT-VIDs could be used to decide on the actual relative VID to use. In the event that the ECT paths are not sufficiently diverse the operator has the option of adjusting the inputs to the distributed ECT algorithms to apply attraction or repulsion from a given node by adjusting that node's Bridge Priority. This can be experimented with via offline tools until the desired routes are achieved at which point the bias can be applied to the real network and then ISIDs can be moved to the resulting routes. Looking at the animations in Figure 6 shows the diversity available for traffic engineering in a 66 node network. In this animation, there are 8 ECT paths available from each highlighted source to destination and therefore services could be assigned to 8 different pools based on the VID. One such initial assignment in Figure 6 could therefore be (ISID modulo 8) with subsequent fine tuning as required.Example
We will work through SPBM behavior on a small example, with emphasis on the shortest-path trees for unicast and multicast. The network shown in Figure 1 consists of 8 participating nodes numbered 0 through 7. These would be switches or routers running the IEEE 802.1aq protocol. Each of the 8 participating nodes has a number of adjacencies numbered 1..5. These would likely correspond to interface indexes, or possibly port numbers. Since 802.1aq does not support parallel interfaces each interface corresponds to an adjacency. The port / interface index numbers are of course local and are shown because the output of the computations produce an interface index (in the case of unicast) or a set of interface indexes (in the case of multicast) which are part of the forwarding information base (FIB) together with a destination MAC address and backbone VID. The network has a fully meshed inner core of four nodes (0..3) and then four outer nodes (4,5,6 and 7), each dual-homed onto a pair of inner core nodes. Normally when nodes come from the factory they have a MAC address assigned which becomes a node identifier but for the purpose of this example we will assume that the nodes have MAC addresses of the form 00:00:00:00:N:00 where N is the node id (0..7) from Figure 1. Therefore, node 2 has a MAC address of 00:00:00:00:02:00. Node 2 is connected to node 7 (00:00:00:00:07:00) via node 2's interface/5. The IS-IS protocol runs on all the links shown since they are between participating nodes. The IS-IS hello protocol has a few additions for 802.1aq including information about backbone VIDs to be used by the protocol. We will assume that the operator has chosen to use backbone VIDs 101 and 102 for this instance of 802.1aq on this network. The node will use their MAC addresses as the IS-IS SysId and join a single IS-IS level and exchange link-state packets (LSPs in IS-IS terminology). The LSPs will contain node information and link information such that every node will learn the full topology of the network. Since we have not specified any link weights in this example, the IS-IS protocol will pick a default link metric for all links, therefore all routing will be minimum hop count. After topology discovery the next step is distributed calculation of the unicast routes for both ECMP VIDs and population of the unicast forwarding tables (FIBs). Consider the route from Node 7 to Node 5: there are a number of equal-cost paths. 802.1aq specifies how to choose two of them: the first is referred to as the Low PATH ID path. This is the path which has the minimum node id on it. In this case the Low PATH ID path is the 7->0->1->5 path (as shown in red in Figure 2). Therefore, each node on that path will create a forwarding entry toward the MAC address of node five using the first ECMP VID 101. Conversely, 802.1aq specifies a second ECMP tie-breaking algorithm called High PATH ID. This is the path with the maximum node identifier on it and in the example is the 7->2->3->5 path (shown in blue in Figure 2). Node 7 will therefore have a FIB that among other things indicates: * MAC 00:00:00:05:00 / vid 101 the next hop is interface/1. * MAC 00:00:00:05:00 / vid 102 the next hop is interface/2. Node 5 will have exactly the inverse in its FIB: * MAC 00:00:00:07:00 / vid 101 the next hop is interface/1. * MAC 00:00:00:07:00 / vid 102 the next hop is interface/2. The intermediate nodes will also produce consistent results so for example node 1 will have the following entries. * MAC 00:00:00:07:00 / vid 101 the next hop is interface/5. * MAC 00:00:00:07:00 / vid 102 the next hop is interface/4. * MAC 00:00:00:05:00 / vid 101 the next hop is interface/2. * MAC 00:00:00:05:00 / vid 102 the next hop is interface/2. And Node 2 will have entries as follows: * MAC 00:00:00:05:00 / vid 101 the next hop is interface/2. * MAC 00:00:00:05:00 / vid 102 the next hop is interface/3. * MAC 00:00:00:07:00 / vid 101 the next hop is interface/5. * MAC 00:00:00:07:00 / vid 102 the next hop is interface/5. If we had an attached non-participating device at Node 7 talking to a non-participating device at Node 5 (for example Device A talks to Device C in Figure 3), they would communicate over one of these shortest paths with a MAC-in-MAC encapsulated frame. The MAC header on any of the NNI links would show an outer source address of 00:00:00:70:00, an outer destination address of 00:00:00:50:00 and a BVID of either 101 or 102 depending on which has been chosen for this set of non-participating ports/vids. The header once inserted at node 7 when received from node A, would not change on any of the links until it egressed back to non-participating Device C at Node 5. All participating devices would do a simple DA+VID lookup to determine the outgoing interface, and would also check that incoming interface is the proper next hop for the packet's SA+VID. The addresses of the participating nodes 00:00:00:00:00:00 ... 00:00:00:07:00 are never learned but are advertised by IS-IS as the node's SysId. Unicast forwarding to a non-participating client (e.g. A, B, C, D from Figure 3) address is of course only possible when the first hop participating node (e.g. 7) is able to know which last hop participating node (e.g. 5) is attached to the desired non-participating node (e.g. C). Since this information is not advertised by IEEE 802.1aq it has to be learned. The mechanism for learning is identical to IEEE 802.1ah, in short, the corresponding outer MAC unicast DA, if not known is replaced by a multicast DA and when a response is received, the SA of that response now tells us the DA to use to reach the non-participating node that sourced the response. e.g. node 7 learns that C is reached by node 5. Since we wish to group/scope sets of non-participating ports into services and prevent them from multicasting to each other, IEEE 802.1aq provides mechanism for per source, per service multicast forwarding and defines a special multicast destination address format to provide this. Since the multicast address must uniquely identify the tree, and because there is a tree per source per unique service, the multicast address contains two components, a service component in the low order 24 bits and a network-wide unique identifier in the upper 22 bits. Since this is a multicast address the multicast bit is set, and since we are not using the standard OUI space for these manufactured addresses, the Local 'L' bit is set to disambiguate these addresses. In Figure 3 above, this is represented with the DA= ,Owhere the 7 represents packets originating from node 7 and the colored O represents the E-LAN service we are scoped within. Prior to creating multicast forwarding for a service, nodes with ports that face that service must be told they are members. For example, nodes 7,4,5 and 6 are told they are members of the given service, for example service 200, and further that they should be using BVID 101. This is advertised by ISIS and all nodes then do the SPBM computation to determine if they are participating either as a head end or tail end, or a tandem point between other head and tail ends in the service. Since node 0 is a tandem between nodes 7 and 5 it creates a forwarding entry for packets from node 7 on this service, to node 5. Likewise, since it is a tandem between nodes 7 and 4 it creates forwarding state from node 7 for packets in this service to node 4 this results in a true multicast entry where the DA/VID have outputs on two interfaces 1 and 2. Node 2 on the other hand is only on one shortest path in this service and only creates a single forwarding entry from node 7 to node 6 for packets in this service. Figure 3 only shows a single E-LAN service and only the tree from one of the members, however very large numbers of E-LAN services with membership from 2 to every node in the network can be supported by advertising the membership, computing the tandem behaviors, manufacturing the known multicast addresses and populating the FIBs. The only real limiting factors are the FIB table sizes and computational power of the individual devices both of which are growing yearly in leaps and bounds.Implementation notes
802.1aq takes IS-IS topology information augmented with service attachment (I-SID) information, does a series of computations and produces a forwarding table (filtering table) for unicast and multicast entries. The IS-IS extensions that carry the information required by 802.1aq are given in the isis-layer2 IETF document listed below. An implementation of 802.1aq will first modify the IS-IS hellos to include an NLPID (network layer protocol identifier) of 0xC01 in their Protocols-Supported type–length–value (TLV) (type 129) which has been reserved for 802.1aq. The hellos also must include an MSTID (which gives the purpose of each VID) and finally each ECMT behavior must be assigned to a VID and exchanged in the hellos. The hellos would normally run untagged. Note that NLPID of IP is not required to form an adjacency for 802.1aq but also will not prevent an adjacency when present. The links are assigned 802.1aq specific metrics which travel in their own TLV (Type Length Value) which is more or less identical to the IP link metrics. The calculations will always use the maximum of the two unidirectional link metrics to enforce symmetric route weights. The node is assigned a mac address to identify it globally and this is used to form the IS-IS SYSID. A box mac would normally serve this purpose. The Area-Id is not directly used by 802.1aq but should, of course, be the same for nodes in the same 802.1aq network. Multiple areas/levels are not yet supported. The node is further assigned an SPSourceID which is a 20 bit network wide unique identifier. This can often be the low 20 bits of the SYSID (if unique) or can be dynamically negotiated or manually configured. The SPSourceID and the ECMT assignments to B-VIDs are then advertised into the IS-IS network in their own 802.1aq TLV. The 802.1aq computations are restricted to links between nodes that have an 802.1aq link weight and which support the NLPID 0xC01. As previously discussed the link weights are forced to be symmetric for the purpose of computation by taking the min of two dissimilar values. When a service is configured in the form of an I-SID assignment to an ECMT behavior that I-SID is then advertised along with the desired ECMT behavior and an indication of its transmit, receive properties (a new TLV is used for this purpose of course). When an 802.1aq node receives an IS-IS update it will compute the unique shortest path to all other IS-IS nodes that support 802.1aq. There will be one unique (symmetric) shortest path per ECMT behavior. The tie breaking used to enforce this uniqueness and ECMT is described below. The unicast FDB/FIB will be populated based on this first shortest path computation. There will be one entry per ECMT behavior/B-VID produced. The transit multicast computation (which only applies when transit replication is desired and not applicable to services that have chosen head end replication) can be implemented in many ways, care must be taken to keep this efficient, but in general a series of shortest path computations must be done. The basic requirement is to decide 'am I on the shortest path between two nodes one of which transmits an I-SID and the other receives that I-SID.' Rather poor performing pseudocode for this computation looks something like this: for each NODE in network which originates at least one transmit ISID do SPF = compute the shortest path trees from NODE for all ECMT B-VIDs. for each ECMT behavior do for each NEIGHBOR of NODE do if NEIGHBOR is on the SPF towards NODE for this ECMT then T = NODE's transmit ISIDs unioned with all receive ISIDs below us on SPF for each ISID in T do create/modify multicast entry where [ MAC-DA = NODE.SpsourceID:20, , ISID:24, , LocalBit:1, , MulticastBit:1 B-VID = VID associated with this ECMT out port = interface to NEIGHBOR in port = port towards NODE on the SPF for this ECMT ] The above pseudocode computes many more SPF's than strictly necessary in most cases and better algorithms are known to decide if a node is on a shortest path between two other nodes. A reference to a paper presented at the IEEE which gives a much faster algorithm that drastically reduces the number of outer iterations required is given below. In general though even the exhaustive algorithm above is more than able to handle several hundred node networks in a few tens of milliseconds on the 1 GHz or greater common CPUs when carefully crafted. For ISIDs that have chosen head-end replication the computation is trivial and involves simply finding the other attachment points that receive that ISID and creating a serial unicast table to replicate to them one by one.Tie-breaking
802.1aq must produce deterministic symmetric downstream congruent shortest paths. This means that not only must a given node compute the same path forward and reverse but all the other nodes downstream (and upstream) on that path must also produce the same result. This downstream congruence is a consequence of the hop by hop forwarding nature of Ethernet since only the destination address and VID are used to decide the next hop. It is important to keep this in mind when trying to design other ECMT algorithms for 802.1aq as this is an easy trap to fall into. It begins by taking the unidirectional link metrics that are advertised by ISIS for 802.1aq and ensuring that they are symmetric. This is done by simply taking the MIN of the two values at both ends prior to doing any computations. This alone does not guarantee symmetry however. The 802.1aq standard describes a mechanism called a PATHID which is a network-wide unique identifier for a path. This is a useful logical way to understand how to deterministically break ties but is not how one would implement such a tie-breaker in practice. The PATHID is defined as just the sequence of SYSIDs that make up the path (not including the end points).. sorted. Every path in the network therefore has a unique PATHID independent of where in the network the path is discovered. 802.1aq always picks the lowest PATHID path when a choice presents itself in the shortest path computations. This ensures that every node will make the same decision. For example, in Figure 7 above, there are four equal-cost paths between node 7 and node 5 as shown by the colors blue, green, pink and brown. The PATHID for these paths are as follows: *PATHID ''=
* PATHID '' =
* PATHID ''=
* PATHID '' =
The lowest PATHID is therefore the brown path .
This low PATHID algorithm has very desirable properties. The first is that it can be done progressively by simply looking for the lowest SYSID along a path and secondly because an efficient implementation that operates stepwise is possible by simply back-tracking two competing paths and looking for the minimum of the two paths minimum SYSIDs.
The low PATHID algorithm is the basis of all 802.1aq tie breaking. ECMT is also based on the low PATHID algorithm by simply feeding it different SYSID permutations – one per ECMT algorithm. The most obvious permutation to pass is a complete inversion of the SYSID by XOR-ing it with 0xfff... prior to looking for the min of two minimums. This algorithm is referred to as high PATHID because it logically chooses the largest PATHID path when presented with two equal-cost choices.
In the example in figure 7, the path with the highest PATHID is therefore the blue path whose PATHID is . Simply inverting all the SYSIDs and running the low PATHID algorithm will yield same result.
The other 14 defined ECMT algorithms use different permutations of the SYSID by XOR-ing it with different bit masks which are designed to create relatively good distribution of bits. It should be clear that different permutations will result in the purple and green paths being lowest in turn.
The 17 individual 64-bit masks used by the ECT algorithm are made up of the same byte value repeated eight times to fill each 64-bit mask. These 17 byte values are as follows:
Interoperability
The first public interoperability tests of IEEE 802.1aq were held in Ottawa in October 2010. Two vendors provided SPBM implementations and a total of 5 physical switches and 32 emulated switches were tested for control/data and OA&M. Further events were held in Ottawa in January 2011 with 5 vendors and 6 implementations, at 2013's Interop event at Las Vegas where an SPBM network was used as a backbone.Competitors
MC-LAG,Deployments
Deployment considerations and interoperability best practices are documented in an IETF document titled "SPB Deployment Considerations" * 2013Product support
*See also
* Connection-oriented Ethernet * Provider Backbone Bridge Traffic Engineering (PBB-TE) * Virtual Enterprise Network ArchitectureNotes
References
* * * * * * * * * * * * * * * * * * * * * Avaya VSP Configuration Guide *Further reading
* * * *External links