--- title: 'Layered Design' source: 'https://academia.sh/en/courses/switching-and-routing/layered-design' course: 'Switching and Routing' language: en updated: '2026-08-17T18:07:21+00:00' license: 'CC BY-SA 4.0' --- # Layered Design The number of layers determines hop count and convergence rounds together: on the same nine access switches, a flat chain spends 121 hops, a two-layer design 80, and a three-layer design 138, and the link-state family converges in 7, 1, and 3 rounds respectively. Up to this point, the topology was **given**. Eight nodes, nine links, a chord cutting across the ring — these were fixed by the setup, and what was measured was the response to the topology: which family converges in how many rounds, what fate partial information produces, how an overlay's table conflicts with the one beneath it. The topology itself is also a choice. The choice determines convergence rounds, hop count, and how many rows a failure changes, all together. This lesson's question is: when the same access switches are wired into three separate arrangements, how does what the packet pays change? ## The Decision Each Layer Carries **Layered design** separates devices by role and gives each role a single decision to make. The **access layer** is where hosts connect. Its decision is local: does the frame go to one of this switch's ports, or upward? The **distribution layer** aggregates an entire building, floor, or segment; its decision sits at the block's boundary, and everything leaving the block passes through it. The **core layer** only connects blocks to one another; no host attaches to it, and its decision is the narrowest of the three. In a two-layer arrangement, distribution and core merge into the same device; this merger is called a **collapsed core** arrangement. A layerless arrangement, by contrast, is not a choice but the absence of one: each new switch plugs into the previous one, and the network grows as a chain. Three arrangements are built for the measurement. All three have **nine access switches**, and hosts connect only to them; the only thing that changes is the arrangement among them. ```text # taught transcript, not run flat chain — 1 layer access: e1 - e2 - e3 - e4 - e5 - e6 - e7 - e8 - e9 collapsed core — 2 layers core: c1 - c2 access: e1..e9, each to both c1 and c2 three-layer — 3 layers core: c1 - c2 distribution: d1 d2 | d3 d4 | d5 d6, each to both c1 and c2 access: e1 e2 e3 -> d1 d2 e4 e5 e6 -> d3 d4 e7 e8 e9 -> d5 d6 ``` ## What the Layer Promises and Does Not The rationale for layered design is often summarized as "faster," and that summary is wrong. Adding a layer **lengthens** the path: each new layer means two more devices that every inter-block packet must cross. What layering does promise is something else: a change inside one block stays inside that block. The promise is not in the **hop count**, it is in the **table and how a failure propagates**. The measurement counts both sides of the promise. The assumptions the measurement rests on: - **TD1** — All three designs share the same nine access switches, and the forty packets are generated only among these nine. What is compared is not host count but the arrangement among them. - **TD2** — The oracle is known because we build the topology ourselves, and it is the first hop of the shortest path to every destination for every node. Where paths tie in length, the order of node names decides. - **TD3** — Every link costs one; what is measured is **hops**, not bandwidth. - **TD4** — The convergence counter runs from a **cold start**: at round zero, each node knows only its own links. In the distance vector family, a round is learning a neighbor's distance array; in the link-state family, it is learning the links a neighbor knows. - **TD5** — The link that is cut is not chosen by hand: the **busiest link** carrying the shortest paths of the forty packets is found by counting. The same criterion is applied in all three designs. - **TD6** — The hop limit is 12; a packet that burns through this limit is counted as a loop. - **TD7** — A table row is a single record a node holds for one destination; row count in all three designs grows together with node count. - **TD8** — In a set of forty packets, the smallest measurable difference is 1/40 = 0.025; no smaller difference is claimed. ## The Measurement ```python """Layered design: the effect of layer count on hops and convergence rounds. Part 1 - three converged designs: hops, table rows, longest path. Part 2 - convergence rounds from a cold start. Part 3 - the packet's fate when the busiest link fails, and reconvergence. """ SEED = 20260810 HOP_LIMIT = 12 ACCESS = [f"e{i}" for i in range(1, 10)] BLOCK = {"d1": ACCESS[0:3], "d2": ACCESS[0:3], "d3": ACCESS[3:6], "d4": ACCESS[3:6], "d5": ACCESS[6:9], "d6": ACCESS[6:9]} DESIGN = { "flat chain": (ACCESS, [(f"e{i}", f"e{i + 1}") for i in range(1, 9)]), "two-layer": (ACCESS + ["c1", "c2"], [(e, c) for e in ACCESS for c in ("c1", "c2")] + [("c1", "c2")]), "three-layer": (ACCESS + sorted(BLOCK) + ["c1", "c2"], [(e, d) for d, es in BLOCK.items() for e in es] + [(d, c) for d in sorted(BLOCK) for c in ("c1", "c2")] + [("c1", "c2")]), } def make_rng(seed): state = seed % 2147483646 + 1 def rand(n): nonlocal state state = (state * 48271) % 2147483647 return state % n return rand def neighbors(nodes, 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(nodes, links): """First hop of the shortest path to every destination, for every node.""" k, table = neighbors(nodes, links), {} for source in nodes: prev, front, seen = {}, [source], {source} while front: new = [] for u in front: for v in sorted(k[u]): if v not in seen: seen.add(v) prev[v] = u new.append(v) front = new 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, nodes, links): k, u, crossed, hops = neighbors(nodes, links), source, [], 0 while u != dest: if hops >= HOP_LIMIT: return "loop", hops nxt = tables.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hops if (u, nxt) in crossed: return "loop", hops crossed.append((u, nxt)) u, hops = nxt, hops + 1 return "reached", hops def pairs(count=40, seed=SEED): rand, out = make_rng(seed), [] while len(out) < count: x, y = ACCESS[rand(9)], ACCESS[rand(9)] if x != y: out.append((x, y)) return out def measure(tables, nodes, links): counts, hops, longest = {"reached": 0, "loop": 0, "black hole": 0}, 0, 0 for x, y in pairs(): fate, a = forward(x, y, tables, nodes, links) counts[fate] += 1 hops += a if fate == "reached": longest = max(longest, a) return counts, hops, longest def distance_vector(nodes, links, rounds): """Each round a node learns only its neighbor's distance array.""" k = neighbors(nodes, 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(nodes, links, rounds): """Over rounds the topology is carried; a node with the full topology computes correctly.""" k = neighbors(nodes, links) known = {u: {tuple(sorted((u, v))) for v in k[u]} for u in nodes} for _ in range(rounds): 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: seen = sorted({x for b in known[u] for x in b}) for (x, h), step in oracle(seen, sorted(known[u])).items(): if x == u: tables[(u, h)] = step return tables def busiest_link(nodes, links): t, count = oracle(nodes, links), {} for x, y in pairs(): u = x while u != y: v = t[(u, y)] count[tuple(sorted((u, v)))] = count.get(tuple(sorted((u, v))), 0) + 1 u = v return max(count, key=count.get) print(f"{'design':<14s} {'layers':>6s} {'nodes':>5s} {'links':>5s} " f"{'table rows':>10s} {'reached':>7s} {'hops':>5s} {'longest':>7s}") for i, (name, (D, B)) in enumerate(DESIGN.items()): t = oracle(D, B) s, a, u = measure(t, D, B) print(f"{name:<14s} {i + 1:6d} {len(D):5d} {len(B):5d} {len(t):10d} " f"{s['reached']:7d} {a:5d} {u:7d}") print() print(f"{'round':>5s}" + "".join(f"{name:>17s}" for name in DESIGN)) print(f"{'':>5s}" + f"{'dv ls':>17s}" * 3) for rnd in range(0, 9): row = f"{rnd:5d}" for name, (D, B) in DESIGN.items(): dv = measure(distance_vector(D, B, rnd), D, B)[0]["reached"] ls = measure(link_state(D, B, rnd), D, B)[0]["reached"] row += f"{dv:12d}{ls:5d}" print(row) print() print(f"{'design':<14s} {'cut':>9s} {'at failure':>18s} " f"{'converged':>18s} {'dv/ls rounds':>12s} {'rows changed':>13s}") print(f"{'':<14s} {'':>9s} {'reached black hole':>18s} {'reached black hole':>18s}") for name, (D, B) in DESIGN.items(): cut = busiest_link(D, B) remaining = [b for b in B if tuple(sorted(b)) != cut] old, new = oracle(D, B), oracle(D, remaining) s0 = measure(old, D, remaining)[0] s1 = measure(new, D, remaining)[0] round_ls = next(t for t in range(12) if measure(link_state(D, remaining, t), D, remaining)[0] == s1) round_dv = next(t for t in range(12) if measure(distance_vector(D, remaining, t), D, remaining)[0] == s1) changed = sum(1 for a in old if a in new and old[a] != new[a]) print(f"{name:<14s} {cut[0] + '-' + cut[1]:>9s} {s0['reached']:11d}" f"{s0['black hole']:7d} {s1['reached']:11d}{s1['black hole']:7d} " f"{f'{round_dv}/{round_ls}':>12s} {f'{changed}/{len(old)}':>13s}") ``` ``` design layers nodes links table rows reached hops longest flat chain 1 9 8 72 40 121 8 two-layer 2 11 19 110 40 80 2 three-layer 3 17 31 272 40 138 4 round flat chain two-layer three-layer dv ls dv ls dv ls 0 0 13 0 0 0 0 1 13 22 0 40 0 11 2 22 26 40 40 11 11 3 26 29 40 40 11 40 4 29 34 40 40 40 40 5 34 37 40 40 40 40 6 37 38 40 40 40 40 7 38 40 40 40 40 40 8 40 40 40 40 40 40 design cut at failure converged dv/ls rounds rows changed reached black hole reached black hole flat chain e5-e6 19 21 19 21 3/2 0/72 two-layer c1-e7 26 14 40 0 2/1 18/110 three-layer c1-d3 20 20 40 0 4/3 24/272 ``` ## Hop Count Does Not Grow With Layers The top table directly shows what the layer does not promise. The **two-layer** design carries the forty packets in **80** hops, and the longest path is **2**: every packet goes up and comes back down, and that is all. The **three-layer** design spends **138** hops on the same forty packets, and the longest path climbs to **4**. The third layer adds **58 hops** on top of the two-layer design. What is surprising is the top row: the **flat chain finishes in 121 hops** and spends **fewer** hops than the three-layer design. The reason is in the distribution: in a chain, a packet between neighboring switches arrives in a single hop, and thirteen of the forty packets do exactly that. The chain's longest path is **8** hops, twice the three-layer design's worst case; what keeps the total hop count low is not the worst case but the cheap nearby neighbors. The rule that follows is this: **layer count does not improve hop count.** The two-layer design's 80 is a lower bound, because there are already at least two hops between any two access switches. A third layer can only make this number grow. ## Convergence Rounds Shrink With Layers The middle table follows the same three designs from a cold start, and here the ranking reverses. In the **flat chain**, the link-state family delivers all forty of the forty packets by **round 7**, the distance vector family by **round 8**. Information crawls neighbor to neighbor along the chain: for e1 to learn about e9, the news has to cross eight links. In the **two-layer** design, the link-state family finishes at **round 1** — an access switch's neighbor is the core, and the core knows everyone, so a single round is enough to carry the whole topology. The **three-layer** design converges at **round 3**: the news has to travel from access to distribution, from distribution to core, and back down again. The round-zero row deserves its own reading. In the flat chain, the link-state family delivers **13** packets at the very first instant, because those thirteen packets' destinations are already neighbors and a node knows its own links from the start. In the two-layer and three-layer designs, the same cell is **0**: in a layered design, no access switch is another one's neighbor. This is the first cost of layering — at round zero, no packet arrives. The one-round gap between the two families persists across all three designs: the link-state family finishes **one round ahead** of the distance vector family in every design. ## What the Failure Costs The bottom table cuts the busiest link, and the response of the three designs is entirely different from one another. In the **flat chain**, the link cut is `e5-e6`, and the outcome is permanent: **21 packets fall into a black hole**, and the count stays at **21** even after the tables converge. There is no alternate path in a chain; the failure splits the network into two pieces, and computing a correct table does nothing. The changed-row count of **0/72** says exactly this: there is no new path to compute. This is where the chain's cheap hop count ends. In the **two-layer** design, the link cut is `c1-e7`. At the moment of failure, with the old tables, **26 packets reach, 14 fall into a black hole**; once the tables converge, this returns to **40/40** and the total hop count is again **80** — nothing is lost, because e7 has a second path through c2. The link-state family repairs this in **1 round**. The cost is that **18 of 110 rows** change. In the **three-layer** design, the link cut is `c1-d3`; at the moment of failure, **20 reach, 20 fall into a black hole**, convergence takes **3 rounds**, and the result is again **40/40**. The real difference is in the rightmost column: the changed rows are **24 of 272**, that is **9 percent**. In the two-layer design, the same ratio is **18 of 110**, that is **16 percent**. This is what the third layer buys: a failure moves **fewer rows** in a table that holds more rows, because the change stops at the block boundary. The trade-off is therefore explicit. Adding a layer adds hops, convergence rounds, and table rows; the one thing it gives in return is that **the change stays narrow**. At nine access switches, this trade-off does not justify a third layer; it does when the core has ninety-nine neighbors instead of nine. ## Summary - Layered design separates devices by role: access aggregates hosts, distribution aggregates a block, and core only connects blocks; in a two-layer design, the last two roles merge into the same device. - On the same nine access switches, a flat chain spends **121** hops, a two-layer design **80**, and a three-layer design **138**; adding a layer does **not improve** hop count. - Convergence rounds work in the opposite direction: the link-state family converges in **7** rounds in the chain, **1** in the two-layer design, and **3** in the three-layer design, and in every design it is one round ahead of the distance vector family. - In a layered design, no packet arrives at round zero; in the chain, **13** packets arrive, because their destinations are already neighbors. - When the busiest link fails, the chain **permanently** loses **21 packets**; the two-layer and three-layer designs return to **40/40**, but the changed-row ratios are **18/110** and **24/272** respectively — what the third layer buys is a change that stays narrow. ## Next Step All three designs shared an implicit assumption: a packet climbs up from access, turns somewhere, and comes back down. The forty packets' source and destination were both at access switches, but the arrangement was built around climbing up. In the three-layer design, the cost of this showed — every inter-block packet spent four hops, while intra-block ones spent two. The hop count between the same two endpoints depended on which block they fell into. The next lesson takes up the case where most traffic flows **sideways** rather than up: in an arrangement where every leaf connects to every spine, the hop count between two leaves stays constant, and what this constancy costs in table rows is counted separately.