STP Topology Calculation

STP Algorithm Implementation

1. Initialization

   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.

2. Root bridge election

   During network initialization, every device considers itself the root bridge and sets the root ID to its own BID. The devices then exchange configuration BPDUs and compare their root IDs to find the device with the smallest BID. The device with the smallest BID becomes the root bridge.

3. Root port and designated port selection

   Table 1 describes the process of selecting the root port and designated port.

   Table 1 Selecting the root port and designated port

   Step	Process
   1	A non-bridge device selects the port that receives the optimal configuration BPDU as the root port. Table 2 describes the process of selecting the optimal configuration BPDU.
   2	The device generates a configuration BPDU for each port and modifies the following fields according to the configuration BPDU on the root port and the 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. In Blocking state, the port only receives BPDUs, and does not forward data or send BPDUs.

   Table 2 Selecting the optimal configuration BPDU

   Step	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 port, 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.

Figure 1 STP networking and calculated topology

In Figure 1, 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.

1. Initial state of each device

   Table 3 lists the initial state of each device.

   Table 3 Initial state of each device

   Device	Port	Configuration BPDU
   DeviceA	Port A1	{0, 0, 0, Port A1}
   	Port A2	{0, 0, 0, Port A2}
   DeviceB	Port B1	{1, 0, 1, Port B1}
   	Port B2	{1, 0, 1, Port B2}
   DeviceC	Port C1	{2, 0, 2, Port C1}
   	Port C2	{2, 0, 2, Port C2}

2. Configuration BPDU comparison and result

   Table 4 describes configuration BPDU comparison process and result.

   

   In Table 4, the fields in a configuration BPDU are {root ID, root path cost, sender BID, PID}.

   Table 4 STP topology calculation process and result

   Device	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}. Therefore, 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}. Therefore, 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 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}. Therefore, 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}. Therefore, 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. It then 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. Therefore, 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 {2, 0, 2, Port C1}. Therefore, 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 {2, 0, 2, Port C2}. Therefore, 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. It then 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. Therefore, 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}. Therefore, 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. Therefore, 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. It 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 continues to send 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.