Link State Protocols

All of the previous lesson’s flaws came from a single place: a node heard its neighbor’s decision, not what its neighbor saw. A number in the distance vector had been produced by adding one to a number the neighbor itself had heard from its own neighbor; which path that number passed through was lost during the compression.

The link state family reverses the trade-off. What is sent to a neighbor is not a decision but a raw fact: “this link exists, and its metric is this.” As the fact travels, it is not changed, not summarized, nothing is added to it. Every node accumulates the facts that reach it and computes the shortest path itself. This lesson’s question is how many rounds this exchange saves, and where the gain comes from.

What Is Sent to a Neighbor

In distance vector, a node sent an eight-row sequence of metrics: one number per destination. In link state, what is sent is much smaller — a node advertises only its own links.

# taught transcript, not run

node c's advertisement

  advertiser   c
  neighbor     b   metric 1
  neighbor     d   metric 1

the database accumulated in node c's hands, two rounds later

  a–b   b–c   c–d   d–e   e–f   f–g   g–h   h–a

The difference is not in the notification’s size, it is in who is speaking for whom. In distance vector, c said that h was reached in four hops — this was c’s own decision, and it contained something about h that c did not actually know. In link state, c advertises only the two links it sees itself; it says nothing about h, because it sees nothing about h.

Flooding and the Link-State Database

The advertisement does not stop at the neighbor. The receiving node passes it on to its own neighbors as is; this is the counterpart here of the flooding mechanism built in the Network Models and Protocols course. While passing it on, it does not change the advertisement, does not add to its metric, does not write its own name. As it spreads through the network, the advertisement stays the same advertisement.

Every node accumulates the incoming advertisements. What accumulates is called the link-state database, and in the end it is nothing more than the network’s list of links. Once the database is complete, the node holds the topology itself in its hands — in the form nobody has summarized, nobody has chewed.

What comes after this is a graph computation. Taking itself as the source, the node finds the shortest path to every destination and writes the path’s first hop into its table. This computation itself was established in the Graph Algorithms course of the Algorithms curriculum and is not re-derived here; what matters here is where the computation is done. In distance vector, the computation was distributed, and every node built on top of its neighbor’s computation. Here the computation is local: every node independently derives the same result from the same input.

This has a direct consequence. A wrong table can no longer come from a wrong computation — the computation is the same everywhere. A wrong table comes only from incomplete input: the database has not filled up yet. The measurement counts this incompleteness.

The Database’s Cost

This mechanism is not free, and its cost is collected in two places.

The first is size. In distance vector, what a node holds is as many rows as there are destinations; in link state, what it holds is the entire network. In the measured network, this means eight links, but as the link count grows, every node’s memory and the computation it does on every change grow with it. This is why large networks split the topology into regions and keep each region’s database within itself: the computation’s input is shrunk.

The second is freshness. Because an advertisement is carried without being changed, an old advertisement circulating in the network can get mixed up with a new one, and a node can mistake a past link for a current one. This is why every advertisement carries a sequence number and an age; when a node sees two advertisements from the same advertiser, it keeps the one with the larger number and drops the one whose age has run out. These two fields are the one mechanism that resolves the copies’ disagreement inside the protocol itself.

The measurement’s assumptions:

• RT22 — The network, the oracle, and the forty pairs are the same as in the previous lessons; the measured break is again the loss of the chord that cuts the ring, and both families are measured in the same topology.
• RT23 — In the link state family, a node’s starting information is its own links. This information is not heard from a neighbor, it is directly observed; the device at the link’s end sees its own interface.
• RT24 — A round is every node passing on the set of links it holds to all its neighbors and adding the incoming ones to its own set. The advertisement is not changed while being carried.
• RT25 — A node computes the shortest path from the set of links it holds with the same procedure as the oracle. The procedure is the same at every node; the only thing that comes out different is the input. A table that comes from incomplete input is wrong, not the procedure.
• RT26 — The distance vector side is the previous lesson’s cold-start rule: a node hears its neighbor’s metric sequence and takes only the shorter path.
• RT27 — In the carried-entries count, distance vector sends every neighbor its eight-destination sequence, link state sends the set of links it knows. The model floods every round; real protocols do not flood unless something changes, so the count is meaningful only for the convergence window.
• RT28 — The set’s resolution is 1/40 = 0.025 over forty packets.

