Calculation process of the STP algorithm

The spanning tree calculation process described in the following sections is an example of a simplified process.

The STP algorithm uses the following calculation process:

1. Initialize the network.

   Upon initialization of a device, each port generates a BPDU with the following contents:

   • The port as the designated port.

   • The device as the root bridge.

   • 0 as the root path cost.

   • The device ID as the designated bridge ID.

2. Select the root bridge.

   Initially, each STP-enabled device on the network assumes itself to be the root bridge, with its own device ID as the root bridge ID. By exchanging configuration BPDUs, the devices compare their root bridge IDs to elect the device with the smallest root bridge ID as the root bridge.

3. Root port and designated ports selection on the non-root bridges.

   Step	Description
   1	A non-root–bridge device regards the port on which it received the optimum configuration BPDU as the root port. Table 5 describes how the optimum configuration BPDU is selected.
   2	Based on the configuration BPDU and the path cost of the root port, the device calculates a designated port configuration BPDU for each of the other ports. The root bridge ID is replaced with that of the configuration BPDU of the root port. The root path cost is replaced with that of the configuration BPDU of the root port plus the path cost of the root port. The designated bridge ID is replaced with the ID of this device. The designated port ID is replaced with the ID of this port.
   3	The device compares the calculated configuration BPDU with the configuration BPDU on the port whose port role will be determined, and acts depending on the result of the comparison: If the calculated configuration BPDU is superior, the device performs the following tasks: Considers this port as the designated port. Replaces the configuration BPDU on the port with the calculated configuration BPDU. Periodically sends the calculated configuration BPDU. If the configuration BPDU on the port is superior, the device blocks this port without updating its configuration BPDU. The blocked port can receive BPDUs, but cannot send BPDUs or forward data traffic.

   When the network topology is stable, only the root port and designated ports forward user traffic. Other ports are all in the blocked state to receive BPDUs but not to forward BPDUs or user traffic.

   Table 5: Selecting the optimum configuration BPDU

   Step	Actions
   1	Upon receiving a configuration BPDU on a port, the device compares the priority of the received configuration BPDU with that of the configuration BPDU generated by the port. If the former priority is lower, the device discards the received configuration BPDU and keeps the configuration BPDU the port generated. If the former priority is higher, the device replaces the content of the configuration BPDU generated by the port with the content of the received configuration BPDU.
   2	The device compares the configuration BPDUs of all the ports and chooses the optimum configuration BPDU.

   The following are the principles of configuration BPDU comparison:

   1. The configuration BPDU with the lowest root bridge ID has the highest priority.

   2. If configuration BPDUs have the same root bridge ID, their root path costs are compared. For example, the root path cost in a configuration BPDU plus the path cost of a receiving port is S. The configuration BPDU with the smallest S value has the highest priority.

   3. If all configuration BPDUs have the same root bridge ID and S value, the following attributes are compared in sequence:

      • Designated bridge IDs.

      • Designated port IDs.

      • IDs of the receiving ports.

   The configuration BPDU that contains a smaller designated bridge ID, designated port ID, or receiving port ID is selected.

A tree-shape topology forms when the root bridge, root ports, and designated ports are selected.

Figure 21 provides an example showing how the STP algorithm works.

As shown in Figure 21, the priority values of Device A, Device B, and Device C are 0, 1, and 2, respectively. The path costs of links among the three devices are 5, 10, and 4.

1. Device state initialization.

   In Table 6, each configuration BPDU contains the following fields: root bridge ID, root path cost, designated bridge ID, and designated port ID.

   Table 6: Initial state of each device

   Device	Port name	Configuration BPDU on the port
   Device A	Port A1	{0, 0, 0, Port A1}
   	Port A2	{0, 0, 0, Port A2}
   Device B	Port B1	{1, 0, 1, Port B1}
   	Port B2	{1, 0, 1, Port B2}
   Device C	Port C1	{2, 0, 2, Port C1}
   	Port C2	{2, 0, 2, Port C2}

