The configuration message is a data link layer frame with a regular data link layer header.

The bridge that generates the frame puts its MAC address as the source address of the frame and the bridge multicast MAC address 01-80-C2-00-00-00 as the destination address of the frame. Because the configuration messages are addressed to the bridges multicast group they are processed only by the bridges and discarded by all other network stations.

When a configuration message is transmitted by a bridge on one of its ports, it is received by all the bridges located on the LAN, connected to this port but it is not forwarded by these bridges to other LANs.

The format of the configuration message is as following:

Protocol Identifier - Contains the constant value: 0

Version - Contains the constant value: 0

Message Type - Contains the constant value: 0

Flags -

1. TC - Topology Change flag - There are two filtering database timeout values: a long value and a shorter one. The long value is used to time out the filtering database entries when the network is steady. The shorter value which is equal to the forward delay (see below) is used to time out the entries upon a reconfiguration of the spanning tree as a result of topology change.

   When a configuration message with TC flag on is received on a bridge’s root port, it informs the bridge that it should use a shorter value to time out the entries of its filtering database and not the normal, longer value.

   Bridges that receive through their root port configuration messages with TC flag on, turn on this flag in the configuration messages that they send to their designated ports.

2. TCA - Topology Change Acknowledgement flag - When a configuration message with TCA flag on is received on a bridge’s root port it informs the bridge that its next bridge on the path towards the root bridge, has received the notification about the topology change and thus it should stop reporting the next bridge that a topology change has occurred. The next bridge on the path is now responsible to inform the root bridge of the topology change.

   The rest of the bits in the flags byte are unused.

Root ID – the id of a bridge which the bridge that transmits the configuration message, considers to be a root bridge plus two octet priority field.

Cost of Path to Root - the minimal cost of the path from the bridge that sending the configuration message to the bridge it believes to be the root bridge.

Bridge ID – the id of the bridge sending the configuration message. As it was said above the bridge id field consists of a 2 octets priority value followed by the 6 octets bridge’s MAC address. The bridge with the lowest id becomes the root of the spanning tree.

Port ID – the id of the port on which the sending bridge transmitted the configuration message. The id of the port consists of 1 octet field priority value followed by 1 octet port number. The priority octet is a configurable value which allows the network manager to influence on the selection of a single port among several ports of the bridge that are connected to the same LAN segment. The port number is a unique number that the bridge assigns to each one of its port.

Message Age - the time that has passed since the root bridge sent its configuration message on which the current message is based. The initial age value of a configuration message, transmitted by the root bridge is set to zero. When root’s configuration message arrives to a given bridge it generates its own configuration message with age field value set to zero and transmits the message to its designated ports. Bridges that receive configuration message, transmitted by a designated bridge for a LAN they are connected to, produce, in turn, their own configuration message, set its age to zero and forward it on their designated ports.. The age field of the best configuration message stored for each port of the bridge is incremented upon each timer tick until it reaches the value of max age.

Max Age - the time when the configuration message is no longer valid and thus it should be deleted. The recommended value of the max age is 20 sec. If the age field of a stored configuration message reaches the value of the max age, the bridge drops the stored message, reconfigures again the root bridge, the path with the minimal cost to the root bridge, and the root port through which the root can be reached with the minimal cost. Short max age will result in frequent spanning tree recalculation. Long max age, however, will increase the time it takes to news of a topology change to be spread over the network

Hello Time – the period of time between the transmissions of configuration messages by the root bridge. The recommended time is 2 sec. Shorter hello time increases the number of generated messages and thus is preferred when there is a high probability of packets loss. Longer hello time decreases the number of generated messages and thus reduces the overhead of the spanning tree algorithm.

Forward Delay – half of the amount of time a bridge should wait before it changes the state of its port from blocking to forwarding as a result of topology change.

Short forward delay is more likely to cause temporary loops until the reconfiguration of the spanning tree is over. However, long forward delay will cause longer loss of connectivity, that would continue to take place for some time even after the spanning tree has been reconfigured (see below).

