The Need for Redundancy and the Loop Problem
Redundancy improves network availability and limits the effect of one failed link or device. A single point of failure can interrupt connectivity and cause service downtime. Administrators add redundant links and devices. A common switched-network design connects switches with multiple physical links. If one cable is cut, traffic can be redirected through an alternative path. This can keep connectivity available after a single cable failure.
Redundancy improves availability, but it also introduces a Layer 2 (Data Link Layer) problem. Ethernet switches forward frames using address tables, so a physical loop in the topology can cause the same frames to be forwarded repeatedly. Without a topology-control mechanism, each switch can forward a frame again after receiving it from a neighboring link. In an uncontrolled loop, forwarding can continue indefinitely and overload switches and links. This problem is known as a switching loop or bridging loop.
Effects of a Layer 2 Loop
Ethernet frames do not have a "time-to-live" (TTL) mechanism like IP packets at Layer 3. If a frame gets caught in a loop, its header has no counter that ends forwarding. The frame can circulate through switches while consuming resources until a link is blocked, an entry expires, or the loop is interrupted. A switching loop leads to three main problems:
1. Broadcast storms
This is usually the first visible symptom. When a device sends a (for instance, an ARP request to find another device's MAC address), it enters the loop. Each switch in the loop receives the frame and floods it through the remaining eligible ports in the same broadcast domain. The frame can then return to the loop and be copied by additional switches. This duplication consumes bandwidth and switch and endpoint resources. Additional broadcasts generated by devices add to the same load, so utilization can rise quickly. The network can quickly become unusable, a condition known as a broadcast storm.
2. MAC table instability
Switches learn the location of devices by inspecting the source MAC address of incoming frames. In a loop, this learning process breaks down. Consider a PC connected to Switch A. It sends a frame. Switch B might see this frame arrive on its link from Switch A. A moment later, because of the loop, the same frame might arrive at Switch B from its link with Switch C. From Switch B's perspective, the PC's MAC address appears to be in two places at once. It will rapidly and continuously update its , a phenomenon called "MAC flapping." The entry can move between ports with each duplicate before it expires or is overwritten. The switch may then choose an incorrect output port or flood frames while the entry is unstable.
3. Duplicate frame delivery
Even a unicast frame, sent from one device to another, can be duplicated in a loop. If the destination MAC address is not yet in the switches' MAC tables, the frame will initially be flooded. The destination device might then receive the same frame multiple times from different paths. This can disrupt applications and protocols that do not handle duplicate frames.
Spanning Tree Protocol
Physical redundancy improves reliability. Layer 2 loops disrupt frame forwarding. The Spanning Tree Protocol (STP) limits this problem. STP is a (originally described in IEEE 802.1D) designed to prevent switching loops in networks with redundant paths.
STP creates a loop-free logical topology by selectively blocking ports. It uses information about the switched network to build a tree for an STP instance, so active paths do not form loops. Redundant links remain physically connected, but their ports enter a blocking or equivalent non-forwarding state. If an active link fails, STP can recalculate the tree and unblock a standby link to restore connectivity.
How STP Works: Elections and Calculations
STP builds a loop-free tree through four main stages. Switches participate by exchanging special messages called Bridge Protocol Data Units (BPDUs). BPDUs carry, among other fields, the root bridge identifier, the path cost, and the sender and port identifiers. They let each bridge compare received paths and select the preferred topology. These fields guide the switches when they select the active topology.
Step 1: Elect a Root Bridge
The first STP task is to establish a reference point for the instance. This reference is called the Root Bridge. All other decisions in the STP calculation are made from the perspective of reaching the Root Bridge. To elect one, switches compare their . The BID consists of two parts:
- Bridge Priority: A configurable priority field (typically 32768 by default in classic STP). Administrators can lower this value to influence the root selection.
- MAC Address: The 6-byte MAC address used by the switch.
The switch with the numerically lowest Bridge ID wins the election and becomes the Root Bridge.
The priority field is compared first. If the values are equal, the MAC address is the tie-breaker, with the lower address winning.
Step 2: Elect a Root Port on Each Non-Root Bridge
Every switch that is not the Root Bridge selects its best path to the root. The port leading to this path is elected as the Root Port. The selection uses the lowest total .
Example costs in the short method used by some STP implementations are:
- 10 Gbps Link Cost: 2
- 1 Gbps Link Cost: 4
- 100 Mbps Link Cost: 19
- 10 Mbps Link Cost: 100
A switch adds the link costs on each path to the Root Bridge. The port at the start of the lowest-cost path becomes the Root Port.
When paths have equal costs, additional tie-breakers include the sending switch's Bridge ID and the sending port ID, in the order defined by STP.
Step 3: Elect a Designated Port on Each Network Segment
On each network segment, such as a link between switches, one port is elected as the Designated Port. It forwards traffic onto that segment and advertises the best BPDU for the segment. The other port can remain non-forwarding. All ports on the Root Bridge are Designated Ports. On other segments, the port on the switch with the lower path cost to the Root Bridge wins, with additional tie-breakers applied when needed.
Step 4: Place All Other Ports in a Blocking State
After Root Ports and Designated Ports have been elected, remaining ports are non-designated. STP places them into a blocking state. In classic STP, a blocked port does not forward user data or learn MAC addresses, but it receives BPDUs to detect topology changes. Blocking these ports breaks the physical loop and leaves an active loop-free tree.
STP Timers and Port States
Convergence to a stable, loop-free topology is not instantaneous. The original 802.1D STP uses timers and port states; with classic values of 2 seconds for hello, 20 seconds for max age, and 15 seconds for forward delay, a topology change can cause an interruption of roughly 30-50 seconds. A port transitioning from blocking to forwarding passes through two intermediate states:
- Blocking: The port does not forward user frames to prevent a loop. It receives BPDUs and can later move to a forwarding role after a topology change.
- Listening (15 seconds): The first transition state. The switch evaluates the topology and sends and receives BPDUs, but does not forward data.
- Learning (15 seconds): The port still does not forward user data, but it begins learning MAC addresses from incoming frames to populate its table.
- Forwarding: The port is fully operational, forwarding data frames and actively participating in the network.
This convergence time ( in the transition states) limited the original STP. The max-age timer determines how long received information remains valid, so its expiry can extend the response to a failure.
Spanning Tree Extensions
Extensions of the original STP address convergence time and the use of multiple VLAN instances.
Rapid Spanning Tree Protocol, IEEE 802.1w
RSTP is defined in IEEE 802.1w and interoperates with classic STP. It introduces Alternate and Backup port roles and an active proposal-agreement mechanism between switches. Its discarding state covers the classic blocking and listening states, while learning remains a separate state. This simplifies port changes. In suitable point-to-point topologies, it can converge in less than a second after a link failure, depending on the implementation and topology.
Per-VLAN Spanning Tree Plus, PVST+
Classic STP and a single RSTP instance calculate one tree for the instance. In a VLAN network, a link can therefore remain blocked for traffic even when it could carry a particular VLAN. PVST+ is a Cisco extension that runs a separate STP instance for each VLAN. This allows for , as an administrator can configure one link as the forwarding path for VLAN 10 and another redundant link for VLAN 20, using both links.
Multiple Spanning Tree Protocol, MSTP, IEEE 802.1s
Running hundreds of STP instances on a large network can consume switch CPU resources. MSTP, developed in IEEE 802.1s and incorporated into later 802.1Q editions, lets an administrator map multiple VLANs to one instance. A separate spanning tree is calculated for each instance, reducing the number of calculations compared with one tree per VLAN while allowing different instances to use different links. Switches in one MST region must use the same VLAN-to-instance map, region name, and revision number.