Bridge Protocols and BPDUs

Redundancy and bridging loops

Network designers use redundancy, meaning multiple alternative paths for data. If a link or device fails, for example when a cable is cut during construction, traffic can be rerouted through a backup path. This topology improves service availability.

In Local Area Networks (LANs), redundancy is achieved by connecting switches, historically called bridges, with multiple links. These physical connections improve fault tolerance but can introduce bridging loops at the Data Link Layer.

Without a control mechanism, switches can forward the same frames around a loop, consuming bandwidth and disrupting the network. This affects broadcast frames, unknown unicast, and some multicast frames that are flooded through multiple ports. Bridge protocols, especially the Spanning Tree Protocol (STP), block selected logical paths and keep them available as backups. For a broadcast, a switch does not limit forwarding to one destination port. Each active segment can receive another copy, so the number of frames grows on every circulation.

Broadcast storms and MAC table instability

The effect of a loop can be traced through a broadcast frame in a redundant, unmanaged network. A broadcast frame is intended for every device on the LAN. A common example is an ARP request sent to find another device's MAC address. A switch floods such a frame because there is no single destination address that identifies one output port.

How the loop develops

1. Initial Broadcast: A computer sends a single broadcast frame. It arrives at Switch A.
2. The flood: A switch forwards a broadcast frame out of every port except the incoming port. Switch A sends the frame towards Switch B and Switch C.
3. The loop begins:
   • Switch B receives the frame from Switch A and sends it through its other ports, including the port connected to Switch C.
   • At the same time, Switch C receives the frame from Switch A and sends it towards Switch B as well.
4. Frame duplication: Switches B and C receive copies of the same frame from each other and flood them again. The frame circulates through the network and consumes bandwidth. This is known as a broadcast storm.

Spanning Tree Protocol (STP)

The Spanning Tree Protocol (STP), defined in the IEEE 802.1D standard and developed by Radia Perlman, prevents bridging loops by creating a logical loop-free topology. Switches exchange control information in BPDUs, separate from user-data frames. The information describes the root, path costs, and port roles.

STP transforms the physically redundant graph with cycles into a logical spanning tree. A tree has no loops and provides one active path between nodes. Redundant links are placed in a blocking state, while their physical connections remain available for a later topology change.

A port in a blocking state does not forward user data frames, but it remains active and listens for control messages. After an active path fails, STP can detect the change and transition a previously blocked port to forwarding. The network keeps a loop-free topology while a backup link can take over after the topology changes. A BPDU also carries information needed to judge whether an announcement is current. The switch compares received information with its own state and can ignore an inferior BPDU.

How STP builds the tree

Switches in the LAN participate in an election and exchange special control frames called Bridge Protocol Data Units (BPDUs). The process has several steps.

1. Step 1: elect the Root Bridge

   The switch with the lowest Bridge ID becomes the Root Bridge. It is the reference point for the spanning tree, and path costs are calculated relative to it. The priority field is compared first, followed by the extended system ID and MAC address, so an administrator can select a preferred root.

   The classic Bridge ID is an 8-byte value composed of a 2-byte priority field and a 6-byte MAC address. In the extended form, the first 16 bits contain a 4-bit priority field and a 12-bit system ID extension:

   • Priority field (2 bytes in classic STP, 4 bits in the extended ID): In classic STP this is configurable from 0 to 65535, with a default of 32768. A lower priority makes the switch more likely to be elected.
   • Extended system ID (12 bits): In implementations with the extended identifier, part of the priority field identifies an instance, such as a VLAN.
   • MAC address (6 bytes): The switch hardware address. It resolves a tie when the preceding fields match.

   $\text{Bridge ID} = \text{priority field (4 bits)} \Vert \text{system ID extension (12 bits)} \Vert \text{MAC address (48 bits)}$

   Initially, each switch advertises its own ID as the Root ID. After receiving a BPDU with a lower ID, a switch accepts the better candidate and relays its information. BPDU exchange leads all switches to agree on one Root Bridge. A BPDU carries, among other fields, the root identifier, the root path cost, and the sender identifier.

2. Step 2: elect Root Ports

   Each switch other than the Root Bridge chooses one best path to the root. The port on that path becomes the Root Port. A bridge has one Root Port, which identifies its selected best path to the root.

   The decision uses the lowest Root Path Cost. The cost is the sum of link costs along the path:

   A port cost is assigned from the link bandwidth according to the table used by the STP variant. Summing costs allows paths with different hop counts and link speeds to be compared.

   • A switch receives BPDUs from the Root Bridge directly or through other switches. The BPDU contains the current Root Path Cost.
   • The switch adds the cost of the port on which it received the BPDU. Historical short-scale values are: 10 Gbps (Cost 2), 1 Gbps (Cost 4), 100 Mbps (Cost 19), and 10 Mbps (Cost 100).
   • The port producing the lowest total cost to the root becomes the Root Port. The cost is added across links, so the path with fewer physical hops does not always have the lowest cost.
   • Tie-breakers: With equal costs, the switch chooses the neighbor with the lowest Bridge ID, then the neighbor port with the lowest Port ID, and finally the lower local Port ID.
3. Step 3: elect Designated Ports

   On each network segment, such as a cable connecting two switches, one port forwards traffic onto that segment towards the Root Bridge. It becomes the Designated Port. A segment has one Designated Port.

   All ports on the Root Bridge are Designated Ports. On other segments, the port on the switch with the lower Root Path Cost is selected. Bridge ID and Port ID resolve equal costs, leaving one winning port on each segment.

4. Step 4: block remaining ports

   Ports without the Root Port or Designated Port role are redundant links that could create a loop. They enter the Blocking State. They do not forward user data but continue to listen to BPDUs and can take over after an active path fails. A topology change can cause the election to assign these ports new roles.

Port states in classic STP

In classic STP, a port progresses through several states while the topology changes. The delays between states reduce the risk of a temporary loop.

• Disabled: The port is administratively shut down. It does not participate in STP and does not carry frames on that connection.
• Blocking: This is the initial state and the state for redundant ports in a stable topology. The port listens to BPDUs to learn the topology, does not forward user data frames, and does not learn MAC addresses. This breaks the loop while leaving the port available for a later transition.
• Listening: The first transitional state from Blocking to Forwarding. The port may become a Root or Designated Port, processes BPDUs, and participates in the STP election, but does not forward user data or learn MAC addresses. It lasts for the Forward Delay timer, typically 15 seconds. The switch uses this time to determine the port role.
• Learning: The second transitional state. The port is assigned a forwarding role as Root or Designated but still does not forward data. It receives frames, learns source MAC addresses, and populates the table. This lasts for another 15 seconds of Forward Delay, so the table is ready before forwarding starts. Pre-learning limits unknown destinations when forwarding begins.
• Forwarding: The port is fully operational. It sends and receives BPDUs, forwards user data, and continues learning MAC addresses. This is the normal state for active ports in the spanning tree, and its role can change after a better BPDU arrives.

In classic STP, transition from blocking to forwarding typically takes 30 seconds (15 listening + 15 learning) with the standard timer values. It can take up to 50 seconds when old topology information must time out first (20 seconds Max Age + 30 seconds). Max Age determines how long a switch treats received BPDU information as valid. After it expires, the switch can recalculate port roles. This convergence time was a limitation of original STP and contributed to the development of faster versions such as RSTP (Rapid Spanning Tree Protocol). RSTP shortens convergence through different negotiation rules and port roles, while the states above describe classic STP and its historical timers.