- Google I/O 2013's Coolest Products and Services
- 10 Star Trek Technologies That are Almost Here
- 19 Generations of Computer Programmers
- 25 Must-Have Technologies for SMBs
John Cioffi | Bob Metcalfe | Vint Cerf | Vic Hayes | Radia Perlman | Martin Cooper | Tim Berners-Lee
Network World - 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.
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."