802.1d Spanning-Tree Protocol (STP)

When Ethernet evolved from a single shared cable to networks with multiple bridges and hubs, a loop-detection and loop-prevention protocol was needed. The 802.1d protocol, developed by Radia Perlman, provided this loop protection. It did such a good job that when most networks went from bridged networks to routed networks, so the importance of Spanning Tree was almost forgotten. Because of this, Spanning Tree is probably the most used but least understood protocol in the modern internetwork. But with the huge success of Ethernet switching, Spanning Tree again becomes an important protocol to control and, more importantly, understand. We will discuss why Spanning Tree has become so important in switched Ethernet networks in upcoming sections.

Spanning Tree Operation

Spanning Tree's purpose in life is to elect a root bridge and build loop-free paths leading toward that root bridge for all bridges in the network. When Spanning Tree is converged , every bridge in the network has its bridged interfaces in one of two states: forwarding or blocking. If the port has the best-cost path to the root bridge, it is forwarding and thus is the shortest path to root. All other interfaces on the bridge are in a blocking state. STP accomplishes this by transmitting special messages called Bridge Protocol Data Units (BPDUs). BPDUs exist in two forms:

• A configuration BPDU, used for initial STP configuration

• A Topology Change Notification (TCN) BPDU used for topology changes

BPDUs are transmitted using a reserved multicast address assigned to all bridges. The BPDU is sent out all bridged LAN ports and is received by all bridges residing on the LAN. The BPDU is not forwarded off the LAN by a router. The BPDU contains the following relevant information:

• Root ID The ID of the bridge assumed to be root. Upon initialization, the bridge assumes that it is root.

• Transmitting bridge ID and port ID The BID of the bridge transmitting the BPDU, and what port the BPDU originated from.

• Cost to root The least-cost path to the root bridge from the bridge transmitting the BPDU. Upon initialization, because the bridge assumes itself to be root, it transmits a 0 for the cost to root.

The bridge ID (BID) is an 8-byte field composed from a 6-byte MAC address and a 2-byte bridge priority. The MAC address used for the BID is generated from a number of sources, depending on the hardware in use for the bridge. Routers use a physical address, whereas switches will use an address from the backplane or supervisor module. Figure 2-2 illustrates the BID. The priority value ranges from 0 to 65,535; the default value is 32,768.

Figure 2-2. The BID

The path cost is used by bridges to determine the best possible path to root. Path costs recently have been updated by the IEEE to include Gigabit and greater links. The lower the path cost is, the more preferable the path is. Table 2-6 lists the STP cost values for LAN links.

Table 2-6. STP Cost Values for LAN Links

Bandwidth	STP Cost
4 Mbps	250
10 Mbps	100
16 Mbps	62
45 Mbps	39
100 Mbps	19
155 Mbps	14
622 Mbps	6
1 Gbps [*]	4
10 Gbps	2

^[*] Before the IEEE standard was updated, the lowest value that STP could attain was 1. An STP cost of 1 was used for all links greater than or equal to 1 Gb.

STP has five primary states that it transitions through during its operation. When STP converges, it is in one of two states, forwarding or blocking. Table 2-7 lists the states of STP.

Table 2-7. Various STP States

STP State	STP Activity	User Data Being Passed
Disabled	Port is not active; it is not participating in any STP activity.	No
Broken	The 802.1q trunk is misconfigured on one end, or the default/native VLANs do not match on each end.	No
Listening	Port is sending and receiving BPDUs.	No
Learning	A loop-free bridging table is being built.	No
Forwarding	User data is being sent and received.	Yes
Blocking	User traffic is not permitted out the port.	No
PortFast [*]	Listening/learning states.	Yes

^[*] PortFast is a Cisco-specific states that allow user data traffic to be forwarded during the STP convergence process.

The ports transition from one state to another, as depicted in Figure 2-3.

Figure 2-3. The STP Transition

Let's examine each of these states in more detail.

Disabled

This state appears when a bridge is having problems processing BPDUs, when a trunk is improperly configured, or when the port is administratively down.

Listening

When a bridge port initializes or during the absence of BPDUs for a certain amount of time, STP transitions to the listening state. When STP is in this state, the port is actually blocking and no user data is sent on the link. STP follows a three-step process for convergence:

