Spanning Tree

Bridges are modelled the way they behave: each one starts believing it is the root, tells its neighbours, and the belief spreads until a round changes nothing. That is deliberately not a shortest-path algorithm, because a shortest-path algorithm is what checks it. Dijkstra runs separately from the elected root and its distances must equal the ones the exchange settled on, and a union-find that has never seen either must agree that what forwards is a tree.

A flood in a looped network does not finish, so the simulation has a stated limit rather than a claim of infinity. Eight steps is enough to show a mesh multiplying and a ring circulating; it is not a measurement of how long a real network survives, which depends on frame size, link speed and how quickly somebody pulls the cable.

In a mesh the copies multiply, roughly doubling per step here. In a ring they do not multiply at all: two copies go round in opposite directions forever. Both are fatal and only one is exponential, and calling them both a storm that grows would be wrong about the ring.

802.1D is written for shared segments, where several bridges hang off one wire and one of them is elected the designated bridge for it. Every link here joins exactly two bridges, which is what modern switched Ethernet actually looks like, and for that case the tree is simply the union of the root ports. The designated-port election is real and is not modelled. Blocking is also a PORT state in the standard rather than a property of a link, and a blocked port is not dead: it goes on receiving the protocol's own messages, which is how it learns that the topology changed and it should start forwarding. This page blocks whole links and counts no protocol traffic at all, so what it calls a link carrying nothing is a link carrying no data.

There is no hello time, no max age, no listening or learning state and no thirty-second delay before a port starts forwarding, which is the part that made the original protocol painful and is what rapid spanning tree fixed. There is also no MAC address table: every frame here is flooded, which is the worst case and the case the loop makes fatal.

Link costs of 10, 20, 30 and 40 stand in for the real table, which is derived from link speed and has changed twice as Ethernet got faster. Nothing on the page depends on the actual numbers; what it depends on is that the cheap path is sometimes the long one, which is why one network here has a direct link between two bridges costing 40 while the two-hop path between the same pair costs 20, so the cheap way round is the long way round. The first draft of this sentence said four times, comparing the direct link with a single hop rather than with the path it competes against; the gate that demands every number on a page be pinned by a test is what caught it.

The measurement is a count of frames per step. A tone per frame would be a mood rather than the quantity, and the quantity is already a column of integers.