Spanning Tree Protocol
1st August 2018
Spanning tree protocols are used to prevent layer 2 loops in a switched network. There are various forms of spanning tree that have been standardized by the IEEE. The original standards; 802.1D - Legacy Spanning Tree (STP), 802.1w - Rapid Spanning Tree (RSTP) and 802.1s - Multiple Spanning Tree (MSTP) have now evolved. The 802.1D standard covers RSTP but does not include legacy STP as it is considered obsolete. MSTP is incorporated into the 802.1Q standard. Additionally Cisco has its own proprietary implementation of legacy STP (PVST+) and RSTP (Rapid PVST+) which add support for a spanning tree instance per VLAN.
Legacy Spanning Tree Protocol (STP)
Standardized in 1993 by the IEEE as 802.1D. STP is used to create a loop free flooding domain by calculating the shortest path from each bridge to a single root bridge.
A switch in spanning tree is referred to as a bridge.
Bridge Protocol Data Unit (BPDU)
STP messages are passed around a switching domain in the form of a BPDU. Legacy STP uses two types of BPDUs; Configuration BPDUs and Topology Change Notification BPDUs. Configuration BPDUs are used to build a topology, TCN BPDUs advertise changes in the topology.
Switch ports that participate in spanning tree transmit and receive BPDUs on each LAN segment. Switches compare received BPDUs to their own BPDUs to determine which BPDU is superior. The superior BPDU is then stored for future comparison with received BPDUs and also advertised out any designated ports.
The superior BPDU is determined by examining the following parameters (from top to bottom) the lowest value wins. When a superior value is found, the comparison stops. If the values are equal, the next parameter is examined.
- Root Bridge ID
- Root Path Cost
- Sender Bridge ID
- Sender Port ID
- Receiver Port ID (local evaluation only)
In a stabilized STP domain the root bridges BPDU is forwarded by all other switches as it will always be the superior BPDU.
The responsibility of advertising topology changes falls on the root bridge. TCN BPDUs are forwarded up the tree to the root bridge. The root then advertises the changes back into the spanning tree domain.
In legacy STP, there can be exactly one root bridge. Configuration BPDUs are used to build a loop free topology toward the root bridge.
The root bridge is determined via an election. The switch with the lowest bridge ID will become the root bridge. The bridge ID is composed of a 2 Byte priority field (default 32768 + vlan-id) and a MAC address.
Legacy STP Bridge ID
Once the Root bridge has been elected each non-root bridge will determine its root, designated and blocking ports.
Port Roles and States
Ports connected to other switches in spanning tree end up as one of the following port roles and forwarding states.
|Root Port||Forwarding towards the root|
|Designated Port||Forwarding away from the root|
|Alternate Port||Blocking to prevent spanning tree loops|
Each non-root bridge can have only one root port, one designated port per segment and zero or more blocking ports.
Port Roles Selection Process
For each LAN segment the switch with the superior BPDU is known as the designated switch. The port with the superior BPDU is the designate port. The designated port originates or forwards BPDUs.
- The root bridge sends BPDUs out of its designated ports. All ports on the root bridge are designated.
- On each non root bridge, the root port is the port that receives the superior BPDU.
- Non root bridges add the port cost to the superior BPDU and forward it out all its designated ports.
- All other ports connecting to the segment which do not send or receive a superior BPDU are placed in a blocking state.
BPDUs are sent every 2 seconds by default and act as a hello/keepalive.
Non-disabled ports in legacy STP transition through a number of states staring with blocking and eventually end up in either a forwarding state or back to a blocking state.
Prior to the 802.1D-1998 standard the IEEE did not define spanning tree costs per port type. Cisco did make up their own port costs which are not shown in the table below.
|Port Speed||802.1D-1998 Cost||802.1D-2004 Cost|
Rapid Spanning Tree Protocol (RSTP)
RSTP was originally standardized by the IEEE in 802.1w. In 2004 RSTP was incorporated into the 802.1D standard. RSTP contains a number of enhancements over its predecessor with the main goal of improving the speed of convergence. Correctly design RSTP domains can achieve sub second link failover and convergence.
The was some adjustments to the ports states in RSTP outlined as follows.
|Root Port||Forwarding towards the root, same roles as legacy STP.|
|Designated Port||Forwarding away from the root, same roles as legacy STP.|
|Alternate Port||Potential replacement for a bridges root port. If the root port is lost the alternate port will rapidly transition (sub-second) to the forwarding state.|
|Backup Port||Potential replacement for a bridges designated port. Usually only found with a connection to a hub or on a shared segment (non-p2p). If a designated port is lost the transition to a forwarding state does not occur rapidly but is based on timers.|
The default role when a RSTP port becomes active is Designated.
The port states in RSTP where simplified into three states.
The disabled, blocking and listening states from legacy STP where merged into a discarding state. Additionally RSTP does not use timers to transition ports from discarding to forwarding, it uses a system of proposals and acknowledgements.
There are two port types in RSTP; Non-Edge and Edge.
|Non-Edge||Default port type. Connects to other switches.|
|Edge||Connects to end hosts. Sends BPDUs, but does expect to received them. Reverts to a Non-Edge type if BPDUs are received.|
RSTP defines two classes of links.
|Point-to-Point||Link connected to exactly one RSTP other switch. Default link type for interfaces negotiated to full-duplex.|
|Shared||Link connected to two or more RSTP switches likely via a hub. Default link type for interfaces negotiated to half-duplex.|
Two field where change in the RSTP BPDU. The version field was updated to version 2 and 6 unused bits of the flags field are now used to signal; Proposal, Agreement, Port role and Port state.
Each switch originates its own BPDUs based on the BPDU stored in the root port. Unlike legacy STP If a switch receives an inferior BPDU from a segments designated switch, it will accept the BPDU immediately as if the superior BPDU had expired. This facilitates rapid convergence if a neighboring switch has a connectivity issue towards the root switch.
Proposal and Agreement
RSTP uses the proposal and agreement process to rapidly transition a point-to-point link into operation without causing a temporary switching loop.
The proposal signals a ports willingness to transition to the designated forwarding state. The agreement signals permission to transition. (that's poetry)
There are no TCN BPDUs in RSTP. RSTP topology changes are advertised by setting the Topology Change (TC) bit in the flag field of the BPDU. When a topology change occurs the following takes place.
- BPDUs with the TC bit set are immediately flooded out all non-edge root and designated ports except the port the topology change was received from.
- All MAC addresses learned on the root and designated ports are flushed.
- BPDUs are sent every Hello interval until the tcWhile (Hello + 1 second) timer expires.
Multiple Spanning Trees (MSTP)
MSTP is similar to Cisco's proprietary PVST+ implementation except that it does not create a spanning tree instance per VLAN. MSTP groups multiple VLANs into a instance with generally only a hand full of instances required per switching domain.
MSTP groups switches into one or more regions. Switches in an MST region have the same number of MST instances which contain the same VLANs. An MST region looks like a single switch to other switches outside the region.
MSTP uses a single BPDU to carry information about all MST instances. The MST standard permits up to 65 (0 + 64 user defined) active instances. Designated ports for at least one instance send BPDUs.
MST instance 0 is the default MST instance known as the internal spanning tree (IST). By default all VLANs map to instance 0. Instance 0 is used to communicate with switches outside the MST region.
Various spanning tree PCAPs can be found here.
|Kocharians, N. and Paluch, P. (2014) CCIE Routing and Switching v5.0 Official Cert Guide, Volume 1, 5th Edition - Chapter 3: Spanning Tree Protocol. Indianapolis: Cisco Press|
|cisco.com (2006) Understanding and Tuning Spanning Tree Protocol Timers. Available at https://www.cisco.com/c/en/us/support/docs/lan-switching/spanning-tree-protocol/19120-122.html (Accessed: 20 Jul 2018)|
|cisco.com (2017) Understanding Rapid Spanning Tree Protocol (802.1w). Available at https://www.cisco.com/c/en/us/support/docs/lan-switching/spanning-tree-protocol/24062-146.html (Accessed: 25 Jul 2018)|
|cisco.com (2017) Understanding Multiple Spanning Tree Protocol (802.1s). Available at https://www.cisco.com/c/en/us/support/docs/lan-switching/spanning-tree-protocol/24248-147.html (Accessed: 01 Aug 2018)|