STP and Graph Theory

Spanning Tree Protocol (STP) is one of several methods of avoiding loops in bridged local area networks. For most of us, working with the typical corporate LAN, STP is the default configuration of switches and it just works. But it may not always be the most efficient way to connect switches. This post looks at exactly what a spanning tree is, why it is used to solve the problem of loops in a network, and why it may not always be the most efficient way to do that.

Spanning Tree Protocol

When we build a typical bridged local area network, we add multiple physical paths between different LAN’s. If we did not, we would have a single point of failure. But IEEE 802 frame-based networks (like 802.3 Ethernet) cannot tolerate a switching loop. With a loop, a single frame would be endlessly retransmitted. And if a frame had a broadcast destination, then the retransmission would rise exponentially, since each received instance of the frame would be flooded again to every other port.

So we need a dynamic method or protocol to break any logical loops and ensure that there is only a single logical path between LAN’s at any one moment. If a path breaks, then the protocol needs to reconfigure the logical network to open a previously closed alternate path.

The original Spanning Tree protocol was published in 1984 by Radia Perlman, working at the time for Digital Equipment Corporation (DEC). It was adopted and absorbed into IEEE 802.1D in 1990. It was extended with Rapid Spanning Tree Protocol (RSTP) in 802.1D in 2004, and with Multiple Spanning Tree Protocol (MSTP) in IEEE 802.1Q in 2005. Meanwhile vendors implemented proprietary extensions, such as Cisco Rapid per VLAN Spanning Tree + (Rapid PVSTP+). Or they adopted proprietary alternatives.

The clause covering STP (as well as Rapid STP and Multiple STP) in 802.1Q – 2014 is 86 pages long. You will find plenty of sites on the internet telling you how STP works, although these are inevitably a summary or an interpretation. To know how it really works, you need to read the standard, which is available from the IEEE GET Program.

But what is less clear is why it works this way. For that, we need to look at Graph Theory.

Graph Theory

Graph Theory is the branch of mathematics that studies the abstract relationship between objects and the things connecting any two of them. In Graph terminology, the objects are vertices, and the things connecting them are edges.


Illustration: a Petersen graph

The best description, for our purpose, is here in the MIT course Mathematics for Computer Science, Chapter 5. "Graphs are ubiquitous in computer science because they provide a handy way to represent a relationship between pairs of objects. The objects represent items of interest such as programs, people, cities, or web pages, and we place an edge between a pair of nodes if they are related in a certain way. For example, an edge between a pair of people might indicate that they like (or, in alternate scenarios, that they don’t like) each other. An edge between a pair of courses might indicate that one needs to be taken before the other."

Graphs have no shape. They are a representation of objects and their connections. A simple graph just has vertices and edges. A weighted graph has a value to the edge (a cost, a distance, a mass: anything with quantity). A directed graph has a direction to the edge. Some further definitions:

  • two vertices are adjacent if they are connected by an edge
  • a path is a non-repeating sequence of adjacent vertices and edges
  • two vertices are connected if there is a path from one to the other
  • a cycle is a path that takes you back where you started (a closed path) with no repeated edge
  • a tree is a set of vertices and edges such that there is only a single path connecting any two. If you add an edge, you create a cycle. If you remove an edge, you disconnect one or more of the vertices.
  • a spanning tree is a tree that spans all the vertices in a graph. It has all the vertices connected by a single path, but not all the edges. A graph can have more than one spanning tree.

The Petersen graph (illustrated above) has 2,000 possible spanning trees.

Spanning Trees

Spanning trees connect all the vertices in a graph, with the fewest number of edges. There are no loops and no repeats. But a graph can have more than one spanning tree, and any given spanning tree is not necessarily the most efficient way of connecting the vertices. If all edges have the same weight (as in a simple graph), then all spanning trees must have the same total weight. But if the edges have different weights, such as a cost or a distance, then some spanning trees would be a more efficient way to connect the vertices than others:

  • A minimum spanning tree connects all the vertices with the minimum total weight of the edges. So, if you were laying a fiber optic cable between towns, this would be an efficient way to do it with the least amount of digging. But it does not give us the shortest path from one specific town to another.
  • A shortest path spanning tree obtains the lowest weight path from a given vertex (the root of the tree) to any other vertex. If you start a journey from one town, this is the shortest route to every other given town. But the same path is not the shortest route if you start from a different town.