There are two intermediate states listening and learning between the blocking and the forwarding state. Thus the forward delay is invoked twice: first before the transition from listening to learning state and then before the transition from learning to forwarding state. Hence, because of the fact that the recommended value for the forward delay is 15 sec the period of time until a port will be placed in the forwarding state is 30 sec.

The value of the forward delay is also used as the value of the shorter timeout of the filtering database entries, which is applied upon a reconfiguration of the spanning tree.

The values of the max age, hello time and forward delay fields must be agreed by all the bridges in the network in order to assure that the spanning tree algorithm will work correctly. Thus all the network bridges set the values of these fields according to the values of the root bridge, which they receive through the configuration messages it periodically transmits. When a bridge becomes a root bridge it starts to generate configuration messages with its configured values for this fields. Each bridge extracts these values from a configuration messages it receives on its root port and copies them into configuration messages that it transmits on its designated ports.

Spanning Tree Construction

At the beginning each bridge thinks that it is the root bridge. Therefore, it transmits on all its ports configuration messages which root id and bridge id are equal to its own id and the cost of the path to the root bridge is set to zero. Configuration messages constantly arrive on each one of the bridge’s ports. For each one of its ports the bridge saves the “best” configuration message among the messages that it has received on that port or which it itself would transmit on that port.

Given two configuration messages :
M1(root id - R1, cost of the path - C1, bridge id - B1, port id - P1) and
M2(root id - R2, cost of the path - C2, bridge id - B2, port id - P1)
a configuration message M1 is better than a configuration message M2 if one of the following conditions is true :

1. R1 < R2
2. R1 == R2 but C1 < C2
3. R1 == R2 and C1 < C2 but B1 < B2
4. R1 == R2 and C1 < C2 and B1 == B2 but P1 < P2

When a configuration message arrives on a given port of the bridge, it compares it with the configuration message that is already stored for that port. If the new configuration message is better than the existing message or the same but having a smaller age value, the stored message is replaced with the currently received message and the bridge reconfigures the root bridge, the path with the lowest cost to the root bridge and the root port that gives this path.

According to the information extracted from the best configuration messages, received on all the ports of a given bridge, it independently deduces which one of the network bridges is the root bridge and through which one of its ports the root bridge can be reached with the lowest cost.

First a bridge independently determines the id of the root bridge as the minimum of its own id and the root bridge ids extracted from any configuration message that has arrived on any of the ports of that bridge. Then it computes the distance from itself to the bridge it believes be the root bridge. If a bridge considers itself to be the root bridge, the distance from it to the root bridge is zero. If it considers other bridge than itself to be the root bridge, it selects a configuration message which contains the minimal cost to the chosen root bridge and then computes the cost of the path from itself to the root bridge by adding the cost specified in that configuration message to the cost of the path from it to its neighbor bridge, from which this configuration message was received. Afterwards the bridge chooses the root port, which is the port with the lowest id among all the ports of that bridge having the path with the lowest cost to the root bridge. Next the bridge forms it own configuration message, and for each one of its ports it decides whether it is a designated bridge on that port. The bridge is designated bridge on a given port if its configuration message is better than the best configuration message received on this port. Now the bridge selects its root port and its designated ports to be included in the spanning tree. The ports selected to be part of the spanning tree operate in a forwarding state, receiving and transmitting data packets and configuration messages from and to the network. All the other ports of the bridge remain in a blocking state. In the blocking state the bridge does not forward data packets to or from the blocked ports and does not apply the learning algorithm on traffic arrived to them. However it continues to run the spanning tree algorithm on these ports and thus continue to process the configuration messages, received from them.

Example of spanning tree construction :

Example Explenation :

1. Phase 1 :
   Every bridge thinks it is the root.
2. Phase 2 :
   B2 sends to B3 the configuration message (2,0,2).
   The message received from B2 is better than the message stored on port 1 of B3 (root id 2 < root id 3), therefore, B3 replaces its configuration message on port 1 with the message received from B2 and updates the configuration messages it transmits on port 2 and port 3.
3. Phase 3 :
   B2 sends to B1 the configuration message (2,0,2).
   B1 compares the message it received from B2 on port 2 and does not change the configuration message stored on that port because it is better than the message it received from B2 (root id 1 < root id 2).
