Spanning Tree Protocol

The previous lesson placed a single cable between two switches, and every flooded frame crossed it once and was done. When redundancy is wanted, a second cable is run; the two switches connect through two separate paths, and if one breaks, the other stays up. This is the oldest and most natural request in network design.

The request produces a malfunction when it meets flooding. A flooded frame crosses over on the first cable, the far switch floods it to every port but the one it arrived on — the second cable is among them — and the frame returns to the first switch. When it returns, the first switch floods it again. This lesson’s question is how this return is stopped, and what the stopping decision does to a packet’s fate.

The Frame Carries No Counter

To see why the above return does not end on its own, it is enough to look at the frame. An Ethernet frame has a destination address, a source address, a type field, a payload, and a check sequence. There is no field that counts how many devices it has passed through. The network-layer packet has such a field, and it was established in the Network Models and Protocols course; the link-layer frame has none.

The result is not two-fold but three-fold. First, a circulating frame never dies by aging. Second, every switch on the ring duplicates the frame each round: one incoming copy spawns several outgoing copies. Third, because the same source address is seen from different ports, every switch’s MAC address table gets rewritten round after round — the table is not stale in the sense measured in the previous lesson, it is unstable.

This trio is the first instance of why a loop is more expensive than a black hole. In a black hole, the packet dies and the matter ends; here, the packet does not die, it multiplies and consumes the network’s own carrying capacity by itself. Someone looking from outside sees this as congestion.

The Protocol’s Decision

The solution is to turn a topology that is physically a ring into a logical tree. A tree has no cycle; without a cycle there is no return either. This requires blocking some links: the link stays up, the cable is plugged in, but no data frame passes over it.

Spanning tree protocol lets the switches build this tree among themselves. The decision has three steps. The switches first elect a root: every switch has an identifier, and the smallest identifier becomes root. Then every switch marks its cheapest port toward the root as its root port. Finally, on every link, the end that connects that link to the root more cheaply is counted designated; the other end is blocked.

How the tree itself is built is not this lesson’s subject. The concept of a spanning tree and its greedy construction were established in the Minimum Spanning Tree lesson of the Algorithms course and are not rederived here. What is measured here is the protocol’s decision and what that decision does to packets.

# taught transcript, not run

topology: a-b-c-d-e-f-g-h-a ring + b-f chord   (8 nodes, 9 links)
root: a

port roles (for root a)
  b: root port -> a       | designated -> c, f
  h: root port -> a       | designated -> g
  c: root port -> b       | designated -> d
  f: root port -> b       | designated -> e
  d: root port -> c       | d-e BLOCKED
  g: root port -> h       | f-g BLOCKED

protocol message (switch to switch, not data)
  root identifier | cost to root | sender identifier | port

In root election, a small identifier is not a measure of capability; it is only an ordering rule that gets every switch to the same result. The tree gets built no matter where the root is, but the tree’s shape depends on the root, and so does the length of the paths.

The Measurement’s Assumptions

• ND22 — The topology is the shared definition’s topology: eight switches, a ring of seven links (a–b–c–d–e–f–g–h–a), and the b–f chord cutting the ring; nine links in total. The oracle is known because we built the topology ourselves, and it is the first step of the shortest path to every destination for every node.
• ND23 — The root is a, and the tree is built by walking breadth-first from the root: every switch keeps its port nearest the root, and the remaining links are blocked. The minimum spanning tree algorithm is not run here; the tree’s result is used.
• ND24 — In the flooding measurement, a broadcast frame leaves the root; every node copies the frame to every link but the one it arrived on. There is no mechanism to stop it, because the frame carries no hop count. The measurement is cut off by a round limit; being cut off does not mean the frame has stopped.
• ND25 — Forty source–destination pairs are drawn from a single generator with a single modulus; a draw where the source equals the destination is discarded. The same forty pairs are used in every regime.
• ND26 — The link that breaks is the b–f chord. Because the chord short-circuits the two arms of the ring, most of the tree passes through it; when it breaks, a large number of switches have to change their decision.
• ND27 — Five regimes are compared: tree built, no break; link broken but neither the tree nor the table has been renewed; tree renewed but the tables are stale; tree renewed and only two switches have refreshed their table; tree renewed and every table cleared.
• ND28 — The hop limit is 12. A packet that burns through the limit, or crosses the same link a second time, is counted a loop; a packet whose next node is not in the table or is no longer a neighbor is counted a black hole.
• ND29 — The set’s resolution is forty packets; the smallest measurable difference is $1/40 = 0{,}025$.

The Measurement

"""Spanning tree protocol's decision: the blocked link and the packet's fate.

The tree is built by walking breadth-first from the root; the minimum
spanning tree algorithm was established in the Algorithms course and is
not rederived here.
"""
SEED = 20260810
NODES = ["a", "b", "c", "d", "e", "f", "g", "h"]
LINKS = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"),
         ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")]
