An interactive tour of the spanning tree protocol

Warning This post contains interactive examples. To visualize and interact with them, you need to enable JavaScript. Imagine you rent office space for a three-day event. You quickly set up a few Ethernet switches and tape some cables on the floor to get everyone online. Unfortunately, Stan, your clumsiest coworker, kicks out a cable every time he gets up for coffee. You could add extra cables, but then you’d get a broadcast storm: Ethernet packets that loop and multiply until nothing else gets through. That’s where the spanning tree protocol (STP) comes in. STP blocks just enough of your spare cables to leave a loop-free tree. When Stan strikes again, it rebuilds the tree in a second, leaving some time for Blobby, your one-person support crew, to reconnect the cable.1 See for yourself: the diagram below runs a real STP implementation in your browser! :demo A1 @0,0 prio=4096 A2 @0,1 A3 @0,2 A4 @0,3 B1 @1,0 prio=8192 B2 @1,1 B3 @1,2 B4 @1,3 C1 @2,0 prio=8192 C2 @2,1 C3 @2,2 C4 @2,3 A1 -- A2 hazard=0 A2 -- A3 hazard=0 A3 -- A4 hazard=0 B1 -- B2 B2 -- B3 B3 -- B4 C1 -- C2 hazard=0 C2 -- C3 hazard=0 C3 -- C4 hazard=0 A1 -- B1 cost=10 B1 -- C1 cost=10 A4 -- B4 cost=20 B4 -- C4 cost=20 Leo @-0.3,0.7 proto=none icon=👦🏻 Mia @-0.3,1.3 proto=none icon=👧🏽 Joy @0.3,0.7 proto=none icon=👱🏻♀ Roy @0.3,1.3 proto=none icon=👨🏾 A2 -- Leo hazard=0 A2:edge A2 -- Mia hazard=0 A2:edge A2 -- Joy hazard=0 A2:edge A2 -- Roy hazard=0 A2:edge Max @-0.3,1.7 proto=none icon=👨🏽 Zoe @-0.3,2.3 proto=none icon=👩🏾 Ada @0.3,1.7 proto=none icon=👵🏾 Amy @0.3,2.3 proto=none icon=👩🏼 A3 -- Max hazard=0 A3:edge A3 -- Zoe hazard=0 A3:edge A3 -- Ada hazard=0 A3:edge A3 -- Amy hazard=0 A3:edge Eli @0.7,0.7 proto=none icon=👦🏼 Jay @0.7,1.3 proto=none icon=👨🏻 Kai @1.3,0.7 proto=none icon=🧑🏽 Ben @1.3,1.3 proto=none icon=👱🏼 B2 -- Eli hazard=0.2 B2:edge B2 -- Jay hazard=0.2 B2:edge B2 -- Kai hazard=0.2 B2:edge B2 -- Ben hazard=0.2 B2:edge Ava @0.7,1.7 proto=none icon=👩🏻 Lea @0.7,2.3 proto=none icon=🧑🏾🦱 Ivy @1.3,1.7 proto=none icon=🧕🏽 Rex @1.3,2.3 proto=none icon=👴🏿 B3 -- Ava hazard=0.2 B3:edge B3 -- Lea hazard=0.2 B3:edge B3 -- Ivy hazard=0.2 B3:edge B3 -- Rex hazard=0.2 B3:edge Ana @1.7,0.7 proto=none icon=👩🏿 Eve @1.7,1.3 proto=none icon=👧🏼 Abe @2.3,0.7 proto=none icon=🧓🏿 Ian @2.3,1.3 proto=none icon=🧔🏾 C2 -- Ana hazard=0 C2:edge C2 -- Eve hazard=0 C2:edge C2 -- Abe hazard=0 C2:edge C2 -- Ian hazard=0 C2:edge Ned @1.7,1.7 proto=none icon=👨🏼🦳 Lou @1.7,2.3 proto=none icon=🧑🏿 Fay @2.3,1.7 proto=none icon=👧🏻 Sue @2.3,2.3 proto=none icon=👩🏽🦰 C3 -- Ned hazard=0 C3:edge C3 -- Lou hazard=0 C3:edge C3 -- Fay hazard=0 C3:edge C3 -- Sue hazard=0 C3:edge Note This article is also available as a video, but I advise you to keep reading here to try the interactive demonstrations. The basics Historical interlude Electing the root bridge Assigning roles to ports Port state transition Topology change notification Security Why RSTP today? How large can a network be? How fast is RSTP? About MSTP About the interactive examples The basics# Designed in the ’80s, the spanning tree protocol has evolved into a “rapid” flavor (RSTP) and a “VLAN-aware” variation (MSTP).2 Any sound-minded network engineer knows there are better alternatives, like BGP EVPN VXLAN. Yet, because any switch speaks it, the venerable spanning tree protocol still fills a niche. We focus on RSTP: it replaced the original protocol in 2004. To eliminate network loops, RSTP implements a complex state machine. Timers, link state changes, and the link-local control frames a bridge receives from its neighbors drive its transitions. These Ethernet frames are the Bridge Protocol Data Units (BPDUs). You can watch them in action below: hit the “Start” button. :protocol rstp :tx-hold 10 A1 @0,1 C11 @1,0 prio=4096 icon=🌳 C12 @1,2 prio=4096 icon=🌳 C21 @2,0 prio=4096 icon=🌳 C22 @2,2 prio=4096 icon=🌳 A2 @3,1 H1 @0,0.2 proto=none icon=💻 H2 @0,1.8 proto=none icon=🖨 H3 @3,0.2 proto=none icon=📠 H4 @3,1.8 proto=none icon=📺 A1 -- C11 A1 -- C12 A2 -- C21 A2 -- C22 C11 -- C12 C11 -- C21 C11 -- C21 C11 -- C22 C12 -- C21 C12 -- C22 C21 -- C22 A1 -- H1 A1:edge A1 -- H2 A1:edge A2 -- H3 A2:edge A2 -- H4 A2:edge After some time, the topology converges to a tree: from the root C11, there is a path to each bridge3 and no loop. In the upper right corner, the interface displays a tree icon 🌳 followed by the time it took to reach this state. Cut a link and see how the protocol finds an alternate path to reach C12 in less than a second. You can stop the simulation, move it forward step by step, reset it to its initial state, or slow it down with the “snail” mode 🐌. Don’t worry about all the displayed information: I explain it later. Note While you scroll, the current simulation stays in view so you can look at it while reading. Uncheck this box to disable this behavior: . All examples run in your browser, powered by MSTPD—an open-source user-space4 implementation of RSTP.5 Historical interlude# Radia Perlman, an inductee of the Internet Hall of Fame in 2014, summarized the ancestor of STP she invented at DEC with this poem, later included in a US patent: I think that I shall never see A graph more lovely than a tree. A tree whose crucial property Is loop-free connectivity. A tree which must be sure to span So packets can reach every LAN. First, the root must be selected. By ID, it is elected. Least cost paths from root are traced. In the tree, these paths are placed. A mesh is made by folks like me, Then bridges find a spanning tree. ― Radia Perlman, Algorhyme. Electing the root bridge# To build a tree, RSTP first elects the bridge with the lowest bridge identifier as the root bridge. The bridge identifier combines the priority and the MAC address: 8192.6e:2b:10:a0:5f:29. In the example below, S1 and S2 have priorities of 4,096 and 8,192: S1 becomes root. S4 has a priority of 12,288, while S3 keeps the default priority of 32,768:6 S4 becomes root. S5 and S6 don’t have a specific priority, so the lowest MAC address wins and S5 becomes root. :protocol rstp S1 @0,0 prio=4096 S2 @0,1 prio=8192 S1 -- S2 S3 @1,0 S4 @1,1 prio=12288 S3 -- S4 S5 @2,0 S6 @2,1 S5 -- S6 Initially, each bridge advertises itself as root:7 Spanning Tree Protocol Protocol Identifier: Spanning Tree Protocol (0x0000) Protocol Version Identifier: Rapid Spanning Tree (2) BPDU Type: Rapid/Multiple Spanning Tree (0x02) Root Identifier: 8192.02:00:00:01:00:01 Bridge Identifier: 8192.02:00:00:01:00:01 Once a bridge receives a BPDU advertising a better root bridge, it propagates this new information to its neighbors. Spanning Tree Protocol Protocol Identifier: Spanning Tree Protocol (0x0000) Protocol Version Identifier: Rapid Spanning Tree (2) BPDU Type: Rapid/Multiple Spanning Tree (0x02) Root Identifier: 4096.02:00:00:00:00:00 Bridge Identifier: 8192.02:00:00:00:00:01 Assigning roles to ports# The second step is to assign a role to each port. RSTP defines five roles, each denoted by a letter: root (R), designated (D), alternate (A), disabled (X), or backup (B).8 Each non-root bridge chooses its root port, the one with the lowest-cost path to the root. Unless you override it, each bridge derives the link cost from the speed: 20,000 for 1 Gbps. In case of equality, the lowest port identifier wins. Each remaining port becomes a designated port if the BPDU it sends is “better” than the BPDU it receives. Otherwise, it becomes an alternate port. Later, if the root port goes down, the “best” alternate port becomes the new root port. The tiebreakers for the best BPDU are: the lowest root bridge identifier, the lowest accumulated cost to the root, the lowest bridge identifier, and the lowest port identifier. :protocol rstp S1 @1,0 prio=4096 icon=🌳 S2 @0,1 S3 @2,1 S1 -- S2 S1 -- S3 S1 -- S3 S2 -- S3 In the example above, after convergence, S1 is the root bridge because it has a priority of 4,096, while the other bridges have a priority of 32,768. All its ports are designated ports because the accumulated cost to the root is 0. S2’s port facing S1 becomes a root port because it has the lowest accumulated cost to the root—20,000 vs 40,000. S3 has two ports facing S1, and the one with the lowest port identifier becomes the root port—0x8000 vs 0x8001. The other candidate is an alternate port because the remote port on the link sends a better BPDU, with an accumulated cost of 0. On the segment between S2 and S3, S2’s port wins: while both bridges have the same accumulated cost to the root (20,000), S2’s bridge identifier is smaller—32768.02:00:00:00:00:01 vs 32768.02:00:00:00:00:02. Spanning Tree Protocol Protocol Identifier: Spanning Tree Protocol (0x0000) Protocol Version Identifier: Rapid Spanning Tree (2) BPDU Type: Rapid/Multiple Spanning Tree (0x02) Root Identifier: 4096.02:00:00:00:00:00 Root Path Cost: 20000 Bridge Identifier: 32768.02:00:00:00:00:01 Port identifier: 0x8002 If you cut the active link between S1 and S3, S3 promotes the “best” alternate port to root port. If you also disable the second link, S3 chooses the remaining alternate port as a root port. But if you disable the link between S1 and S2, S2 needs a bit more work to elect a new root port because it does not have an alternate port. Unless a specific event happens, designated ports send BPDUs every 2 seconds.9 If a bridge does not receive BPDUs from its neighbor for 3 consecutive hello periods, it considers the neighbor dead and removes the port information. Port state transition# Each port can have one of three states. The diagram displays a background color for each state: discarding (red), learning (yellow), or forwarding (green). A root port transitions automatically to the forwarding state. An alternate port stays in the discarding state. A designated port has two options to transition from the discarding state to the forwarding state: If the port is an edge port, either through configuration or because the remote device does not speak any flavor of STP, the bridge assumes the device won’t participate in the protocol and