1. Elect one root bridge Upon initialization, the bridge begins sending BPDUs on all interfaces. A root bridge is chosen based on the bridge with the lowest BID. Recall that the BID is a combination of a priority and MAC address. In the event of a tie, the bridge with the lowest MAC address is chosen as root. All ports of the root bridge are put in the forwarding state.

2. Elect one root port for every nonroot bridge After a single root bridge has been elected, STP elects a single root port on each bridge that is not root. The root port is the bridge's best path to the root bridge. When a root port is elected, it is put into the forwarding state. To determine what port should be a root port, STP follows this decision process:

   1. Lowest root BID

   2. Lowest path cost to root bridge; the cumulative cost of the all paths to root

   3. Lowest sender BID

   4. Lowest port ID

   When a bridge receives a BPDU, it stores it in a bridge table for that port. As new BPDUs are received on that port, they are compared to existing BPDUs. Using the four-step process listed previously, BPDUs that are more attractive or that have lower costs are kept, and the other ones are discarded. The primary variable that influences the root port election is the cost to the root bridge. This is the cumulative path cost of all links to the root bridge.

3. Elect one designated port/designated bridge for every segment For every segment, STP elects one port that will send and receive all information from that segment to the root bridge. A root port can be thought of as the port that forwards information to the root, whereas the designated port can be thought of as the port that sends traffic away from the root. This rule applies mostly to shared-media bridges, or routers. Designated ports on back-to-back switched trunk lines do not follow this rule.

4. All remaining ports become nondesignated ports and are put in blocking mode.

Learning

Ports that remain designated or root ports for a period of 15 seconds, the default forward delay, enter the learning state. The learning state is another 15 seconds that the bridge waits while it builds its bridge table.

Forwarding and Blocking

When the bridge reaches this phase, ports that do not serve a special purpose, such as a root port or a designated port, are called nondesignated ports. All designated ports are put in a forwarding state, while all nondesignated ports are put into a blocking state. In the blocking state, a bridge does not send any configuration BPDUs, but it still listens to them. A blocking port also does not forward any user data.

Figure 2-4 illustrates a basic configuration, with the appropriate ports marked .

Figure 2-4. STP Ports and Roles

STP Timers

STP has three basic timers that regulate and age BPDUs: a hello timer, a forward delay timer, and a max age time. The timers accomplish the following for STP:

• Hello timer The default hello timer is 2 seconds. This is the amount of time between configuration BPDUs sent by the root bridge.

• Forward delay timer This timer is the default 15 seconds that the routers wait while building its bridging table. The listening and learning stages each use this single 15-second timer.

• Max age timer The max age timer is how long a BPDU is stored before it is flushed. If this timer expires before the interface receives a new BPDU, the interface transitions to the listening state. An expired max ageparameter usually is caused by a link failure. The default value is 20 seconds.

STP uses the hello timer to space BPDUs and has a keepalive mechanism. The hello timer always should prevent the MAX age value from being hit. When the max agetimer expires, it usually indicates a link failure. When this happens, the bridge re-enters the listening state. For STP to recover from a link failure, it takes approximately 50 seconds; it takes 20 seconds for the BPDU to age out, the max age; and it takes 15 seconds for the listening state and 15 seconds for the learning state.

NOTE

Two other forms of STP exist besides IEEE 802.1d. DEC and IBM are two other forms of Spanning Tree in use. The operation of all forms of STP is similar, and Cisco routers support all forms.

By now, you might be asking yourself, how could a protocol like this play a role in the modern network, with a Layer 2 protocol, 2-second hellos, and a 50-second convergence time? Because a switch is a Layer 2 device, all VLANs use Spanning Tree to build loop-free paths between switches. Cisco implements Per VLAN Spanning Tree (PVST). With PVST, there is one instance of Spanning Tree running in every VLAN. Now, take a modern network with 50 VLANs, that's 50 instances of Spanning Tree running on every trunk and every switch! Quickly, the need to understand and control this protocol becomes evident. Because this is so important, controlling Spanning Tree is one of major focuses of the section, "Configuring Catalyst Ethernet Switches."