Sticker 006 · Radia Perlman · Back to the album card · Leggi in italiano
A spare cable should make a network more reliable. In Ethernet, however, an extra connection can close a loop. Some messages can then keep circulating and congest the network. Radia Perlman found a way to preserve those spare links and let the devices decide which ones to use. Her solution is the basis of the Spanning Tree Protocol, or STP.
Radia Perlman and the Ethernet loop problem
In 1985 Perlman was working at Digital Equipment Corporation. In her paper on distributed computation of a spanning tree, she described how bridges could connect multiple network segments while keeping the active topology free of loops. A bridge forwards Ethernet frames between segments. When bridges form a circuit, a frame sent to all devices can be copied and forwarded again and again. An ordinary Ethernet header has no hop counter to stop those copies. The resulting traffic can overwhelm the very links meant to make the network more resilient.
How the Spanning Tree Protocol works
Picture three switches wired in a triangle. When all three sides forward traffic, the triangle is a loop. Keep two sides active and you can still reach every switch, but the loop disappears. Ports on the redundant connection can remain in a state that prevents data forwarding where needed. If an active link fails, the devices can recalculate the topology and use the spare connection. That change takes time, known as convergence time.
To choose which ports to use, bridges exchange control messages, called BPDUs in the standard, and agree on a root bridge. Each bridge determines its lowest-cost path to the root. Link costs and protocol rules guide the choice, with identifiers used to break ties. Network segments also select a bridge to connect them to the tree. The root provides a reference for the calculation. Ordinary frames between two devices do not necessarily pass through it.
Each device makes decisions from information exchanged with the others, without relying on a controller that knows the full wiring plan. Perlman also described how to limit the memory required at each bridge and the control traffic on each segment. The design addressed both reliability and the need to let a network grow.
The algorithm, the standard and free software
The 1985 paper has a single author. Standardising Ethernet bridging was a separate collective effort, historically associated with IEEE 802.1D and brought into the IEEE 802.1Q family. The software implementing those rules has its own authors. In the Linux kernel, for example, net/bridge/br_stp_if.c credits Lennert Buytenhek and is marked GPL-2.0-or-later.
Where to read the original work
The scan of the 1985 paper documents Perlman’s algorithm and states ACM’s conditions for reproduction. I could not verify an STP source-code excerpt with both individual authorship by Perlman and reuse terms compatible with republication. The triangle above is an original teaching example. The linked Linux file is a later implementation readers can study under its stated licence.
The legacy and the trade-off of using a tree
A tree makes forwarding more predictable, but it can leave some available capacity unused. In July 2011 Perlman and four co-authors published RFC 6325, the base specification for the Routing Bridges used in TRILL. It describes how routing, encapsulation and a hop count can support multiple paths. Her USENIX profile also documents her work on routing and security. A practical lesson connects these projects: design for how a network will respond to an extra link as well as to a missing one.
Portrait: Radia Perlman in 2009, Scientist-100, public domain. Wikimedia Commons.
Nominate a programmer
Tell us about a programmer whose work deserves a place in the album, whether widely recognised or overlooked. Include the project and sources we can check. Editors review each nomination before publication. Your email is optional and used for follow-up.