Measurement

"""Link state: a neighbor is sent raw link facts, not a decision.

Part 1 - both families' packet fate, round by round, side by side.
Part 2 - correct rows, known links, and entries carried up to that 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 = {"reached": 0, "loop": 0, "black hole": 0}
    for x, y in pairs(count):
        tally[forward(x, y, tables, links)[0]] += 1
    return tally


def distance_vector(links, rounds):
    """A summarized metric is heard from a neighbor; only a shorter path is taken."""
    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 first


def link_state(links, rounds):
    """Raw link facts are carried unchanged; the node computes them itself."""
    k = neighbors(links)
    known = {u: {(u, v) for v in k[u]} for u in NODES}
    carried = 0
    for _ in range(rounds):
        carried += sum(len(known[u]) * len(k[u]) for u in NODES)
        new = {u: set(known[u]) for u in NODES}
        for u in NODES:
            for v in k[u]:
                new[u] |= known[v]
        known = new
    tables = {}
    for u in NODES:
        local = oracle([tuple(sorted(b)) for b in known[u]])
        for (x, h), step in local.items():
            if x == u:
                tables[(u, h)] = step
    return tables, known, carried


correct = oracle(BROKEN)
k_broken = neighbors(BROKEN)
dv_round_entries = sum(len(NODES) * len(k_broken[u]) for u in NODES)
print(f"nodes {len(NODES)} | links after break {len(BROKEN)} | table rows "
      f"{len(correct)} | measured packets {len(pairs())}")
print()
print(f"{'round':>3s} | {'distance vector: reached':>25s} {'loop':>6s} {'blk hole':>8s}"
      f" | {'link state: reached':>25s} {'loop':>6s} {'blk hole':>8s}")
for rnd in range(6):
    dv = measure(distance_vector(BROKEN, rnd), BROKEN)
    ls = measure(link_state(BROKEN, rnd)[0], BROKEN)
    print(f"{rnd:3d} | {dv['reached']:25d} {dv['loop']:6d} {dv['black hole']:8d}"
          f" | {ls['reached']:25d} {ls['loop']:6d} {ls['black hole']:8d}")

print()
print(f"{'round':>3s} {'DV correct rows':>15s} {'LS correct rows':>15s} "
      f"{'LS known links':>15s} {'LS carried':>11s} {'DV carried':>11s}")
for rnd in range(6):
    dv = distance_vector(BROKEN, rnd)
    ls, known, carried = link_state(BROKEN, rnd)
    links_known = {len({tuple(sorted(b)) for b in known[u]}) for u in NODES}
    print(f"{rnd:3d} {sum(1 for a in correct if dv.get(a) == correct[a]):12d}/56"
          f" {sum(1 for a in correct if ls.get(a) == correct[a]):12d}/56"
          f" {min(links_known):8d}/{len(BROKEN):<5d} {carried:11d} {dv_round_entries * rnd:11d}")

nodes 8 | links after break 8 | table rows 56 | measured packets 40

round |  distance vector: reached   loop blk hole |       link state: reached   loop blk hole
  0 |                         0      0       40 |                         9      0       31
  1 |                         9      0       31 |                        20      0       20
  2 |                        20      0       20 |                        32      0        8
  3 |                        32      0        8 |                        40      0        0
  4 |                        40      0        0 |                        40      0        0
  5 |                        40      0        0 |                        40      0        0

round DV correct rows LS correct rows  LS known links  LS carried  DV carried
  0            0/56           16/56        2/8               0           0
  1           16/56           32/56        4/8              32         128
  2           32/56           48/56        6/8             128         256
  3           48/56           56/56        8/8             288         384
  4           56/56           56/56        8/8             512         512
  5           56/56           56/56        8/8             768         640

Ahead in Every Round

The top table places the two families side by side in the same break, with the same forty packets. Link state reaches the correct table in three rounds, distance vector in four. And the difference is not only at the finish line: link state is ahead every round. In round zero, 9 against 0; in round one, 20 against 9; in round two, 32 against 20.

Round zero is the row that says the most. No advertisement has been sent yet, and link state still delivers 9 packets. The reason is assumption RT23: a node’s own links are not heard from a neighbor, they are seen directly. The device at the link’s end knows that link exists without a protocol. In distance vector, even this piece of information waits for a round’s notification, because there, what gets written into the table is a metric that has been heard.

The loop column is 0 from start to finish in both families. This is not a coincidence, it is the result of the cold start: both rules accept only a shorter path, and no table row points at a wrong neighbor — it points at nothing yet. A wrong direction first has to have some direction written; an empty row produces a black hole, not a loop.

Where the Difference Is

The bottom table looks for the source of the gain, and at first glance it does not give the expected answer.

The correct-rows columns advance by exactly sixteen rows per round in both families: distance vector 0, 16, 32, 48, 56; link state 16, 32, 48, 56. The rate of increase is the same. Both families advance one neighborhood hop per round, because in both, information crosses one link per round. Link state does not spread faster, and distance vector does not spread slower.

The only difference between the two sequences is their starting point. Link state’s sequence is distance vector’s sequence shifted by one round. The round gained is not gained speed, it is a gained head start.

The carried-entries columns also say the opposite of what is expected. By its own convergence round (the third), link state has carried 288 entries; by its own convergence round (the fourth), distance vector has carried 384. So the family that converges earlier has carried less information. The known-links column confirms this: the largest load a link-state node carries is eight links, and it stops there, because the entire network is eight links. Distance vector, on the other hand, resends its eight-destination sequence to every neighbor every round, and this load never shrinks.

The fourth reading follows from this: the difference is not in the amount of information, it is in how far the information is carried unread. In distance vector, the number a node knows about h has come by being recomputed at every node in between, starting from h; at every stop, an addition was made and everything before that stop was erased. In link state, h’s links arrive in the form they left h’s mouth; the nodes in between are carriers, not interpreters. Information that is not interpreted is the same information regardless of the distance it is carried.

The fifth round’s row also calls for honesty. There, the entries link state has carried climb to 768, overtaking distance vector. This is the consequence of the model constraint written in RT27: the measurement floods every round. Real protocols do not flood once converged unless something changes; the count is therefore read only for the convergence window.

Where the Two Families Both Arrive

Despite all these differences, the two families arrive at the same place. After the fourth round, both columns give 56/56 correct rows and 40/40 reached packets. The tables are not just equally correct, they are identical to each other: both are the oracle’s table.

The reason is structural. Both families search for the same thing — the shortest path. Distance vector finds it by summing its neighbors’ metrics, link state finds it by building the topology and computing it itself; but the criterion being searched for is single. A search with a single criterion has a single result, and this is why the place where the two families part ways is not the result, it is the time it takes to arrive at it and the packet’s fate during that time.

Summary

• In the link state family, a neighbor is sent not a decision but raw link information; the advertisement is not changed while being carried, and every node computes the shortest path itself.
• A wrong table cannot come from a wrong computation, because the computation is the same at every node; a wrong table comes only from incomplete input.
• The correct table is reached in three rounds, and it is ahead of distance vector every round: reached packets are 9, 20, 32, 40 against 0, 9, 20, 32. The 9 packets in round zero come from a node knowing its own links without a protocol.
• The correct-row increase is sixteen per round in both families; link state’s sequence is distance vector’s sequence shifted by one round. What is gained is not speed, it is a head start.
• At the convergence round, entries carried are 288 for link state, 384 for distance vector: the earlier-converging family carries less information. The difference is not in the amount of information, it is in how far the information is carried without being interpreted.
• Both families reach 56/56 correct rows and 40/40 reached packets after the fourth round; the tables are identical to each other, because both search for the same criterion.

Next Step

The last part’s finding is this: both families were searching for the shortest path, and both eventually arrived at the same table. Because the criterion was single, the result was single too; the entire difference between them was packed into the rounds it took to reach that result. This means the criterion itself was never questioned — shortness was taken as good without being examined. But a path is not judged by its length alone: whose network it passes through, whose link it fills, and what it costs whom are also qualities of the path. The next lesson asks: what if the shortest path is not wanted — what does the table get built on then, and is a longer path a flaw?