Spanning Tree

Introduction

As Ethernet networks became business-critical, it became important to be able to build networks which could automatically detect and recover from the failure of individual components and/or links.

Consider the network in Figure 1:-

Two Bridges forming loop

To guard against the failure of the Ethernet bridge linking the desktop LAN to the server LAN, a second bridge is added in parallel.

Assume that one of the desktop systems sends out a broadcast packet (which happens a lot !). The first Ethernet bridge will forward that packet from the user LAN onto the server LAN. The second bridge will see the broadcast on the server LAN and will forward it back onto the user LAN (unaware that this is where the packet originated from). The first bridge will see this broadcast on the user LAN and will forward it onto the server LAN (unaware that this is a copy of the original packet it had forwarded only a moment before). Almost immediately, both LANs will “freeze”, totally swamped with packets looping endlessly. Worse than this, because all of the packets are broadcasts, every single device on both LANs will have to process them, potentially causing devices to “freeze” as they are overwhelmed by the number of network packets arriving.

This is not a good thing.

What is needed is a mechanism for the Ethernet bridges to monitor each other, and to agree that only one of them will forward traffic between the user LAN and the server LAN. This is accomplished by having both bridges run the IEEE 802.1d Spanning Tree protocol

History

To follow...

The Basics

To state it at its simplest, the functions of the IEEE 802.1d Spanning Tree algorithm are to:-

There are three fundamental steps in the execution of the algorithm:-

  1. A root bridge is elected. This becomes the “centre” of the network, and should be placed near the focal point of all network traffic (e.g. near the servers)
  2. Every bridge which is not the root bridge (i.e. those which lost the election) chose a root port, which is the port through which it is “closest” to the root bridge.
  3. On every LAN segment, a designated port is chosen from among all the ports on all the bridges connected to that segment. This is the port through which traffic from that segment will head towards the root bridge

Once these three steps are complete, any port which is neither a root port or a designated port is blocked.  In our simple network, this will be the result:-

 

The left-hand bridge is elected as the root bridge.  Every port on a root bridge is automatically the designated port for the LAN segment is connects to (the reason for this will become apparent when we look at the exact mechanics of each of the steps in the algorithm).  The other bridge chooses the port connecting to the Server LAN as its root port (i.e. its best path to the root).  The other port on this bridge, being neither a root port nor a designated port, is placed into the blocking state (meaning it doesn’t receive or transmit any “user” network traffic).

When designing a LAN, it is very important not to leave these choices to chance !  Bridge parameters should be tweaked to ensure that the network topology turns out appropriately, or very poor network performance could result (and probably will, for reasons discussed later)

Happily, all of the choices made by the Spanning Tree algorithm can be controlled by altering settings on the bridges

A Word On Switches

So far, I’ve talked exclusively about bridges.  An Ethernet switch is nothing more than a multi-port bridge (a very fast one !).  It runs the very same Spanning Tree algorithm as the most humble of bridges and the terms "bridge" and "switch" can be used interchangeable throughout.