4. Phase 4 :
   B3 sends to B4 the configuration message (2,1,3) .
   Since the message received from B3 is better than the message stored on port 2 of B4 (root id 2 < root id 4) B4 replaces its message on port 2 with the message received from B3 and updates the configuration message it transmits on port 1 to (2,2,4).
5. Phase 5 :
   B1 sends to B2 the configuration message (1,0,1).
   The message received from B1 is better than the message stored on port 1 of B2 (root id 1< root id 2), therefore, B2 replaces its message on port 1 with the message received from B1 and updates the configuration message it transmits on port 2 to (1,1,2).
6. Phase 6 :
   B1 sends to B4 the configuration message (1,0,1).
   The message received from B1 is better than the message stored on port 1 of B4 (root id 1< root id 2), therefore, B4 replaces its message on port 1 with the message received from B1 and updates the configuration message it transmits on port 2 to (1,1,4).
7. Phase 7 :
   B2 sends to B3 the configuration message (1,1,2).
   Since the message received from B2 is better than the message stored on port 1 of B3 (root id 1< root id 2) B3 replaces its message on port 1 with the message received from B2 and updates the configuration messages it transmits on port 2 and port 3 to (1,2,3).
8. Phase 8 :
   B4 sends to B3 the configuration message (1,1,4).
   The received message is better than the message stored on port 2 of B3 (cost 1< cost 2), B3 replaces its message on port 2 with the message received from B4.
   Also, B3 notes that B4 is closer to the root bridge than it is and thus B4 is the designated bridge for LAN4. Therefore B3 stops forwarding messages on port 2 and puts it into blocking state.

Handling Topological Changes

The spanning tree algorithm keeps running even after the construction of the spanning tree has been completed in order to detect and handle topological changes. The root bridge continues to transmit configuration messages with period that equals the hello time. Network bridges that receive on their ports, a configuration message from the root bridge or the designated bridge, generate in turn, their own configuration message and transmit it on their designated ports.

Nevertheless, bridges may be powered up or down. New network links can be created and existing bridges and network links may fail and come up again. All these cause the network topology to change. When the network topology changes the spanning tree must be reconfigured.

Bridges that have detected first that the topology was changed must spread this information to other bridges in the network. Once a given bridge has noticed that its port has to be moved into blocking state or out of it as a result of a spanning tree reconfiguration, it begins to transmit on its root port special topology change notification (TCN) messages indicating that a topology change has occurred. The TCN messages are being transmitted periodically, with delay that equals the hello time. When the next bridge in the path from the transmitter of the TCN messages to the root bridge, receives the TCN message it forwards it on its own root port and so on. This way the information about the topology change is being forwarded along the network until it finally arrives to the root bridge. When the root bridge receives a notification of the topology change it sets the TC flag in the configuration messages that it transmits periodically on its ports, indicating that a change in the network topology has occurred.Bridges that receive through their root port configuration messages with TC flag on, also turn on this flag in the configuration messages that they send to their designated ports.

When a bridge, receives from its designated port a TCN message, it forwards it on its root port and turns on the TCA flag in the next configuration messages that it sends to that port. The TCA flag is turned on because a bridge that has detected a change in the network topology continues to transmit periodically TCN messages, until it receives on its root port, a configuration message which TCA flag is on.

The format of the topology change configuration message is:

Protocol Identifier: contains constant value: 0

Version Id – contains constant value: 0

Message Type – contains constant value: 0x80

When a new bridge is plugged in it starts transmitting its own configuration messages. Once a configuration message of the new bridge arrives on port of another bridge, connected to the same LAN, this bridge retransmits its saved configuration message for that port. In this case the retransmitted configuration message will arrive to the new bridge with its current age value and not with zero age causing the same affect as if it was received by the new bridge when it had been originally generated

