The Internet Chronicles – Part 7 of 12: The Tree the Internet Grows on

Andrei Mihai

Previously, we watched Tim Berners-Lee knit the world together with the Web, giving us pages to browse and links to click. But a web of information is useless if the physical network carrying it collapses under its own weight. In the early days of the internet, this was a very real problem.

The primary challenge was connectivity, but the next one was stability. As networks grew from a few dozen nodes in a single laboratory to thousands of nodes across a campus or city, the statistical probability of configuration errors, link failures, and topology loops approached certainty. Early networks were fragile; a single misconnected cable could create a feedback loop that would saturate the bandwidth of the entire system, bringing all communication to a halt (a phenomenon known as a broadcast storm).

Hardware engineers struggled to fix this. They needed a way to build big, redundant networks that wouldn’t self-destruct. They needed a logic that could be scaled. Enter Radia Perlman, the mathematician who put the internet on a tree.

The Reluctant Engineer

Radia Perlman did well in school and liked math and physics, but she did not originally intend to be a network engineer. In fact, growing up in New Jersey in the 1950s, she found the “gadget-obsessed” culture of early computing a bit weird. Computer people liked to take things apart and tinker. Perlman liked puzzles and mathematics more.

“I was not a hands-on type person. It never occurred to me to take anything apart. I assumed I’d either get electrocuted, or I’d break something,” she recalled, but she did take a programming class in high-school (where she was the only woman). Yet, as a graduate of MIT, she continued to engage with computers. She developed a child-friendly version of the educational robotics language LOGO, called TORTIS (“Toddler’s Own Recursive Turtle Interpreter System”), becoming a pioneer in teaching children computer science.

Working with three-year-olds taught Perlman a lesson that would define the modern internet: Systems must be “child-proof.” Toddlers are agents of chaos. They push buttons simultaneously; they hit things repeatedly; they do the unexpected. Internet users are not that different in some regards. A good system has to handle “garbage” input without crashing. She also observed that children learned best with minimal human interference, and tried to apply this principle to the network.

She believed that network switches should be “plug and play” – so robust that you could connect them in any messy configuration and they would just work, without a human having to type a single command.

But this was, of course, easier said than done.

A Poem for the Network

After graduating, Perlman worked in local network equipment and, in 1980, made an impression on a manager for Digital Equipment Corporation, one of the leading players in computer technology at the time. She joined the firm, but her approach was still mathematical. A network was a mathematical graph, a collection of nodes and edges that needed to obey strict logical rules. The cables and everything else were secondary.

Management gave Perlman a tough assignment: Design a protocol that allows bridges (early switches) to automatically discover the network topology and block loops, all while running within constant memory limits. It was a complex problem and she was not the first one to try to tackle it.

Perlman solved it in a week. Some “urban legends” that we could not verify claim she figured out the core concept in a single evening. However fast it was, the solution was the Spanning Tree Protocol (STP).

STP’s core approach was pure graph theory. Perlman thought that no matter how messy the physical network was, it should not look like a spiderweb of redundant cables, but rather as a tree that has a root and branches, but no loops.

The first stage is a bit like an election. Every switch claims to be the “Root.” They shout this claim to their neighbors and start verifying their level. If a switch hears a neighbor with a lower ID number, it admits defeat and acknowledges the neighbor as the superior path. Eventually, everyone agrees on one Root Bridge. They then calculate the shortest path to that root.

Each bridge identifies which of its ports offers the “least cost” path to the Root. Cost is typically based on link speed (e.g., a 10Mbps link has a lower cost than a 1Mbps link). On every individual network segment (the wire connecting two bridges), there can be only one bridge responsible for forwarding traffic to and from that segment.

The key detail was that any connection not part of this shortest path was put into a “Blocking State”. It simply sits silent, acting as a backup. If the main cable is cut (or chewed by a rat), the silent port wakes up and restores the connection.

It was a deterministic and self-stabilizing approach, exactly what was recommended for the scaling of the internet.

Networks (especially large-scale networks) are challenging to conceptualize. Drawing from her pedagogical experience, Perlman also wrote (in addition to technical specifications) a poem, the “Algorhyme,” which she embedded in the code’s header. In twelve lines, she encapsulated the entire logic of the algorithm.

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 that 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.

Beyond the Tree

This protocol essentially defined the scaling of the internet for almost two decades. It was only in 2001 that the IEEE introduced Rapid Spanning Tree Protocol (RSTP) as 802.1w to replace the original STP. RSTP was designed to be backwards-compatible with standard STP and was substantially faster.

But in the meantime, Perlman continued to bring key innovations for the internet and networks in general.

The STP works at the so-called “Layer 2” of networking. It handles data transfers between devices on the same physical network (like your home Wi-Fi or an office LAN). It uses MAC addresses (burned into the hardware) to identify devices and the key hardware here is the switch (historically called a bridge). The superior “Layer 3” handles routing, which is moving data between different networks (internetworking) to reach a final destination. It uses IP addresses (like logical coordinates) and the key hardware is the router.

In the 1980s, the dominant routing protocol was RIP (Routing Information Protocol), which used a “distance vector” algorithm (based on the Bellman-Ford algorithm). This protocol suffered from slow convergence and the “count to infinity” problem (where bad information loops between routers).

Perlman championed a different approach called link-state routing. In this model, every router builds a complete, identical map of the entire network. She was the principal designer of the IS-IS protocol, which introduced a game-changing concept: TLV (Type-Length-Value) encoding.

Before this, data packets were rigid. If you wanted to add a new feature, you had to redesign the whole packet. Perlman made them flexible. The “Type” told the router what the data was, the “Length” told it how long it was, and the “Value” was the data itself. If a router saw a “Type” it didn’t understand, it could just skip over that “Length” and keep reading.

This approach is still used today as the backbone for major Internet Service Providers. When the world needed to switch from IPv4 to IPv6 (core internet protocols used for identifying and locating devices on a network), IS-IS adapted easily because of Perlman’s extensible design, while other protocols like OSPF (which she also influenced) had to be rewritten.

The Internet as a Lasagna

In an Ask Me Anything (AMA) on Reddit from 2022, Perlman shared some of her insights and impressions about her work, her life, and the internet. When prompted by the classic “lasagna question” (if you stack two lasagnas on top of each other, do they become one lasagna), she explained why the term “internet” is actually a really unfortunate one.

“I’ve always hated the term “Internet” … to me, if you have two networks, and connect them, you don’t get an “Internet” … you get a bigger network. So I’d say that two lasagnas stacked on top of each other are just a taller lasagna. Unless it overflows your pan, in which case you get a lasagna and a messy oven.”

In the same AMA, Perlman goes on to give several nuggets of wisdom, including one that may be useful for Young Researchers attending the Heidelberg Laureate Forum (HLF) as well:

“Self-confidence is important, but it’s hard to force that on yourself. Perhaps find people that you feel comfortable asking questions of. I’m glad I had a math background (rather than majoring in CS), because math makes you think cleanly. CS has a lot of meaningless buzzwords, which drive me crazy.

“But again … what are you really good and passionate about? Find a way to leverage those skills in a networking career. The more different you are from the majority of other people in the skills, the more valuable you will be.”

Perlman went on to hold over 200 patents and influence other key protocols and algorithms. In recent times, she has turned a critical eye on blockchain and the alleged promise it holds. But in the early days of the STP, the internet was finally ready to truly take off. There was only one major problem: How do you keep it safe? This is where two familiar HLF faces (Martin Hellman and Whitfield Diffie) will come in.

The post The Internet Chronicles – Part 7 of 12: The Tree the Internet Grows on originally appeared on the HLFF SciLogs blog.