IEEE 802.1 Spanning Tree Protocols

With bridged local area networks, the bridges are the vertices and the LAN’s are the edges connecting them. The bridges are usually connected by more than one physical path, for redundancy; or they may be connected in such a way by accident. To avoid a loop we need to switch ports off so that there is only one active path between any pair of bridges at any one time. A fully connected graph with only one path between vertices is a spanning tree. So we need to implement a spanning tree across all the bridges.

The title of Perlman’s paper in 1984 was "An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN". From the paper:

"This approach [transparent bridging] assumes that the topology is a tree (loop-free). However, requiring a topology to be loop-free means there are no backup paths in the case of bridge or LAN failures. Also, because the technology allows network growth so easily, it might be difficult to prevent someone from adding a bridge and creating a loop. A loop in the topology might cause severe performance degradation in the entire extended network due to congestion caused by infinitely circulating packets. It is undesirable to have a network that can be brought down so easily, merely by plugging a cable into the wrong place."

"Thus we have designed an algorithm that allows the extended network to consist of an arbitrary topology. The algorithm is run by the bridges, and computes a subset of the topology that connects all LANs yet is loop-free (a spanning tree). The algorithm is self-configuring. The only a priori information necessary in a bridge is its own unique ID (MAC address), which we are assuming can be attained in some manner, for instance with a hardware ROM containing the value."

The algorithm also meets several other design goals, including low memory and bandwidth regardless of the number of bridges; stabilises in a small multiple of the round trip delay across the network; and completely deterministic behaviour.

This design is carried through to the IEEE 802.1Q standard today, over thirty years later.

Spanning Tree Type

I am interested in what type of spanning tree we obtain with the current IEEE 802.1Q algorithm. The textbook and online guide: Algorithms, by Robert Sedgewick and Kevin Wayne, has a good description and illustration of the standard algorithms for deriving a spanning tree of a graph:

The selection of a starting vertex is common to any spanning tree algorithm. After picking a starting point, the next step is to evaluate the edges, to see which to add to the developing tree. The minimum path algorithms add the next lowest weight edge. The shortest path algorithms add the next lowest root cost path. The IEEE 802.1 STP algorithm uses the root path cost (together with user configurable parameters) to evaluate the vectors it receives, which gives us a shortest path spanning tree algorithm.

However, the standard spanning tree algorithms require somewhere to store the data structures while the tree is constructed. A network of bridges, in an arbitrary topology, in which bridges may be added or removed without pre-configuration, does not have this. Instead, the bridges exchange vectors with their adjacent bridges, discarding those that contain worse information, and replacing their own with any that is better.

This is somewhat similar to the Bellman-Ford algorithm (published in about 1958). This algorithm uses repeated passes, and discards paths that are worse, ending up with the least cost (shortest) path. It is not a distributed algorithm, but I can just about see how the algorithm could be implemented in a distributed fashion. Each bridge only needs to know which adjacent bridge provides the best path to the root. If it receives a lower cost path, it can discard the one it had previously.

In summary, STP (as well as RSTP and MSTP) has the effect of creating a shortest path spanning tree, although the protocol itself does not claim to do so. The tree is rooted on a random bridge, unless one is configured. The spanning tree is guaranteed to be acyclic (loop free) but it is most definitely not the shortest path from any given bridge to another, or to a gateway, or to a core switch (unless you configure the core switch to be the root bridge).

In a network of arbitrary topology, or a simple hierarchy with an obvious root, then STP (and RSTP and MSTP) may be the best way to calculate the spanning tree. But if you have a campus, sites across a metropolitan area, a factory floor or a mesh of sensors, then it may not be.

Two alternatives to STP are:

  • IEEE 802.1Q – 2014 Shortest Path Bridging (SPB): one spanning tree for each entry point to the network
  • IEC 62429 – 2010 Part II Media Redundancy Protocol (MRP): a ring protocol with a topology manager and clients

These have to be the subject of a different post.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.