Spanning Tree Protocol

Introduction

Spanning Tree Protocol (STP) is a Layer 2 network protocol that prevents loops in Ethernet networks with redundant paths. It creates a loop-free logical topology by selectively blocking redundant links and dynamically reconfiguring network paths to maintain connectivity and fault tolerance.

"Spanning Tree Protocol ensures reliability and stability in bridged Ethernet networks by logically removing loops without disabling physical links." -- Radia Perlman

Background and Need

Loop Formation in Ethernet Networks

Ethernet frames lack a time-to-live field, causing broadcast frames to loop indefinitely in redundant topologies, resulting in broadcast storms and MAC table instability.

Redundancy vs. Loops

Redundant links improve fault tolerance but introduce loops. STP balances redundancy with loop prevention by dynamically disabling some links.

Historical Context

Developed by Radia Perlman at Digital Equipment Corporation in 1985, standardized as IEEE 802.1D in 1990 to address Ethernet loop problems.

Protocol Overview

Purpose

Eliminate Layer 2 loops by creating a spanning tree from network topology, allowing only one active path between any two nodes.

Functionality

Elects a root bridge, calculates shortest path costs, blocks redundant paths, and reacts to topology changes by recalculating the tree.

Standardization

Defined by IEEE 802.1D, interoperable across vendors, foundational for subsequent protocols like Rapid STP and Multiple STP.

Key Terms and Roles

Root Bridge

Central reference point with lowest Bridge ID. All path calculations are relative to root.

Designated Bridge and Port

Bridge and port responsible for forwarding frames towards root on a network segment.

Blocked Port

Port placed in blocking state to prevent loops, does not forward frames except BPDUs.

Non-Designated Port

Port that is neither root nor designated, typically in blocking state.

Path Cost

Metric representing the cost to reach the root bridge via a port, based on link speed.

Operation Phases

Initialization

All bridges consider themselves root and send BPDUs with own Bridge ID.

Root Bridge Election

Bridge with lowest Bridge ID becomes root, others update their root info accordingly.

Path Selection

Each bridge determines shortest path to root using path cost metrics.

Port Role Assignment

Ports assigned roles: root, designated, or blocked to enforce loop-free topology.

Topology Changes

Detected via BPDUs; triggers recalculation of spanning tree to maintain loop-free state.

Bridge ID and Election Process

Bridge ID Components

Consists of 2-byte priority value and 6-byte MAC address.

Priority Value

Default 32768, adjustable in increments of 4096 to influence election.

Election Algorithm

Lowest Bridge ID (priority + MAC) elected root. Ties resolved by MAC address.

Impact on Network

Root bridge location affects overall topology and path costs.

Example Calculation

Bridge ID = Priority (2 bytes) + MAC Address (6 bytes)Example:Priority = 32768MAC = 00:11:22:33:44:55Bridge ID = 0x8000 + 0x001122334455

Port States and Transitions

Blocking State

Prevents frame forwarding; listens for BPDUs.

Listening State

Prepares to forward frames; processes BPDUs to avoid loops.

Learning State

Populates MAC address table; does not forward frames yet.

Forwarding State

Forwards frames and processes BPDUs.

Disabled State

Manually or administratively shut down; no frame or BPDU processing.

State Transition Diagram

Blocking → Listening → Learning → ForwardingForwarding → Blocking (on topology change)Any State → Disabled (manual)

Path Cost Calculation

Definition

Numerical value representing link speed; used to select least-cost path to root.

Cost Values

Lower cost for higher speed links: e.g., 10 Mbps = 100, 100 Mbps = 19, 1 Gbps = 4.

Calculation Method

Sum of port costs along path to root bridge.

Path Selection

Bridge selects path with lowest total cost; used in port role assignment.

Table of Default IEEE 802.1D Path Costs

BPDU Frames

Definition

Bridge Protocol Data Units (BPDUs) are messages exchanged between switches to share spanning tree information.

Types of BPDUs

Configuration BPDUs (for topology info), Topology Change Notification BPDUs (for updates).

BPDU Fields

Root ID, Bridge ID, Path Cost, Port ID, Message Age, Max Age, Hello Time, Forward Delay.

Transmission

Sent every Hello Time interval on all designated ports.

Role in Topology Changes

Trigger recalculation and port state changes to preserve loop-free topology.

Timers and Parameters

Hello Time

Interval between BPDU transmissions; default 2 seconds.

Max Age

Maximum BPDU lifetime; default 20 seconds.

Forward Delay

Time spent in listening and learning states; default 15 seconds each.

Message Age

Age of BPDU since root generation.

Parameter Summary Table

Advantages and Limitations

Advantages

Prevents Layer 2 loops, supports redundancy, automatic topology reconfiguration, interoperable standard.

Limitations

Slow convergence (30-50 seconds), inefficient bandwidth use due to blocked ports, scalability issues in large networks.

Impact on Network Performance

Convergence delay can disrupt traffic; inefficient bandwidth utilization reduces throughput.

Security Considerations

Vulnerable to BPDU spoofing; requires configuration safeguards.

Alternatives

Rapid Spanning Tree Protocol (RSTP), Multiple Spanning Tree Protocol (MSTP), Shortest Path Bridging (SPB).

Variants and Extensions

Rapid Spanning Tree Protocol (RSTP)

IEEE 802.1w; faster convergence via improved port states and handshake mechanisms.

Multiple Spanning Tree Protocol (MSTP)

IEEE 802.1s; supports multiple spanning trees for VLAN-aware networks, improves scalability.

Per-VLAN Spanning Tree (PVST)

Cisco proprietary; runs independent spanning tree per VLAN for load balancing.

Shortcomings Addressed

Reduced convergence time, better bandwidth utilization, VLAN support, enhanced scalability.

Future Directions

Integration with Software Defined Networking (SDN) and enhanced loop prevention algorithms.

References

• Perlman, R., "An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN," ACM SIGCOMM Computer Communication Review, vol. 15, no. 4, 1985, pp. 44-53.
• IEEE Standards Association, "IEEE Standard for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges," IEEE Std 802.1D-2004, 2004, pp. 1-279.
• Medhi, D., & Ramasamy, K., "Network Routing: Algorithms, Protocols, and Architectures," Morgan Kaufmann, 2017, pp. 185-210.
• Seifert, R., "The All-New Switch Book: The Complete Guide to LAN Switching Technology," Wiley, 2006, pp. 223-258.
• Fitzgerald, J., Dennis, A., "Business Data Communications and Networking," 13th Edition, Wiley, 2019, pp. 312-345.