As important as Spanning Tree has been to the acceptance and spread of Ethernet, making it possible to link Ethernet segments without creating loops and packet storms, its inventor, Radia Perlman, says she always thought it was a bad idea.
Read about Network World's other living legends
After all, Perlman is a Layer 3 wizard. The routing protocol she designed for Layer 3 of Digital Equipment Corp.'s DECnet architecture was adopted by ISO, renamed IS-IS, and remains widely deployed today. "Ethernet (Layer 2) is supposed to just be a way of talking to neighbors," she says. "Routing between links was Layer 3's job. When I tried to argue that we may need to forward packets from one Ethernet link to another, the reply was 'Our customers would never want to do that'. Their perception was Layer 3 was just unnecessary bytes on the wire."
But it didn't take long for that shortsightedness to become obvious.
Customers did, after all, want to talk from one Ethernet to another.
Layer 3 switches (routers), cannot forward packets unless the end nodes implement the router's Layer 3 protocol. "So it was necessary to invent some sort of kludge - what would become known as a bridge -- that could forward Ethernet packets, without requiring the end nodes to do anything differently than they would when talking to Ethernet neighbors," Perlman says.
With the writing on the wall, Perlman's manager at DEC turned to her as an expert in distributed algorithms and gave her what he thought was a complex problem: "Come up with something you just plug together with no configuration and somehow it breaks all the symmetries and comes out with a single, loop-free topology on which to forward the data packets," Perlman recalls.
"He thought it was going to be really hard and, I think just to be funny, he said, 'make it scale, make the overhead of the algorithm a constant, so no matter how many bridges and links there are in the network, the amount of memory necessary to run this thing would be a constant.'"
Nothing is a constant, Perlman says. "Maybe linear if you are lucky, more likely N squared."
He gave her the puzzle on a Friday afternoon and was gone all the next week and unreachable. But that night as Perlman was dozing off, the flash bulb exploded. "I realized, 'Oh my gosh, it's trivial, and, furthermore, it scales as a constant.'"
Spanning Tree was born.
It's really a simple algorithm, Perlman says modestly. "If you are a bridge with six ports, every time you see a spanning tree message on any port you have to compare it to the one you have stored. There are three main fields in the packet. One is the ID of the best root bridge you have heard of, your cost to get to it, and then your own ID. And if you concatenate those as a sort of multi-precision integer, then the "spanning tree message that is the numerically smaller value is better. If the one you just received is better than what you have stored, you throw that one away and store the new one.
"That way everyone will eventually converge on the bridge with the lowest ID as being the root. So you only have to remember one message on each port and the message is about 50 bytes long so it takes a bridge with six ports 300 bytes to run the algorithm no matter how many bridges and links there are."
Did she shoot out of bed to write the idea down?
"Absolutely," Perlman laughs. "I would have been really annoyed if I had waited until the next day and forgotten what it was."
It didn't take long to refine the idea because it was so intrinsically simple, she says. She spent Monday and Tuesday of the next week writing it out in detail, which took something like 25 pages. "But my manager was still gone and I couldn't concentrate on anything else because I thought this thing was so cool, so I spent the remainder of the week working on a poem which was an abstract of the paper in which I published the algorithm:"
Algorhyme
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.
While simple and elegant, Spanning Tree wasn't supposed to last more than a few years until people reversed the mistake they had made and adopted Layer 3, Perlman says. "There were other Layer 3 protocols that would have made bridges easy to get rid of. It is unfortunate the one that won out was IP. In IP, each link has a different block of addresses, so it takes a lot of configuration of the routers to know which addresses are on which ports, and end nodes have to change their Layer 3 address if they move.
"In contrast, ISO's CLNP packet format (Connectionless Network Layer Protocol) had the bottom level of routing being an entire chunk of network, with lots of links sharing the same block of addresses, where the routers inside the chunk did not need to be configured, and end nodes could move within the chunk without changing their address. If the Internet had adopted CLNP, bridges would have died a peaceful death."
Given the disadvantages of IP and spanning tree Ethernet, Perlman decided it was time to create a new concept; combining the advantages of Ethernet (ease of management) with IP (optimal routes, multipathing). This idea has been standardized in IETF as TRILL (TRansparent Interconnection of Lots of Links). Instead of doing Spanning Tree, a new type of bridge (called RBridge for "routing bridge") uses the IS-IS protocol to compute Layer 3-like paths.
"If you have a big Ethernet you can replace any subset of your bridges with RBridges and the end nodes still think they are just talking on an Ethernet and the existing switches still do their job. But the more you replace with RBridges, the better use of the topology you will get and the more stable it will get."
That makes it easier to migrate to large, flat, Layer 2 networks, which is all the rage today.
So even if Spanning Tree fades away, Perlman is assured of having at least one of her inventions running the networks of tomorrow.
Read more about lan and wan in Network World's LAN & WAN section.