Spine–Leaf Design

The previous lesson measured three designs on the same nine access switches and left an inconsistency in the three-layer design: the hop count between the same two endpoints depended on which block they fell into. A packet inside a block spent two hops, a packet between blocks spent four. The layered design’s implicit assumption was that most traffic flows upward — leaving the host and crossing out of the network, north-south traffic. When that assumption holds, the four inter-block hops are rarely paid.

The assumption does not always hold. If what a host talks to is not outside the network but another host on the same network, traffic flows sideways rather than upward. This lesson’s question is: when most traffic runs leaf to leaf, which design makes the hop count independent of where the endpoints sit, and what does that cost?

East-West Traffic

Traffic between two endpoints on the network that never leaves the network is called east-west traffic. Its counterpart is north-south traffic: flow that leaves the host, crosses the core, and exits the network.

Layered design is built for north-south traffic. A block’s distribution pair collects all of the block’s traffic and hands it to the core; the core carries it outward. In this design, east-west traffic is handled as an exception: every packet between two blocks climbs to its own distribution pair, rises to the core, descends to the other distribution pair, and reaches the leaf from there. The previous lesson’s measurement counted this as four hops.

The problem is not the hop count alone. When an intra-block packet spends two hops and an inter-block packet spends four, the cost between two endpoints depends on where they plug in. Moving a host to a different leaf changes its latency without changing who it talks to.

Spine and Leaf

Spine–leaf design removes this dependency structurally. There are two kinds of device. The leaf is the switch hosts connect to. The spine only connects leaves, and no host attaches to it. There is a single rule: every leaf connects to every spine, spines do not connect to each other, and leaves do not connect to each other.

This rule has a direct consequence: every path from one leaf to another is exactly two hops — leaf, spine, leaf. No path of any other length exists, because no other link exists.

# taught transcript, not run

spine–leaf, 3 spines
  spine:  o1        o2        o3
  leaf:   y1 y2 y3 y4 y5 y6 y7 y8 y9
  rule:   every y connects to every o  (9 x 3 = 27 links)
          no o-o link, no y-y link

  paths for y3 -> y8:  y3-o1-y8   y3-o2-y8   y3-o3-y8
  all 2 hops, all equal cost

Because all three paths are equal in length, the leaf must choose one. The choice is made by the equal-cost multipath rule: the leaf keeps every equal-cost next hop toward a destination in its table and picks one for each flow. Every packet of the same flow gets the same choice. The rule that a flow is never split was established in the Link Aggregation lesson; there, the choice was among the legs of a link bundle, and here the same rule operates over a path.

The assumptions the measurement rests on:

• TD9 — The nine leaves (y1-y9) are the previous lesson’s nine access switches; the forty pairs are generated only among these. What is measured is therefore entirely east-west traffic.
• TD10 — Spine count is tried at 1, 2, 3, and 4; leaf count is fixed in every trial. As a comparison row, the previous lesson’s three-layer design is rebuilt with the same nine leaves.
• TD11 — The oracle gives all of the first hops of the shortest path for every destination; equal-cost paths are not reduced to one.
• TD12 — Flow selection is made by the remainder of the flow number divided by the number of equal-cost candidates. In a real deployment, the choice is made by hashing header fields; what matters for the measurement is that the choice is constant per flow and spread evenly across the paths.
• TD13 — Every link costs one; what is measured is hops.
• TD14 — The “single-path row” count counts one record per destination, the “multi-path row” count counts a separate record for each equal-cost next hop. The two are two accountings of the same table.
• TD15 — The break is applied the same way in every design: a leaf’s link to the first spine is cut (y7-o1). In the three-layer design, the counterpart is the same leaf’s distribution link (d5-y7).
• TD16 — In a set of forty packets, the smallest measurable difference is 1/40 = 0.025; the hop limit is 12.

The Measurement

"""Spine-leaf design: the constancy of the leaf-to-leaf hop and its cost in table rows.

Part 1 - hops, links, and table rows as spine count changes.
Part 2 - the moment of failure and the converged state when a leaf-spine link breaks.
"""
SEED = 20260810
HOP_LIMIT = 12
LEAF = [f"y{i}" for i in range(1, 10)]
BLOCK = {"d1": LEAF[0:3], "d2": LEAF[0:3], "d3": LEAF[3:6],
         "d4": LEAF[3:6], "d5": LEAF[6:9], "d6": LEAF[6:9]}
