A spanning tree is a subset of a network that reaches all nodes in the network and has no loops. The "nodes" are the red circles in the picture to the left. The spanning tree is the blue path through the network. Note that the path spans (reaches) all the nodes, but there's only one path to each node from any other node. There are no loops. It's a tree. Granted, this example makes it look like kind of a funny tree, but use your imagination.
The spanning tree algorithm converts a mesh network into a tree-shaped network. To understand a mesh network, think of the Los Angeles freeway system, with its numerous interconnected roads. To understand a tree, think of a real tree with a root and branches, but no interconnected, looped branches. Or think of an org chart (an upside down tree) or a file system on your computer that has directories, subdirectories, and files. Going back to the Los Angeles freeway system, to understand the spanning tree algorithm, think of yourself sitting at home in, let’s say Redondo Beach, trying to get to San Bernardino.
Here are some good resources regarding the spanning tree algorithm:
- Wikipedia’s article on minimum spanning trees is good.
- Wikipedia’s article on the particular spanning tree protocol that Radia Perlman invented for use on internal switched (bridged) networks is good too.
- Cisco's article on the rapid spanning tree protocol used by switches is a must-read for those of us in the networking field.
- I wrote about Radia Perlman last year for Ada Lovelace Day.
- Finally, be sure to read Dr. Perlman’s famous poem about spanning trees at the bottom of this terrific interview with her.