Static and Dynamic Routing

The previous measurement had two table generations, and the second was handed over ready-made: the reality after the break was computed, written into the tables, and the packets run through as is. Nobody made the transition in between.

In a real network, someone has to make that transition, and there are only two ways to do it: either an administrator writes the rows by hand — static routing — or the devices tell each other the state of their links and build their own tables — dynamic routing. This lesson’s question is not which one is better, but: when a break happens, how many rounds does it take to reach the correct table, and if it is never reached, what does the loss do over time?

Writing and Telling

In static routing, the table is a configuration text. The administrator writes, for every node, the next hop for every destination; the device reads these rows and never questions them. There is no mechanism that checks whether a row is correct, because the device has no second source to compare it against.

# taught transcript, not run

rows hand-written for node b

  destination   next hop
  a             a
  c             c
  d             c
  e             f
  f             f
  g             f
  h             a

In the eight-node network, seven rows are written for every node, and the e, f, g rows route through the chord. When the chord breaks, this text does not change — the device keeps reading whatever is written in the file.

In dynamic routing, the table is not a configuration but the output of an agreement. Devices notify their neighbors at regular intervals, produce their own rows from the incoming notifications, and tell their neighbors when a link drops. What the administrator writes is not the rows, but which links the protocol speaks on.

The two regimes’ costs fall in different places. In the static regime, the cost is at write time: in an eight-node network, every node has seven destinations, for a total of fifty-six rows. If the node count is $n$, the row count grows as $n(n-1)$ — eight hundred seventy rows at thirty nodes. In the dynamic regime, the cost is at run time: devices send notifications, process incoming notifications, and the tables stay wrong for a while during convergence.

Part of the write cost can be shortened with the default route from the previous lesson. A node can pile every destination but one neighbor into a single empty-prefix row, dropping hand-written rows from seven to two. The measurement does not use this shortcut, because what is measured is not writing effort but the correctness of the decision: the default route reduces the row count, it does not change the ability to hear about a break. A shortened table that still points at the broken link sends the packet there just the same.

The Static Table’s Blind Spot

A static table never learns that a link has broken. This is not a delay, it is an absence: no channel is defined for the news to travel through. A device can see its own link go down, but not one two hops away, and if its row points at that link, it keeps sending the packet there.

The consequence in the measurement is this: in the static regime, the black-hole count is not a function of time. However many packets die in the first round, that many die in the hundredth round too. The loss does not stop, it accumulates. Stopping it requires an event from outside the measurement: an administrator noticing the fault and rewriting the rows.

In the dynamic regime, on the other hand, the news has a channel. The two ends of the broken link see it directly, tell their neighbors, and those neighbors tell their own neighbors. The news spreads through the network like a wave, advancing one neighborhood hop every round. The measurement below models exactly this wave.

The measurement’s assumptions:

• RT8 — The network, the oracle, and the forty pairs are the same as in the previous lesson: eight nodes, nine links, the chord that cuts the ring. The measured break is again the loss of that chord.
• RT9 — In the static regime, the table never changes during the measurement. The administrator noticing the fault and intervening is outside the measurement; what is measured is the time until that intervention.
• RT10 — In the dynamic regime, the news starts from the two ends of the broken link and advances one neighborhood hop every round. A node that hears the news makes its table correct; a node that has not heard keeps its old table as is.
• RT11 — A round is a node receiving notifications from its neighbors and updating its table. A round is not a unit of clock time; its real-world counterpart is the protocol’s notification interval, and it varies in seconds.
• RT12 — The same forty pairs are run again every round, and the measurement keeps no memory between rounds; every round is measured independently, with that round’s tables.
• RT13 — The hop limit is 12; a packet that burns through it is counted as a loop.
• RT14 — The set’s resolution is 1/40 = 0.025 over forty packets; no difference smaller than this is claimed.

Measurement

"""Static and dynamic: a table that never hears the break vs. one that does.

In the static regime the table never changes. In the dynamic regime the
news starts from the two ends of the broken link and advances one
neighborhood hop every round.
"""
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 = [b for b in LINKS if b != ("b", "f")]
HOP_LIMIT = 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):
    k = {u: set() for u in NODES}
    for x, y in links:
        k[x].add(y)
        k[y].add(x)
    return k


def oracle(links):
    k, table = neighbors(links), {}
    for source in NODES:
        prev, frontier, seen = {}, [source], {source}
        while frontier:
            nxt = []
            for u in frontier:
                for v in sorted(k[u]):
                    if v not in seen:
                        seen.add(v)
                        prev[v] = u
                        nxt.append(v)
            frontier = nxt
        for dest in NODES:
            if dest == source or dest not in prev:
                continue
            step = dest
            while prev[step] != source:
                step = prev[step]
            table[(source, dest)] = step
    return table


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


