In layer 3 devices, which are typically routers, the routing protocols are responsible for making sure routing loops do not occur in the network. What is used to make sure network loops do not occur in layer 2 switched networks? That is the job of the Spanning Tree Protocol (STP).
Digital Equipment Corporation (DEC), which was purchased by Compaq before the merger with Hewlett-Packard, was the original creator of STP. Actually, Radia Perlman is credited with the main development of STP and should get the credit. The IEEE created its version of STP, called 802.1D, using the DEC version as the basis. By default, all Cisco switches run the IEEE 802.1D version of STP, which is not compatible with the DEC version.
The big difference between the two types of STP from an administrative point of view is the range of values that can be set for the priority. A bridge using DEC STP can be set as high as 255, and a switch using IEEE STP can be set as high as 65535. If the two could be used together, a bridge set as a very low priority on DEC would stand a good chance of becoming the root in an IEEE STP network.
The big picture is that STP stops network loops from occurring on your layer 2 network (bridges or switches). STP is constantly monitoring the network to find all links and to make sure loops do not occur by shutting down redundant links.
The Spanning Tree Protocol executes an algorithm called the spanning-tree algorithm. This algorithm chooses a reference point in the network and calculates the redundant paths to that reference point. After it finds all the links in the network, the spanning-tree algorithm chooses one path on which to forward frames and shuts down the other redundant links to stop any network loops from occurring in the network. It does this by electing a root bridge that will decide on the network topology.
There can be only one root bridge in any given network. The root bridge ports are called designated ports, and designated ports operate in what is called forwarding state. Forwarding state ports send and receive traffic.
If you have other switches in your network, as shown in Figure 4.4, they are called non-root bridges. However, the port that has the lowest cost to the root bridge is called a root port and sends and receives traffic. The cost is determined by the bandwidth of a link.
Figure 4.4: Spanning tree operations
Ports that forward traffic away from the root bridge are called the designated ports. Because the root can forward traffic only away from itself, all its ports are designated ports. The other port or ports on the bridge are considered nondesignated ports and will not send or receive traffic. This is called blocking mode.
This section will cover exactly how a group of switches determines the best path throughout the network and how you can modify the results. This section will cover port selection and link cost values as well as the different spanning tree states a particular port might be in.
Using spanning tree, a group of switches determines the best path from any point A to any point B. To do this, all the switches need to communicate and each switch needs to know what the network looks like. In order to know what links should be dynamically disabled, a root bridge must be selected and each switch needs to determine the type of each port.
Switches or bridges running STP exchange information with what are called Bridge Protocol Data Units (BPDUs). BPDUs are used to send configuration messages by using multicast frames. The bridge ID of each device is sent to other devices using BPDUs.
The bridge ID is used to determine the root bridge in the network and to determine the root port. The bridge ID is 8 bytes long and includes the priority and the MAC address of the device. The priority on all devices running the IEEE STP version is 32768 by default. The lower the bridge ID, the more likely a device is to become the root bridge.
To determine the root bridge, the switches in the network compare the bridge IDs they receive via the BPDUs. Whichever switch has the lowest bridge ID becomes the root bridge. If two switches or bridges have the same priority value, then the MAC address is used to determine which has the lowest ID.
For example, if two switches, A and B, both use the default priority of 32768, the MAC address will be used. If switch A's MAC address is 0000.0c00.1111 and switch B's MAC address is 0000.0c00.2222, switch A would become the root bridge.
Because each switch comes with a burned-in MAC address, if the switches use the default priority, then the one with the lowest MAC address becomes the root bridge. This means that this device will have a large number of packets passing through it. If you have a 6509 and have spent lots of money on the fabric upgrades to a 256Gb backplane, the last thing you want is for an old switch in a closet to become the root bridge. For this reason, it is strongly recommended that you lower the number on the priority for core switches. Chapter 5 gives more information on dealing with designs.
The following network analyzer output shows a BPDU broadcasted on a network. BPDUs are sent out every two seconds by default. That might seem like a lot of overhead, but remember that this is only a layer 2 frame, with no layer 3 information in the packet:
Flags: 0x80 802.3 Status: 0x00 Packet Length:64 Timestamp: 19:33:18.726314 02/28/2003 802.3 Header Destination: 01:80:c2:00:00:00 Source: 00:b0:64:75:6b:c3 LLC Length: 38 802.2 Logical Link Control (LLC) Header Dest. SAP: 0x42 802.1 Bridge Spanning Tree Source SAP: 0x42 802.1 Bridge Spanning Tree Command: 0x03 Unnumbered Information 802.1 - Bridge Spanning Tree Protocol Identifier: 0 Protocol Version ID: 0 Message Type: 0 Configuration Message Flags: %00000000 Root Priority/ID: 0x8000 / 00:b0:64:75:6b:c0 Cost Of Path To Root: 0x00000000 (0) Bridge Priority/ID: 0x8000 / 00:b0:64:75:6b:c0 Port Priority/ID: 0x80 / 0x03 Message Age: 0/256 seconds (exactly 0seconds) Maximum Age: 5120/256 seconds (exactly 20seconds) Hello Time: 512/256 seconds (exactly 2seconds) Forward Delay: 3840/256 seconds (exactly 15seconds) Extra bytes (Padding): …….. 00 00 00 00 00 00 00 00 Frame Check Sequence: 0x2e006400
Notice the cost of path to root. It is zero because this switch is actually the root bridge. We'll discuss path costs in more detail in the upcoming section, 'Selecting the Designated Port.'
The preceding network analyzer output also shows the BPDU timers, which are used to prevent bridging loops because the timers determine how long it will take the spanning tree to converge after a failure.
BPDUs are susceptible to propagation delays, which happen because of packet length, switch processing, bandwidth, and utilization problems. This can create an unstable network because temporary loops might occur in the network when BPDUs are not received on time to the remote switches in the network. The STP uses timers to force ports to wait for the correct topology information.
As you can see in the output, the hello time is exactly 2 seconds, the maximum age is exactly 20 seconds, and the forward delay is exactly 15 seconds.
When a switch first boots up, the only MAC address it knows is its own, so it advertises itself as the root. As it collects BPDUs, it will acknowledge another device as the root, if necessary. When a switch receives a BPDU advertising a device as root, with a better bridge ID than the current root is using, the switch caches this information and waits. It will wait the duration of the MaxAge timer before using the new root, allowing other switches in the network to also receive the BPDU. This reduces the possibility of loops.
After the root bridge selection process is complete, all switches must relate to the root bridge. Each switch listens to BPDUs on all active ports, and if more than one BPDU is received, the switch knows it has a redundant link to the root bridge. The switch has to determine which port will become the root port and which port will be put into blocking state.
To determine the port that will be used to communicate with the root bridge, the path cost is determined. The path cost is an accumulated total cost based on the bandwidth of the links. Table 4.2 shows the typical costs associated with the different Ethernet networks.
New IEEE Cost
Original IEEE Cost
The IEEE 802.1D specification was revised to handle the new higher-speed links, hence the different costs shown in Table 4.2.
Included in the BPDUs that a switch sends out is the cost of getting a frame to the root bridge. A neighboring device receives this information and adds the cost of the link the BPDU arrived on, and that becomes the cost for the neighboring device. For example, switch A sends out a BPDU to switch B saying that A can reach the root with a path cost of 38. The BPDU travels across a gigabit link between switch A and B. B receives the BPDU giving the cost of 38 and adds the cost of the link the BPDU arrived on, which is 4. Switch B knows that it can reach the root by sending frames through switch A with a total path cost of 42.
After the cost is determined for all links to the root bridge, the switch decides which port has the lowest cost. The lowest-cost port is put into forwarding mode, and the other ports are placed in blocking mode. If there are equal-cost paths, the port with the lowest port ID is put into the forwarding state. In the previous example, if switch B had two paths to the root, both with a cost of 42, the switch needs some other way of figuring out which single path will be used. If switch A is accessed via gigabit port 0/3 and switch C is accessed via gigabit port 0/7, switch B will send frames via switch A because it is attached to the lower numerical port number.
A designated port is one that is active and forwarding traffic, but doesn't lead to the root. Often, a designated port on one switch connects to the root port on another switch, but it doesn't have to. Because the root bridge doesn't have any ports that lead to itself and because its ports are never dynamically turned off, all its ports are labeled as designated ports.
The selection of a designated port is fairly easy. If there are two switches that have equal-cost paths to get to the root and are connected to each other, there must be some way of resolving the topological loop that exists. The switches simply examine the bridge IDs, and whichever device has the lower bridge ID is the one that will be responsible for forwarding traffic from that segment. Figure 4.4, shown earlier, illustrates this point.
The ports on a bridge or switch running the STP will go through four transitional states:
Blocking Won't forward frames; listens to BPDUs. All ports are in blocking state by default when the switch is powered on.
Listening Listens to BPDUs to make sure no loops occur on the network before passing data frames.
Learning Learns MAC addresses and builds a filter table, but does not forward frames.
Forwarding Bridge port is able to send and receive data. A port is never placed in forwarding state unless there are no redundant links or the port determines that it has the best path to the root bridge.
An administrator can put a port in disabled state, or if a failure with the port occurs, the switch puts it into disabled state.
Typically, switch ports are in either blocking or forwarding state. A forwarding port is a port that has been determined to have the lowest cost to the root bridge. However, if the network has a topology change because of a failed link, or the administrator adds a new switch to the network, the ports on a switch will be in listening and learning states.
Blocking ports are used to prevent network loops. After a switch determines the best path to the root bridge, all other ports may be placed in the blocking state. Blocked ports will still receive BPDUs.
If a switch determines that a blocked port should now be the designated port, it will go to listening state. It checks all BPDUs heard to make sure that it won't create a loop after the port goes to forwarding state.
Figure 4.5 shows the default STP timers and their operation within STP.
Figure 4.5: STP default timers
Notice the time from blocking to forwarding. Blocking to listening is 20 seconds. Listening to learning is another 15 seconds. Learning to forwarding is 15 seconds, for a total of 50 seconds. However, the switch could go to disabled if the port is administratively shut down or the port has a failure.
Convergence occurs when bridges and switches have transitioned to either the forwarding or blocking state. No data is forwarded during this time. Convergence is important in making sure that all devices have the same database.
The problem with convergence is the time it takes for all devices to update. Before data can start to be forwarded, all devices must be updated. The time it usually takes to go from blocking to forwarding state is 50 seconds. Changing the default STP timers is not recommended, but the timers can be adjusted if they need to be. The time it takes to transition a port from the listening state to the learning state or from the learning state to the forwarding state is called the forward delay.
Each device uses the timers configured on the root bridge. If the timers need to be changed, Cisco recommends that they not be changed directly. Instead, first experiment with the spantree diameter option. It will set the timers based on the size of the switched network. The larger the network, the more time is allowed for propagation, which increases the timers. The default diameter is seven switches across. Setting the diameter smaller than your actual network size increases the chance of broadcast storms.
In Figure 4.6, the three switches all have the same priority of 32768. However, notice the MAC address of each switch. By looking at the priority and MAC addresses of each switch, you should be able to determine the root bridge.
Because 2950A has the lowest MAC address and all three switches use the default priority, 2950A will be the root bridge.
To determine the root ports on switches 2950B and 2950C, you need to look at the cost of the link connecting the switches. Because the connection from both switches to the root switch is from port 0 using a 100Mbps link, that has the best cost and both switches' root port will then be port 0.
Use the bridge ID to determine the designated ports on the switches. The root bridge always has all ports as designated. However, because both 2950B and 2950C have the same cost to the root bridge and because switch 2950B has the lowest bridge ID, the designated port will be on switch 2950B. Because 2950B has been determined to have the designated port, switch 2950C will put port 1 in blocking state to stop any network loop from occurring.
Figure 4.6: Spanning tree example
The STP algorithm is often referred to after the name of its creator, Edsger W. Dijkstra, as in Dijkstra's Algorithm. It's not as descriptive as the STP algorithm, but I still like to use it.