Three Steps of Initial STP Convergence

Three Steps of Initial STP Convergence

This section considers the algorithm that the Spanning-Tree Protocol uses to initially converge on a loop-free logical topology. Although there are many facets to the Spanning-Tree Protocol, the initial convergence can be broken down into three simple steps:

1. Elect one Root Bridge

2. Elect Root Ports

3. Elect Designated Ports

When the network first starts, all of the bridges are announcing a chaotic mix of BPDU information. However, the bridges immediately begin applying the four-step decision sequence discussed in the previous section. This allows the bridges to hone in on the set of BPDUs that form a single tree spanning the entire network. A single Root Bridge is elected to act as the "center of the universe" for this network (Step 1). All of the remaining bridges calculate a set of Root Ports (Step 2) and Designated Ports (Step 3) to build a loop-free topology. You can think of the resulting topology as a wheel the Root Bridge is the hub with loop-free active paths (spokes) radiating outward. In a steady-state network, BPDUs flow from the Root Bridge outward along these loop-free spokes to every segment in the network.

After the network has converged on a loop-free active topology utilizing this three-step process, additional changes are handled using the Topology Change process. This subject is covered later in the "Topology Change Process" section.

For the discussion that follows in the rest of the chapter, refer to Figure 6-6 as the model layout of a three switches/bridges network.

Figure 6-6. Model Network Layout for Discussion of Basic STP Operations

This network consists of three bridges connected in a looped configuration. Each bridge has been assigned a fictitious MAC address that corresponds to the device's name (for example, Cat-A uses MAC address AA-AA-AA-AA-AA-AA).

Step One: Elect One Root Bridge

The switches first need to elect a single Root Bridge by looking for the bridge with the lowest Bridge ID (BID). Remember, in "STP economics", the lowest BID wins! This process of selecting the bridge with the lowest BID often goes by the exciting title of a Root War.

Tip

Many texts use the term highest priority when discussing the results of the Root War. However, notice that the bridge with the highest priority actually has the lowest value. To avoid confusion, this text always refers to the values.

As discussed in the "Bridge ID" section earlier, a BID is an 8-byte identifier that is composed of two subfields: the Bridge Priority and a MAC address from the supervisor or backplane. Referring back to Figure 6-6, you can see that Cat-A has a default BID of 32,768.AA-AA-AA-AA-AA-AA. Note the mixing of a decimal Bridge Priority with a hexadecimal MAC address. Although this might look a little strange, this convention enables you to view each section of the BID in its most common format.

Tip

Remember, the lowest BID wins.

Continuing with the example, Cat-B assumes a default BID of 32,768.BB-BB-BB-BB-BB-BB, and Cat-C uses 32,768.CC-CC-CC-CC-CC-CC. Because all three bridges are using the default Bridge Priority of 32,768, the lowest MAC address (AA-AA-AA-AA-AA-AA) serves as the tie-breaker, and Cat-A becomes the Root Bridge. Figure 6-7 illustrates this process.

Figure 6-7. The Network Must Select a Single Root Bridge

Okay, but how did the bridges learn that Cat-A had the lowest BID? This is accomplished through the exchange of BPDUs. As discussed earlier, BPDUs are special packets that bridges use to exchange topology and Spanning Tree information with each other. By default, BPDUs are sent out every two seconds. BPDUs are bridge-to-bridge traffic; they do not carry any end-user traffic (such as Doom or, if you are boring, e-mail traffic). Figure 6-8 illustrates the basic layout of a BPDU. (BPDU formats are covered in detail in the "Two Types of BPDUs" section.)

Figure 6-8. Basic BPDU Layout

For the purposes of the Root War, the discussion is only concerned with the Root BID and Sender BID fields (again, the real names come later). When a bridge generates a BPDU every 2 seconds, it places who it thinks is the Root Bridge at that instant in time in the Root BID field. The bridge always places its own BID in the Sender BID field.

Tip

Remember that the Root BID is the bridge ID of the current Root Bridge, while the Sender BID is the bridge ID of the local bridge or switch.

