Spanning Tree Protocol

Basic concept

Spanning Tree Protocol (STP) is a Layer 2 switching protocol, originally specified in IEEE 802.1D.  The purpose of STP is to prevent loops in networks, where redundant paths exist.  STP does this by logically disabling certain ports, so that frames are not forwarded on those links, and thus, ensuring that loops are not created.

Consider the following scenario.  SW-A and SW-B have redundant connections.  Now let’s see, how a broadcast frame can create havoc in the network.  By principle, a broadcast frame is sent out all interfaces, except the one that it was received on.  So let’s assume that SW-A received a broadcast frame from a directly connected host (not shown in the diagram).  SW-A would proceed to forward the frame out both Gi0/1 and Gi0/2.  SW-B would then receive the frame on its respective interface, and forward it out the other.  Once the frame arrived back to SW-A, SW-A would go through the same process, and the frame would loop over the links endlessly in that manner.  I’m using color coding to differentiate between the two interfaces but, essentially, it is the same frame.  The red frame indicates the frame sent out Gi0/1, and the blue frame represents the frame sent out Gi0/2 on SW-A.  The diagram visualizes how the frames would end up being forwarded on the links indefinitely.

Unlike Layer 3 packets, which rely on the TTL field as a last resort to prevent loops, Layer 2 frames have no such built-in mechanism.  That’s why a frame can bounce between switches for an unlimited number of times, as demonstrated in the previous diagram.  Therefore, there is need for a separate protocol that breaks loops but allows redundant connections to be used, in case of a connection fail.  STP, enabled on switches by default, will calculate that loop-free topology.  

Referring to the earlier scenario, STP would logically block one of the ports, preventing frames from being forwarded on that link, and effectively breaking the loop.  The resulting topology would look like this.

If the forwarding link (Gi0/1) would become unavailable, STP would automatically reconfigure the network, and activate the standby link (Gi0/2).

Building The Tree

 

The previous section quickly referred to STP building a loop-free topology.  So how exactly does STP calculate this topology?  The key is for all the switches in a Layer 2 domain to elect a root bridge (also referred to as a root switch) that becomes the focal point in the network.  STP uses deterministic rules to decide, which ports to block (to break loops) and which ports to put in the forwarding mode.  All decisions are made from the perspective of the root switch. 

Since the root switch is central in the network, its placement is very important.  An administrator can manually control the selection of the root switch, or let the switches automatically run through the process and decide amongst themselves.  However, suboptimal forwarding paths can result as a consequence of the latter.  It is recommended that the administrator plan the placement of the root switch prior to deployment, and modify the configuration accordingly. 

Switches exchange information for use of the root switch selection and subsequent configuration in the network using a special frame type called the Bridge Protocol Data Unit, or BDPU for short.  The STP calculation is based on comparing BPDUs.  A switch simply compares the parameters of a received BDPU against the information saved in its own BPDU, and makes decisions accordingly.  In STP, lower is better.

The following are three key steps that STP goes through to calculate the loop-free topology:

1. Determine the root switch.

2. Find the best path to the root switch.

3. Block redundant links.

Let’s look at each step more specifically.

Selecting The Root Switch

 

The root switch is determined by the bridge ID (BID).  The bridge ID consist of a configurable priority value and the MAC address of the switch. The switch with the lowest bridge ID is selected as the root switch. If the bridge priorities are equal (32 768 by default), the lowest MAC address is preferred.  

Let’s look at the following scenario.  Which switch will become the root switch?

 

   
For clarity, I have separated the bridge priority from the MAC address with a colon.  
 

Now I mentioned briefly that the bridge priority is 32 768 by default.  So why does it say 32 769 in the diagram?  The reason is that the switches are using what is called the system ID extension.  STP actually calculates the topology on a per-VLAN basis, so the system ID extension is used to create a unique BID for each VLAN.  Hence, there is no need to use a different MAC address to identify each STP instance. 

Therefore, the default bridge priority for VLAN 1 is actually 32 769 (default bridge priority + VLAN ID).  

Coming back to the question of which switch will be selected as the root switch.  The answer is SW-A, because it has the lowest MAC address. 

SW-A: 32769:0090.0C29.4720

SW-B: 32769:00E0.B044.B69D

SW-C: 32769:0090.2BC9.313A

The MAC addresses are simply compared from left to right, until a differentiating value is found.  

Let’s verify.  SW-A have been the selected as the root switch, and this should be indicated by the show spanning-tree command output. 

SW-A#show spanning-tree