Although the spanning tree algorithm is designed to deal with dynamic topology changes, a period of time has to pass until the news of the topological change are spread over the entire network. Thus until the bridges detect that the topology has changed they will base their decisions on inconsistent data, which may result in temporary loss of connectivity or in temporary loops. For example, if a bridge has not detected yet that in the new topology one of its blocked ports should start operating in a forwarding mode it will continue not to forward data packets to or from this port causing a temporary loss of connectivity. Or if a bridge has not detected yet that in the new topology it need to block one of its forwarding ports, it will continue to transmit and receive data over this port causing temporary loops.

In order to prevent the creation of temporary loops after the topology has changed, a bridge which finds out that the state of one of its ports needed to be transferred from blocking to forwarding state doesn’t transition that port to forwarding state immediately but instead it transition the port into an intermediate state, called listening state. In the listening state the bridge transmits configuration messages on the port but it does not forward data packets to and from that port and does not learn the locations of the hosts on that port. After a period of time, that equals the forward delay the bridge transitions the port into the learning state. In the learning state the bridge starts to accept data packets on that port in order to learn the addresses of the hosts located on it, thought it still does not forward data packets on that port. When the forward delay is over the bridge can finally move the port into a forwarding state (unless the bridge has received a configuration message indicating to move this port back to blocking state) hoping that during this period all the bridges have been informed of the topology change, and managed to block all the ports that needed to be turned off in the new topology.

Example : Suppose that the link in the previous example between B4 and LAN1 fails. After the link failure, B3 waits until max age timer expires and because no configuration message was received on port 2 of B3, B3 decides that it should become the designated bridge on port 2 and adds it to the spanning tree:
First, B3 transitions port 2 into the listening state. Next it waits a period of time equals forward delay and then transitions the port into the learning state. Finally after another forward delay expires port 2 is transitioned by B3 to the forwarding state and starts to forward packets to and from LAN1.

Example of Spanning Tree Reconfiguration After a Topology Change :

The States Of A Bridge Port

Each port of a bridge can be placed on one of the following states:

1. Disabled - The disabled port is inactive and does not participate at the computation of the spanning tree. Data packets and configuration messages are not forwarded from or to the disabled port.

2. Blocking - Data packets received on blocking port are ignored by the bridge and no data packets are forwarded onto it. The bridge does not transmit its configuration messages to the blocked port, but processes configuration messages received on it from other network bridges.

3. Listening - The first intermediate state between the forwarding state and the blocking state. When a bridge decides that a port should be moved from a blocking state to a forwarding state it first places the port in the listening state. In the listening state the bridge transmits configuration messages on the port but it does not forward data packets to and from it and does not learn MAC addresses of the hosts connected to that port. The port remains in this state for a period of time that is equal to a forward delay and then it is placed in the learning state

4. Learning - The second intermediate state between the forwarding state and the blocking state. The learning state is just as the listening state except that in this state the bridge starts to learn the MAC addresses of the hosts located on the port. The port remains in this state for a period of time that equals the forward delay and then if the bridge does not decide to move it back to the blocking state, it is placed in the forwarding state.

5. Forwarding – In the forwarding state the port is working in a full functional mode. In this state, the bridge processes the packets received from that port and forwards data packets to it. The bridge transmits on this port the configuration messages it generates and receives through it configuration messages sent by other bridges.

Bridge Required Performances

If a configuration message has not been received for a long time on a blocked port of a bridge, the bridge will assume that it should be the designated bridge on that port, and will include it in the spanning tree. If the configuration messages have not been received on this port due to network congestion the addition of this port to the spanning tree will result in a creation of a loop in the topology that may radically increase the congestion, causing the spanning tree algorithm to fail.

Therefore in order that the spanning tree algorithm will be able to run correctly in a congested network the bridges should fill the following requirements:

1. The CPU of the bridge should be powerful enough, to be able to process packets as fast as they come in. Otherwise the bridge will start to drop data and configuration messages without analyzing them.
2. The bridge should have the ability to transmit a configuration message regardless the level of the network congestion. The fact that all the stations connected to a LAN have equal access rights, assures that the bridge will eventually transmit the packet at the front of its queue. Therefore the bridge should be able to distinguish between transmitting a regular data packet and a configuration message in a way that it should be able to put the configuration message, to be transmitted, at the front of the its queue.