The Comparison Algorithm

The whole point of spanning tree is to eliminate loops by automatically blocking ports on the network. It figures out which ports to block through the comparison algorithm. The comparison algorithm uses up to four fields to make the comparison: root identifier, root path cost, bridge identifier (transmitting bridge/switch), and the port identifier (transmitting port). From a spanning tree perspective, lower numbers are better. The order is important, with the root identifier being determined first. Figure 3-2 shows a decoded packet along with the hexadecimal version of the same packet. The spanning tree header is highlighted to show the associated hexadecimal values. Wireshark provides some clarification regarding the content of the BPDU, adding some information that is not present in the actual frame.

The information in these four fields is “compared” with information already known by the switch. The comparisons are used to make decisions regarding control of looped topologies. Spanning tree imposes a logical topology on the network by blocking ports from transmitting data frames. This means that the physical and logical topologies can differ.

Alliteration aside, the functions of the four fields follow:

Root identifier

An eight-byte field that is a combination of the root bridge priority and the root bridge MAC address. A typical bridge priority value is 32768 (8000 in hex). The virtual local area network identifier (VLAN ID) can be added to this number. Since all of the ports on a Cisco switch start out in VLAN 1, the priority changes to 32768 + 1 (32769). The hexadecimal equivalent is 8001. In a converged or steady state topology, all BPDUs will have the same root ID. From Figure 3-2, the decoded view has a root ID of 32768/1/000af4586b80. Examining the hex section, the value 8001000af4586b80 starts after the first five bytes. This difference is the merging of the priority and VLAN id.

Root path cost

A four-byte field describing the distance away from the root in terms of the number and speed of the links. In Figure 3-2, the path cost is 0, which means that we are looking a BPDU that came directly from the root bridge. The values for link speed are:

10BaseT	100
100BaseT	19
1000Baset	4

BPDUs leaving the root bridge will have a path cost of 0 regardless of the link speed. All other BPDUs will have topology-based values. For example, in a 100BaseT network, BPDUs that are two switches downstream would have a root path cost of 38, as shown in Figure 3-3.

Figure 3-3. Increased path cost

Bridge identifier

An eight-byte field that is a combination of the transmitting bridge priority and the transmitting bridge MAC address. “Transmit” is the key here because it refers to the switch sending the BPDU. Again, the typical value for the bridge priority is 32768 (8000 in hex) with an addition for any VLANs. The switch sending the current BPDU fills in its own values here. Figure 3-3 is actually a BPDU caught on the same network as the BPDU seen in Figure 3-2, just farther from the root bridge. From Figure 3-3, not only has the path cost been incremented, but the bridge ID has changed. The root ID field stays the same since all of the switches in the topology agreed on this value. The bridge ID is now 32768/1/000af45bcf40 (8001000af45bcf40 in hex) since a switch other than the root transmitted the frame. In Figure 3-2, the root ID and the bridge ID are the same, which is another indicator that the BPDU came from the root.

Port identifier

This is the last field in the comparison algorithm. These two bytes are a combination of the transmitting port priority and the port number. A common value for the port priority is 128 (80 in hex). From Figure 3-2 we can see that the value is 8002 so the BPDU came from port 2. Figure 3-3 shows a value of 8001, which means that while the two switches were using the same port priorities, the BPDUs were sent out on different ports and, based on the different bridge ID, separate switches.

The first task of the algorithm is to elect a root bridge. It is a straightforward procedure in which the bridge with the lowest priority and MAC address combination becomes the root bridge. If all switches start with the same priority (which is common) the switch with the lowest MAC address becomes the root bridge. It does not matter which switch starts the process because switches exchange BPDUs and the spanning tree topology can change based on the information received. After the election of a root bridge, the spanning tree algorithm elects designated bridges, sets port roles, and blocks ports to eliminate loops. The following sections will first cover the building blocks of the protocol and then go through the operational aspects tying all of them together.

Some Definitions

There are several terms used within the spanning tree protocol, and understanding these will help during the topology example:

Root bridge

This is the switch with the lowest numerical value for its priority and MAC address.

Designated bridge

As traffic leaving a segment of the network flows to the root switch, it may pass through (be forwarded by) another switch. This switch would be the designated bridge for that segment.

Root and designated ports