def pairs(count=40, seed=SEED):
    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, count=40):
    tally, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0
    for x, y in pairs(count):
        fate, h = forward(x, y, tables, links)
        tally[fate] += 1
        hops += h
    return tally, hops


def partial(old, new, informed):
    """Only the informed set has updated after the break; the rest carry their old table."""
    return {(u, h): (new if u in informed else old)[(u, h)] for (u, h) in old}


def informed_by(rnd, links=BROKEN, source=("b", "f")):
    """The news starts from the ends of the broken link, advancing one neighborhood hop per round."""
    if rnd <= 0:
        return set()
    k, group, edge = neighbors(links), set(source), set(source)
    for _ in range(rnd - 1):
        edge = {v for u in edge for v in k[u]} - group
        group |= edge
    return group


old, new = oracle(LINKS), oracle(BROKEN)
changed = [(u, h) for (u, h) in old if old[(u, h)] != new[(u, h)]]
print(f"table rows {len(old)} | rows to fix by hand after the break "
      f"{len(changed)} | nodes touched {len({u for u, _ in changed})}")
print()
print(f"{'round':>5s} {'informed':>8s} | {'static: reached':>16s} {'loop':>5s} {'blk hole':>8s}"
      f" {'hops':>4s} | {'dynamic: reached':>16s} {'loop':>5s} {'blk hole':>8s} {'hops':>4s}")
static_loss = dynamic_loss = 0
for rnd in range(6):
    s, sh = measure(old, BROKEN)
    group = informed_by(rnd)
    d, dh = measure(partial(old, new, group), BROKEN)
    static_loss += s["loop"] + s["black hole"]
    dynamic_loss += d["loop"] + d["black hole"]
    print(f"{rnd:5d} {len(group):8d} | {s['reached']:16d} {s['loop']:5d} "
          f"{s['black hole']:8d} {sh:4d} | {d['reached']:16d} {d['loop']:5d} "
          f"{d['black hole']:8d} {dh:4d}")
print(f"packets that miss their destination over six rounds: static {static_loss}, "
      f"dynamic {dynamic_loss}")

print()
print(f"{'informed set':<26s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} "
      f"{'hops':>5s} {'died with correct table':>24s}")
for name, group in (("nobody", set()),
                     ("only b and f", {"b", "f"}),
                     ("b, f, and their neighbors", informed_by(2)),
                     ("everybody but d", set(NODES) - {"d"}),
                     ("everybody", set(NODES))):
    tab = partial(old, new, group)
    s, h = measure(tab, BROKEN)
    correct_died = sum(1 for x, y in pairs()
                        if forward(x, y, tab, BROKEN)[0] != "reached" and x in group)
    print(f"{name:<26s} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d} "
          f"{h:5d} {correct_died:24d}")

table rows 56 | rows to fix by hand after the break 11 | nodes touched 6

round informed |  static: reached  loop blk hole hops | dynamic: reached  loop blk hole hops
    0        0 |               26     0       14   61 |               26     0       14   61
    1        2 |               26     0       14   61 |               34     6        0   94
    2        6 |               26     0       14   61 |               40     0        0   99
    3        8 |               26     0       14   61 |               40     0        0   99
    4        8 |               26     0       14   61 |               40     0        0   99
    5        8 |               26     0       14   61 |               40     0        0   99
packets that miss their destination over six rounds: static 84, dynamic 20

informed set               reached   loop  black hole  hops  died with correct table
nobody                          26      0          14    61                        0
only b and f                    34      6           0    94                        1
b, f, and their neighbors       40      0           0    99                        0
everybody but d                 40      0           0    99                        0
everybody                       40      0           0    99                        0

The Flat Line and the Falling Line

The static column is the same across all six rounds: 26 reached, 14 black hole, 61 hops. This constancy is the measurement’s most important finding. The loss does not shrink because there is no event to shrink it; the table did not hear about the break, and there is no channel for it to hear through. The packets that miss their destination over six rounds reach 84, and this number keeps growing linearly with rounds.

The dynamic column closes in two rounds: reached climbs to 40 in the second round and stays there. Total loss over six rounds is 20. Same break, same topology, same forty packets — the only difference is whether the news has a channel.

The manual-correction cost sits in the top row. 11 of the fifty-six rows become wrong, spread across 6 separate nodes. Even if the administrator learns that a link has broken, what needs fixing is not a single row: six devices have to be touched, and on each, which rows need to change has to be recomputed. In an eight-node network, this is one session’s work; in a thirty-node network, it is something else.

