Distance Vector Protocols

The previous measurement did not model the news being carried: the informed set was given from outside, and an informed node arrived at the correct table instantly. In reality, what a node hears from its neighbor is not the entire topology; nobody sends its neighbor a map saying “the network is connected like this.”

The plainest protocol family hears exactly one thing from a neighbor: how many hops away the neighbor is from every destination. This family is called the distance vector family, and this lesson’s question is whether this single number is enough to build the correct table.

The One Thing Heard From a Neighbor

A node sends its neighbors a list: a metric for every destination. Here, the metric is the hop count. The list does not say who the neighbor’s neighbor is, which path is taken, or how the network is connected — it says only the distance.

# taught transcript, not run

node c's notification to its neighbors

  destination   metric
  a                  3
  b                  1
  d                  1
  e                  2
  f                  2
  g                  3
  h                  4

The node receiving the notification takes two steps. It adds one to every incoming metric — the cost of reaching the neighbor is one hop. Then it compares this to the metric in its own table and takes the smaller one; when it does, it writes that neighbor’s name into the next-hop field.

The information constraint here is the family’s definition. b, receiving c‘s notification, learns that a is reached in three hops; it does not learn which nodes are passed through to get there. This makes the computation cheap: the notification received is not the topology, it is the neighbor’s already-chewed decision. The node does not do its own computation, it adds one to its neighbor’s computation.

What Convergence Means Here

What is measured throughout the course is convergence, and this same term was also used in the Introduction to System Design course. There, what converged was copies of a data value: copies of the same record read differently for a while, eventually arrive at the same value, and what is observed is the value read. Here, what converges is not data but the routing table, and what is observed is not the value read but the packet’s fate. The term is the same, the sense is different; the two are not to be confused.

The Rule That Accepts Only Improvement

The rule’s first form is the plainest: a node changes its table only when it hears of a shorter path. If the incoming metric is larger than what it already holds, it discards the notification. This rule is intuitive and guarantees one thing for certain — the table never gets worse.

The measurement’s first part traces this rule from a cold start: no node holds anything, everybody knows only its own neighbors, and the tables fill up round by round.

The measurement’s assumptions:

• RT15 — The network, the oracle, and the forty pairs are the same as in the previous lessons. In the first and third parts, the broken link is again the chord that cuts the ring.
• RT16 — In the first part, the start is cold: every node’s distance to itself is zero, to everyone else it is 99, and there is no table row at all. What is measured is the round-by-round build-up from scratch.
• RT17 — A round is every node receiving notifications from its neighbors and updating its table once; notifications are taken as simultaneous. A round has no counterpart in seconds.
• RT18 — The metric is the hop count, and every link’s cost is one. The metric’s ceiling is 16, and an entry that reaches this ceiling is counted as unreachable; the ceiling is infinity’s finite stand-in.
• RT19 — The break measured in the second part is different: both links into node d drop at once, and d is cut off from the network. The remaining seven nodes stay connected to each other. The start in this part is not cold; it is the table converged to the pre-break reality.
• RT20 — The hold-down window is six rounds and opens only when an entry becomes unreachable; for that window, no notification is accepted for that entry.
• RT21 — The set’s resolution is 1/40 = 0.025 over forty packets. The second part’s window is twelve rounds at five packets per round; the set there is sixty packets.

Measurement

"""Distance vector: only a single number is heard from a neighbor.

Part 1 - cold start; a node accepts only a BETTER path.
Part 2 - bad news is accepted too; counting to infinity and two restrictions.
"""
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")]
ISOLATED = [b for b in LINKS if b not in (("c", "d"), ("d", "e"))]
HOP_LIMIT, INFINITY, WINDOW = 12, 16, 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 = {"reached": 0, "loop": 0, "black hole": 0}
    for x, y in pairs(count):
        tally[forward(x, y, tables, links)[0]] += 1
    return tally


def only_improve(links, rounds):
    """A neighbor's distance vector is heard; only a shorter path is accepted."""
    k = neighbors(links)
    dist = {(u, h): (0 if u == h else 99) for u in NODES for h in NODES}
    first = {}
    for _ in range(rounds):
        new_dist, new_first = dict(dist), dict(first)
        for u in NODES:
            for v in sorted(k[u]):
                for h in NODES:
                    if dist[(v, h)] + 1 < new_dist[(u, h)]:
                        new_dist[(u, h)] = dist[(v, h)] + 1
                        new_first[(u, h)] = v
        dist, first = new_dist, new_first
    return dist, first


