STP Topology Calculation
After STP is enabled on all devices on a network, all devices initially consider themselves as the root bridge. They only transmit and receive BPDUs and do not forward user traffic, and all ports on the devices are in Listening state. The devices select the root bridge, root ports, and designated ports based on configuration BPDUs.
BPDU Exchange
Figure 14-8 shows the initial information exchange process. The four parameters in a pair of brackets represent the root ID (S1_MAC and S2_MAC are the BIDs of the two devices), root path cost, sender BID, and PID carried in configuration BPDUs. Configuration BPDUs are sent at Hello timer intervals.
STP Algorithm Implementation
Initialization
Because each bridge considers itself the root bridge, the BPDU sent from a port is set as follows:
The root ID is the BID of the local bridge, the root path cost is the accumulative path cost from the port to the local bridge, the sender BID is the BID of the local bridge, and the PID is the ID of the port that sends the BPDU.
Root bridge election
During network initialization, every device considers itself the root bridge and sets the root ID to its own BID. Then devices exchange configuration BPDUs and compare their root IDs to find the device with the smallest BID, which becomes the root bridge.
Root port and designated port selection
Table 14-7 describes the process of selecting the root port and designated port.
Table 14-7 Selecting the root port and designated portStep Process 1 A non-bridge device selects the port that receives the optimal configuration BPDU as the root port. Table 14-8 describes the process of selecting the optimal configuration BPDU. 2 The device generates a configuration BPDU for each port and modifies the following fields based on the configuration BPDU on the root port and path cost of the root port: - Replaces the root ID with the root ID in the configuration BPDU on the root port.
- Replaces the root path cost with the sum of the root path cost in the configuration BPDU on the root port and the path cost of the root port.
- Replaces the sender BID with the local BID.
- Replaces the PID with the local port ID.
3 The device compares the calculated configuration BPDU with the configuration BPDU received on the port: - If the calculated configuration BPDU is superior, the port is selected as the designated port and periodically sends the calculated configuration BPDU.
- If the port's own configuration BPDU is superior, the configuration BPDU on the port is not updated and the port is blocked. After that, the port only receives BPDUs, and does not forward data or send BPDUs.
Table 14-8 Selecting the optimal configuration BPDUStep Process 1 Each port compares the received configuration BPDU with its own configuration BPDU: - If the received configuration BPDU is inferior, the port discards the received configuration BPDU and retains its own configuration BPDU.
- If the received configuration BPDU is superior, the port replaces its own configuration BPDU with the received one.
- If the received configuration BPDU is the same, the port discards the received configuration BPDU.
2 The device compares configuration BPDUs on all the ports and selects the optimal one.
Example of STP Topology Calculation
After the root bridge, root ports, and designated ports are selected successfully, a tree topology is set up on the entire network. The following example illustrates how STP calculation is implemented.
In Figure 14-9, DeviceA, DeviceB, and DeviceC are deployed on the network, with priorities 0, 1, and 2, respectively. The path costs between DeviceA and DeviceB, DeviceA and DeviceC, and DeviceB and DeviceC are 5, 10, and 4, respectively.
Initial state of each device
Table 14-9 lists the initial state of each device.
The fields in a configuration BPDU are {root ID, root path cost, sender BID, PID}.Configuration BPDU comparison and result
Table 14-10 describes configuration BPDU comparison process and result.
Table 14-10 Topology calculation process and resultDevice Comparison Configuration BPDU After Comparison DeviceA - Port A1 receives the configuration BPDU {1, 0, 1, Port B1} from Port B1 and finds it inferior to its own configuration BPDU {0, 0, 0, Port A1}, so Port A1 discards the received configuration BPDU.
- Port A2 receives the configuration BPDU {2, 0, 2, Port C1} from Port C1 and finds it inferior to its own configuration BPDU {0, 0, 0, Port A2} superior, so Port A2 discards the received configuration BPDU.
- DeviceA finds that the root bridge and designated bridge specified in the configuration BPDUs on its ports are on itself. Therefore, DeviceA considers itself as the root bridge and periodically sends configuration BPDUs from each port without modifying the BPDUs.
- Port A1: {0, 0, 0, Port A1}
- Port A2: {0, 0, 0, Port A2}
DeviceB - Port B1 receives the configuration BPDU {0, 0, 0, Port A1} from Port A1 and finds it superior to its own configuration BPDU {1, 0, 1, Port B1}, so Port B1 updates its configuration BPDU.
- Port B2 receives the configuration BPDU {2, 0, 2, Port C2} from Port C2 and finds it inferior to its own configuration BPDU {1, 0, 1, Port B2}, so Port B2 discards the received configuration BPDU.
- Port B1: {0, 0, 0, Port A1}
- Port B2: {1, 0, 1, Port B2}
- DeviceB compares the configuration BPDU on each port and finds that Port B1 has an optimal configuration BPDU. DeviceB selects Port B1 as the root port and retains the configuration BPDU on Port B1.
- DeviceB calculates the configuration BPDU {0, 5, 1, Port B2} for Port B2 based on the configuration BPDU and path cost of the root port, and compares the calculated configuration BPDU with the original configuration BPDU {1, 0, 1, Port B2} on Port B2. The calculated configuration BPDU is superior to the original one, so DeviceB selects Port B2 as the designated port, replaces Port B2's configuration BPDU with the calculated one, and periodically sends configuration BPDUs from Port B2.
- Root port (Port B1): {0, 0, 0, Port A1}
- Designated port (Port B2): {0, 5, 1, Port B2}
DeviceC - Port C1 receives the configuration BPDU {0, 0, 0, Port A2} from Port A2 and finds it superior to its own configuration BPDU {0, 0, 0, Port C1}, so Port C1 updates its configuration BPDU.
- Port C2 receives the configuration BPDU {1, 0, 1, Port B2} from Port B2 and finds it superior to its own configuration BPDU {1, 0, 1, Port C2}, so Port C2 updates its configuration BPDU.
- Port C1: {0, 0, 0, Port A2}
- Port C2: {1, 0, 1, Port B2}
- DeviceC compares the configuration BPDU on each port and finds that the configuration BPDU on Port C1 is optimal. DeviceC selects Port C1 as the root port and retains the configuration BPDU on Port C1.
- DeviceC calculates the configuration BPDU {0, 10, 2, Port C2} for Port C2 based on the configuration BPDU and path cost of the root port, and compares the calculated configuration BPDU with the original configuration BPDU {1, 0, 1, Port B2} on Port C2. The calculated configuration BPDU is superior to the original one, so DeviceC selects Port C2 as the designated port and replaces its configuration BPDU with the calculated one.
- Root port (Port C1): {0, 0, 0, Port A2}
- Designated port (Port C2): {0, 10, 2, Port C2}
- Port C2 receives the configuration BPDU {0, 5, 1, Port B2} from Port B2 and finds it superior to its own configuration BPDU {0, 10, 2, Port C2}, so Port C2 updates its configuration BPDU.
- Port C1 receives the configuration BPDU {0, 0, 0, Port A2} from Port A2 and finds it the same as its own configuration BPDU, so Port C1 discards the received configuration BPDU.
- Port C1: {0, 0, 0, Port A2}
- Port C2: {0, 5, 1, Port B2}
- The root path cost of Port C1 is 10 (root path cost 0 in the received configuration BPDU plus the link patch cost 10), and the root path cost of Port C2 is 9 (root path cost 5 in the received configuration BPDU plus the link patch cost 4). DeviceC finds that Port C2 has a smaller root path cost and therefore considers the configuration BPDU of Port C2 superior to that of Port C1. DeviceC then selects Port C2 as the root port and retains its configuration BPDU.
- DeviceC calculates the configuration BPDU {0, 9, 2, Port C1} for Port C1 based on the configuration BPDU and path cost of the root port, and finds the calculated configuration BPDU inferior to the original configuration BPDU {0, 0, 0, Port A2} on Port C1. DeviceC blocks Port C1 and does not update its configuration BPDU. Port C1 no longer forwards data until STP recalculation is triggered, for example, when the link between DeviceB and DeviceC is down.
- Blocked port (Port C1): {0, 0, 0, Port A2}
- Root port (Port C2): {0, 5, 1, Port B2}
After the topology becomes stable, the root bridge still sends configuration BPDUs at a specific interval. If the received configuration BPDU is superior, a non-root bridge replaces the configuration BPDU on the corresponding port with the received configuration BPDU. If the received configuration BPDU is inferior or the same, a non-root bridge discards the received configuration BPDU.
STP Topology Changes
Figure 14-10 shows the packet transmission process after an STP topology change.
- When the status of the interface at point T changes, a downstream device continuously sends TCN BPDUs to the upstream device.
- The upstream device processes only the TCN BPDUs received on the designated port and discards TCN BPDUs received on other ports.
- The upstream device sets the TCA bit of the Flags field in the configuration BPDUs to 1 and returns the configuration BPDUs to instruct the downstream device to stop sending TCN BPDUs.
- The upstream device sends a copy of the TCN BPDUs toward the root bridge.
- Steps 1, 2, 3 and 4 are repeated until the root bridge receives the TCN BPDUs.
- The root bridge sets the TC and TCA bits of the Flags field in the configuration BPDUs to 1. The TC bit of 1 indicates that the root bridge notifies the downstream device of deleting MAC address entries, and the TCA bit of 1 indicates that the root bridge notifies the downstream device of stopping sending TCN BPDUs.
- TCN BPDUs are used to inform the upstream device and root bridge of topology changes.
- Configuration BPDUs with the TCA bit set to 1 are used by the upstream device to inform the downstream device that the topology changes are known and instruct the downstream device to stop sending TCN BPDUs.
- Configuration BPDUs with the TC bit set to 1 are used by the upstream device to inform the downstream device of topology changes and instruct the downstream device to delete MAC address entries. This increases network convergence speed.