Skip to main content

IEEE 802.1w RSTP: the Rapid Spanning Tree Protocol

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

Ethernet frames carry no hop count, so a loop in a bridged network would circulate broadcasts forever. Bridges therefore agree on a loop-free subset of the links: a spanning tree. The Rapid Spanning Tree Protocol (RSTP) is the standard way to compute it, and the first control protocol listed for the active topology in the bridge post.

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 RSTP acts: in the control plane of every bridge. It decides which ports forward; the data plane enforces that decision in its first step, active topology enforcement.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 (9)
AbbreviationStands forMeaning
BPDUBridge Protocol Data UnitThe message bridges exchange to run STP, RSTP and MSTP.
FRERFrame Replication and Elimination for ReliabilityIEEE 802.1CB: frames are numbered, sent over disjoint paths, and duplicates are removed.
IEEEInstitute of Electrical and Electronics EngineersThe professional association whose Standards Association publishes the IEEE 802 LAN/MAN standards.
LANLocal Area NetworkA network covering a limited area, such as a building or a vehicle; IEEE 802 standardises LANs.
MSTPMultiple Spanning Tree ProtocolIEEE 802.1s, now in 802.1Q: several spanning trees, each used by a group of VLANs.
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.
STPSpanning Tree ProtocolThe original 802.1D protocol that blocks redundant links to leave a loop-free tree; now replaced by RSTP.
VLANVirtual LANA logical LAN within a bridged network, identified by a 12-bit VLAN ID in the 802.1Q tag.

1. Definition​

The Rapid Spanning Tree Protocol was introduced by IEEE in 2001 as IEEE 802.1w and incorporated into IEEE 802.1D-2004, which made the original Spanning Tree Protocol (STP) obsolete [1]. It is backward compatible with STP [1]. The bridge functions of 802.1D, including RSTP, have since been brought into IEEE 802.1Q [2]. The IEEE 802.1 tutorial notes that STP is now historical, replaced by RSTP [3].

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. The three distributed protocols for the active topology, as the IEEE 802.1 tutorial draws them: RSTP builds one spanning tree shared by all traffic, MSTP lets groups of VLANs use different spanning trees, and SPB gives each bridge its own shortest path tree.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.

RSTP sits on the first layer of the bridge's control. It decides the active topology: which of the physical links are actually used. VLAN membership and station locations are then learned on top of it [3].

2. How a spanning tree is built​

A bridged network of seven bridges and six LAN segments, with bridge 3 elected root bridge
Figure 3. A bridged network with redundant links: seven bridges (numbered boxes) joined through six LAN segments (clouds). Bridge 3, with the lowest bridge ID, is the root.Source: Spanning tree protocol at work 2.svg by GhosT, from the Wikipedia article “Spanning Tree Protocol”, Wikimedia Commons, CC BY 3.0.

Bridges exchange bridge protocol data units (BPDUs) with their neighbours. From them [1]:

  1. the bridges elect a root bridge;
  2. every other bridge adds up the path cost towards the root and selects its best port towards it, the root port;
  3. on each LAN segment, the bridge with the best path to the root forwards for that segment through its designated port;
  4. every other port that would close a loop stops forwarding user data.

The default path cost is inversely proportional to link speed: RSTP uses 20 Tbit/s divided by the bandwidth [1].

The same network after root and designated ports are chosen; the ports that would close loops are blocked
Figure 4. The resulting tree. Designated ports (DP) and root ports (RP) forward; the ports marked BP are blocked, so exactly one path remains between any two bridges.Source: Spanning tree protocol at work 4.svg by GhosT, from the Wikipedia article “Spanning Tree Protocol”, Wikimedia Commons, CC BY 3.0.

3. What makes it rapid​

RSTP keeps the idea of the spanning tree but changes how fast it reacts [1]:

STPRSTP
Reaction to a topology change30 to 50 sWithin 3 hello times (6 s by default), or a few milliseconds after a physical link failure
Port statesFiveThree: discarding, learning, forwarding
Port rolesRoot, designated, blockedRoot, designated, alternate (another path to the root), backup (another path to a segment), disabled
Edge ports—Ports with no bridge behind them forward at once, but still watch for BPDUs

Two mechanisms do most of the work [1]:

  • Prepared alternatives. An alternate or backup port already knows it is the next best choice, so it can take over without waiting for timers when the active port fails.
  • Proposal and agreement. On point-to-point links, a bridge proposes its spanning-tree information on its designated ports. A neighbour that accepts it as superior puts its other ports into discarding and returns an agreement, and the first bridge then moves the port straight to forwarding. The handshake cascades away from the root, instead of each port waiting through listening and learning.
A failed link between bridge 24 and segment c
Figure 5. A failure: the link between bridge 24 and segment c goes down.Source: Spanning tree protocol at work 5.svg by GhosT, from the Wikipedia article “Spanning Tree Protocol”, Wikimedia Commons, CC BY 3.0.
The spanning tree rebuilt after the failure, with a previously blocked port now forwarding
Figure 6. The tree after reconvergence: the port of bridge 5 on segment f, blocked before, now forwards, and bridge 4 reaches the root through it.Source: Spanning tree protocol at work 6.svg by GhosT, from the Wikipedia article “Spanning Tree Protocol”, Wikimedia Commons, CC BY 3.0.

An RSTP bridge falls back to legacy STP on a port where it detects an old-style BPDU [1].

4. What a spanning tree means for determinism​

For the analyses in this series, three properties of a spanning tree matter:

  • One path. Between two bridges there is exactly one active path, and all traffic shares it. Redundant links stay idle until a failure. That is why MSTP and SPB were developed.
  • Paths change after a failure. When the tree reconverges, streams move to new paths through new queues. A network calculus bound computed for the old path no longer applies, which is the problem studied in the reconfiguration post.
  • Reconvergence is not seamless. Even milliseconds of reconvergence lose frames. Applications that cannot afford this rely on FRER, which sends every frame on two disjoint paths at once and needs no reconvergence at all.

References​

  1. Wikipedia, "Spanning Tree Protocol," sections on protocol operation and on the Rapid Spanning Tree Protocol. Article
  2. Wikipedia, "IEEE 802.1aq," section on associated protocols (802.1Q-2014 incorporates functionality previously specified in 802.1D). Article
  3. 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 25–26. Slides