def recompute(links, rounds, start, split_horizon=False, hold_down=0):
    """Every round, the table is rebuilt from neighbor notifications; bad news is accepted too."""
    k, trace = neighbors(links), []
    dist, first = dict(start[0]), dict(start[1])
    frozen = {key: 0 for key in dist}
    for _ in range(rounds):
        new_dist, new_first = dict(dist), dict(first)
        for u in NODES:
            for h in NODES:
                if u == h or frozen[(u, h)] > 0:
                    continue
                best, pick = (1, h) if h in k[u] else (INFINITY, None)
                for v in sorted(k[u]):
                    if split_horizon and first.get((v, h)) == u:
                        continue
                    cost = min(dist[(v, h)] + 1, INFINITY)
                    if cost < best:
                        best, pick = cost, v
                if best >= INFINITY > dist[(u, h)]:
                    frozen[(u, h)] = hold_down
                new_dist[(u, h)], new_first[(u, h)] = best, pick
        for key in frozen:
            frozen[key] = max(0, frozen[key] - 1)
        dist, first = new_dist, new_first
        trace.append((dict(dist), dict(first)))
    return trace


correct = oracle(BROKEN)
print("Part 1 -- cold start, only a shorter path is accepted")
print(f"{'round':>5s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} {'rows matching oracle':>21s}")
for rnd in range(6):
    first = only_improve(BROKEN, rnd)[1]
    s = measure(first, BROKEN)
    same = sum(1 for key in correct if first.get(key) == correct[key])
    print(f"{rnd:5d} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d}"
          f" {same:18d}/{len(correct)}")

start = only_improve(LINKS, 8)
d_targeted = [(x, y) for x, y in pairs() if y == "d"]
print()
print(f"Part 2 -- d isolated, {WINDOW}-round window, {len(d_targeted)} packets per round")
print(f"{'restriction':<28s} {'ceiling round':>13s} {'loop':>6s} {'black hole':>11s} "
      f"{'hops':>5s} {'peak metric':>11s}")
for label, sh, hd in (("none", False, 0), ("hold-down", False, 6),
                      ("split horizon", True, 0),
                      ("split horizon + hold-down", True, 6)):
    loop = black = hops = peak = 0
    ceiling = None
    for i, (dist, first) in enumerate(recompute(ISOLATED, WINDOW, start, sh, hd), 1):
        for x, y in d_targeted:
            fate, h = forward(x, y, first, ISOLATED)
            loop += fate == "loop"
            black += fate == "black hole"
            hops += h
        peak = max(peak, max(dist[(u, "d")] for u in NODES if u != "d"))
        if ceiling is None and all(dist[(u, "d")] >= INFINITY for u in NODES if u != "d"):
            ceiling = i
    print(f"{label:<28s} {ceiling if ceiling else '>' + str(WINDOW):>13} {loop:6d} "
          f"{black:11d} {hops:5d} {peak:11d}")

print()
print("Part 3 -- chord broke, every destination stays reachable")
print(f"{'restriction':<28s} {'convergence round':>18s}")
for label, sh, hd in (("none", False, 0), ("hold-down", False, 6),
                      ("split horizon", True, 0),
                      ("split horizon + hold-down", True, 6)):
    reached_round = None
    for i, (dist, first) in enumerate(recompute(BROKEN, 20, start, sh, hd), 1):
        if all(first.get(key) == correct[key] for key in correct):
            reached_round = i
            break
    print(f"{label:<28s} {reached_round if reached_round else '>20':>18}")

Part 1 -- cold start, only a shorter path is accepted
round reached   loop  black hole  rows matching oracle
    0       0      0          40                  0/56
    1       9      0          31                 16/56
    2      20      0          20                 32/56
    3      32      0           8                 48/56
    4      40      0           0                 56/56
    5      40      0           0                 56/56

Part 2 -- d isolated, 12-round window, 5 packets per round
restriction                  ceiling round   loop  black hole  hops peak metric
none                                   >12     60           0   202          13
hold-down                              >12     60           0   202          13
split horizon                          >12      5          55    59          16
split horizon + hold-down                6      5          55    41          16

Part 3 -- chord broke, every destination stays reachable
restriction                   convergence round
none                                          2
hold-down                                     2
split horizon                                 3
split horizon + hold-down                     7

Four Rounds

The first part gives the family’s basic number. From cold start, the correct table is reached in four rounds, and reached packets per round go 0, 9, 20, 32, 40.

In round zero, no packet arrives: because the table is empty, every packet dies at the first node — forty black holes. Distance vector starts the network knowing nothing at all; it has not even written who its neighbor is into the table.

