Routing Decision

Every decision covered so far was made within the same local network. A switch looked up the frame’s destination in its own address table; when it found an entry, it sent the frame straight out that port, and when it did not, it flooded. The destination was in every case a direct neighbor: inside the same broadcast domain, one hop away.

If the destination is on another network, this setup does not work. It is not a direct neighbor, it has no port entry in the table, and flooding is not an option — a network of networks cannot be flooded. The decision now has to answer not “which port” but “whom do I hand it to”. This lesson’s question is where that answer is read from.

What the Decision Looks At

The decision a router makes is called the routing decision, and it has exactly one output: the next hop. The packet’s destination address is the input, one of the neighboring nodes is the output. The router does not know the entire path to the destination, and it does not need to; it knows only one hop and hands the packet there. The rest of the path is the next node’s problem.

The decision is not made by looking at the packet itself. The packet carries its destination address and nothing else; it does not say which neighbor gets closer to that destination. What says that is the device’s own routing table, held in memory. The table is a set of rows that maps destination-address prefixes to next hops:

# taught transcript, not run

routing table — rows in the order they were written

  prefix      length   next hop
  1010            4    north
  10110           5    west
  101011          6    east
  (empty)         0    central
  10101100        8    local
  10100           5    south

This transcript is not a specification but a reading of a device’s memory; it has not been run and no numeric claim follows from it. The only thing to notice is the order of the rows: they were added over time and are not sorted by length. The last row carries a longer prefix than the first.

The empty-prefix row is special: its length is zero and it matches every address. This row is the default route, and it covers whatever the table leaves out. Because of it, the table never has to enumerate every address in the world.

Longest Prefix Match

In the table above, an address can match more than one row. An address beginning with 10101100 fits four of the five rows. Which one wins?

The rule is called longest prefix match: among the matching rows, the one with the longest prefix is chosen. The reasoning is the amount of information. A longer prefix covers a narrower set of addresses, and is therefore a more precise statement about that set. A shorter prefix lumps a wide set together with a coarse approximation. When two statements conflict, the precise one wins.

The real point here is this: the rule is not written inside the table. The table carries only the rows; the rule that decides which row wins lives in the device’s specification. A device that reads the same set of rows with a different rule makes a different decision. The most common wrong rule is to scan the rows in the order they were written and take the first match.

The Table Is a Copy

In the Linux Network Administration and Troubleshooting course, the routing table was read as a single machine’s configuration: a file, a command’s output, a reality belonging to that machine. Here, the table is not a configuration but a copy of a shared reality — the network’s topology is one, but every device keeps its own copy of it and reads its decision from that copy.

As long as the copies agree, this distinction is invisible. It becomes visible the moment the topology changes and the copies have not yet been updated. The state in which every copy matches reality is called convergence; what is measured throughout the course is not convergence itself but the time spent not converged.

During that time, a packet has three possible fates. Reached: it arrived at its destination. Black hole: a node’s table pointed to a neighbor that no longer exists, and the packet died there. Loop: the tables sent the packet back and forth to each other, and it circled until it burned through the hop limit.

The measured network has eight nodes. Seven links form a ring, and the eighth is a chord that cuts across the ring. Because the chord short-circuits the two sides of the ring, most tables route through it; when it breaks, a large number of rows are forced to change their decision. Reality itself — the oracle — is known because we built the topology ourselves: it is the first hop of the shortest path from each node to every destination.

The measurement’s assumptions:

• RT1 — The network has eight nodes and nine links; seven links form the ring, and the ninth is the chord that cuts across it. The oracle is known because we built the topology ourselves.
• RT2 — The oracle is the first hop of the shortest path from each node to every destination, and it is not changed during the measurement. Reality is always the shortest path.
• RT3 — The measured break is only the loss of the chord: one link drops, there is no node loss, and the network does not partition. After the break, every destination still has a path.
• RT4 — Forty source–destination pairs are generated from a fixed seed. The same pair can come up more than once, and the measurement counts each recurrence as a separate packet.
• RT5 — The hop limit is 12; a packet that burns through it is counted as a loop. In an eight-node network, the longest loop-free path is seven hops, well below the limit.
• RT6 — In the prefix measurement, the address is eight bits wide and the entire space is scanned; no sample is chosen. Table rows stay in the order they were written.
• RT7 — The set’s resolution is the measurement band’s floor: in a set of forty packets, the smallest measurable difference is 1/40 = 0.025; in the address space, 1/256.

