Spanning tree in one article: why a blocked port is the feature, and how RSTP and MSTP made it fast

Redundant links between switches make loops, and Ethernet has nothing in its header to stop a frame circling forever. The Spanning Tree Protocol solves it by electing a root and blocking every port the tree does not need. The election, the costs and the timers, the 30 to 50 seconds classic STP took to recover, the handshake that made RSTP fast, the regions and instances of MSTP, Cisco's per-VLAN variants and guards, and the engineer who wrote the algorithm's abstract as a poem.

Two links between two switches are better than one: if a cable fails, the other carries on. They are also a loop, and at layer 2 a loop is not a performance problem but an outage. The () exists to let a network be built with redundant links and still behave as if it had none, by switching off, on purpose, every link the network does not need at the moment. The blocked port that puzzles people on a new switch is not a fault. It is the protocol doing its job.

Why a loop is fatal at layer 2

An IP packet carries a time-to-live () counter that each router lowers by one, so a packet caught in a routing loop dies after a bounded number of hops. An frame has nothing like it: "Ethernet frames do not have a time to live (TTL) attribute, like IP packets" (Cisco Networking Academy, Scaling Networks). A broadcast that enters a loop is copied out of every port, comes back, and is copied again, until the result is a broadcast storm, "so many broadcast frames caught in a Layer 2 loop that all available bandwidth is consumed". The switches suffer too: "Instability in the content of the table results from copies of the same frame being received on different ports" (same source), so the switch keeps relearning where each address lives and sends unicast frames the wrong way.

The 1985 paper that introduced the algorithm names the problem in six words: "congestion caused by infinitely circulating packets" (Perlman, 1985). Cisco's troubleshooting guide names the cause just as plainly, and it is the reason the blocked port matters: a bridging loop "still comes from a port that can block, but instead forwards traffic" (Cisco, troubleshooting STP).

The algorithm in four decisions

Every switch running spanning tree takes part in the same calculation, and the result is a tree: one path, and only one, from any switch to any other.

Elect a root. "The bridge with the lowest bridge ID is elected as the root bridge" (Juniper, spanning tree overview). The bridge ID is a two-byte priority followed by the switch's MAC (media access control) address; on Cisco's Catalyst 9300, the priority is "a 4-bit priority value and a 12-bit extended system ID value equal to the ID", configurable from 0 to 61440 "in increments of 4096; the default is 32768", and when priorities tie, the lowest MAC address wins (Cisco, configuring STP). Left at the defaults, the root is simply whichever switch has the lowest MAC address, chosen by accident rather than by design. Setting the priority on purpose is the first thing any design does.
Each other switch picks a root port: the one port that "provides the best path (lowest cost)" to the root (Cisco, as above).
Each segment picks a designated port: "A forwarding port elected for every switched segment" (Cisco, as above), the port on that segment closest to the root.
Everything else blocks. "All paths that are not needed to reach the root switch from anywhere in the switched network are placed in the spanning-tree blocking mode" (Cisco, as above).

Path cost: how "closest" is counted

"Best path" means the lowest sum of port costs on the way to the root, and the costs depend on link speed. Two scales are in use. The original 802.1D values were small integers; the later, 32-bit values of 802.1t-2001 scale to much faster links (Extreme Networks, port path costs).

Link speed	Short cost (802.1D-1998)	Long cost (802.1t)
10 Mb/s	100	2,000,000
100 Mb/s	19	200,000
1 Gb/s	4	20,000
10 Gb/s	2	2,000

The short values are as Cisco's academy text and Juniper give them ("a 100-Mbps link has a default path cost of 19, a 1000-Mbps link has a default path cost of 4", Juniper; one Extreme table gives 99 rather than 100 for 10 Mb/s); the long values are from the defaults table of Cisco's Catalyst 9300 guide. Which scale a switch uses by default depends on the platform and the release, so the rule is simple: in a mixed network, set every switch to the same method, or two switches will disagree about which path is cheaper.

Bridge protocol data units, timers and the old 30 to 50 seconds

Switches exchange the information in BPDUs (bridge protocol data units). In classic STP the root sends configuration messages and the others relay them, with three timers whose defaults are a hello time of 2 seconds, a forward delay of 15 seconds and a maximum age of 20 seconds (Cisco, configuring STP). A port does not jump from blocking to forwarding: it moves through listening and learning first, and "the forward delay is the time spent in the listen and learn state" (Cisco, STP timers).

That caution is what made classic spanning tree slow. When a switch's own link to the root fails, "the recovery takes up to 30 seconds", two forward delays (Cisco, UplinkFast); when the failure is elsewhere and has to be noticed by information aging out, the wait is "the max_age value (20 seconds) plus twice the fw_delay value (2x15 seconds)", "50 seconds with the default parameters" (Cisco, BackboneFast). Half a minute of silence for one failed cable is a long outage for anything a network carries today.

RSTP: the same tree, built by handshake

The Rapid Spanning Tree Protocol (), 802.1w, keeps the tree and replaces the waiting. It was "Incorporated into 802.1D-2004" (IEEE 802.1w), and Arista's documentation states the consequence: "Standard 802.1D-2004 incorporates RSTP and obsoletes STP" (Arista, spanning tree). Cisco's explanation of RSTP is the clearest account of what changed (Cisco, understanding RSTP):

