Layered Design

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.

# 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

"""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.