BROKEN, ROOT, HOP_LIMIT = ("b", "f"), "a", 12


def generator(seed):
    d = seed % 2147483646 + 1

    def r(n):
        nonlocal d
        d = (d * 48271) % 2147483647
        return d % n
    return r


def neighbors(links):
    n = {u: set() for u in NODES}
    for x, y in links:
        n[x].add(y)
        n[y].add(x)
    return n


def oracle(links):
    """First step of the shortest path to every destination, for every node."""
    n, table = neighbors(links), {}
    for source in NODES:
        previous, frontier, seen = {}, [source], {source}
        while frontier:
            next_frontier = []
            for u in frontier:
                for v in sorted(n[u]):
                    if v not in seen:
                        seen.add(v)
                        previous[v] = u
                        next_frontier.append(v)
            frontier = next_frontier
        for destination in NODES:
            if destination == source or destination not in previous:
                continue
            step = destination
            while previous[step] != source:
                step = previous[step]
            table[(source, destination)] = step
    return table


def tree(links, root=ROOT):
    """The port nearest the root is kept, the remaining link is blocked."""
    n, seen, frontier, kept = neighbors(links), {root}, [root], []
    while frontier:
        next_frontier = []
        for u in frontier:
            for v in sorted(n[u]):
                if v not in seen:
                    seen.add(v)
                    kept.append(tuple(sorted((u, v))))
                    next_frontier.append(v)
        frontier = next_frontier
    return kept


def forward(source, destination, tables, links):
    n, u, crossed, hop = neighbors(links), source, [], 0
    while u != destination:
        if hop >= HOP_LIMIT:
            return "loop", hop
        next_node = tables.get((u, destination))
        if next_node is None or next_node not in n[u]:
            return "black hole", hop
        if (u, next_node) in crossed:
            return "loop", hop
        crossed.append((u, next_node))
        u, hop = next_node, hop + 1
    return "reached", hop


def pairs(count=40):
    r, result = generator(SEED), []
    while len(result) < count:
        x, y = NODES[r(8)], NODES[r(8)]
        if x != y:
            result.append((x, y))
    return result


def measure(tables, links):
    tally, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0
    for x, y in pairs():
        fate, h = forward(x, y, tables, links)
        tally[fate] += 1
        hops += h
    return tally, hops


def partial(old, new, updated):
    """Only one set has heard of the new tree; the rest keep the old one."""
    return {(u, h): (new if u in updated else old)[(u, h)]
            for (u, h) in old if (u, h) in new}


def flood(links, source, round_limit):
    """Broadcast frame: every node copies to every link but the one it arrived on."""
    n, wave, copies = neighbors(links), [(source, None)], 0
    for _ in range(round_limit):
        next_wave = []
        for u, arrived_from in wave:
            for v in sorted(n[u]):
                if v != arrived_from:
                    copies += 1
                    next_wave.append((v, u))
        wave = next_wave
        if not wave:
            break
    return copies, len(wave)


BROKEN_LINKS = [b for b in LINKS if b != BROKEN]
OLD, NEW = tree(LINKS), tree(BROKEN_LINKS)
OLD_BROKEN = [b for b in OLD if b != BROKEN]
print(f"links {len(LINKS)} | tree links {len(OLD)} | old tree blocks "
      f"{[b for b in LINKS if tuple(sorted(b)) not in OLD]}")
print(f"broken link {BROKEN} | new tree blocks "
      f"{[b for b in BROKEN_LINKS if tuple(sorted(b)) not in NEW]}")
print()
print(f"{'round':>5s} {'ring copies':>11s} {'in flight':>9s} {'tree copies':>11s} "
      f"{'in flight':>9s}")
for rnd in (1, 2, 4, 6, 8, 10, 12):
    c1, f1 = flood(LINKS, ROOT, rnd)
    c2, f2 = flood(OLD, ROOT, rnd)
    print(f"{rnd:5d} {c1:11d} {f1:9d} {c2:11d} {f2:9d}")
print()
print(f"{'regime':<34s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} "
      f"{'hops':>5s}")
for name, tab, links in (
        ("tree built, no break", oracle(OLD), OLD),
        ("link broken, tree and table stale", oracle(OLD), OLD_BROKEN),
        ("tree new, tables stale", oracle(OLD), NEW),
        ("tree new, table on two switches",
         partial(oracle(OLD), oracle(NEW), {"b", "f"}), NEW),
        ("tree new, tables clean", oracle(NEW), NEW)):
    tally, h = measure(tab, links)
    print(f"{name:<34s} {tally['reached']:7d} {tally['loop']:6d} "
          f"{tally['black hole']:11d} {h:5d}")

links 9 | tree links 7 | old tree blocks [('d', 'e'), ('f', 'g')]
broken link ('b', 'f') | new tree blocks [('e', 'f')]