Once the topology has stabilized, all switches downstream from the root switch will have ports that are closer to the root switch and those that are farther from the root. The ports that are closer are called root ports. Ports that are farther are called designated. Another way to look at this is to say that root ports point toward the root and that traffic on its way to the root switch flows out of these ports. There is only one root port per switch. Designated ports point away from the root switch and traffic on its way to the root switch flows into these. All ports on the root switch are considered designated. Root and designated labels are called the port roles.

Spanning Tree Addressing

Spanning tree uses a specific set of addresses. In Figure 3-4, the Ethernet and Logical Link Control (LLC) headers are expanded to show the specifics. This is another view of the frame shown in Figure 3-3.

Compare the Ethernet source address in Figure 3-4 (000af45bcf41) to the bridge ID (8001000af45bcf40) seen in Figure 3-3. Removing the bridge priority leaves 000af45bcf40. Note that the Ethernet source address has simply been incremented by 1. This particular BPDU came from port 1 on the switch because of the port ID of 8001 and now this is verified by the MAC addresses because the port number is simply added to the MAC address of the switch. If this BPDU would have come from port 10, then the port ID in the spanning tree data would have been 800a and the source MAC address seen in the Ethernet frame would have been 000af45bcf4a. So the switch and its individual ports have unique MAC addresses.

Figure 3-4. BPDU addressing

The Ethernet destination MAC of 0180c2000000 is defined as the Bridge Group Address. All switches and bridges are supposed to understand and listen to this particular address. This is also why a Cisco switch can engage in spanning tree operations with a switch from another vendor. This address, along with the LLC Destination Service Access Point (DSAP) and the LLC Source Service Access Point (SSAP), are specified in IEEE 802.1D for use with the spanning tree protocol.

Port States

In an operating network, administrators are typically unaware of spanning tree port “states” because several are transitions. By the time one looks, ports that are sending/receiving traffic are already in a “forwarding” state. All ports start out in the “blocked” state. Movement between states is governed by a forwarding delay timer.

Blocked

A port in this state can receive but not transmit BPDUs. It does not transmit or forward data frames. A port in this state may actually begin forwarding depending on the STP information received (or not received) from neighboring bridges.

Listening

This is the first transitional state and is entered when spanning tree detects that the port may have to participate in data frame forwarding. The port will receive and process BPDUs but does not forward data frames. In this state, ports begin sending BPDUs.

Learning

This state is similar to listening except that the port and switch now understand the topology and are preparing to forward data frames. The port will continue to receive and process BPDUs.

Forwarding

This is the final state. A port will now forward data frames even as it continues to process any new information from incoming BPDUs.

Shutdown/Disabled

A port that has been administratively shutdown is not participating in either forwarding of data frames or spanning tree (BPDU frames).

Spanning Tree Timers

Much of the operation of spanning tree is controlled via a series of timers. The values in use on a network can be seen in the ending BPDU data, such as in Figure 3-3 and Figure 3-7.

Step 1—Switch 1 Is Powered Up

When a Cisco switch is booting, all of the port link lights are amber, meaning that they are not currently forwarding traffic. In addition, when plugging a computer into a switch port, there is usually a delay before the link light goes green. This is because switch ports typically come up in the “blocking” state. The switch must first learn about the network topology before it starts forwarding traffic. This is to avoid creating an immediate loop.

Once Switch 1 has listened for and processed potential BPDU traffic, it is free to begin forwarding traffic. During this time, the ports have been transitioning between the various states. Using the debug spanning-tree events command on a Cisco switch yields the output in Figure 3-6.

Figure 3-6. Port states

As port FastEthernet 0/3 (F0/3) comes up it transitions from blocking→listening→learning→forwarding, pausing for 15 seconds in listening and learning states.

Flowing out of ports 1 and 3 we would see the BPDUs in Figure 3-7. Note that the Ethernet source MAC addresses and the port IDs seen in the BPDU data correspond to the port transmitting the BPDU. Since Switch 1 is the only one running, it is the root switch and the transmitting switch as well. This is reflected in the BDPU root ID and bridge ID fields. The path cost for both BPDUs is 0.

Figure 3-7. Step 1 BPDUs

The result of this step can also be seen with the show spanning-tree command.

From Figure 3-8, the root ID and the bridge ID are the same. The bridge priority is listed as 32769. Port F0/1 and F0/3 are forwarding with a cost of 19 (indicating 100Mbps) and a port priority of 128. The timer values are also listed.