It turns out that a bridge is a lot like a human in that it starts out assuming that the world revolves around itself. In other words, when a bridge first boots, it always places its BID in both the Root BID and the Sender BID fields. Suppose that Cat-B boots first and starts sending out BPDUs announcing itself as the Root Bridge every 2 seconds. A few minutes later, Cat-C boots and boldly announces itself as the Root Bridge. When Cat-C's BPDU arrives at Cat-B, Cat-B discards the BPDU because it has a lower BID saved on its ports (its own BID). As soon as Cat-B transmits a BPDU, Cat-C learns that it is not quite as important as it initially assumed. At this point, Cat-C starts sending BPDUs that list Cat-B as the Root BID and Cat-C as the Sender BID. The network is now in agreement that Cat-B is the Root Bridge.

Five minutes later Cat-A boots. As you saw with Cat-B earlier, Cat-A initially assumes that it is the Root Bridge and starts advertising this fact in BPDUs. As soon as these BPDUs arrive at Cat-B and Cat-C, these switches abdicate the Root Bridge position to Cat-A. All three switches are now sending out BPDUs that announce Cat-A as the Root Bridge and themselves as the Sender BID.

Step Two: Elect Root Ports

After the bloodshed of the Root War is behind them, the switches move on to selecting Root Ports. A bridge's Root Port is the port that is closest to the Root Bridge. Every non-RootBridge must select one Root Port.

Tip

Every non-Root Bridge will select one Root Port.

As discussed earlier, bridges use the concept of cost to judge closeness. Specifically, bridges track something called Root Path Cost, the cumulative cost of all links to the Root Bridge. Figure 6-9 illustrates how this value is calculated across multiple bridges and the resulting Root Port election process.

Figure 6-9. Every Non-Root Bridge Must Select One Root Port

When Cat-A (the Root Bridge) sends out BPDUs, they contain a Root Path Cost of 0 (Step 1). When Cat-B receives these BPDUs, it adds the Path Cost of Port 1/1 to the Root Path Cost contained in the received BPDU. Assume the network is running Catalyst 5000 switch code greater than version 2.4 and that all three links in Figure 6-9 are Fast Ethernet. Cat-B receives a Root Path Cost of 0 and adds in Port 1/1's cost of 19 (Step 2). Cat-B then uses the value of 19 internally and sends BPDUs with a Root Path Cost of 19 out Port 1/2 (Step 3).

When Cat-C receives these BPDUs from Cat-B (Step 4), it increases the Root Path Cost to 38 (19+19). However, Cat-C is also receiving BPDUs from the Root Bridge on Port 1/1. These enter Cat-C:Port-1/1 with a cost of 0, and Cat-C increases the cost to 19 internally (Step 5). Cat-C has a decision to make: it must select a single Root Port, the port that is closest to the Root Bridge. Cat-C sees a Root Path Cost of 19 on Port 1/1 and 38 on Port 1/2 Cat-C:Port-1/1 becomes the Root Port (Step 6). Cat-C then begins advertising this Root Path Cost of 19 to downstream switches (Step 7).

Although not detailed in Figure 6-9, Cat-B goes through a similar set of calculations: Cat-B:Port-1/1 can reach the Root Bridge at a cost of 19, whereas Cat-B:Port-1/2 calculates a cost of 38…Port-1/1 becomes the Root Port for Cat-B. Notice that costs are incremented as BPDUs are received on a port.

Tip

Remember that STP costs are incremented as BPDUs are received on a port, not as they are sent out a port.

For example, BPDUs arrive on Cat-B:Port-1/1 with a cost of 0 and get increased to 19 "inside" Cat-B. This point is discussed in more detail in the section "Mastering the show spantree Command."

Tip

Remember the difference between Path Cost and Root Path Cost.

Path Cost is a value assigned to each port. It is added to BPDUs received on that port to calculate the Root Path Cost.

Root Path Cost is defined as the cumulative cost to the Root Bridge. In a BPDU, this is the value transmitted in the cost field. In a bridge, this value is calculated by adding the receiving port's Path Cost to the value contained in the BPDU.

Step Three: Elect Designated Ports

