Overlay Networks

The previous lesson moved the decision to the edge, but the path still ran over the network’s own links: a labeled packet going from b to c genuinely used the b–c link. The label named the path, and the path it named was physical.

This lesson’s question is: what would happen if the link between two nodes were not a physical link but a logical one, built over another network? Then there would not be one table but two tables, the two would converge separately, and the packet’s fate would be tied to both of them agreeing. This is the most extreme form of the course’s axis of measurement.

Overlay and Underlay

An overlay network is a logical topology built with tunnels. A link in the overlay does not mean there is a direct cable between two nodes; it means those two nodes count each other as neighbors. The real set of links the overlay stands on is called the underlay. (Subnet on its own is reserved for the concept that divides an address block; the concept here is named the underlay, and the two are not to be confused.)

The Containers course built container networks’ overlay; that procedure is not repeated here. Here, the overlay is measured as a logical topology: it has its own table, its own neighborhood, its own convergence, and its own hop counter.

# taught transcript, not run

overlay link   path in the underlay   meaning
  a-c            a-b-c                   a and c are neighbors in the overlay
  a-e            a-b-f-e                 a and e are neighbors in the overlay
  c-f            c-b-f                   c and f are neighbors in the overlay

tunneled packet
  outer header   source a   dest c   <- only the underlay reads this
  inner header   source a   dest g   <- only the overlay reads this
  payload        ...

node a's two tables
  overlay table                underlay table
  dest   next hop               dest   next hop
  g      e                      c      b
  d      d                      e      b

The two tables on the right are the whole lesson. Node a’s overlay points to e for destination g; e is a neighbor in the overlay but three hops away in the underlay. As the packet leaves a, it goes to b according to the underlay table, and the overlay never sees this at all. The two tables are inside the same device, and neither reads the other.

This has a direct consequence: one overlay hop is several hops in the underlay. The two layers’ counters are separate, and they have to be counted separately.

The measurement’s assumptions:

• RT81 — The underlay is the same throughout the course: eight nodes, the a–b–c–d–e–f–g–h–a ring, and the b–f chord that cuts the ring.
• RT82 — The overlay is built from nine tunnels, and none of the tunnels is the same as an underlay link; every tunnel corresponds to a path of between two and four hops in the underlay.
• RT83 — The two layers’ tables are computed separately and do not see each other. The rule is the same in both: the first hop of the shortest path to every destination. The oracle is not changed.
• RT84 — Every layer has its own hop counter, and the limit for both is 12. Underlay hops spent inside one overlay hop are not added to the overlay counter.
• RT85 — An overlay hop is counted as taken only if the tunnel was delivered in the underlay; if the tunnel cannot be delivered, the packet’s fate is the tunnel’s fate.
• RT86 — In the last two regimes, the overlay link that drops is the a–c tunnel. In the fourth, only a and c hear about the drop; the other seven nodes keep their old overlay table.
• RT87 — In the last two regimes, the underlay’s table is the oracle itself: there is not a single wrong decision in the underlay, and not a single tunnel is undeliverable.
• RT88 — The forty source–destination pairs come from the course’s core generator, each occurrence is a separate packet, and the set’s resolution is 1/40 = 0.025.

Measurement

