On this page
In 1985, Radia Perlman, an engineer at Digital Equipment Corporation, published a short paper that used school-level graph theory to show how the bridges joining Ethernet segments could agree, with no central controller, on a set of links with no loops. We now call it the spanning tree protocol, or STP.
Who is Radia Perlman?
Perlman was born on 18 December 1951 and earned her doctorate in 1988, according to the National Inventors Hall of Fame, which inducted her in 2016. That page says spanning tree "transformed Ethernet from a technology limited to a few hundred nodes confined within a single building into a technology that can create large networks with hundreds of thousands of computers". The Internet Hall of Fame inducted her in 2014. It also credits her with IS-IS, a routing protocol she designed in the 1980s that is still used to route IP traffic today.
Her work picks up after Bob Metcalfe invented Ethernet in 1973: how to join many Ethernets into one network without loops.
Why do network loops break Ethernet?
Spare cables let a network survive a cable failure, but they create loops. Cisco's spanning tree configuration guide warns: "If a loop exists in the network, end stations might receive duplicate messages and switches might learn endstation MAC addresses on multiple Layer 2 interfaces. These conditions result in an unstable network."
An Ethernet frame has no field that counts hops, so a frame caught in a loop can keep circling. In RFC 5556, Joe Touch and Perlman write that spanning tree protocols must "strictly avoid loops, even temporary ones" because of "the lack of header loop detection support".
How does the spanning tree protocol work?
Picture the network as a graph: switches are vertices and cables are edges. A spanning tree of a graph is a subgraph that is a tree and reaches every vertex, and on n vertices it has exactly n − 1 edges, as Wolfram MathWorld states. No cycles means no loops, yet every switch stays reachable.
The paper's abstract says bridges "compute, in a distributed fashion, an acyclic spanning subset of the network" (Perlman, 1985). It ends with a poem, "Algorhyme", whose middle couplets give the method: "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."
In today's switches, as Cisco documents it, the steps are:
Every switch sends small messages called bridge protocol data units (BPDUs) at regular intervals.
The switch with the lowest bridge ID becomes the root. If every switch keeps the default priority of 32768, the lowest MAC address wins.
Every other switch picks one root port: the port with the lowest-cost path to the root.
On each link, the switch with the cheaper path to the root forwards traffic for that link.
Every other port goes into the blocking state. It forwards no data but keeps listening to BPDUs.
Worked example: can you find the spanning tree?
Four switches are named S1, S2, S3 and S4, and the number is their bridge ID. Cisco's guide lists a default path cost of 4 for Gigabit Ethernet and 19 for Fast Ethernet (Cisco), so use those:
S1–S2: cost 4
S1–S3: cost 4
S2–S4: cost 4
S3–S4: cost 4
S1–S4: cost 19
Five edges on four vertices means at least one loop. The tree must keep exactly 4 − 1 = 3 edges.
S1 has the lowest ID, so it is the root.
S2 reaches the root directly at cost 4, so its root port faces S1.
S3 also reaches the root directly at cost 4, so its root port faces S1.
S4 has three routes: via S2 (4 + 4 = 8), via S3 (4 + 4 = 8), or direct (19). The two 8s tie. The next tie-breaker is the lowest sender bridge ID (9tut STP tutorial), so S4 chooses S2.
Kept: S1–S2, S1–S3, S2–S4. Blocked: S3–S4 and S1–S4.
Three edges, all four switches connected, no cycle. Now cut the S2–S4 cable and redo step 4: S4 goes through S3 at cost 8, and the blocked S3–S4 link becomes the backup.
What did spanning tree cost, and what came after?
A tree is safe but wasteful. In RFC 5556, Touch and Perlman note that spanning tree "often results in inefficient use of the link topology". In a ring of N switches it disables one link, so traffic between the two switches on that link travels N − 1 hops around the ring instead of one. Perlman later designed TRILL, which the Internet Hall of Fame says "allows Ethernet to make optimal use of bandwidth".
Modelling systems as graphs runs from Euler's seven bridges of Königsberg to the PageRank algorithm behind web search.
If trees, cycles and graphs still feel slippery, the Fermi Concept Library has a lesson for every concept in mathematics and computing, each with its place in the map. Then try the example above with six switches of your own.