THREE_LAYER = (LEAF + sorted(BLOCK) + ["c1", "c2"],
               [(y, d) for d, ys in BLOCK.items() for y in ys]
               + [(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 distances(nodes, links):
    k, dist = neighbors(nodes, links), {}
    for source in nodes:
        seen, front, d = {source}, [source], 0
        dist[(source, source)] = 0
        while front:
            d, new = d + 1, []
            for u in front:
                for v in sorted(k[u]):
                    if v not in seen:
                        seen.add(v)
                        dist[(source, v)] = d
                        new.append(v)
            front = new
    return dist


def oracle(nodes, links):
    """All (equal-cost) first hops of the shortest path, for every destination."""
    k, dist, table = neighbors(nodes, links), distances(nodes, links), {}
    for u in nodes:
        for h in nodes:
            if u == h or (u, h) not in dist:
                continue
            table[(u, h)] = [v for v in sorted(k[u])
                              if dist.get((v, h), 99) == dist[(u, h)] - 1]
    return table


def forward(flow, source, dest, tables, nodes, links):
    """One of the equal-cost paths is chosen by the flow number."""
    k, u, crossed, hops = neighbors(nodes, links), source, [], 0
    while u != dest:
        if hops >= HOP_LIMIT:
            return "loop", hops
        candidates = [v for v in tables.get((u, dest), []) if v in k[u]]
        if not candidates:
            return "black hole", hops
        nxt = candidates[flow % len(candidates)]
        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 = LEAF[rand(9)], LEAF[rand(9)]
        if x != y:
            out.append((x, y))
    return out


def measure(tables, nodes, links):
    counts, hops, lengths = {"reached": 0, "loop": 0, "black hole": 0}, 0, []
    for i, (x, y) in enumerate(pairs()):
        fate, a = forward(i, x, y, tables, nodes, links)
        counts[fate] += 1
        hops += a
        if fate == "reached":
            lengths.append(a)
    return counts, hops, (min(lengths), max(lengths)) if lengths else (0, 0)


def max_load(tables, nodes, links):
    """How many of the forty flows use each link; the busiest link's count."""
    k, count = neighbors(nodes, links), {}
    for i, (x, y) in enumerate(pairs()):
        u, hops = x, 0
        while u != y and hops < HOP_LIMIT:
            candidates = [v for v in tables.get((u, y), []) if v in k[u]]
            if not candidates:
                break
            v = candidates[i % len(candidates)]
            link = tuple(sorted((u, v)))
            count[link] = count.get(link, 0) + 1
            u, hops = v, hops + 1
    return max(count.values())


def spine_leaf(spines):
    s = [f"o{i}" for i in range(1, spines + 1)]
    return LEAF + s, [(y, sp) for y in LEAF for sp in s]


DESIGN = {f"spine–leaf, {s} spine{'s' if s != 1 else ''}": spine_leaf(s) for s in (1, 2, 3, 4)}
DESIGN["three-layer (lesson 01)"] = THREE_LAYER

print(f"{'design':<26s} {'nodes':>5s} {'links':>5s} {'reached':>7s} {'hops':>5s} "
      f"{'range':>6s} {'busiest link':>12s} {'single-path':>11s} {'multi-path':>10s}")
for name, (D, B) in DESIGN.items():
    t = oracle(D, B)
    s, a, (mn, mx) = measure(t, D, B)
    print(f"{name:<26s} {len(D):5d} {len(B):5d} {s['reached']:7d} {a:5d} "
          f"{f'{mn}–{mx}':>6s} {max_load(t, D, B):12d} {len(t):11d} "
          f"{sum(len(v) for v in t.values()):10d}")

print()
print(f"{'design':<26s} {'cut':>7s} {'at failure':>18s} {'converged':>18s} "
      f"{'hops':>5s}")
print(f"{'':<26s} {'':>7s} {'reached black hole':>18s} {'reached black hole':>18s}")
for name, (D, B) in DESIGN.items():
    cut = ("y7", "o1") if "spine" in name else ("d5", "y7")
    remaining = [b for b in B if tuple(sorted(b)) != tuple(sorted(cut))]
    old, new = oracle(D, B), oracle(D, remaining)
    s0 = measure(old, D, remaining)[0]
    s1, a1, _ = measure(new, D, remaining)
    print(f"{name:<26s} {cut[0] + '–' + cut[1]:>7s} {s0['reached']:11d}"
          f"{s0['black hole']:7d} {s1['reached']:11d}{s1['black hole']:7d} {a1:5d}")

design                     nodes links reached  hops  range busiest link single-path multi-path
spine–leaf, 1 spine           10     9      40    80    2–2           14          90         90
spine–leaf, 2 spines          11    18      40    80    2–2            9         110        198
spine–leaf, 3 spines          12    27      40    80    2–2            6         132        324
spine–leaf, 4 spines          13    36      40    80    2–2            5         156        468
three-layer (lesson 01)       17    31      40   138    2–4           11         272        500

design                         cut         at failure          converged  hops
                                   reached black hole reached black hole
spine–leaf, 1 spine          y7–o1          26     14          26     14    52
spine–leaf, 2 spines         y7–o1          38      2          40      0    80
spine–leaf, 3 spines         y7–o1          38      2          40      0    80
spine–leaf, 4 spines         y7–o1          39      1          40      0    80
three-layer (lesson 01)      d5–y7          38      2          40      0   138

The Hop Is Constant

The range column reads 2–2 in all four spine–leaf rows: the shortest and the longest of the forty packets are both two hops. Total hops are 80 in all four designs, and this never changes with spine count.

This constancy holds in three separate dimensions, and all three can be read from the table. Independent of the leaf pair: the forty pairs were generated among nine leaves, and none of them found a path longer than two hops. Independent of spine count: going from one spine to four, link count rose from nine to thirty-six, and the hop count stayed the same. Independent of the break: in the bottom table, after y7–o1 is cut, the converged hop total is again 80.

The comparison row shows the difference. The three-layer design carries the same forty packets in 138 hops, with a range of 2–4. The entire 58-hop gap comes from inter-block traffic climbing to the core. For east-west traffic, the layered design is not only slower, it is unpredictable: its cost is determined by which block the endpoints fall into.

The source of this constancy is not an optimization but an absence. Because spines do not connect to each other and leaves do not connect to each other, a three-hop path cannot be constructed. The design does not select the short path; it does not let the long one exist.

The Cost of Constancy Is Table Rows

The two right-hand columns show the cost, and the two must be read separately.

The single-path row count counts one record per destination: 90 with one spine, 110 with two, 132 with three, 156 with four. The increase comes from adding nodes: every new spine is itself a destination, and it adds one row to everyone’s table.

The multi-path row count is the real cost. A leaf must keep every equal-cost next hop toward a destination; with two spines, every remote destination has two records, with four spines, four. The count climbs from 90 to 468 — as spine count quadruples, rows grow 5.2 times. And the hop count never changes.

The rule is this: in a spine–leaf design, scale is paid in rows, not hops. In layered design, growth lengthens the hop count and caps the table at the block boundary; in spine–leaf, growth never changes the hop count and widens every leaf’s table. The two designs charge the same resource to two different accounts.

The comparison row favors spine–leaf here: the three-layer design holds 272 single-path and 500 multi-path rows, the two-spine design 110 and 198. The three-layer design’s excess comes from the intermediate layer’s own nodes — six distribution and two core devices, all present in each other’s tables.

What Spine Count Changes

If the hop count never changes, why build more than two spines? The answer is in the busiest link column. The link most loaded by the forty flows carries 14 flows with one spine; 9 with two, 6 with three, 5 with four. Adding a spine does not reduce latency, it reduces density — flows spread across parallel paths.

The second answer is in the bottom table. A single-spine design is not a design: when y7–o1 is cut, 14 packets fall into a black hole, and after the tables converge, 14 remain, because y7 has no other path. From two spines onward, the same break leaves 0 black holes after convergence; the 2 packets remaining at the moment of failure are the flows that had chosen o1 at that instant. With four spines, this number drops to 1: the fraction of flows using the cut link shrinks with spine count.

A caveat is necessary. The measurement counts every link’s cost as one and never accounts for bandwidth. In a real deployment, a leaf’s total downward-facing capacity can exceed its total upward-facing capacity; in that case, the busiest link column does not show flow count but where flows fail to fit. This lesson does not do that accounting; it only counts how many links a flow spreads across.

Summary

• East-west traffic is traffic that stays inside the network; layered design is built for north-south traffic and forces east-west packets to climb to the core.
• In a spine–leaf design, every leaf connects to every spine, and spines and leaves do not connect among themselves; every leaf-to-leaf path is therefore 2 hops.
• The constancy holds in three dimensions — independent of leaf pair, spine count, and break — for a total of 80 hops; the three-layer design gives 138 hops and a 2–4 range for the same forty packets.
• The cost is table rows: going from one spine to four, the single-path row count climbs from 90 to 156, and the multi-path row count from 90 to 468.
• Adding a spine reduces density, not hops — the busiest link drops from 14 flows to 5; in a single-spine design, a break permanently loses 14 packets, while from two spines onward the loss converges to 0.

Next Step

In a spine–leaf design, redundancy is structural: no single device owns a path, and the loss of a spine only changes how flows are distributed. But a host attached to a leaf sends its outbound packet not to a path but to an address — the default gateway’s address. That address sits on a single device at any moment, and when that device fails, redundancy stops being structural and turns into a failover: the address’s owner must change, and everyone must hear about the change. The next lesson counts the packet’s fate during the failover window, and measures a second time that partial information produces a loop.