In a Local Area Network layer 2 broadcast domain, the Spanning Tree Protocol is a Data Link Layer protocol. It is standardized as IEEE 802.1D. As the name suggests, it creates a spanning tree within a mesh network of connected layer-2 bridges (typically Ethernet switches), and disables those links that are not part of the spanning tree, leaving a single active path between any two network nodes.
STP is based on an algorithm invented by Radia Perlman while working for Digital Equipment Corporation.
The protocol uses mathematical graph theory to model the layer 2 network as an interconnected graph and, by means of judiciously disabling links, applies continuous tests to ensure it satisfies the conditions necessary to be a specific type of bipartite graph known as a spanning tree. Hence the name of the 802.1D protocol.
Now, in order to do this, the protocol needs to transfer information about the network topology as well as many other things to each node of the network. The packets which carry this information are called Bridge Protocol Data Units (BPDU’s).
The protocol needs to manage the election of a node (or bridge) as the root of the tree (or root bridge). Once this has been done, the protocol has to determine which links need to be closed (or blocked) in order to satisfy the rules of spanning tree theory. The BPDU’s carry this information around the network allowing the bridges to have an awareness of the wider broadcast domain.
A bridge sends a BPDU frame using the unique MAC address of the port itself as a source address, and a destination address of the STP multicast address 01:80:C2:00:00:00.
There are three types of BPDUs:
- Configuration BPDU (CBPDU), used for Spanning Tree computation
- Topology Change Notification (TCN) BPDU, used to announce changes in the network topology
- Topology Change Notification Acknowledgment (TCA)
BPDUs are exchanged regularly (every 2 seconds by default) and enable switches to keep track of network changes and to start and stop forwarding at ports as required.
When a host is initially connected to a switch port, it will not begin to forward data straight away. Instead, it goes through a number of states while it processes BPDUs and determines the topology of the network. When a device such as a PC or server is attached, the port must always settle to the forwarding state but it needs to listen for BPDU’s first. This process can take approximately 30 seconds while it goes through the listening and learning states. The time taken to step through the listening and learning states is determined by a value known as the forward delay. The default value for the forward delay is 15 seconds and but can be set by the root bridge if necessary. If BPDU’s are detected during this period, the network treats the device connected to the port as a bridge and processes the BPDU’s as appropriate. In doing so, by using Topology Change Notification (TCN) BPDUs, any changes are propagated around the network. If it is subsequently determined that the enablement of the newly available link would cause a loop in the network the port be placed into blocking mode. TCNs are injected into the network by a non-root switch and propagated to the root. Upon receipt of the TCN, the root switch will set a Topology Change flag in its normal BPDUs. This flag is propagated to all other switches to instruct them to rapidly age out their forwarding table entries and thus the new topology is learned across the network.
STP switch port states:
- 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 other links in use were to fail and the spanning tree algorithm determines the port may transition to the forwarding state. BPDU data is still received in blocking state.
- Listening – The switch processes BPDUs and awaits possible new information that would cause it to return to the blocking state.
- Learning – While the port does not yet forward frames (packets) it does learn source addresses from frames received and adds them to the filtering database (switching database)
- Forwarding – A port receiving and sending data, normal operation. STP still monitors incoming BPDUs that would indicate it should return to the blocking state to prevent a loop.
- Disabled – Not strictly part of STP, a network administrator can manually disable a port.
The bridge ID, or BID, is a field inside a BPDU packet. It is eight bytes in length. The first two bytes are the Bridge Priority, an unsigned integer of 0-65,535. The last six bytes are a MAC address supplied by the switch. In the event that MAC Address Reduction is used, the first two bytes are used differently. The first four bits are a configurable priority, and the last twelve bits carry either the VLAN ID or MSTP instance number.