Figure 3-8. Step 1 show spanning tree

Step 2—Switch 2 Is Powered Up

In steady state conditions, BPDUs flow away from the root bridge. This is simply because there is no need to inform upstream switches about network conditions since the upstream switches are the original source. This is true until something in the network changes. In this case, the MAC address of Switch 2 is lower than that of Switch 1. This means that if the bridge priorities are the same (they are), Switch 2 will become the new root. The ports on Switch 2 come up blocking but listen to the BPDUs coming from Switch 1. Switch 2 notices that the value contained in the root ID field is inferior to its own bridge ID and responds with a BPDU back to Switch 1 indicating that a coup d’etat is underway. Examining the debugging output on Switch 1, we can follow its reaction.

Figure 3-9. Switch 1 debug output showing a new root switch

Capturing BPDUs between Switch 1 and Switch 2 shows that the BPDUs are now flowing from Switch 2 instead of Switch 1. The important details are that the root and bridge IDs have changed. Recall that since these are the same, this BPDU came from the root. This is supported by a root path cost of 0. Compare Figure 3-10 to Figure 3-7.

Figure 3-10. BPDU from the new root

The results can also be seen in the BPDUs transmitted from Switch 1 on the other side of the topology. In Figure 3-11 the BPDU was sent from the old root (bridge ID field) but Switch 2 is advertised as the new root in the root ID field (32768/1/000af4586b80).

Figure 3-11. BPDU from old root advertising the new root

The path cost has also increased to 19 because traffic must now cross the 100Mbps Switch 1 in order to reach the root switch. Lastly, the summary on Switch 1 displays the changes to the topology in another form.

Figure 3-12. Switch1 show spanning tree with new root

Figure 3-9 contained the debugging results of Switch 1 receiving a BPDU from Switch 2. This event also changed the information output from the show spanning-tree command, as shown in Figure 3-12. Like most network processes, examining the packet captures and the output from the network devices provides a window into the operation of the protocol.

Step 3—Switch 3 Is Powered Up

With the addition of Switch 3, the topology is complete, though not yet converged. Based on MAC address and priority, all three switches will recognize Switch 2 as the root. BPDUs will flow away from Switch 2, advertising the topology information as they go. Adding Switch 3 does not change very much in the topology except to extend it. At the farthest point from Switch 2 (top computer in Figure 3-5), a capture would reveal that the path cost to the root is now 38 and that Switch 3 is the transmitting switch. This is shown in Figure 3-13.

Figure 3-13. BPDU transmitted by Switch 3

Note that the bridge ID has changed but the root ID has not. The path cost has increased to 38. The port ID is 8003.

After developing an understanding of the structure and basic operation of spanning tree, one might realize that given this small network, spanning tree is not necessary because the topology is not looped. But what if someone came along and connected Switch 2 to Switch 3 either by accident (happens all the time) or due to an interest in redundancy? That is where the fun begins. On to step 4.

Step 4—Creation of a Loop

When a physical loop is created by connecting Switches 2 and 3, spanning tree responds by blocking one of the ports in the topology. If more loops are created, more ports would be blocked until all of the loops were eliminated. Initially, the physical and logical topologies are the same. The decision as to which port is blocked is based entirely on the information used by the comparison algorithm. But we have another question to address first: How are loops detected? During normal operations, BPDUs flow away from the root. Stated another way, a switch should only receive information about the root switch from one direction. When a switch “hears” about the root via BPDUs on more than one port, a loop has occurred.

Regardless of the spanning tree version, switches react very quickly to eliminate the loop. As switches compare BPDU information, the switch with the highest values is the loser and must block a port. Figure 3-14 is a depiction of the new topology with the loop created. We know that based on the priorities and MAC addresses, Switch 2 became the root switch. Thus, all of the BPDUs seen in this network have the same value in the first field of the comparison algorithm.

Root ID – 32768/1/000af4586b80

The next field to consider is the path cost to the root. The root switch sends out a path cost of 0 from ports 2 and 3. Clearly these are the lowest path cost values and the root will not be asked to block a port. Switches 1 and 3 cannot improve upon either the root ID or the path cost. So, it is up to Switch 1 and 3 to decide which of the downstream ports will be blocked as they fire BPDUs at each other.

