Skip to main content

IEEE 802.1aq SPB: shortest path bridging with IS-IS

· 6 min read
PhD candidate, LyRIDS (ECE) × CEDRIC (Cnam)

Spanning trees avoid loops by switching links off. Shortest Path Bridging (SPB) avoids loops differently: every bridge computes its own shortest path tree from a shared view of the network, so all links can be used. It brings to Ethernet the link-state routing that IP networks have long used.

The IEEE 802.1Q bridge: architecture and data-plane actionsIEEE 802.1Q bridge ↗Control planeSRP (Qat), TSN configuration (Qcc), path control (Qca)frame inframe outIngressPSFP (Qci)FRER (CB)Relayforwardingexplicit treesQueuingCBS (Qav)ATS (Qcr)Tx selectiongates (Qbv)CQF (Qch)MAC / PHYpreemption(Qbu, 802.3br)Common time: gPTP (802.1AS)
Figure 1. Where SPB acts: in the control plane, where IS-IS replaces the spanning tree protocols. The data plane still forwards on destination MAC address and VLAN ID, using the filtering entries SPB computes.Source: own drawing, after the bridge architecture, data-plane actions and QoS function chain in J. Farkas, TSN Basic Concepts, DetNet–TSN workshop, 11 November 2018, slides 7, 8 and 10.
Abbreviations used in this post (16)
AbbreviationStands forMeaning
ECTEqual Cost TreeIn SPB and PCR, an algorithm that chooses one tree among several of equal cost; each one is used through its own VID.
IEEEInstitute of Electrical and Electronics EngineersThe professional association whose Standards Association publishes the IEEE 802 LAN/MAN standards.
IPInternet ProtocolThe network-layer protocol of the Internet (IPv4, RFC 791; IPv6, RFC 8200).
IS-ISIntermediate System to Intermediate SystemA link-state routing protocol (ISO/IEC 10589, RFC 1195); the control plane of SPB and PCR.
MACMedium Access ControlThe lower sublayer of the data link layer, which frames data and controls access to the medium. A MAC address identifies a network interface.
MPLSMultiprotocol Label SwitchingForwarding of packets on short labels along label-switched paths (RFC 3031).
MSTPMultiple Spanning Tree ProtocolIEEE 802.1s, now in 802.1Q: several spanning trees, each used by a group of VLANs.
RFCRequest for CommentsThe document series in which IETF standards and related documents are published.
RSTPRapid Spanning Tree ProtocolIEEE 802.1w, now in 802.1Q: a faster-converging spanning tree with alternate and backup port roles.
SPBShortest Path BridgingIEEE 802.1aq: bridges compute shortest path trees with IS-IS, so all links can be used.
SPBMShortest Path Bridging – MACThe SPB mode built on Provider Backbone Bridges, with trees identified by backbone MAC addresses and no backbone learning.
SPBVShortest Path Bridging – VIDThe SPB mode in which shortest path trees are identified by VLAN IDs; flooding and learning, plug and play.
SPTShortest Path TreeIn SPB, the tree of shortest paths from one bridge to all others; each bridge forwards only on its own SPT.
STPSpanning Tree ProtocolThe original 802.1D protocol that blocks redundant links to leave a loop-free tree; now replaced by RSTP.
VIDVLAN IdentifierThe 12-bit field of the 802.1Q tag that names a frame’s VLAN.
VLANVirtual LANA logical LAN within a bridged network, identified by a 12-bit VLAN ID in the 802.1Q tag.

1. Definition​

IEEE 802.1aq, Shortest Path Bridging, is an amendment to IEEE 802.1Q, approved in March 2012 and later incorporated into 802.1Q-2014 [1]. Its aims are as follows [1]:

  • replace STP, RSTP and MSTP, which block redundant paths, with a control plane that keeps all paths active;
  • support much larger Layer 2 topologies, with faster convergence;
  • spread load over all paths of a mesh;
  • preserve the plug-and-play nature of Ethernet.

Its control plane is IS-IS, the link-state routing protocol, extended with a few TLVs specified in RFC 6329. SPB needs no change to the IS-IS state machine, only a new protocol identifier and these TLVs [1].

Five bridges controlled by RSTP (one shared tree), MSTP (one tree per group of VLANs) and SPB (one shortest path tree per bridge)
Figure 2. SPB compared with the spanning tree protocols (right): each bridge has its own shortest path tree, instead of all traffic sharing one or a few spanning trees.Source: P. Thaler, N. Finn, D. Fedyk, J. Farkas, G. Parsons, E. Gray, “IEEE 802.1Q: Media Access Control Bridges and Virtual Bridged Local Area Networks,” IEEE 802.1 tutorial, IETF 86, 10 March 2013, slide 26; cropped, with neighbouring slide text, logos or navigation icons blanked.

2. How it works​

The IEEE 802.1 tutorial summarises the principle as "computation instead of signaling" [2]:

  1. IS-IS runs between SPB bridges and floods link-state information. Every bridge holds an identical replica of a database with the topology, the properties of the bridges, and service information [2].
  2. From that database, every bridge independently computes symmetric shortest path trees from each participating bridge to all others [1].
  3. Each bridge fills its filtering database from the result. A frame is forwarded only along the shortest path tree of the bridge where it entered [1][2].

The MAC service model of Ethernet, such as in-order delivery, is preserved [2].

