The Spanning Tree Protocol (STP) is a network protocol that builds a loop-free logical topology for Ethernet networks. The basic function of STP is to prevent bridge loops and the broadcast radiation that results from them. Spanning tree also allows a network design to include backup links providing fault tolerance if an active link fails.
As the name suggests, STP creates a spanning tree that characterizes the relationship of nodes within a network of connected layer-2 bridges, and disables those links that are not part of the spanning tree, leaving a single active path between any two network nodes. STP is based on an algorithm that was invented by Radia Perlman while she was working for Digital Equipment Corporation.
In 2001, the IEEE introduced Rapid Spanning Tree Protocol (RSTP) as 802.1w. RSTP provides significantly faster recovery in response to network changes or failures, introducing new convergence behaviors and bridge port roles to do this. RSTP was designed to be backwards-compatible with standard STP.
STP was originally standardized as IEEE 802.1D but the functionality of spanning tree (802.1D), rapid spanning tree (802.1w), and Multiple Spanning Tree Protocol (802.1s) has since been incorporated into IEEE 802.1Q-2014.Bridges and Bridged Networks
While STP is still in use today, in many modern networks its primary use is as a loop-protection mechanism rather than a fault tolerance mechanism. Link aggregation protocols such as LACP bond multiple links to provide link-level fault tolerance while simultaneously increasing overall link capacity. However, implementing switch-level redundancy requires multi-chassis link aggregation, of which only proprietary variants exist. Shortest Path Bridging combines both loop-free forwarding and link aggregation, but hasn't reached STP's or LACP's popularity yet, .
Protocol operation
The need for the Spanning Tree Protocol (STP) arose because switches in local area networks (LANs) are often interconnected using redundant links to improve resilience should one connection fail. However, this connection configuration creates a switching loop resulting in broadcast radiations and MAC table instability. If redundant links are used to connect switches, then switching loops need to be avoided.
To avoid the problems associated with redundant links in a switched LAN, STP is implemented on switches to monitor the network topology. Every link between switches, and in particular redundant links, is catalogued. The spanning-tree algorithm then blocks forwarding on redundant links by setting up one preferred link between switches in the LAN. This preferred link is used for all Ethernet frames unless it fails, in which case a non-preferred redundant link is enabled. When implemented in a network, STP designates one layer-2 switch as root bridge. All switches then select their best connection towards the root bridge for forwarding and block other redundant links. All switches constantly communicate with their neighbors in the LAN using (BPDUs).
Provided there is more than one link between two switches, the STP root bridge calculates the cost of each path based on bandwidth. STP will select the path with the lowest cost, that is, the highest bandwidth, as the preferred link. STP will enable this preferred link as the only path to be used for Ethernet frames between the two switches, and disable all other possible links by designating the switch ports that connect the preferred path as root port.
After STP-enabled switches in a LAN have elected the root bridge, all non-root bridges assign one of their ports as a root port. This is either the port that connects the switch to the root bridge, or if there are several paths, the port with the preferred path as calculated by the root bridge. Because not all switches are directly connected to the root bridge, they communicate amongst each other using STP BPDUs. Each switch adds the cost of its own path to the cost received from the neighboring switches to determine the total cost of a given path to the root bridge. Once the cost of all possible paths to the root bridge has been added up, each switch assigns a port as a root port that connects to the path with the lowest cost, or highest bandwidth, that will eventually lead to the root bridge.
Path cost +Path cost for different port speed and STP variation Data rate(link bandwidth) Original STP cost(802.1D-1998) RSTP/MSTP cost(recommended value) 250 5,000,000 100 2,000,000 62 1,250,000 19 200,000 4 20,000 3 10,000 2 2,000 N/A 200 N/A 20
The STP path cost default was originally calculated by the formula . When faster speeds became available, the default values were adjusted as otherwise speeds above would have been indistinguishable by STP. Its successor RSTP uses a similar formula with a larger numerator: . These formulas lead to the sample values in the table.
Port states All switch ports in the LAN where STP is enabled are categorized. Blocking A port that would cause a switching loop if it were active. To prevent the use of looped paths, no user data is sent or received over a blocking port. BPDU data is still received in the blocking state. A blocked port may go into forwarding mode if the other links in use fail and the spanning tree algorithm determines that the port may transition to the forwarding state. Listening The switch processes BPDUs and awaits possible new information that would cause it to return to the blocking state. It does not populate the MAC table and it does not forward frames. Learning While the port does not yet forward frames, it does learn source addresses from frames received and adds them to the MAC table. Forwarding A port in normal operation receiving and forwarding frames. The port monitors incoming BPDUs that would indicate it should return to the blocking state to prevent a loop. Disabled A network administrator has manually disabled the switch port.
When a device is first attached to a switch port, it will not immediately start to forward data. It will instead go through a number of states while it processes BPDUs and determines the topology of the network. The port attached to a host such as a computer, printer or server always goes into the forwarding state, albeit after a delay of about 30 seconds while it goes through the listening and learning states. The time spent in the listening and learning states is determined by a value known as the forward delay (default 15 seconds and set by the root bridge). If another switch is connected, the port may remain in blocking mode if it is determined that it would cause a loop in the network. Topology change notification (TCN) BPDUs are used to inform other switches of port changes. TCNs are injected into the network by a non-root switch and propagated to the root. Upon receipt of the TCN, the root switch will set the topology change flag in its normal BPDUs. This flag is propagated to all other switches and instructs them to rapidly age out their forwarding table entries.
Configuration Before configuring STP, the network topology should be carefully planned. Basic configuration requires that STP be enabled on all switches in the LAN and the same version of STP chosen on each. The administrator may determine which switch will be the root bridge and configure the switches appropriately. If the root bridge goes down, the protocol will automatically assign a new root bridge based on bridge ID. If all switches have the same bridge ID, such as the default ID, and the root bridge goes down, a tie situation arises and the protocol will assign one switch as the root bridge based on the switch's MAC addresses. Once the switches have been assigned a bridge ID and the protocol has chosen the root bridge switch, the best path to the root bridge is calculated based on port cost, path cost and port priority. Ultimately, STP calculates the path cost on the basis of the bandwidth of a link. Administrators can influence the protocol's choice of the preferred path by configuring the port cost; the lower the port cost, the more likely it is that the protocol will choose the connected link as root port for the preferred path. The selection of how other switches in the topology choose their root port, or the least cost path to the root bridge, can be influenced by the port priority. The highest priority will mean the path will ultimately be less preferred. If all ports of a switch have the same priority, the port with the lowest number is chosen to forward frames.
Root bridge and the bridge ID
The root bridge of the spanning tree is the bridge with the smallest (lowest) bridge ID. Each bridge has a configurable priority number and a MAC address; the bridge ID is the concatenation of the bridge priority and the MAC address. For example, the ID of a bridge with priority 32,768 and MAC is . The bridge priority default is 32,768 and can be configured only in multiples of 4096. When comparing two bridge IDs, the priority portions are compared first and the MAC addresses are compared only if the priorities are equal. The switch with the lowest priority of all the switches will be the root; if there is a tie, then the switch with the lowest priority and lowest MAC address will be the root. For example, if switches A (MAC = ) and B (MAC = ) both have a priority of 32,768 then switch A will be selected as the root bridge. If the network administrators would like switch B to become the root bridge, they must set its priority to be less than 32,768.
Path to the root bridge The sequence of events to determine the best received BPDU (which is the best path to the root) is:
Lowest root bridge ID (BID)Determines the root bridge. Lowest cost to the root bridgeFavors the upstream switch with the least cost to root Lowest sender bridge IDServes as a tiebreaker if multiple upstream switches have equal cost to root Lowest sender port IDServes as a tiebreaker if a switch has multiple (non-EtherChannel) links to a single upstream switch, where: Bridge ID = priority (4 bits) + locally assigned system ID extension (12 bits) + ID [MAC address] (48 bits); the default bridge priority is 32,768, and Port ID = priority (4 bits) + ID (Interface number) (12 bits); the default port priority is 128.
Tiebreakers
Root ports When multiple paths from a bridge are least-cost paths, the chosen path uses the neighbor bridge with the lower bridge ID. The root port is thus the one connecting to the bridge with the lowest bridge ID. For example, in the figures, if switch 4 were connected to network segment d instead of segment f, there would be two paths of length 2 to the root, one path going through bridge 24 and the other through bridge 92. Because there are two least-cost paths, the lower bridge ID (24) would be used as the tiebreaker in choosing which path to use. Paths When more than one bridge on a segment leads to a least-cost path to the root, the bridge with the lower bridge ID is used to forward messages to the root. The port attaching that bridge to the network segment is the designated port for the segment. In the figures, there are two least-cost paths from network segment d to the root, one going through bridge 24 and the other through bridge 92. The lower bridge ID is 24, so the tiebreaker dictates that the designated port is the port through which network segment d is connected to bridge 24. If bridge IDs were equal, then the bridge with the lowest MAC address would have the designated port. In either case, the loser sets the port as being blocked. Designated ports