The Cost of Partial Information

The bottom table looks inside the dynamic regime, and something unexpected is there.

When nobody has heard, 14 packets fall into a black hole, spending a total of 61 hops. When only b and f have heard about the break, the black hole drops to zero — an improvement at first glance, but the reached count is not 40, it is 34: the remaining 6 packets enter a loop, and total hops climb from 61 to 94.

This row pays off the course’s second claim: partial information produces a fault more expensive than no information at all. The reason is in the nature of the fates. A packet that falls into a black hole dies immediately: it arrives at a node, finds a neighbor with no counterpart, and is dropped. The resource it spends is the hops it took up to that point. A packet that enters a loop, however, does not die; it circles the network until it burns through the hop limit, consuming link and processing capacity every round.

The measurement says this in hop counts. The number of lost packets drops from 14 to 6 — more than half — while hops spent climb from 61 to 94. Few packets, many hops. The fault’s appearance changes too: a black hole looks like a loss and is relatively easy to find; a loop looks like congestion, because the links are full and packets are flowing — it is just that none of them arrive.

The rightmost column says why this is unavoidable. In the only b and f row there is 1 packet that leaves a node whose table is correct and dies anyway. That node has heard about the break, its row matches reality, its decision is flawless — and it still loses the packet, because the neighbor it hands the packet to has not heard. A structural conclusion follows: no single device can put a packet into a loop by itself. The situation where two tables send a packet back and forth to each other is called a routing loop; the measurement’s short fate name for it is loop. The correctness of a device’s decision does not depend on its own table but on its neighbor’s.

The last two rows show something else. When everybody but d has heard, the result is 40/40 — even though one node has still not heard. The reason is that none of the measured forty pairs pass through d‘s changed rows. Partial information does not always produce a fault; the fault is born **only when the missing information falls on the packet’s path**.

Choosing by the Criterion

The choice between the two regimes rests on a criterion readable from this measurement, and the criterion is not “which one is more advanced”.

Static routing is the right choice when the path to the destination is unique. In a stub network with a single exit, there is no alternative path; even if a dynamic protocol ran there, it would have no second path to discover, and nothing to do at the moment of a break. In a place like this, a protocol’s notification traffic and state-keeping are an unreturned cost.

Dynamic routing pays off when there is more than one path. The ring in the measurement is exactly this: when the chord breaks, every destination still has a path, and the dynamic regime finds it in two rounds. The reason the static regime cannot find it is not the absence of a path, but the absence of a mechanism that looks for one.

A mix of the two is also an option, and a common one: static rows for stub networks, a dynamic protocol for the core. The criterion is the same in both cases — when a link breaks, how many rounds it takes to reach the correct table, and how many packets miss their destination during those rounds.

This criterion is defined for the static regime too, but its counterpart is not in the protocol, it is in a person. A static network’s convergence time is the time between the fault being noticed and the rows being rewritten; the measurement left this outside with RT9, because this duration cannot be read from the protocol: it has no upper bound like a notification interval, and it depends on how long the fault takes to be seen. The flat line in the measurement represents exactly this uncertainty — that line does not fall on its own.

Summary

• The administrator writes the static table, and its cost is at write time; the row count grows as $n(n-1)$ and is fifty-six rows at eight nodes.
• The static table never hears about the break: the black-hole count stays at 14 across all six of the six rounds, and total loss over six rounds reaches 84 packets, versus 20 in the dynamic regime.
• A manual correction is not a one-row job; 11 of the fifty-six rows become wrong across 6 separate nodes.
• When only two nodes hear about the break, the black hole drops to 0, but 6 packets enter a loop and hops climb from 61 to 94: partial information produces a fault that is more expensive and harder to see than no information at all.
• Even 1 packet leaving a node with a correct table dies; no single device can put a packet into a loop by itself, a loop is a disagreement between at least two tables.
• The choice criterion is the number of paths: a static row is enough in a single-path stub network; in a network with more than one path, the rounds the dynamic protocol finds pay off.

Next Step

In this measurement, the carrying of the news was not modeled: the informed set was given from outside, and every informed node arrived at the correct table instantly, as if it held the whole reality the moment the link broke. In reality, what a node hears from its neighbor is not the entire topology — the plainest protocol family hears exactly one thing from a neighbor: how many hops away the neighbor is from every destination. The next lesson measures how this single number spreads, how many rounds it takes to reach the correct table, and what fault this plainness brings.