Same Table, Two Rules

First the rule itself is measured. The six-row table above is read with two different rules, and the entire eight-bit address space is scanned.

"""Longest prefix match: same table, two reading rules.

Rows stay in the order they were written, not sorted by length; the
entire eight-bit address space is scanned, no example is picked.
"""
TABLE = [("1010", "north"), ("10110", "west"), ("101011", "east"),
         ("", "central"), ("10101100", "local"), ("10100", "south")]
NODES = ("north", "south", "east", "west", "central", "local")
ADDRESSES = [format(a, "08b") for a in range(256)]


def longest_prefix(address):
    chosen = None
    for prefix, node in TABLE:
        if address.startswith(prefix) and (chosen is None or len(prefix) > len(chosen[0])):
            chosen = (prefix, node)
    return chosen


def first_match(address):
    for prefix, node in TABLE:
        if address.startswith(prefix):
            return (prefix, node)
    return None


diverging = [a for a in ADDRESSES if longest_prefix(a)[1] != first_match(a)[1]]
print(f"table rows {len(TABLE)} | address space {len(ADDRESSES)} | "
      f"addresses where the two rules diverge {len(diverging)}")
print()
print(f"{'next hop':>18s} {'longest prefix':>14s} {'first match':>12s}")
for node in NODES:
    print(f"{node:>18s} {sum(longest_prefix(a)[1] == node for a in ADDRESSES):14d}"
          f" {sum(first_match(a)[1] == node for a in ADDRESSES):12d}")
print()
for a in (diverging[0], diverging[8], diverging[11]):
    u, i = longest_prefix(a), first_match(a)
    print(f"  {a} -> longest prefix {u[1]} ({u[0]}), first match {i[1]} ({i[0]})")

table rows 6 | address space 256 | addresses where the two rules diverge 12

          next hop longest prefix  first match
             north              4           16
             south              8            0
              east              3            0
              west              8            8
           central            232          232
             local              1            0

  10100000 -> longest prefix south (10100), first match north (1010)
  10101100 -> longest prefix local (10101100), first match north (1010)
  10101111 -> longest prefix east (101011), first match north (1010)

The two rules diverge on 12 of the 256 addresses. The divergence runs one way: a device reading by row order sends 16 addresses to north, one reading by longest prefix sends 4. Of the twelve addresses in between, eight should have gone to south, three to east, one to local. The central column is 232 in both: the default route remains the last resort in both rules, because for addresses that match no longer prefix, it is the only match.

The 8 in the west column is also the same in both, and this is not a coincidence: the prefix 10110 overlaps with no shorter prefix, and no other row in the table contains it. Divergence is born only from nested prefixes. If the table had no nesting, the two rules would give the same decision, and the rule would not need to be written into the specification at all.

Before and After the Break

Now the rule is held fixed and the table changes. Three generations are placed side by side: tables converged with no break, tables that are still stale at the moment of the break, and tables converged again after the break. The same forty packets are run through all three between the same pairs.

"""The table is a copy: same rule, three table generations.

Eight nodes, a chord that cuts the ring; the measured break is that
chord's loss.
"""
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):
    """The first hop of the shortest path from each node to each destination."""
    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):
    """Runs the packet through the tables; returns its fate, hop count, and where it died."""
    k, u, crossed, hop = neighbors(links), source, [], 0
    while u != dest:
        if hop >= HOP_LIMIT:
            return "loop", hop, u
        nxt = tables.get((u, dest))
        if nxt is None or nxt not in k[u]:
            return "black hole", hop, u
        if (u, nxt) in crossed:
            return "loop", hop, u
        crossed.append((u, nxt))
        u, hop = nxt, hop + 1
    return "reached", hop, None


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