The loop prevention part of STP becomes obvious during the third step of initial STP convergence: electing Designated Ports. Each segment in a bridged network has oneDesignated Port. This port functions as the single bridge port that both sends and receives traffic to and from that segment and the Root Bridge. The idea is that if only one port handles traffic for each link, all of the loops have been broken! The bridge containing the Designated Port for a given segment is referred to as the Designated Bridge for that segment.

As with the Root Port selection, the Designated Ports are chosen based on cumulative Root Path Cost to the Root Bridge (see Figure 6-10).

Figure 6-10. Every Segment Elects One Designated Port Based on the Lowest Cost

To locate the Designated Ports, take a look at each segment in turn. First look at Segment 1, the link between Cat-A and Cat-B. There are 2 bridge ports on the segment: Cat-A:Port-1/1 and Cat-B:Port-1/1. Cat-A:Port-1/1 has a Root Path Cost of 0 (after all, it is the Root Bridge), whereas Cat-B:Port-1/1 has a Root Path Cost of 19 (the value 0 received in BPDUs from Cat-A plus the Path Cost of 19 assigned to Cat-B:Port1/1). Because Cat-A:Port-1/1 has the lower Root Path Cost, it becomes the Designated Port for this link.

For Segment 2 (Cat-A to Cat-C link), a similar election takes place. Cat-A:Port-1/2 has a Root Path Cost of 0, whereas Cat-C:Port-1/1 has a Root Path Cost of 19. Cat-A:Port-1/2 has the lower cost and becomes the Designated Port. Notice that every active port on the Root Bridge becomes a Designated Port. The only exception to this rule is a Layer 1 physical loop to the Root Bridge (for example, you connected two ports on the Root Bridge to the same hub or you connected the two ports together with a crossover cable).

Now look at Segment 3 (Cat-B to Cat-C): both Cat-B:Port-1/2 and Cat-C:Port-1/2 have a Root Path Cost of 19. There is a tie! When faced with a tie (or any other determination), STP always uses the four-step decision sequence discussed earlier in the section "Four-Step STP Decision Sequence." Recall that the four steps are as follows:

1. Lowest Root BID

2. Lowest Path Cost to Root Bridge

3. Lowest Sender BID

4. Lowest Port ID

In the example shown in Figure 6-10, all three bridges are in agreement that Cat-A is the Root Bridge, causing Root Path Cost to be evaluated next. However, as pointed out in the previous paragraph, both Cat-B and Cat-C have a cost of 19. This causes BID, the third decision criteria, to be the deciding factor. Because Cat-B's BID (32,768.BB-BB-BB-BB-BB-BB) is lower than Cat-C's BID (32,768.CC-CC-CC-CC-CC-CC), Cat-B:Port-1/2 becomes the Designated Port for Segment 3. Cat-C:Port-1/2 therefore becomes a non-Designated Port.

Initial STP Convergence Review

Before continuing, this section recaps the points already discussed. Recall that switches go through three steps for their initial convergence:

1. Elect one Root Bridge

2. Elect one Root Port per non-Root Bridge

3. Elect one Designated Port per segment

First, the bridged network elects a single Root Bridge. Second, every non-Root Bridge elects a single Root Port, the port that is the closest to the Root Bridge. Third, the bridges elect a single Designated Port for every segment.

For example, in a network that contains 15 switches and 146 segments (remember every switch port is a unique segment), the number of STP components that exist corresponds to the values documented in Table 6-2.

Table 6-2. STP Components in a 15 Switch and 146 Segment Network

STP Component

Number

Root Bridge

1

Root Port

14

Designated Ports

146

Also, all STP decisions are based on a predetermined sequence as follows:

1. Lowest Root BID

2. Lowest Path Cost to Root Bridge

3. Lowest Sender BID

4. Lowest Port ID

Every BPDU received on a port is compared against the other BPDUs received (as well as the BPDU that is sent on that port). Only the best BPDU (or superior BPDU) is saved. Notice in all cases that "best" is determined by the lowest value (for example, the lowest BID becomes the Root Bridge, and the lowest cost is used to elect the Root and Designated Ports). A port stops transmitting BPDUs if it hears a better BPDU that it would transmit itself.