--- title: 'Overlay Networks' source: 'https://academia.sh/en/courses/switching-and-routing/overlay-networks' course: 'Switching and Routing' language: en updated: '2026-08-17T18:07:20+00:00' license: 'CC BY-SA 4.0' --- # Overlay Networks A logical topology built with tunnels keeps its own table and never sees the table beneath it: when the underlay breaks, not a single row of the overlay's table changes, but the underlay's hops climb from 188 to 211; when the underlay's tables go stale, 21 packets die even though the overlay's table is correct; and the overlay tables' partial information puts 12 packets into a loop with not a single wrong decision in the underlay. 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. ```text # 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 ```python """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.