Figure 3-14. Looped topology

On the link between Switch 1 and Switch 3, BPDUs would be sent out with the same root ID and, as indicated in Figure 3-14, the same path cost. In this case, the decision as to which port to block comes down to the bridge ID. With the bridge priorities the same, the higher MAC address “loses” and Switch 1 must block a port. While the physical topology will continue as drawn in Figure 3-14, the logical topology will behave like the one seen in Figure 3-15 with port 3 on Switch 1 blocked and the loop is eliminated.

Figure 3-15. Resolved topology

The output of the show spanning tree command run on Switch 1 (Figure 3-16) depicts the topology changes made. Remember that the cable is still physically connected.

Figure 3-16. Switch 1 show spanning tree with blocked port

At the top of Figure 3-16 the event is recorded and the final state is displayed at the bottom with the interface list. Root ports, designated ports, root bridges and designated bridges were defined in a previous section. Once the topology has stabilized we can now clearly see the roles of each network device and port. In Figure 3-17, the letters B, R, and D indicate blocked, root, and designated ports, respectively.

Figure 3-17. Switch and port roles

These roles can also be seen in the output from the show spanning tree command in Figure 3-12 and Figure 3-16.

Problems with Spanning Tree

Spanning tree is very good at eliminating loops. It took less than five seconds to solve the problem in our sample topology. However, when information is lost or when better pathways are created, spanning tree can be excruciatingly slow. For example, if the loop was removed from the topology by unplugging the cable between Switch 1 and 2 (reverting back to the one seen in Figure 3-5), spanning tree would not instantaneously “unblock” port 3 on Switch 1. Instead, we would have to wait for the information received by Switch 3 to age out. Switch 3 would no longer receive BPDUs from the root switch. Eventually the max age timer would expire and a topology change would begin. But how long would it take? The max age timer is 20 seconds, after which the TCN would be sent. The forwarding delay timer is 15 seconds for both the listening and learning states. So, port 3 on Switch 1 would remain blocked for 50 seconds even after the loop was gone. Any node connected to Switch 3 would be isolated for that entire time. As the network size or complexity increases, this length of time will also increase. This delay makes the original spanning tree inappropriate for a redundancy solution.

Another problem, and one of the reasons that it is good to understand the protocol, is that “automatic” spanning tree topologies can often be suboptimal in terms of forwarding. Assume that a host is connected to Switch 3 and attempts to open a web page. Based on the original blocking solution (port 3 on Switch 1), the traffic would have to flow around the entire topology as shown in Figure 3-22.

Figure 3-22. Suboptimal forwarding

In this case, the spanning tree eliminated the loop but created problems for traffic handling. In order to improve things for all nodes, the priority of Switch 1 could be changed such that it becomes the root. Recall that the bridge ID is a combination of bridge/switch priority followed by the MAC address. In Figure 3-23, the priority has been lowered to 4096 + 1 for the VLAN (1001 in hex) making Switch 1 the new root.

Figure 3-23. BPDU with priority change

The topology now resolves itself as shown in Figure 3-24. The pathway off the network for nodes connected to both Switch 2 and 3 is now straight through Switch 1. Port 3 on Switch 1 has been unblocked and port 3 on Switch 3 has been blocked.

Figure 3-24. Topology with new root based on priority

Switch to Switch: A Special Case

Regardless of topology, the whole process begins with the election of a root switch based on priority and MAC address. From there, switches with the best path cost to the root become designated bridges for the traffic traveling off of a particular network segment. In the event of a path cost tie such as that seen earlier in this chapter, the nonroot switch having the highest bridge ID (priority and MAC address) loses and must block a port. But when does the port ID field get used?

In Figure 3-25, two switches are connected directly to each other in a loop. Again, spanning tree will step in and block one of the ports. In order to determine which one, the comparison algorithm must be used:

Figure 3-25. Special case

1. Elect a root Switch. Assuming that the priorities are the same (32768 + 1), the deciding factor is the MAC address. Switch 1 becomes the root.

2. Path Cost. BPDUs flow away from the root and since both BPDUs are also leaving the root, they will have a path cost of 0.

3. Compare bridge IDs. Bridge ID is the ID of the transmitting bridge. In this case, both BPDUs will have the same value of 8001:000af4586b80 since they both come from the root.