Roles. "The blocking port role is split into the backup and alternate port roles." An alternate port is a ready-made second path to the root, receiving "more useful BPDUs from another bridge"; a backup port is a redundant link to the same segment, receiving them "from the same bridge it is on".
States. "The 802.1D disabled, blocking, and listening states are merged into a unique 802.1w discarding state." There are three: discarding, learning, forwarding.
A handshake instead of timers. A designated port that wants to forward "sets the proposal bit on the BPDUs it sends out"; the neighbour makes sure its own ports cannot form a loop and answers with an agreement, and "once p0 receives that agreement, it can immediately transition to the forwarding state." Juniper sums it up as "a handshake mechanism based on point-to-point links instead of the timer-based process used by STP" (Juniper).
Edge ports. A port facing a host goes straight to forwarding, and the moment it receives a it "immediately loses edge port status", because a BPDU means a switch is there.
Hellos as keepalives. Every switch now sends hellos, and "if hellos are not received three consecutive times, protocol information can be immediately aged out."

The limit is worth knowing: RSTP "can only achieve rapid transition to the forwarding state on edge ports and on point-to-point links", and the link type comes from the duplex: "A port that operates in full-duplex is assumed to be point-to-point, while a half-duplex port is considered as a shared port by default." Where it applies, recovery is "sometimes in the order of a few hundred milliseconds" (Cisco, understanding RSTP).

MSTP: many VLANs, a few trees

With VLANs (virtual LANs), a single tree for the whole network wastes links: the blocked uplink carries nothing for any VLAN. The Multiple Spanning Tree Protocol (MSTP), IEEE 802.1s, "maps multiple VLANs into a spanning tree instance, with each instance having a spanning tree topology independent of other spanning tree instances" (Juniper, MSTP), so one group of VLANs can block the left uplink and another the right. The amendment of 2002 was folded into IEEE 802.1Q's 2003 edition (IEEE SA, 802.1s).

MSTP works in regions, and a region is defined by agreement: "All switches in an MST region must have the same name, revision, and VLAN-to-instance map" (Arista). Cisco gives the sizes, a 32-byte name, a two-byte revision and a 4096-element table, and the consequence of any difference: "If for any reason two switches differ on one or more configuration attribute, the switches are part of different regions" (Cisco, understanding MSTP). Seen from outside, "the entire region appears as one virtual bridge"; inside it, the IST (internal spanning tree) is "an RSTP instance that extends the CST inside the MST region", and the CIST (common and internal spanning tree) connects regions to each other and to switches running plain RSTP or STP (Cisco, as above; Juniper, MSTP). Because one changed VLAN mapping splits a region, MSTP configuration is planned once and pushed to every switch identically.

Cisco's per-VLAN variants, and the guards

Cisco runs a tree per VLAN by default: PVST+ (per-VLAN spanning tree plus) is "based on the standard and Cisco proprietary extensions", and Rapid PVST+, "a Cisco enhancement of RSTP that uses PVST+", is "the default STP mode" on the Catalyst 9300 (Cisco, configuring STP; Cisco Networking Academy, as above). Around the protocol sit features that protect it from the network's edge:

PortFast "immediately transitions an access or trunk port from the blocking state directly to the forwarding state" (Cisco, PortFast and BPDU Guard); it is Cisco's name for what the standard calls an edge port.
BPDU Guard: if a PortFast port receives a BPDU, "the switch immediately shuts the port down by placing it in the errdisable state" (same source), so a switch plugged in under a desk cannot join the tree.
Root Guard "ensures that the port on which root guard is enabled is the designated port" (Cisco, Root Guard): a superior BPDU arriving there blocks the port instead of moving the root. The IEEE model has the same control as restrictedRole (IEEE 802.1Q RSTP YANG).
Loop Guard moves a port that stops receiving BPDUs "into the STP loop-inconsistent blocking state" rather than letting it forward (Cisco, Loop Guard).

Older Cisco features that sped classic STP up, UplinkFast and BackboneFast, are no longer needed: "RSTP natively includes most of the Cisco proprietary enhancements to the 802.1D spanning tree, such as BackboneFast, UplinkFast, and PortFast" (Cisco, understanding RSTP).

Where the standard lives now

There is no separate spanning tree standard any more. "IEEE Std 802.1D-2004 was superseded by IEEE Std 802.1Q-2014", which "merged IEEE Std 802.1D with IEEE Std 802.1Q in order to create a single bridging standard" (IEEE 802.1, 2021). RSTP and MSTP are specified in Clause 13 of 802.1Q (IEEE 802.1Q MSTP YANG), whose current edition is 802.1Q-2022 (IEEE 802.1 maintenance).

The engineer and the poem

The algorithm is the work of , at Digital Equipment Corporation, whose paper on it was published in 1985 (Perlman, 1985). The abstract is a poem, "Algorhyme", which opens "I think that I shall never see / A graph more lovely than a tree" (Heidelberg Laureate Forum). In her own words: "I spent the remainder of the week working on the poem, which is the abstract of the paper" (LACNIC, 2019). The Internet Hall of Fame inducted her in 2014 for designing "the spanning tree algorithm that transformed Ethernet" (Internet Hall of Fame). The story of bridges and switches around her work is told in one idea, solved twice.

What to remember

Ethernet frames have no TTL, so a loop circulates forever; spanning tree prevents loops by blocking.
Lowest bridge ID is root; every other switch has one root port; every segment one designated port; the rest block. Set the root's priority on purpose.
Classic STP took 30 to 50 seconds to recover; RSTP's proposal and agreement can converge in a few hundred milliseconds on point-to-point links and edge ports.
MSTP maps groups of VLANs to a few trees; a region is name plus revision plus mapping, identical on every switch.
Protect the edge: edge ports (PortFast) with BPDU Guard toward hosts, Root Guard where the root must never be.