In the following rounds, the number of rows matching the oracle advances as 16, 32, 48, 56: exactly sixteen rows correct themselves every round. The regularity is not a coincidence, it is the nature of the notification. In one round, information advances exactly one neighborhood hop; in the first round, one-hop destinations are written correctly, in the second, two-hop destinations. Whatever the network’s diameter is, that is the convergence round.

It is also meaningful that the reached-packet count does not grow as fast as the row count: for a packet to arrive, every row along its path has to be correct. Even when thirty-two rows are correct, eight packets still die, because those eight have a not-yet-filled row somewhere on their path.

Learning Bad News

The first part’s rule cannot do one thing: it cannot learn bad news. A node that accepts only a shorter path can never hear that a path has gotten longer or has vanished — because by definition, that news arrives with a larger metric, and the rule discards it.

This is why real protocols make a trade-off: a notification from the neighbor chosen as the next hop is accepted even when it is bad news. The trade-off is mandatory; without it, the blindness of the static regime from the previous lesson comes back.

Counting to infinity is born exactly from this trade-off. When a destination becomes unreachable, nodes hear each other’s old metric, add one, and write it; their neighbor hears theirs in turn, adds one, and writes it. The metric grows one by one round after round, and no node understands that the destination is really gone until it reaches the ceiling. This behavior is called counting to infinity.

Counting to Infinity and Two Restrictions

The second part measures this behavior. When node d is cut off from the network, under the unrestricted rule the peak metric only climbs to 13 in twelve rounds — it does not even reach the ceiling of 16. In that window, all sixty of the sixty d-targeted packets enter a loop, and 202 hops are spent. The black-hole count is 0: no packet dies, all of them circle. The reading built in the previous lesson shows up here in its purest form — the fault is not a lost packet, it is saturated links.

The first restriction is called split horizon, and it is a single rule: a node does not advertise a path to a destination back to the neighbor that is that path’s first hop. The reasoning is plain — that neighbor is already routing through it; selling its own path back to it is not information, it is an echo. The measurement confirms the gain: loop drops from 60 to 5, hops from 202 to 59. Black hole climbs to 55, meaning most packets now die immediately instead of circling.

This is not a loss. In both fates the packet fails to reach its destination, but one dies in one hop, the other spends twelve hops of network resources; the drop in the hops column measures this.

Split horizon still is not enough. The ceiling round column says it is still not complete at twelve rounds: it cuts two-node loops, but not the longer loops the ring forms. A node reaches the ceiling, then hears an old metric from a neighbor that has not reached it yet and drops back down.

The second restriction is this hold-down: when an entry becomes unreachable, the node freezes that entry for a window and accepts no notification for that destination during it. Over the window, the neighbors’ stale metrics filter out. Its effect in the measurement is clean: the round the ceiling is reached is 6, and hops drop from 59 to 41.

But hold-down by itself does nothing — the second row is identical to the unrestricted row: 60 loop, 202 hops. The reason is that hold-down opens only when an entry becomes unreachable, and under the unrestricted rule no entry ever reaches the ceiling, so the window never opens. There is no restriction whose trigger never fires.

The third part gives the cost. In an ordinary break where destinations stay reachable, the unrestricted rule converges in 2 rounds, split horizon in 3, and the two together in 7. Hold-down hurts twice here: split horizon temporarily shows an entry as unreachable, and hold-down mistakes this temporary state for true and freezes it for six rounds. Every restriction that speeds up bad news slows down good news.

Summary

• In the distance vector family, a node hears from its neighbor only a sequence of metrics; it does not learn the topology, it learns its neighbor’s already-made decision and adds one to it.
• From cold start, the correct table is reached in four rounds; reached packets per round are 0, 9, 20, 32, 40, correct rows are 0, 16, 32, 48, 56 — every round advances one neighborhood hop.
• A rule that accepts only a shorter path cannot learn bad news; the trade-off made to learn it gives rise to counting to infinity.
• When a destination becomes unreachable, under the unrestricted rule, all sixty of the sixty packets in a twelve-round window enter a loop, 202 hops are spent, and the metric does not even reach the ceiling.
• Split horizon brings loop down to 5 and hops to 59; when hold-down is added, the ceiling is reached in round 6 and hops drop to 41, but hold-down by itself does nothing because its trigger never fires.
• The restrictions’ cost is paid in an ordinary break: the convergence round climbs from 2 to 3, and to 7 when both are combined.

Next Step

All these flaws have a single source: a node hears its neighbor’s decision, not what its neighbor sees. Because the metric is compressed into a single number, which path that number summarizes is lost; the node cannot tell whether its own name appears inside that path, and the restrictions try to patch this ignorance from the outside. The next lesson reverses the trade-off: if neighbors send each other not a decision but raw link information, and every node computes the shortest path itself, how many rounds does it take to converge?