Spanning Tree Protocol (STP)

Where two bridges are used to interconnect the same two computer network segments, spanning tree is a protocol that allows the bridges to exchange information so that only one of them will handle a given message that is being sent between two computers within the network. The spanning tree protocol prevents the condition known as a bridge loop.

In a local area network (LAN) such as an Ethernet or Token Ring network, computers compete for the ability to use the shared telecommunications path at any given time. If too many computers try to send at the same time, the overall performance of the network can be affected, even to the point of bringing all traffic to a near halt. To make this possibility less likely, the local area network can be divided into two or more network segments with a device called a bridge connecting any two segments. Each message (called a frame) goes through the bridge before being sent to the intended destination. The bridge determines whether the message is for a destination within the same segment as the sender's or for the other segment, and forwards it accordingly. A bridge does nothing more than look at the destination address and, based on its understanding of the two segments (which computers are on which segments), forwards it on the right path (which means to the correct outgoing port). The benefit of network segmentation (and the bridge) is that the amount of competition for use of the network path is reduced by half (assuming each segment has the same number of computers) and the possibility of the network coming to a halt is significantly reduced.

Each bridge learns which computers are on which segment by sending any first-time message to both segments (this is known as flooding) and then noticing and recording the segment from which a computer replied to the message. Gradually, the bridge builds a picture for itself of which computers are in which segments. When a second and subsequent messages are sent, the bridge can use its table to determine which segment to forward it to. The approach of allowing the bridge to learn the network through experience is known as transparent bridging (meaning that bridging does not require setup by an administrator).

In order to build into a network, it is typical to add a second bridge between two segments as a backup in case the primary bridge fails. Both bridges need to continually understand the topography of the network, even though only one is actually forwarding messages. And both bridges need to have some way to understand which bridge is the primary one. To do this, they have a separate path connection just between the bridges in which they exchange information, using bridge protocol data units (BPDUs).

The program in each bridge that allows it to determine how to use the protocol is known as the spanning tree algorithm. The algorithm is specifically constructed to avoid bridge loops (multiple paths linking one segment to another, resulting in an infinite loop situation). The algorithm is responsible for a bridge using only the most efficient path when faced with multiple paths. If the best path fails, the algorithm recalculates the network and finds the next best route.

The spanning tree algorithm determines the network (which computer hosts are in which segment) and this data is exchanged using Bridge Protocol Data Units (BPDUs). It is broken down into two steps:

Step 1: The algorithm determines the best message a bridge can send by evaluating the configuration messages it has received and choosing the best option.

Step 2: Once it selects the top message for a particular bridge to send, it compares its choice with possible configuration messages from the non-root-connections it has. If the best option from step 1 isn't better than what it receives from the non-root-connections, it will prune that port.

The spanning tree protocol and algorithm were developed by a committe of the IEEE. Currently, the IEEE is attempting to institute enhancements to the spanning tree algorithm that will reduce network recovery time. The goal is to go from 30 to 60 seconds after a failure or change in link status to less than 10 seconds. The enhancement, called Rapid Reconfiguration or Fast Spanning Tree, would cut down on data loss and session timeouts when large, Ethernet networks recover after a topology change or a device failure