Spanning Tree Protocol (STP) is probably one of the more confusing protocols. However, it is still hugely relevant in today’s networks, particularly in Enterprise LANs and Metro Ethernet.
Spanning Tree is a loop avoidance protocol, and works by prohibiting Layer 2 loops from forming.
Basic Switch Operation
To properly understand STP you need to know why loops occur in the first place. Let’s first remind ourselves of how a layer 2 switch works. Consider the following simple network:
In order for hosts to communicate, they need to know each other’s Media Access Control (MAC) addresses.
Let’s suppose Host A wants to communicate with Host B. Host A has IP address 10.1.1.1/24 and host B has IP address 10.1.1.2/24. Host A will send an ARP (Address Resolution Protocol) request asking “who has IP address 10.1.1.2?”. Switch 1 will receive this request and forward it on all ports except the port it received it on.
Host B receives the ARP request and replies with its MAC address. Switch 1 now knows the MAC address for host B is connected to port 15. It stores this information in its MAC address table. The switch also knows that host A is connected to port 3 (because of the ARP request), and it also stores this in its MAC address table.
Now when host A wants to talks to host B, Switch 1 knows to forward the frame out of port 15.
Introducing a Loop
Now let’s see what happens when we introduce a loop. Consider the following network:
- Host A sends an ARP request that is received by Switch 1. Switch 1 then forwards it out of ports 14 and 15 (orange).
- Switch 2 receives it (from Switch 1) on port 1 and forwards it out of port 2 (green).
- Switch 3 receives it (from Switch 1) on port 5, and forwards it out port 1 and 6 (blue).
- Switch 3 now receives it on port 1 (from Switch 2) and consequently sends it out port 5 and 6 (grey)
- Switch 2 also receives it on port 2 (from Switch 3), and consequently sends it out of port 1, back to switch 1. Hence a loop, or broadcast storm, is formed. The longer the loop occurs the more traffic loops around the network.
Legacy Spanning Tree Protocol (802.1d)
Spanning tree protocol (STP) was originally described in IEEE 802.1D and was designed to address this exact problem.
To avoid a layer 2 loop forming, some ports in the topology are blocked from sending traffic. However it is important that the most appropriate ports are blocked, for example, it is better to block a low bandwidth port than a high bandwidth port. In order to address this STP uses the concept of cost, selecting the path with the lowest cost.
Originally the cost was calculated using the formula 1 Gbps / bandwidth, however, this did not account for speeds higher than 1Gbps, and so these values have subsequently been adjusted. With Rapid Spanning Tree Protocol (RSTP) the formula used is 20 Tbps / bandwidth.
The table below shows a comparison of the values used for STP and RSTP
STP is based on an algorithm that was invented by Radia Perlman while she was working for Digital Equipment Corporation (DEC).
Bridge Protocol Data Units (BPDUs).
In order for STP to operate, switches need to share information about themselves. This is done using Bridge Protocol Data Units (BPDUs). BPDUs are sent as multicast frames in well-known multicast groups 01:80:C2:00:00:00 (or 01:00:0C:CC:CC:CD for Per VLAN STP).
Any changes in the topology (such as a link going down, or a new link added) is shared via BPDUs causing the STP algorithm to re-calculate a new loop-free topology. The default BPDU advertisement is 2 seconds
There are three types of BPDUs, as outlined below:
- Configuration BPDU, used by STP to exchange general information
- TCN BPDU (Topology Change Notification) – used for topology changes.
- TCA BPDU (Topology Change Acknowledgement) – confirming the receipt of TCN BPDUs
The mechanism used to determine a loop-free network is to elect one switch as the root of the network and determine a loop-free path to this switch. Note this is referred to as the “root-bridge”. The term “bridge” is used because historically a bridge was the precursor to a switch, and enabled two network segments to be joined together.
Electing the Root-Bridge
Only one switch can be the root-bridge in a network (or more accurately single VLAN). In order to determine this, an election is held. Each switch sends a Bridge Protocol Data Unit (BPDU) claiming to be the root-bridge.
The root bridge will be the bridge with the lowest bridge ID (keep reading for an explanation of a bridge ID).
If the switch receives a BPDU with a lower bridge ID, then it concedes and stops claiming to be the root-bridge, and instead forwards on the BPDUs. Eventually, all switches except one, will claim to be the root-bridge.
The bridge ID is the concatenation of a configurable priority number and a MAC address. For example, the default priority is set as 32768, if the system MAC address is 001E.1489.C400 then the bridge ID will be 32768.001E.1489.C400. When comparing two bridge IDs the priorities are evaluated first, and the MAC address is only compared if the priorities are equal. The switch with the lowest priority is preferred. If priorities are equal the lowest priority and lowest MAC will be chosen.
In the original Spanning Tree specification the bridge ID was calculated as follows:
However as the concept of VLANs were adopted by manufacturers, the first two bytes were split into two fields, of 4bits and 12bits respectively.
The addition of the System ID Extension allowed for a different bridge ID per STP instance (i.e. per VLAN). Note that, with this format, the priority uses the upper 4 bits of the two-byte field:
This means the priority can only be configured in increments of 4096. This can be seen when you configured priority on the command line:
switch-1(config)#spanning-tree vlan 1 priority ? <0-61440> bridge priority in increments of 4096 switch-1(config)#spanning-tree vlan 1 priority 1 % Bridge Priority must be in increments of 4096. % Allowed values are: 0 4096 8192 12288 16384 20480 24576 28672 32768 36864 40960 45056 49152 53248 57344 61440
If an engineer wants a particular switch to be the root bridge, then they should set the priority low. Note, in a stable network it is always advisable to set the root-bridge manually. This is because if the lowest mac address is used, this invariably ends up being an older piece of kit, or at the very least a device over which you may not have administrative control.
When configuring the root-bridge, Cisco has an optional parameter allowing you to set the root-bridge as either primary, or secondary. In reality, this executes an inbuilt macro that automatically sets the priority based on the existing spanning tree topology:
switch-1(config)#spanning-tree vlan 1 root ? primary Configure this switch as primary root for this spanning tree secondary Configure switch as secondary root
For example, here we can see the root bridge has the default priority. To ensure the switch stays as the root bridge we can use the spanning-tree vlan 1 root primary command.
switch-1#show spanning-tree
VLAN0001
Spanning tree enabled protocol ieee
Root ID Priority 32769
Address 001e.f6bc.bc80
This bridge is the root
Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec
switch-1(config)#spanning-tree vlan 1 root primary
switch-2#show spanning-tree
VLAN0001
Spanning tree enabled protocol ieee
Root ID Priority 24577
Address 001e.f6bc.bc80
This bridge is the root
Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec
Determining the Root Port
After the Root Bridge is elected the other switches in the spanning tree domain need to determine their “Root Port”. The Root Port is defined as the interface on the switch that has the lowest cost back to the Root Bridge. There can only be one Root Port per switch.
The Root Port is determined by the following sequence:
- Choose the port with the least cost to the Root Bridge
- If there are more than one ports meeting the condition of 1, choose the port receiving the lowest forwarding bridge ID (priority + MAC address), from the upstream switch.
- If there is more than one port meeting the condition of 1, and 2. choose the port with the lowest physical port number, from the upstream switch.
Consider the following examples:
This network uses Fast Ethernet connections, equating to a cost of 19 on each link (referencing the cost table). Switch 1 has the lowest spanning tree priority and is therefore the root-bridge. Switch 2 has two paths to the root bridge, one with cost 19 and another with cost 38. Consequently fa1 will become the Root Port.
In this scenario Switch 2 is the Root Bridge. Switch 3 has two equal cost paths back to the Root Bridge. Consequently the lowest forwarding bridge IDs are considered. As the priorities of Switch 1 and Switch 4 are the same (32768) the MAC addresses are compared. As can be seen the forwarding MAC address from switch 4 is lower, and so fa2 will become the Root Port
In this scenario Switch 1 is the Root Bridge. Switch 3 has two equal cost paths back to the Root Bridge. As both links on Switch 3 connect to the same switch (Switch 2) the forwarding bridge ID (priority and MAC address), is the same on each link. Consequently the lowest forwarding port ID is considered, and fa1 becomes the Root Port (this is because the upstream port, fa10, is numerically lower than fa20).
Determining the Designated Port
If you consider the following diagram there are two switches connected back-to-back. All the connections are in VLAN 1, and consequently in the same layer-2 segment. As the switches are connected together STP needs to block frames on two of the links in order to stop a layer 2 loop from forming.
BPDUs are multicast, which by definition means they are destination based (i.e. are sent in one direction). In this scenario ports have to be chosen (or designated) as ports that send out BPDUs.
As the loop-free topology is based on there being a loop-free path to the Root-Bridge, it makes sense that BPDUs are sent in a direction away from the Root-Bridge. Therefore all the ports on the Root-Bridge are designated ports. It also makes sense that designated ports, by definition, always forward frames because they need to forward BDPUs
By contrast, non-designated ports only receive BPDUs, as these ports are facing the Root-Bridge. It makes sense that non-designated ports should be blocked from sending BPDUs, or any other frames, in order to maintain a loop free-topology. As can be seen on Switch 2 the only port forwarding frames is the Root-Port, which is the lowest (best) path cost to the Root-Bridge.
The below diagram shows a more complex example.
Here we can see the Root-Bridge has been chosen, and all switches have determined their Root-Ports. The question is, how is the designated port determined for the layer-2 segment between Switch 2 and Switch 3?
This is determined by the same method as identified for the RP.
- Choose the port with the least cost
- If the condition of 1 results in a tie, choose the port receiving the lowest forwarding Bridge ID (priority + MAC address) from the attached switch.
- If the condition of 1 and 2 results in a tie, choose the port with the lowest physical port number, from the attached switch.
In this scenario switch 2 is seeing a cost of 19 from switch 3, and switch 3 is seeing a cost of 19 from switch 2. The priorities also match, so the decision is based on the lowest MAC address. Switch 2 receives a lower MAC address (00:1e:14:89:c4:00) than Switch 3 so switch 2 becomes the designated port.
Port Roles and States
From the above we see that STP ports have the following roles:
The Traceroute Blog 