round ring copies in flight tree copies in flight
    1           2         2           2         2
    2           5         3           5         3
    4          14         5           7         0
    6          27         7           7         0
    8          50        13           7         0
   10          85        19           7         0
   12         142        33           7         0

regime                             reached   loop  black hole  hops
tree built, no break                    40      0           0   106
link broken, tree and table stale       21      0          19    70
tree new, tables stale                  20      0          20    64
tree new, table on two switches         25     10           5   100
tree new, tables clean                  40      0           0   129

What Blocking Buys

The table above gives the protocol’s reason for existing. On the nine-link ring, a single broadcast frame produces 14 copies by round four, 50 by round eight, 142 by round twelve, with 33 copies still in flight at that point. The count keeps growing; it stops because the measurement’s round limit ends, not because the frame stops. A single frame fills an eight-switch network all by itself.

On the tree, the same frame ends at 7 copies by round four, with nothing left in flight. The number seven is the tree’s link count, and it is not a coincidence: on a tree, every link is crossed exactly once, moving away from the root. Flooding is finite on a tree and infinite on a cycle, and the difference amounts to nothing more than two blocked links.

The cost sits in the same place. Two of the nine links carry no data; the cables are plugged in, the ports are up, but no frame passes over them. The cable run for redundancy waits idle until the need for redundancy arises.

Until the Block Lifts

The lower table reads the time from the moment the chord breaks to the new tree settling in in five steps.

While the tree is built, all forty of the forty packets reach their destination, spending 106 hops. This is also an indicator of blocking’s cost: the same forty pairs would take shorter paths if every link were open. Blocking lengthens paths but loses no packet.

When the link breaks and no one hears about it, reached drops to 21, and 19 packets fall into a black hole. Hops drop to 70 — fewer hops does not mean less work, it means early death. A packet falling into a black hole stops making progress; the hops it does not spend are a loss, not a gain.

When the tree is rebuilt but the tables stay stale, the situation is a bit worse: reached is 20, black hole is 20. The protocol has fixed the topology, but the MAC address tables still point at the old tree’s ports. The new tree has opened one link and blocked another; as long as the tables point at the closed port, a packet is sent somewhere that is no longer a neighbor, and it ends there. This is the reason the protocol does not settle for rebuilding just the tree: when a topology change is announced, the tables’ lifetime is also shortened, so that stale entries drop quickly.

When only two switches have refreshed the table, the table produces a third fate for the first time: 25 reach, 5 fall into a black hole, and 10 packets enter a loop. Hops climb from 64 to 100. While the two switches point at the new port, their neighbors point at the old one, so the packet goes forward and comes back, circling until it burns through the hop limit.

From here, the shared definition’s second claim can be read: partial information produces a more expensive malfunction than no information at all. When no one heard, the packet died right away; when two switches heard, black holes dropped from 20 to 5, but 10 packets started circling instead of dying, and hops climbed from 64 to 100. The count of lost packets fell, the work spent rose, and the malfunction became invisible — a circling packet looks not like an error but like congestion.

A third claim is read from the same row, and it is structural. No single switch can put a packet into a loop by itself. A loop needs at least two tables, one sending the packet forward and the other sending it back; in the first three regimes, every table pointed at the same tree, so no loop arose even though they were wrong. A loop is born not from a table being wrong, but from tables disagreeing.

When every table is cleared, all forty of the forty packets reach again, and hops climb to 129. Paths have lengthened because the chord is gone; but no packet is lost. This is the definition of convergence: expensive but correct.

Summary

• The link-layer frame carries no hop count; on a topology with a cycle, a flooded frame does not die by aging, it multiplies every round and leaves the tables unstable.
• Spanning tree protocol elects a root, keeps every switch’s port toward the root, and blocks the remaining links; a single broadcast frame on the ring climbs to 142 copies by round twelve, while on the tree it ends at 7.
• Blocking’s cost is idle cable and longer paths: on the tree, forty packets reach in 106 hops; on the new tree after the break, in 129 — but all forty reach.
• When no one hears of the break, 19 packets fall into a black hole; when the tree is rebuilt but tables stay stale, 20 do; hops dropping to 70 and 64 is early death, not a gain.
• When only two switches refresh the table, black holes drop to 5 but 10 packets enter a loop and hops climb to 100: partial information produces a more expensive malfunction than no information.
• A loop is not something a single table can produce; it is a disagreement between at least two tables.

Next Step

The spanning tree’s answer to redundancy is one-directional: the second link exists, but it waits. In the measurement, two links were blocked, and their carrying capacity went unused until the moment of the break. A question follows from this: can two links be used at the same time? The cycle ban seems to forbid it, because two links mean two paths, and two paths bring a flooded frame back. The next lesson measures the mechanism that goes around this ban: an aggregation that counts several links as a single logical link, why the distribution decision does not split a given flow, and how many flows get moved when a port drops.