4. Compare port IDs. This is our last chance to stop the loop. All of the other fields have had the same values in each BPDU. However, when we compare the BPDU leaving ports 1 and 2, we finally see a difference. From port 1, the port ID is 8001 (priority of 128 and a port number of 1) while the BPDU leaving port 2 on Switch 1 has a port ID of 8002 (priority of 128 and a port number of 2).

Because of the information received from Switch 1, Switch 2 now decides to block its own port 2 which terminates the loop. It is important to realize that the information contained in the BPDUs had nothing to do with Switch 2.

Portfast

Spanning tree is for bridges and switches. Hosts do not care very much about the network topology. So, when a host is connected to the network, it is not really necessary to have them wait for the transitions between the port states. In fact, devices like voice over IP phones may actually suffer because of it. This is because the phone is attempting to complete a number of transactions early in the connection process.

The command spanning-tree portfast informs the port that it does not have to go through the listening and learning port states. It is very handy when working in a dynamic environment during troubleshooting or testing. However, this is only to be used with end nodes. Accidentally connecting an interface configured for portfast with another switch can create loops. The potential hazards are advertised by Cisco when you issue the command.

Figure 3-26. Portfast warning

Uplinkfast

Uplinkfast is designed to help speed up convergence in cases where an alternate path to the root switch exists. One of the downfalls of spanning tree is that it can lead to lengthy convergence delays because of the timers, even though a failover pathway might exist. Even in the small topology discussed earlier, the convergence time was 50 seconds when the loop was removed.

Using the same topology, Switches 1 and 3 will be given the command spanning-tree uplinkfast and become members of an uplink group with their neighbors. There are a couple of changes to the BPDU; bridge priority and path cost are increased. This ensures that they will not become the root as they now have specified roles. Figure 3-27 depicts these BPDU changes.

Another look at the output from show spanning-tree reveals that the switch has a completely different view of the topology. The change noted in the BPDU is here but in addition, one will be listed as an alternate. To be complete, the blocked port was listed as alternates before (Figure 3-16) but they operated with the longer delays.

With uplinkfast configured, when the link to the root is lost, the switch immediately fails over to the secondary pathways through Switch 3. In addition, port 3 on Switch 1 starts forwarding. This takes about 1 second as opposed to nearly a minute.

Figure 3-27. Uplinkfast BPDU

Figure 3-28. Uplinkfast output

Backbonefast

The uplinkfast goal is to improve slow convergence time for a switch that has lost its connection to the root switch. But what about when a switch elsewhere in the topology loses the connection to the root? Normally it would be “every switch for itself” and max age timers would have to be exceeded before anything could be done. For example, in topology from Figure 3-17, Switch 2 is the root and Switch 1 is blocking port 3 to eliminate the loop. Uplinkfast helped with a loss of the connection between Switch 1 and 3. But if the link between Switch 2 (root) and Switch 3 were to be lost, is there anything Switch 1 can do to help?

With backbonefast, when Switch 3 loses its connection to the root, it responds by advertising itself as the root via a BPDU sent to Switch 1. However, Switch 1 is still connected to the original root and so recognizes the BPDU from Switch 3 as inferior. Switch 1 can use a special frame called a root link query (RLQ) to determine if the root is still present. If the root still lives, Switch 1 can transition blocked port 3 immediately to the listening state without waiting for the max age timer to expire. This saves about 20 seconds in convergence time over standard spanning tree.

Figure 3-29. Root link query

Wireshark does not decode the entire root link query. Recall that this is highly proprietary and not commonly deployed. However, an examination of the data field shows us the MAC addresses of the switches involved. Even more telling is the conversation between the switches. This frame is generated from a nonroot switch upon receipt of the inferior BPDU. It is followed by an RLQ response from the root switch. Once the path to the root is established, the blocked port on Switch 1 immediately transitions to the listening state.

The Operation of RSTP

Unlike 802.1D spanning tree, in which switches only send BPDUs if they have received one from upstream, RSTP switches send BPDUs every Hello time regardless. In addition, rather than wait for the max age timer of 20 seconds to expire, RSTP only waits for three Hello times (6 seconds) before aging out neighbor information. This means that there is faster failure detection and the Hello or configuration BPDU can be thought of as a “keep alive” message. RSTP also allows immediate acceptance of inferior BPDU information in the event that the path to the root switch is lost. This is similar to the behavior of backbonefast.