old, new = oracle(LINKS), oracle(BROKEN)
print(f"nodes {len(NODES)} | links {len(LINKS)} | table rows {len(old)} | "
      f"measured pairs {len(pairs())} | hop limit {HOP_LIMIT}")
print()
print(f"{'table generation':<27s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} {'hops':>5s}")
for name, tab, links in (("converged, no break", old, LINKS),
                          ("at break, tables stale", old, BROKEN),
                          ("after break, converged", new, BROKEN)):
    s, h = measure(tab, links)
    print(f"{name:<27s} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d} {h:5d}")
print()
changed = sum(1 for key in old if old[key] != new[key])
print(f"rows whose decision must change after the break: {changed}/{len(old)}")
died = {}
for x, y in pairs():
    fate, _, node = forward(x, y, old, BROKEN)
    if fate != "reached":
        died[node] = died.get(node, 0) + 1
print("node where the packet died:", dict(sorted(died.items())))

nodes 8 | links 9 | table rows 56 | measured pairs 40 | hop limit 12

table generation            reached   loop  black hole  hops
converged, no break              40      0           0    83
at break, tables stale           26      0          14    61
after break, converged           40      0           0    99

rows whose decision must change after the break: 11/56
node where the packet died: {'b': 6, 'f': 8}

Reading the Break

The three rows say three separate things.

In the converged network, all forty of the forty packets reach their destination, in a total of 83 hops. This is the state where the tables agree with reality, and it is the measurement’s baseline. The bottom row gives the same result after the break: again 40/40, but with 99 hops. Once the chord is gone, paths get longer; that is the sixteen-hop difference. What the network loses is not connectivity but shortness — no packet is lost.

The middle row is the time in between. While the tables still point at the chord, 26 packets reach their destination and 14 fall into a black hole. That fourteen is a measurable share: 0.350 of the set of forty packets, fourteen times the band’s floor.

The total hop count dropping to 61 here looks like an improvement at first glance, and that is exactly why it needs attention. Hops went down because a third of the packets did not continue on their way: a packet that falls into a black hole dies immediately and does not spend its remaining hops. A low hop count here is not a success, it is the signature of a loss.

The last two rows say where the fault is. The number of rows whose decision must change after the break is 11; the table carries fifty-six rows, so the large majority of rows stay correct. And yet fourteen packets die. The reason is that every dying packet dies at one of two nodes: six at b, eight at f. These are the two ends of the broken chord.

What follows from this is the course’s axis. A packet’s fate does not depend on the correctness of the table at the node it leaves from. The source node’s row can be correct; the packet, along the way, passes through a node whose table is wrong and dies there. Along the chain of decisions, it is the oldest copy that determines the outcome.

Summary

• The routing decision’s input is the packet’s destination address, its output is the next hop; the router knows not the whole path but only one hop.
• The decision is made by looking not at what the message says but at the device’s own table; the rule that determines the decision lives in the specification, not the table.
• Longest prefix match chooses the narrowest set among the matching rows; a rule that reads by row order gives a different decision on 12 of the 256 addresses in the same table, and the divergence is born only from nested prefixes.
• The table is not a configuration but a copy of a shared reality; in a converged network, all forty of the forty packets reach their destination, in 83 hops before the break and 99 after.
• At the moment of the break, with stale tables, 26 packets reach their destination and 14 fall into a black hole; the drop in hops to 61 is not a gain, it is dying packets not spending hops.
• Only 11 of the fifty-six rows are wrong, but all fourteen dying packets die at the two ends of the broken link: what determines the fate is not the source’s copy but the oldest copy along the path.

Next Step

In this measurement, the tables were built by hand twice: once from the reality before the break, once from the reality after it. Nobody made the transition in between — the second-generation table was handed to the measurement already made. In a real network, someone has to make that transition, and there are two options: an administrator writes the table, or the devices tell each other. The next lesson puts these two options side by side and asks: when does a hand-written table learn about a break, and what does the black-hole count do over time?