Shortest path trees of bridges A and C over four SPT bridges running ISIS-SPB
Figure 3. Each bridge uses only its own shortest path tree: the trees of bridges A and C over four bridges running ISIS-SPB.Source: P. Thaler, N. Finn, D. Fedyk, J. Farkas, G. Parsons, E. Gray, “IEEE 802.1Q: Media Access Control Bridges and Virtual Bridged Local Area Networks,” IEEE 802.1 tutorial, IETF 86, 10 March 2013, slide 31; cropped, with neighbouring slide text, logos or navigation icons blanked.

3. Two flavours: SPBV and SPBM​

SPB has two operation modes that apply the same principle to different data planes [1][2]:

SPBV (SPB VID)SPBM (SPB MAC)
Data planeIEEE 802.1Q VLANs (or 802.1ad)Provider Backbone Bridges, IEEE 802.1ah "MAC-in-MAC"
Trees identified byVLAN IDBackbone MAC address
LearningFlooding and learning, as in ordinary bridgesNo backbone MAC flooding or learning; addresses known from IS-IS
Typical useAll types of VLANs, plug and playLarge managed networks, full isolation of customer MAC addresses

4. An example: equal-cost trees​

An example SPB network of eight nodes: a fully meshed core of four nodes and four dual-homed outer nodes, with interface numbers
Figure 4. An example SPB network: a fully meshed core of four nodes (0 to 3) and four outer nodes (4 to 7), each dual-homed to two core nodes. Small numbers are interface indexes.Source: 802d1aq Wiki Example.gif by Peterashwoodsmith, from the Wikipedia article “IEEE 802.1aq”, Wikimedia Commons, Public domain.

With all links at the same cost, there are several equal shortest paths from node 7 to node 5. SPB specifies how to choose among them deterministically. Its first tie-breaking algorithm prefers the path with fewer hops, then the path with the lowest bridge identifier. Other algorithms use permutations of the identifiers [1].

Two equal-cost paths from node 7 to node 5: the low path ID path on VID 101 and the high path ID path on VID 102
Figure 5. Two equal-cost paths from node 7 to node 5: the low path ID path, carried on VID 101, and the high path ID path, carried on VID 102.Source: 802d1aq Wiki Example3.png by Peterashwoodsmith, from the Wikipedia article “IEEE 802.1aq”, Wikimedia Commons, Public domain.
Three equal-cost trees between nodes 7 and 5 produced by three tie-breaking algorithms, each on its own VID
Figure 6. Three equal-cost trees from three tie-breaking (ECT) algorithms, each on its own VID. The operator chooses which service uses which tree.Source: 802d1aq Wiki Example 4.png by Peterashwoodsmith, from the Wikipedia article “IEEE 802.1aq”, Wikimedia Commons, Public domain.

Sixteen equal-cost tree (ECT) algorithms are initially defined [1]. Unlike hashing in IP or MPLS, the choice is made by the operator at the edge: a service is assigned to one ECT VID, and all its traffic follows that tree in both directions [1]. The IEEE 802.1 tutorial calls this provisioned load spreading: a VLAN is assigned to an SPT set [2].

Two equal-cost shortest path tree options for bridge A in a five-bridge network
Figure 7. Load spreading on the IEEE 802.1 slide: two shortest path tree options for bridge A, from two tie-breaking variations.Source: P. Thaler, N. Finn, D. Fedyk, J. Farkas, G. Parsons, E. Gray, “IEEE 802.1Q: Media Access Control Bridges and Virtual Bridged Local Area Networks,” IEEE 802.1 tutorial, IETF 86, 10 March 2013, slide 32; cropped, otherwise unchanged.
Animation of eight equal-cost tree algorithms between a source and a destination in a larger SPB network
Figure 8. Eight equal-cost tree algorithms between one source (purple) and one destination (yellow) in a larger network (animation).Source: 802d1aqECMP (cropped).gif by Peterashwoodsmith, from the Wikipedia article “IEEE 802.1aq”, Wikimedia Commons, Public domain.

5. Failure recovery​

When a link fails, IS-IS advertises the failure and every bridge recomputes its trees and filtering entries [1]:

  • No relearning in the SPBM core. Ethernet addresses are not advertised by IS-IS, so nothing has to be relearned there.
  • Fast failure detection. Failures can be detected faster with the Continuity Check Protocol of IEEE 802.1ag than with IS-IS hellos.
  • Fast multicast rebuild. Multicast trees are rebuilt about as fast as unicast routes, because they are computed locally rather than signalled.

The tutorial gives convergence "within the range of 100 msec" [2].

6. What SPB means for determinism​

Three properties make SPB attractive under the analyses of this series:

  • Paths are symmetric and predictable. The forward and reverse paths coincide, and the choice among equal-cost paths is an operator decision rather than a hash. Offline tools can model where every flow goes, and one-way delay can be taken as half the round-trip delay [1].
  • Paths are computed, not negotiated. Every bridge derives the same trees from the same database. A configuration tool can compute the same paths and the delay bounds along them.
  • Shortest is not always enough. Streams that need disjoint paths, or paths that avoid a busy link, need more than shortest-path trees. Path control (802.1Qca) extends SPB's IS-IS with explicit trees for exactly that.

References​

  1. Wikipedia, "IEEE 802.1aq," sections on history, associated protocols, high level, equal cost multi tree, failure recovery and the example. Article
  2. P. Thaler, N. Finn, D. Fedyk, J. Farkas, G. Parsons, E. Gray, "IEEE 802.1Q: Media Access Control Bridges and Virtual Bridged Local Area Networks," IEEE 802.1 tutorial, IETF 86, 10 March 2013, slides 26 and 30–34. Slides
  3. D. Fedyk, P. Ashwood-Smith et al., RFC 6329, "IS-IS Extensions Supporting IEEE 802.1aq Shortest Path Bridging," IETF, April 2012. RFC Editor