Spanning tree protocol

The spanning tree network protocol provides a loop free topology for any bridged LAN. The Spanning Tree Protocol, which is also referred to as STP, is defined in the IEEE Standard 802.1D. Spanning tree is based on an algorithm invented by Radia Perlman while working for Digital Equipment Corporation. STP is used in switched networks to prevent loops, and has been standardised by IEEE 802.1D. As the name suggests it finds a spanning tree within the mesh formed by the network installer and disables the links that are not part of that tree.

If more than one open path were to be active at once then there would be several problems. First, there would be a broadcast storm caused by broadcast packets looping. Second, the traditional source-based location system used by switches would fail to operate correctly. The result of this would be to cripple the network. However, a good network design should include spare (redundant) links to provide an alternate path if one fails. Hence the need for spanning tree protocol.

Protocol operation

* Elect a root bridge.
* Find least cost (measured as hopcount) paths to root bridge.
* Disable links that are not part of those paths.

Electing a root bridge

Each switch has a MAC address and a configurable priority number, both of these numbers make up the bridge identification or BID. The BID is used to elect a root bridge based upon the lowest priority number; if this is a tie then the numerically lowest MAC address wins. Because it is unlikely that two MAC addresses will be the same, one switch should always be successfully elected as the root bridge. Other switches in the network will then calculate the shortest distance to the root bridge using bandwidth as a measurement and so produce a loop free tree topology. The priority number is normally left at its default value but can be reconfigured to a lower number if the network administrator wishes a particular switch to be elected; otherwise the whole process is totally automated.

Bridge Protocol Data Units (BPDUs)

BID's and other Spanning Tree Protocol information are carried in special data frames called bridge protocol data units (BPDUs). BPDUs are exchanged regularly (every 2 seconds by default) and enable switches to keep track of network changes and activate or disable ports as required. When a device is first attached to a switch port, it will not immediately start to forward data. It will instead go through a number of states while it processes BPDUs and determines the topology of the network. When a host is attached such as a computer, printer or server the port will always go into forwarding mode, albeit after a delay of about 50 seconds while it goes through the listening and learning states (see below). However, if instead another switch is connected, the port may remain in blocking mode if it is determined that it would cause a loop in the network. Topology Change Notification (TCN) BPDU's are used to inform other switches of port changes. TCN's are injected into the network by a non-root switch and propagated to the root. Upon receival of the TCN, the root switch will set a Topology Change flag in its normal BPDU's. This flag is propagated to all other switches to instruct them to rapidly age out their forwarding table entries.

STP switch port modes:
*Listening - The switch processes BPDUs and determines the network topology
*Learning - The switch builds a switching table that maps MAC addresses to port numbers
*Blocking - A port that would cause a switching loop, no user data is sent or received but it may go into forwarding mode if the trunk link in use were to fail. BPDU data is still sent and received in blocking mode
*Forwarding - A port receiving and sending data, normal operation
*Disabled - Not strictly part of STP, a network administrator can manually disable a port

To prevent the delay when connecting hosts to a switch Rapid STP was developed and standardised by IEEE 802.1w which allows a switch port to go immediately into forwarding mode when an end device is attached.

Evolutions and extensions

Per-VLAN Spanning Tree (PVST)

In Ethernet switched environments where multiple Virtual LANs exist, spanning tree can be deployed per Virtual LAN. Cisco's name for this is per VLAN spanning tree (PVST and PVST+ which is the default protocol used by Cisco switches).

Rapid Spanning Tree Protocol (RSTP)

In 1998, the IEEE introduced an evolution of the Spanning Tree Protocol: Rapid Spanning Tree Protocol (RSTP) or 802.1w. In the 2004 edition of 802.1D, STP is superseded by the RSTP.

Multiple Spanning Tree Protocol (MSTP)

The 2003 revision of the standard also rolled in the Multiple Spanning Tree Protocol (MSTP) originally defined in IEEE 802.1s and later merged into IEEE 802.1Q-2003

Trivia

Radia Perlman, the inventor of the algorithm summarized it in the form of a poem, titled "Algorhyme":
(This poem was modified from the original entitled "Trees", by Joyce Kilmer).

I think that I shall never see:A graph more lovely than a tree.:A tree whose crucial property:Is loop-free connectivity.: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.

References

*{{cite book