"""Overlay network: when the overlay's table and the underlay's table disagree."""
SEED = 20260810
NODES = "abcdefgh"
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")]
OVERLAY = [("a", "c"), ("a", "d"), ("a", "e"), ("b", "d"), ("b", "g"),
           ("c", "f"), ("d", "h"), ("e", "g"), ("f", "h")]
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 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 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 for every node to every destination."""
    kom, t = neighbors(links), {}
    for source in NODES:
        prev, frontier, seen = {}, [source], {source}
        while frontier:
            nxt = []
            for u in frontier:
                for v in sorted(kom[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]
            t[(source, dest)] = step
    return t


def forward(source, dest, t, links):
    """Runs a single layer; returns the fate and the hops it took."""
    kom, u, crossed, hop = neighbors(links), source, [], 0
    while u != dest:
        if hop >= HOP_LIMIT:
            return "loop", hop
        s = t.get((u, dest))
        if s is None or s not in kom[u]:
            return "black hole", hop
        if (u, s) in crossed:
            return "loop", hop
        crossed.append((u, s))
        u, hop = s, hop + 1
    return "reached", hop


def overlay_forward(source, dest, over, over_links, under, under_links):
    """Every overlay hop is a tunnel, and it is also run in the underlay."""
    kom, u, crossed, over_hop, under_hop = neighbors(over_links), source, [], 0, 0
    while u != dest:
        if over_hop >= HOP_LIMIT:
            return "overlay loop", over_hop, under_hop
        s = over.get((u, dest))
        if s is None or s not in kom[u]:
            return "overlay black hole", over_hop, under_hop
        if (u, s) in crossed:
            return "overlay loop", over_hop, under_hop
        fate, a = forward(u, s, under, under_links)
        under_hop += a
        if fate != "reached":
            return "tunnel " + fate, over_hop, under_hop
        crossed.append((u, s))
        u, over_hop = s, over_hop + 1
    return "reached", over_hop, under_hop


def partial(old, new, informed):
    """Only the informed set has heard that the overlay link came down."""
    return {(u, h): (new if u in informed else old)[(u, h)]
            for (u, h) in old if (u, h) in new}


def measure(over, over_links, under, under_links):
    tally = {"reached": 0, "overlay loop": 0, "overlay black hole": 0,
             "tunnel black hole": 0, "tunnel loop": 0}
    oa = ua = 0
    for x, y in pairs():
        fate, o_, a_ = overlay_forward(x, y, over, over_links, under, under_links)
        tally[fate] += 1
        oa += o_
        ua += a_
    return tally, oa, ua


UP, DOWN, DOWN_NEW = oracle(OVERLAY), oracle(LINKS), oracle(BROKEN)
MISSING = [b for b in OVERLAY if b != ("a", "c")]
UP_MISSING = oracle(MISSING)
REGIME = (("both layers converged", UP, OVERLAY, DOWN, LINKS),
          ("underlay broke, converged", UP, OVERLAY, DOWN_NEW, BROKEN),
          ("underlay broke, table stale", UP, OVERLAY, DOWN, BROKEN),
          ("tunnel dropped, two ends heard",
           partial(UP, UP_MISSING, {"a", "c"}), MISSING, DOWN, LINKS),
          ("tunnel dropped, everybody heard", UP_MISSING, MISSING, DOWN, LINKS),
          ("both layers stale",
           partial(UP, UP_MISSING, {"a", "c"}), MISSING, DOWN, BROKEN))
RESULT = [(name, measure(over, ol, under, ul)) for name, over, ol, under, ul in REGIME]

print(f"{'regime':<32s} {'reached':>7s} {'overlay loop':>16s} "
      f"{'tunnel black hole':>18s}")
for name, (s, oa, ua) in RESULT:
    print(f"{name:<32s} {s['reached']:7d} {s['overlay loop']:16d} "
          f"{s['tunnel black hole']:18d}")

print()
print(f"{'regime':<32s} {'overlay hops':>14s} {'underlay hops':>20s}")
for name, (s, oa, ua) in RESULT:
    print(f"{name:<32s} {oa:14d} {ua:20d}")

print()
print("a tunnel's length in the underlay")
print(f"{'tunnel':>6s} {'converged':>11s} {'after break':>14s} {'with old table':>15s}")
for x, y in OVERLAY:
    _, a0 = forward(x, y, DOWN, LINKS)
    k1, a1 = forward(x, y, DOWN_NEW, BROKEN)
    k2, a2 = forward(x, y, DOWN, BROKEN)
    print(f"{x + '-' + y:>6s} {a0:11d} {a1:14d} "
          f"{('black hole' if k2 != 'reached' else str(a2)):>15s}")

regime                           reached     overlay loop  tunnel black hole
both layers converged                 40                0                  0
underlay broke, converged             40                0                  0
underlay broke, table stale           19                0                 21
tunnel dropped, two ends heard        28               12                  0
tunnel dropped, everybody heard       40                0                  0
both layers stale                     17                3                 20

regime                             overlay hops        underlay hops
both layers converged                        74                  188
underlay broke, converged                    74                  211
underlay broke, table stale                  40                  124
tunnel dropped, two ends heard               77                  205
tunnel dropped, everybody heard              97                  264
both layers stale                            41                  134

a tunnel's length in the underlay
tunnel   converged    after break  with old table
   a-c           2              2               2
   a-d           3              3               3
   a-e           3              4      black hole
   b-d           2              2               2
   b-g           2              3      black hole
   c-f           2              3      black hole
   d-h           4              4               4
   e-g           2              2               2
   f-h           2              2               2

The Overlay Never Sees the Break

The first two regimes measure the chord breaking. All forty of the forty packets arrive in both regimes, and overlay hops are 74 in both. Not a single row of the overlay’s table changed; as far as the overlay is concerned, nothing happened.

Underlay hops climb from 188 to 211. The third table says where the twenty-three extra hops come from: the a-e tunnel goes from three hops to four, the b-g and c-f tunnels go from two hops each to three each. These were the tunnels using the chord; once the chord was gone, the underlay built them from the other side of the ring.

This is the overlay’s most advertised feature, and the measurement confirms it: as long as the underlay repairs itself, the overlay never sees the break at all. But the measurement gives the cost too. An observer watching the overlay cannot see the twenty-three extra hops, because nothing has changed in its own counter. The layer hides the fault, and hides the cost along with it.

Correct Table, Dead Packet

The third regime measures the same break with the underlay not yet converged. The overlay’s table still has not changed, and it is still correct; only 19 of the forty packets arrive, and 21 fall into a tunnel black hole.

The third table’s last column names three tunnels: a-e, b-g, and c-f cannot be delivered with the old underlay table. The overlay still counts these three links as standing and sends packets to them.

This is the first form of two-layer disagreement: the table above is flawless, and the packet still dies. A check that looks only at the overlay’s own metrics reports no fault at all — the overlay’s neighborhoods are complete, its paths are valid, its hop count is even lower than expected (40, because a dying packet stops spending hops). The fault is a layer below, and the layer above cannot see it.

Underlay Flawless, Overlay in a Loop

The fourth regime turns the disagreement around. In this regime, the underlay’s table is the oracle itself: there is not a single wrong decision in the underlay, and all nine of the nine tunnels are deliverable. The only thing that changes is in the overlay — the a-c tunnel has dropped, and only a and c have heard about it.

The result: 28 of the forty packets arrive, 12 enter an overlay loop. Black hole is zero. The fifth regime measures the same tunnel drop when everybody has heard about it: 40 arrive, overlay hops climb to 97, underlay hops to 264.

The course’s second claim gets paid off again here, one layer up. Partial information produces a fault more expensive than total ignorance: when everybody has heard, forty packets arrive; when only the two ends have heard, twelve packets circle in the network. And the third claim gets paid off a second time too: not a single one of the twelve packets was put into a loop by a single table. The loop is a disagreement between two overlay tables — a knows the tunnel has dropped, d does not, and sends the packet back.

The sharpest point is this: the underlay cannot see this loop. What the underlay sees is tunnel deliveries, each valid on its own. The tunnel from a to d was delivered, the tunnel from d to a was delivered too; both are correct. The loop is visible only to an eye that puts the two deliveries side by side, and the underlay has no such eye.

Both Layers at Once

The sixth regime stacks the two disagreements on top of each other: the a-c tunnel has dropped and only the two ends have heard, and at the same time the chord has broken and the underlay’s tables have gone stale. 17 of the forty packets arrive — fewer than either the underlay fault alone (19) or the overlay fault alone (28).

The real observation is in how the fates are distributed. Overlay loop drops from 12 to 3, tunnel black hole from 21 to 20. Most of the packets that would have entered a loop instead fall into a tunnel black hole and die at the very first turn: the fault below hides the fault above. An eye watching the overlay sees the loop count drop and might mistake it for an improvement. The hop counts point the same way — overlay from 77 to 41, underlay from 205 to 134. The network’s worst state is the state in which every counter looks the calmest.

Two Counters, Two Diagnoses

The counters’ separateness separates the diagnosis too. In the regime that enters a loop, the overlay spends 77 hops, the underlay 205 hops: every hop in the overlay is worth more than two and a half hops in the underlay on average, and a loop in the overlay layer grows by this factor in the underlay.

Two observers see two separate things. The counter watching the overlay sees the loop as a loop: packets are circling, the hop limit is burning through. The counter watching the underlay sees only a rise in load: there are more packets on the links than expected, and no delivery is failing. The course’s shared finding that “a loop looks like congestion” is, in a two-layer network, a finding that changes depending on which layer it is viewed from.

This is not a reason not to use overlays; it is a reason overlays cannot be used without watching both layers at once. In a single-layer network, the table and the link set stand in the same place, and a fault shows up in both at once. In three of the six overlay regimes measured, a packet dies, and each of the three has a different symptom: one only a black hole, one only a loop, one both at once.

Summary

• An overlay network is a logical topology built with tunnels; an overlay link declares a neighborhood, not a cable. The real set of links beneath it is called the underlay, and even though the two layers’ tables sit on the same device, neither reads the other.
• When the underlay repairs itself, the overlay never sees the break at all: overlay hops stay at 74, underlay hops climb from 188 to 211. The layer hides the fault, and hides the cost along with it.
• If the overlay works with its correct table before the underlay converges, 21 packets fall into a tunnel black hole; the a-e, b-g, and c-f tunnels that used the chord cannot be delivered. The table above is flawless, and the packet still dies.
• With not a single wrong decision in the underlay, the overlay tables’ partial information puts 12 packets into a loop; when everybody has heard, all forty of the forty packets arrive. The loop is a disagreement between two overlay tables, and the underlay cannot see it.
• 77 hops in the overlay are 205 hops in the underlay; the counter watching the overlay sees a loop, the counter watching the underlay sees only a rise in load.
• When both layers go stale at once, reached packets drop to 17, but loop drops to 3: the black hole below hides the loop above, and the worst state looks the calmest in the counters.

Next Step

Up to this point, the topology was given in every measurement. Eight nodes, nine links, and a chord cutting the ring were laid down from the start; what was measured was always the response given to it — which table converges in how many rounds, how much a given policy lengthens the path, which layer sees the break. The topology itself was never questioned. But the topology is a choice too: which node connects to which, how many backup paths are left, how many nodes’ tables a break will change are all decided when the network is laid out. The next topic measures this choice and shows that the choice directly touches the convergence round.