Given a graph G=(V,E), a spanning tree of G is a subset E' of the edges E, which connects all vertices of V and is a tree.

In other words,

1. (V,E') is a connected graph.
2. (V,E') contains no cycles.

Spanning trees are some kind of "backbone" of a graph.

This is just bizzare:

Algorhyme

I think that I shall never see
A graph as lovely as a tree.

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.

-- Radia Perlman, Interconnections                    

A spanning tree is created so that loops do not occur in a network when there are multiple paths to a host that is down. First, using a beautiful ASCII diagram, I will show you some examples where spanning trees are needed:

                     H1
                     |
                     B1              H = Host
                    / \              B = Bridge
                   /   \
              H3--B3   |
                   \   /
                    \ /
                    B2
                     |
                     H2 (down)

Now, picture this: H1 is sending a packet to H2 which at the moment is down for some irrelevant reason. H1 send the packet to B1, which thinks that B2 knows the path to H2. Since H2 is down, B2 does not have access to it, therefore B2 forwards the packet to B3 who might have a path to it. As any other bridge in this network, B3 hasn't got a path to H2 either, therefore the packet is forwarded to B1. B1 will then forward the packet to B2 and so on.

To prevent these types of loops, spanning trees got invented. To create a spanning tree, first a root bridge must be selected. This is how it is done:

1. Each bridge starts to advertise itself as the root-bridge, sending CBPDUs containing the MAC Adress of itself, and the cost of the interface the CBPDU was sent from.
   
   The cost is set by the administrator on each port
   
   
2. The bridges continue to advertise themselves as root bridges until they receive a CBPDU containing info about a better candidate. The bridge receiving a CBPDU containing a better candidate forwards this CBPDU out the other interface, after adding those interfaces' costs to the cost of the interface the CBPDU was originally sent from.
   (Cumbersome? yes! but I couldn’t come up with a better way to write it)
   
   
3. When the bridges don't receive any more CBPDUs, the bridges choose the bridge with the lowest cost link as the root port. The designated bridge is the bridge that has links to other parts of the network.
   NOTE: If to bridges has the same cost, the bridge with the lowest MAC Address of those, is elected as the root bridge

Now that a root bridge has been selected, the interfaces on the bridges are put in either Forwarding State (FS) or Blocking State (BS). The interfaces that are in BS will not forward any packets, while those in FS will. Here are the rules:

• An interface that is a part of the path with the lowest cost to the root bridge = FS.
• All interfaces on the root bridge = FS
• An interface that is a part of the path with the lowest cost to the designated bridge = FS
• Any interface that doesn't match one of the above criteria’s = BS

After this is done, CBPDUs are sent once in a while in case changes in the topology have occurred. A change in the topology usually leads at least one interface changing from FS to BS or vice versa.

Distributed Spanning Tree Algorithm

Finding a spanning tree for a graph is an easy problem. One can simply pick a node and elect links to new nodes continuously until all nodes are included. Where the problem gets more difficult is when you don't have any knowledge of the graph topology. If you imagine a local area network that is constantly being modified you can see that it would be real nice to avoid having to manually reconfigure the network every time something changes.

To demonstrate the distributed spanning tree algorithm we use a simple network constructed of the following:

• Stations - A station is simply an address on the network, an end point that does nothing as far as the network is concerned.
• Hubs - A hub is a repeater, a message comes comes in on one port and is sent out to all the others. Stations must be connected to hubs.
• Bridges - A bridge links any number of hubs together to form more complex networks. The bridges are the only way to form a loop, and thus are responsible for creating and maintaining the spanning tree.

Other terminology:

• Root - The root is the ID number of the bridge which will be considered the root of the spanning tree. All bridges must have a unique ID number or the algorithm will have no way to agree on a root and thus will fail.
• Ports - Ports are simply the connections on a bridge. For the sake of the algorithm we can allow unlimited ports. If our bridges were full-blown routers then they would maintain routing tables mapping certain addresses/subnets to. But that's a whole 'nother distributed algorithm. In this case we just want to know which ports are part of the spanning tree and which are not.
• Distance - Distance is the number of hops to the root bridge. In reality each port can be assigned a different distance according to bandwidth or some other metric, but for the sake of explanation hops is good enough.

Our goal is a distributed algorithm that can dynamically handle any physical network changes. The code should be simple and identical in each bridge. Some bandwidth will be wasted due to unused connections, but such is life. This algorithm is very closely related to Dijkstra's Algorithm.

The Algorithm

Each bridge must keep track of the following information:

• selfid - A globally unique hardware number such as MAC address.
• bestroot - The ID# of the bridge currently treated as root.
• bestdist - The distance to bestroot.
• bestport - The port to use to get to that root.
• isactive - Initialized to true, set to false if the bridge does not have any picked ports (see below).

Plus for each port:

• picked - Set to true if this port is a leaf in the spanning tree.
• lasttime - The last time a config message was read on this port.
• root - The root according to this port.
• dist - The distance to this port's root.
• neighbor - The hub connected on this port.

Initially, in the absence of remote information, a bridge will assume bestroot to be itself, and bestdist to be 0. The root sends out special configuration messages on all ports at regular time intervals. Initially all bridges will be sending these, but soon all bridges will recognize the same root. The message includes only three data: bestroot, bestdist, and selfid.

Processing Config Messages

Upon receipt of a config message, the bridge checks to see if the new config is 'better' and updates the info for that port accordingly. Better means that either we haven't heard anything from that port, or the root is lower, or the root is the same but the distance is lower, or the root and distance are the same but the neighbor is lower.

If the port info was updated then those same three data need to be tested against the overall best for the bridge using the same criteria, with bestroot, bestdist, and bestport updated accordingly. The bestdist is, of course, equal to the port distance + 1 since it's effectively one more hop.

After the best info is updated, we must designate which ports are the leaves on the spanning tree. This is done by a similar comparison to see if bestroot, bestport, and bestport's neighbor are superior to the last received info on every port. If so then those ports are picked, otherwise they are not picked and will receive no transmissions (other than config messages) from this bridge.

If no ports are picked then the bridge can be designated inactive indicating that it doesn't need to process any incoming packets at all.

Reconfiguring

The algorithm works pretty well as is, but if a bridge is disconnected then we can start losing packets into the ether as messages are transmitted to a non-existent bridge. For this purpose we set up a time interval on which we expect to hear from each unpicked port (picked ports may be receiving config messages only from us, and thus we should not expect hear back from them). If no config message comes before the end of that interval we trigger a reconfiguration where the best info is recalculated from the remaining ports that are still communicating. This will fix the entire network in at most twice the length of the reconfiguration interval.

---

Andrew S. Tanenbaum. Computer Networks, 4th Ed. Upper Saddle River, NJ: Prentice Hall, 2003.