VLAN0001

  Spanning tree enabled protocol ieee

  Root ID    Priority    32769

             Address     0090.0C29.4720

             This bridge is the root

             Hello Time  2 sec  Max Age 20 sec  Forward Delay 15 sec

  Bridge ID  Priority    32769  (priority 32768 sys-id-ext 1)

             Address     0090.0C29.4720

             Hello Time  2 sec  Max Age 20 sec  Forward Delay 15 sec

             Aging Time  20

For comparison, SW-B agrees.  

SW-B#show spanning-tree

VLAN0001

  Spanning tree enabled protocol ieee

  Root ID    Priority    32769

             Address     0090.0C29.4720

             Cost        19

             Port        1(FastEthernet0/1)

             Hello Time  2 sec  Max Age 20 sec  Forward Delay 15 sec

  Bridge ID  Priority    32769  (priority 32768 sys-id-ext 1)

             Address     00E0.B044.B69D

             Hello Time  2 sec  Max Age 20 sec  Forward Delay 15 sec

             Aging Time  20

Finding the Best Path To The Root Switch

 

After the switches have agreed on who is elected as the root switch, they start calculating the best path towards it.  There can only be one such path, and it is the one with the lowest cost.  The path cost is inversely proportional to the bandwidth of the link, i.e. the higher the bandwidth, the lower (and more preferred) the cost.

Link Speed	STP Cost
10 Mbps	100
100 Mbps	19
1 Gbps	4
10 Gbps	2

If there are two equal cost paths, the switch will prefer the path through the switch with the lower bridge ID.  

Let’s go back to the previous diagram.  Each link is 100 Mbps, i.e. STP cost 19.  Both SW-B and SW-C have a directly connected 100 Mbps link to SW-A, which is their lowest cost path to the root switch.  Fa0/1 becomes the Root Port on both switches, and it is put in the forwarding state.  The Root Port (RP) is simply the least cost path to reach the root switch, and there must be exactly one Root Port per each non-root switch. 

 

Let’s verify the Root Port selection.  

SW-B#show spanning-tree

VLAN0001

Interface        Role Sts Cost      Prio.Nbr Type

---------------- ---- --- --------- -------- ----

Fa0/1            Root FWD 19        128.1    P2p

Fa0/2            Altn BLK 19        128.2    P2p

SW-C#show spanning-tree

VLAN0001

Interface        Role Sts Cost      Prio.Nbr Type

---------------- ---- --- --------- -------- ----

Fa0/1            Root FWD 19        128.1    P2p

Fa0/2            Desg FWD 19        128.2    P2p

Ignore the Altn and Desg roles for now.

Blocking Redundant Links

Once the Root Port has been selected, the switch must decide, which remaining ports are put in the forwarding state, and which are blocked.  There must be exactly one forwarding port in each segment, called the Designated Port (DP).  

In order to become the Designated Port, the switch must send superior BPDUs on that segment.  To determine the superior BPDU, the BPDUs are compared in the following sequence, looking for the first occurrence of a lower value:

• Root Bridge ID
• Root Path Cost
• Sender Bridge ID
• Sender Port ID

Again, returning back to the topology, one end of the link between SW-B and SW-C will become the Designated Port and the other will be blocked.  Both SW-B and SW-C have a cost of 38 (19+19) to reach the root switch out their respective Fa0/2 ports.  Therefore, the Sender Bridge ID must be evaluated to break the tie.  Since the BID of SW-C is lower than that of SW-B, Fa0/2 on SW-C will become the Designated Port for that segment, and Fa0/2 will be put in the blocking mode (as indicated by the link status lights in the diagram below).

 

Let’s view how data is forwarded in the resulting STP topology.  

 

Let's add two PCs in the topology, and ping between them.  The ping is successful. 

PC>ping 192.168.1.11

Reply from 192.168.1.11: bytes=32 time=0ms TTL=128

But what path do the packets take?  Looking at the topology, you might mistakenly assume that the traffic is forwarded through the directly connected link between SW-B and SW-C, because that is the shortest path between the PCs.  Yes, from the PC’s perspective that would be correct.  However, the underlying Layer 2 topology is built from the perspective of the root switch.  Now it is more evident how the placement of the root switch dictates packet forwarding.   

Viewing the CAM table on SW-B, the MAC address of PC1 is, in fact, learned on Fa0/1. 

SW-B#show mac address-table dynamic

Vlan    Mac Address       Type        Ports

----    -----------       --------    -----

   1    0030.a383.b639    DYNAMIC      Fa0/1

In conclusion, from a data traffic forwarding perspective, the resulting Layer 2 topology will stabilize in the following form. 

 

Because of STP, from the end host communication perspective, the underlying Layer 2 topology is effectively the same as if the link between SW-B and SW-C didn't exist.  User traffic is not allowed to pass on the blocked link, but control plane messaging, like sending of BPDUs, still occurs.