![[Computing and Information Science Department]](/cis.jpg)
Note that Cisco and others have variations and improvements on this. Here we show just the basic algorithm. We assume that we are dealing with layer 2 switches.
The switches exchange special control messages to figure out a spanning tree (and to adjust it later if something changes, perhaps because of component failure or the addition of another switch). Each switch is configured with a priority number (often all the same). The default priority number is typically 32768, though this can be changed in order to cause a specific switch to become the root of the spanning tree. Each switch also has an ID number which is a concatenation of the priority number and the MAC address of the switch, with the priority number coming before the MAC address.
The root is chosen as the switch with the lowest ID number. If there is a switch with a lower priority number than all the others, then that switch has the lowest ID and becomes the root of the tree. If more than one have the same lowest priority, then the one with the lowest MAC address is chosen.
Determine the root path cost (RPC) for each port on each switch other than the root. The RPC is the least cost for a frame to go from the root to the port under consideration. This is the total cost for traversing all the links taken by this frame to go from the root switch to the port under discussion. Each link between 2 switches has a cost that is based on the bandwidth. Typical cost numbers are 100 for a 10 Mbps link (Ethernet), 19 for 100 Mbps (Fast Ethernet), and 4 for 1 Gbps (Gigabit Ethernet). Once all of the RPCs are known for each switch, the switch chooses the port with the lowest RPC as its root port (RP). If 2 or more ports have the same RPC, the lowest numbered port is chosen as the RP. The root port is then used to receive all control messages from the root to this switch.
For each link, a designated port (DP) is chosen as the one that gives the least total cost to go from this link to the root switch. (Cost is computed as in step 2.) If 2 or more ports on different switches give the same lowest cost, the port on the switch with the smallest ID number is chosen. All of the ports of the root switch are obviously designated ports. Note that a root port cannot be chosen as a designated port.
The root and designated ports of each switch are set to the forwarding state. Any other ports are set to the blocking state (i.e. these ports are essentially shut down except to listen to the control messages passed between the switches). This establishes the spanning tree.
Maintained by: Br. David Carlson
Last updated: 11/06/2005