Many things have been reinvented independently in solving some particular problem. The spanning tree algorithm is a reinvention of the depth-first search, first investigated by 19th century French mathematician Charles Tremaux while working on the expansion of the French telegraph system. I guess that actually was actually a very similar problem.
Ah the bit the Ethernet people got "wrong",
OK, war story.
remember the thick yellow ethernet and the side shoots, the self puncturing center tap to the thick cable . After a few years of changes the big cable sort of looiked a bit holly...
Or the company I worked at that had two buildings , about 500 m apart, who decided to lay a think yellow cable between the buildings, to connect the two computer centers.
would have worked great, apart from the installer who insisted on earthing both ends of the braid to the building earth. One building had VERY big machine presses sucking hundreds of amps at a time when they struck, and the other was a small office. 'worked', for a while till the earths in the machine shop were changed, The blue smoke from the Ethernet cable one day was the braid melting the plastic.
Or trying to document where a data tap had to go on the big yellow cable, and what angle. As you could not turn the cable very well, it was too stiff, if the tap had to come out at a certain angle to fit into the cabinets, then fun.
The idea of fitting the yellow cable and then tapping on site was just not in the procedures, we HAD to make up cable harnesses to a document, then feed them into the cabinet !
Dont think the procedures ever did catch up with the idea that many things could sit anywhere on the cable, it did not matter what order you wired them in/ Each and every time a cabinet was wired up, we had to do a change request to accomodate the system. Each cabinet to a standard, each one different.
Here is a comment Bob Metcalfe shared with me last night over email:
"When people say that the only thing left of Ethernet is the name and frame, they are right sort of, but they are overlooking the idea of a high-bandwidth packet LAN for PCs, which was revolutionary in its time and commonplace (not noticed) today. Or they are overlooking the Ethernet Ethic, which I reviewed in my terminal keynote last week - de jure standard, owned implementations, fierce competition, interoperability, evolution, backward compatibility."
It has been fascinating to watch ethernet - data comm's "wild child" - adapt, adopt and improve the policing, timing and QoS functions of pdh, sonet and atm. Ethernet did not just "win" over these technologies - it ingested them....
The reason the Ethernet spanning tree algorithm is so simple is that it is not calculating a "minimal cost" tree...the goal was to be very simple and have "constant overhead" (the amount of memory necessary for bridge B to run the algorithm is the size of a spanning tree message, about 50 bytes, times the number of ports on B). For instance, if B has 7 ports, it takes 7*50 bytes, or 350 bytes, for B to run the algorithm. The tree it computes I call "greedy", which is a tree in which everyone tries to get closest to the Root bridge, which might arguably be preferable to a minimum cost spanning tree which could wind up being very long. And the Ethernet spanning tree algorithm handles not only a single computation, but it is always active, and reacting to failures."
Gallager, Humblet and Spira have a distributed algorithm to compute a minimum *weight*spanning tree (also known as "minimal cost").
Because it is calculating an optimal tree according to minimal weight, it is
much more complex and expensive than the Ethernet spanning tree algorithm. Furthermore, I don't think it handles link failures, though I suppose one could add something to have some sort of signal that everyone should start over when a link fails, but it would be tricky. But as I said, it's a different problem.
So basically...distributed algorithms are totally different than graph problems where one node has the complete graph and does computations."
I asked Radia how the Ford Fulkerson algorithm, and minimum weight spanning tree computation algorithms, related to her spanning tree algorithm, and this is her explanation, which I am posting with her permission:
"The concept of a graph which is a spanning tree is indeed super old...I have no idea how old. But I believe the algorithms prior to the Ethernet spanning tree algorithm are not distributed...in other words, one computer gets as input, the full view of the network, and calculates a spanning tree on the graph with various properties (e.g. minimum cost, where the sum cost of all the links in the tree is minimal across all possible trees).
I think the Ford Fulkerson algorithm the person is talking about is the "max flow" problem, which is yet even a different problem, and actually isn't even a tree...you want lots of paths to push as much "flow" as possible.
So, hopefully I'm explaining it clearly. A graph problem where one computer does computations based on seeing the whole graph is different from the Ethernet spanning tree algorithm, in which you just plug things together and the bridges do really minimal work and keep minimal state in order to do a "distributed computation."
NASA's Orion Flight Software Production Systems Manager Darrel G. Raines joins Planet Analog Editor Steve Taranovich and Embedded.com Editor Max Maxfield to talk about embedded flight software used in Orion Spacecraft, part of NASA's Mars mission. Live radio show and live chat. Get your questions ready.
Brought to you by