- STP / 802.1D (Original STP)
- PVST+ (Cisco improvements of STP, adding a per VLAN feature)
- RSTP / 802.1W (Improved STP with much faster convergence)
- Rapid PVST+ (Cisco improvement of RSTP, adding per VLAN feature)
You can see that Cisco has made a lot of improvements in this field. Let’s go back to the basics and look into the reason why STP was needed in the first place.
Before we look into the need of STP, let us have a quick glance at how layer 2 operates when it has to find out the address of a particular host.
When a switch receives a packet, but it does not have the MAC address of the destination node in its table, it broadcasts the messages on all the nodes, the except it receives from. If you want to know more about it, please refer to this article on ARP.
Scenario 1: Broadcast Storm
Let us have a look at the scenario below:
Let’s say there are three switches in a network as shown above. All the switches are connected to each other. Switch B sends a broadcast, and Switch A and Switch C receive it. They do not find the address and re-broadcast the message.
Switch B receives the re-broadcasted message again from Switch A and Switch C. Thinking of that broadcast as a fresh broadcast, Switch B again broadcasts the same messages that it had already been broadcasted before. This way, a broadcast storm takes place. It continues until ports fail or Switch/Switches also fail.
If you have a look at the definition again, now you will get to know why STP was invented at first place.
Scenario 2: Duplicate packets
Consider the same network architecture as given in the scenario one above. There is a little twist here. This time Switch C is connected to the destination host that Switch B has been looking for. So now what?
Switch B will broadcast again. The broadcast reaches Switch C and Switch A as well. Switch C looks into the packet and delivers the packet to the destination host.
However, on the other parallel side, Switch A also checked its table and could not find the destination host. So, it also broadcasted the message and Switch C again received the same packet. So, it looks into the packet and delivers to the destination host again.
What is the problem here? Can you guess without reading further?
The biggest problem here is duplicate delivery and wastage of bandwidth.
Now, let us find out the solution for scenario 2. One of the best and easiest solutions would be to disconnect Switch B with Switch C so that there is no packet duplication. Because, anyway, Switch A will broadcast the packet to Switch C if the destination host is not found in the Switch A’s list. It looks something like this now:
Though we have found out the solution, we, still, are not sure if blocking the link between B to C was more beneficial or blocking the same between Switch B and A. Let’s cover all these in details now.
Which Port to block in STP?
STP follows a series of simple steps which helps STP in resolving many issues, including which port to block. But, before that, here are some of the terminology that might be of your help:
Root Bridge
Just like a “Root” in a tree structure, Root Bridge is the main Switch or Bridge in a Graph where different nodes represent all other bridges. The Root bridge controls the spanning tree topology.
Designated Bridge
The designated bridge is the switch closest to the Root bridge through which the frames will be forwarded to the Root Bridge.
Alternate Bridge
This is an alternate path to the Root Switch but is different than that of the path involving the Root Bridge.
Back up Bridge
This a back up path to a segment, though there will be another path which exists.
Disabled
Ports which are disabled.
Following are the different states that a switch port might be at any given point in time:
Forwarding port
A port that is full-fledged working.
Learning port
A port that is not forwarding the frames but it is learning the MAC addresses.
Listening Port
A port that is neither forwarding the frames nor learning the MAC addresses.
Discarding port
A port that does not forward any data.
Let’s see how does STP work and decides which Switch, Bridge, and Port has to be in what state:
- In step one, a root bridge is elected (how root Bridge is elected has been covered later in this article).
- Ports at the root bridge are placed in the forwarding state.
- Ports in the designated Bridges connecting the Root Bridge are named as Root Port.
- Remaining links on a designated Bridge choose designated ports.
- Rest of the ports are put in the blocking state.
Here is a very beautiful example from Wikipedia.
RP: Root Port
DP: Designated Port
BP: Blocked Port
Overall, the whole process might look easier, but the working algorithm behind the scene is complex. The larger the network, the longer it takes for the algorithm to put everything in its place.
Spanning Tree Protocol Operation
The following set of operations takes place.
Determining the Root Bridge
Let us think of this scenario from the beginning. Let us assume that the network is brought up from scratch. All the switches that are part of the network, when powered up, they all claim to be the root bridge.
To validate the claim, all the switches have to broadcast their Bridge ID (BID) using BPDUs (Bridge Protocol Data Units). Bridge ID has a total size of 8 Bytes out of which 2 Bytes are reserved for the Bridge Priority, and rest of the 6 Bytes are reserved for the MAC address.
Bridge ID is a combination of Bridge priority and a MAC address. Behind the scenes, the BID is a concatenated version of Bridge priority and the MAC address of the Switch/ Bridge. By default, each bridge will have the bridge ID of 32768 and each bridge ID will be in multiples of 4096.
How is the Root Bridge determined?
After each Bridge has their Bridge ID broadcasted, the Bridge with the minimum BID becomes the Root bridge. In case the Bridge priority is same in both cases, then the lowest Mac address becomes winner.
Example:
Let us say there is a tie between two bridges with the BIDs as:
Bridge A: 32768.df56.6765.7876 and,
Bridge B: 32768.df56.6765.7875
Now here is a question for you – which Bridge will become the root bridge here? If you guessed that it was Bridge B, then you were right.
Graphical Example:
Let us observe how these individual switches react to the BPDUs:
The moment all the switches are powered up, all the switches, as mentioned before, advertise that they are the root bridge by sending their Bridge ID in a hello packet.
Switch 1:
When Switch 1 receives the hello BPDUs from Switch 2 and Switch 3, it compares the Bridge ID values. In this situation, Switch 1 has the lowest BID. So, Switch 1 discards the hello packets received from the rest of the Switches and keeps on advertising itself as the Root Bridge.
Switch 2:
Here, Switch 2 receives Hello BPDUs from both of Switches, i.e., Switch 1 and Switch 3. Let’s see how Switch 2 reacts to both of the BPDUs.
When Switch 2 receives the packet from Switch 1, it compares the BID values and for sure, hello packet BPDU from Switch 1 supersedes its BID. So, Switch 2 changes its BID to that of Switch 1. When it also receives the BPDU from Switch 3, it will compare the values and will keep on dropping the BPDUs from Switch 3.
Switch 3:
Let us say Switch 3 receives the BPDU first from Switch 2. So, it changes its BID to that of Switch 2. But, when it further receives the BPDU from Switch 1, it again changes it to that of Switch 1.
At this point of time, all the switches have received each other’s BPDU and have agreed that Switch 1 has the lowest BID value and is, therefore, the right candidate to be the Root Bridge of the network.
Once the Root bridge has been decided, then Switch 2 and Switch three start organizing their respective links into Root Ports and Designated Ports as discussed at the beginning of the article.
But electing the Root Bridge is not the end of the game. This is just the beginning. And the game follows on: –
Determining the least cost route to the Root Bridge
If you are aware of the spanning tree from the graph theory, then you can relate why we are talking about calculating the least cost route to the root bridge.
In the graph theory, a spanning tree is a subset of Graph. Spanning tree allows covering all the vertices of the graph with minimum a possible number of edges. Hence, a spanning tree does not have a loop, and on top of that, it can neither be disconnected.
Spanning Tree Protocol utilizes the fact that just like the Spanning Tree from the graph theory, this network protocol can calculate the least cost path from any node to the root bridge.
So, after the Root Bridge has been decided, each node starts finding out the least cost to the Root bridge so that the whole network gets optimized.
As the first step, Root Bridge sends out the BPDUs flow to all the other Switches. The root cost is determined by summing up the costs of the segments on the path on which it took a BPDU packet to traverse from the Root Bridge to the node.
The cost of the segment is also dependent upon the link speed of a particular segment. Here is a chart of the same.
| Bandwidth | Cost |
| 10 Mbit | 100 |
| 100 Mbit | 19 |
| 1000 Mbit | 4 |
Sometimes these link costs arise fascinating situations regarding the least cost path link to the Root Bridge. Take a look at the picture below: –
Can you guess the Root Port for Switch 3 in the Picture above?
Although it might seem that Switch 3 is directly connected to the Root Bridge and that should be its path, but if we calculate the link cost it comes out that the following flow is the best flow for Switch 3 to send data to the Root Bridge.
Root Bridge -> Switch 2 -> Switch 4 -> switch 3
Can you guess why? As per the chart above, here are the costs,
Switch 3 to Root Bridge directly is 100 because of its a 10 Mbps link. But if we calculate the path as told above, it will be (19+19 +4 = 42).
Thus, in each of the non-root Bridge, the port which gets the BPDU with the least cost becomes the root port of that Bridge.
Next, all the links connected opposite to the Root port are marked as the Designated port. Also, the blocked ports are determined. Once, everything is marked and fixed; the network will have the fully optimized version of spanning tree protocol.
There might be other conditions. In case of a large network, there will be a tie in the link cost. In that case, network cost is calculated as a part of Advanced STP. Advanced STP also talks about what happens in a case of a link failure.
If you are more interested in learning about computer networks, read our complete coverage on computer networks.