2. Configuration BPDUs comparison on each device.

   In Table 7, each configuration BPDU contains the following fields: root bridge ID, root path cost, designated bridge ID, and designated port ID.

   Table 7: Comparison process and result on each device

   Device	Comparison process	Configuration BPDU on ports after comparison
   Device A	Port A1 performs the following tasks: Receives the configuration BPDU of Port B1 {1, 0, 1, Port B1}. Determines that its existing configuration BPDU {0, 0, 0, Port A1} is superior to the received configuration BPDU. Discards the received one. Port A2 performs the following tasks: Receives the configuration BPDU of Port C1 {2, 0, 2, Port C1}. Determines that its existing configuration BPDU {0, 0, 0, Port A2} is superior to the received configuration BPDU. Discards the received one. Device A determines that it is both the root bridge and designated bridge in the configuration BPDUs of all its ports. It considers itself as the root bridge. It does not change the configuration BPDU of any port and starts to periodically send configuration BPDUs.	Port A1: {0, 0, 0, Port A1} Port A2: {0, 0, 0, Port A2}
   Device B	Port B1 performs the following tasks: Receives the configuration BPDU of Port A1 {0, 0, 0, Port A1}. Determines that the received configuration BPDU is superior to its existing configuration BPDU {1, 0, 1, Port B1}. Updates its configuration BPDU. Port B2 performs the following tasks: Receives the configuration BPDU of Port C2 {2, 0, 2, Port C2}. Determines that its existing configuration BPDU {1, 0, 1, Port B2} is superior to the received configuration BPDU. Discards the received BPDU.	Port B1: {0, 0, 0, Port A1} Port B2: {1, 0, 1, Port B2}
   	Device B performs the following tasks: Compares the configuration BPDUs of all its ports. Decides that the configuration BPDU of Port B1 is the optimum. Selects Port B1 as the root port with the configuration BPDU unchanged. Based on the configuration BPDU and path cost of the root port, Device B calculates a designated port configuration BPDU for Port B2 {0, 5, 1, Port B2}. Device B compares it with the existing configuration BPDU of Port B2 {1, 0, 1, Port B2}. Device B determines that the calculated one is superior, and determines that Port B2 is the designated port. It replaces the configuration BPDU on Port B2 with the calculated one, and periodically sends the calculated configuration BPDU.	Root port (Port B1): {0, 0, 0, Port A1} Designated port (Port B2): {0, 5, 1, Port B2}
   Device C	Port C1 performs the following tasks: Receives the configuration BPDU of Port A2 {0, 0, 0, Port A2}. Determines that the received configuration BPDU is superior to its existing configuration BPDU {2, 0, 2, Port C1}. Updates its configuration BPDU. Port C2 performs the following tasks: Receives the original configuration BPDU of Port B2 {1, 0, 1, Port B2}. Determines that the received configuration BPDU is superior to the existing configuration BPDU {2, 0, 2, Port C2}. Updates its configuration BPDU.	Port C1: {0, 0, 0, Port A2} Port C2: {1, 0, 1, Port B2}
   	Device C performs the following tasks: Compares the configuration BPDUs of all its ports. Decides that the configuration BPDU of Port C1 is the optimum. Selects Port C1 as the root port with the configuration BPDU unchanged. Based on the configuration BPDU and path cost of the root port, Device C calculates the configuration BPDU of Port C2 {0, 10, 2, Port C2}. Device C compares it with the existing configuration BPDU of Port C2 {1, 0, 1, Port B2}. Device C determines that the calculated configuration BPDU is superior to the existing one, selects Port C2 as the designated port, and replaces the configuration BPDU of Port C2 with the calculated one.	Root port (Port C1): {0, 0, 0, Port A2} Designated port (Port C2): {0, 10, 2, Port C2}
   	Port C2 performs the following tasks: Receives the updated configuration BPDU of Port B2 {0, 5, 1, Port B2}. Determines that the received configuration BPDU is superior to its existing configuration BPDU {0, 10, 2, Port C2}. Updates its configuration BPDU. Port C1 performs the following tasks: Receives a periodic configuration BPDU {0, 0, 0, Port A2} from Port A2. Determines that it is the same as the existing configuration BPDU. Discards the received BPDU.	Port C1: {0, 0, 0, Port A2} Port C2: {0, 5, 1, Port B2}
   	Device C determines that the root path cost of Port C1 (10) (root path cost of the received configuration BPDU (0) plus path cost of Port C1 (10)) is larger than that of Port C2 (9) (root path cost of the received configuration BPDU (5) plus path cost of Port C2 (4)). Device C determines that the configuration BPDU of Port C2 is the optimum, and selects Port C2 as the root port with the configuration BPDU unchanged. Based on the configuration BPDU and path cost of the root port, Device C performs the following tasks: Calculates a designated port configuration BPDU for Port C1 {0, 9, 2, Port C1}. Compares it with the existing configuration BPDU of Port C1 {0, 0, 0, Port A2}. Determines that the existing configuration BPDU is superior to the calculated one and blocks Port C1 with the configuration BPDU unchanged. Port C1 does not forward data until a new event triggers a spanning tree calculation process: for example, the link between Device B and Device C is down.	Blocked port (Port C1): {0, 0, 0, Port A2} Root port (Port C2): {0, 5, 1, Port B2}

After the comparison processes described in Table 7, a spanning tree with Device A as the root bridge is established, as shown in Figure 22.

The configuration BPDUs of STP are forwarded according to these guidelines:

• Upon network initiation, every device regards itself as the root bridge and generates configuration BPDUs with itself as the root. Then it sends the configuration BPDUs at a regular hello interval.

• If the root port received a configuration BPDU superior to the configuration BPDU of the port, the device performs the following tasks:

  • Increases the message age carried in the configuration BPDU.

  • Starts a timer to time the configuration BPDU.

  • Sends this configuration BPDU through the designated port.

• If a designated port receives a configuration BPDU with a lower priority than its configuration BPDU, the port immediately responds with its configuration BPDU.

• If a path fails, the root port on this path no longer receives new configuration BPDUs and the old configuration BPDUs will be discarded due to timeout. The device generates a configuration BPDU with itself as the root and sends the BPDUs and TCN BPDUs. This triggers a new spanning tree calculation process to establish a new path to restore the network connectivity.

However, the newly calculated configuration BPDU cannot be propagated throughout the network immediately. As a result, the old root ports and designated ports that have not detected the topology change continue forwarding data along the old path. If the new root ports and designated ports begin to forward data as soon as they are elected, a temporary loop might occur.

The most important timing parameters in STP calculation are forward delay, hello time, and max age.

• Forward delay

  Forward delay is the delay time for port state transition.

  A path failure can cause spanning tree recalculation to adapt the spanning tree structure to the change. However, the resulting new configuration BPDU cannot propagate throughout the network immediately. If the newly elected root ports and designated ports start to forward data immediately, a temporary loop will likely occur.

  The newly elected root ports or designated ports require twice the forward delay time before they transit to the forwarding state. This allows the new configuration BPDU to propagate throughout the network.

• Hello time

  The device sends hello packets at the hello time interval to the neighboring devices to make sure the paths are fault-free.

• Max age

  The device uses the max age to determine whether a stored configuration BPDU has expired and discards it if the max age is exceeded.