Ports are now identified according to their link type without the addition of vendor improvements. Edge ports are those that do not receive BPDUs and so transition to forwarding immediately without stopping in the other port states. This is similar to portfast. An edge port receiving a BPDU converts to a standard spanning tree port. Point-to-point links are those connecting switches directly together. These ports also transition quickly to the forwarding state because a loop is less likely. This is based on the port being full duplex. These link types can also be configured manually. Figure 3-33 depicts the output of the show spanning-tree command after RSTP has been enabled. Note the changes to the link types.

Figure 3-33. RSTP show spanning tree output

On point-to-point links, switches negotiate for permission to begin forwarding via proposal and agreement. Upon changes, ports go into “sync” by blocking/discarding or converting to edge ports. The negotiation elects root ports and transitions some ports directly to forwarding. For RSTP topology changes, switches start a topology change timer for all “nonedge” designated ports and the root port. Spanning tree MAC addresses are flushed for these ports. In this way, the new information is quickly reported to the other switches in the network. Convergence time is drastically reduced making RSTP part of redundancy and failover solutions.

Alternate and backup blocked ports

Alternate ports are blocked ports that still receive BPDUs from other bridges though better pathways exist. Building on the topology used earlier, I’ve added Switch 4 downstream of Switch 3. Upon loss of the “better” pathway to the root via Switch 3, the alternate port on Switch 1 will quickly transition to forwarding. This is similar to, but much faster than the idea of uplinkfast.

Figure 3-34. Alternate and backup ports

Backup ports receive BPDUs from their own switch but are the inferior port. In this case they are blocked but have no guarantee back to the root. This is also shown in Figure 3-34 on Switch 4. Looking closely at port 2 on Switch 4, we can understand why it was blocked. Comparing the BPDUs from Switch 3 to Switch 4, the BPDU leaving port 4 would be inferior. If port 2 on Switch 3 stopped sending BPDUs, port 4 on Switch 3 should take over. But Switch 4 is not guaranteed access to the root since the overall path did not change; it is still via Switch 3 and so is dependent upon connectivity elsewhere in the network. This is also one of the few cases where RSTP does not outperform 802.1D STP in terms of convergence.

Activity 1—Capture of a BPDU

Materials: A computer with an active network connection to a switch and packet capture software (Wireshark)

1. If not already connected to the switch, connected the computer NIC to the switch.

2. Once the link light turns green, start the packet capture software.

3. Examine the packets captured and find a BPDU.

4. Open the BPDU and analyze the fields used by the comparison algorithm. What are the values?

Activity 2—BPDU Address Analysis

Materials: A computer with an active network connection to a switch and packet capture software (Wireshark)

1. Using the BPDU captured in Activity 1, examine the addressing used. Look for the following:

2. Source and destination MAC addresses

3. Root bridge MAC address

4. Transmit Bridge MAC address.

5. How are these related to each other? How are they used?

Activity 3—Looping the Switch Back to Itself

Materials: Managed Switch

1. Prior to starting this activity, determine what you are going to do and try to determine what will happen with this loop.

2. Using an Ethernet cable, loop one port on the switch to another.

3. What happens to the link lights?

4. In the management interface, what is the status of the ports? Are any blocked? If so, which one and why? Be very specific in your answer.

Activity 4—Looping Switches Together

Materials: Two or three managed switches, a computer capable of capturing packets

1. This activity assumes access to a collection of switches. Two will be sufficient for the experiments.

2. As in Activity 3, try to determine what will happen when the loop is created. Be very specific about what will happen and why.

3. Connect the 2 or 3 switches in a line. Which switch is the root? What will the BPDU look like at a point farthest from the root? Consider the four fields of the comparison algorithm.

4. Connect the switches in a loop. What port will be blocked? Why? What will the changes be to the BPDUs on each segment of the network?

Activity 5—Removing the Loop

Materials: Two or three managed switches, a computer capable of capturing packets

1. Using the topology from Activity 4, remove the physical loop you created.

2. How long does it take for the blocked port to move to the forwarding state?

3. What happens if you change the switch priorities on one of the nonroot switches? How long does it take for the effect to be reflected in the network topology and BPDUs?