Interconnection Networks

Once you accept that the future is many cores — dozens on a chip, thousands in a rack, millions in a datacenter — a new question dominates everything: how do they talk to each other? A processor that cannot get data to its neighbours is a very expensive space heater. The wires, switches and routers that move data between cores, caches, chips and machines are the interconnection network, and at scale the network, not the arithmetic, is what decides whether a design flies or dies.

The same theory spans two very different scales. Inside a chip, a Network-on-Chip (NoC) routes packets between tens of cores over millimetres of copper. Across a building, a system network routes between thousands of servers over kilometres of fibre. The vocabulary — topology, latency, bandwidth, routing, flow control — is identical; only the constants change. Master it once and you can reason about both.

The shape of the network: topology

The topology is the wiring diagram — who is directly connected to whom. It fixes the network's cost and, before a single packet moves, its best-case performance. Reveal the four classics one at a time:

A bus is one shared wire: dead cheap, but only one message travels at a time, so it chokes the instant you add nodes. A ring gives each node two neighbours; better, but a message may crawl halfway around the loop. A mesh lays nodes on a grid with short links to their four neighbours — the workhorse of on-chip networks. A torus is a mesh whose edges wrap around, so the grid becomes a doughnut with no far corners, cutting the worst-case distance roughly in half. Two more you can't draw as tidily: the crossbar, which wires every input to every output (fast but O(N^2) switches), and the fat-tree, the tree-of-switches that stitches together modern datacenters.

Four numbers that describe any network

To compare topologies without hand-waving, architects reduce each to a handful of figures:

Latency — the time for one message to cross the network, roughly proportional to the number of hops it must take;
Bandwidth — the total rate of data the network can carry when many nodes send at once;
Degree — links per node; more degree means more wires, pins and cost;
Diameter — the maximum shortest-path hop count between any two nodes; it bounds the worst-case latency;
Bisection bandwidth — cut the network into two equal halves; the number of links you must sever (the bisection width) times each link's bandwidth. It is the single most important number for all-to-all traffic, because it caps how fast the two halves can talk.

Here is how the topologies stack up (for N nodes, or a k \times k grid so N = k^2):

Topology	Degree	Diameter	Bisection width	Notes
Bus	1	1	1	cheapest; no parallelism, dies at scale
Ring	2	⌊N/2⌋	2	simple; latency grows with N
Crossbar	N	1	N/2	full bandwidth, but O(N²) switches
2-D mesh (k×k)	≤4	2(k−1)	k	short links; on-chip favourite
2-D torus (k×k)	4	≈k	2k	mesh + wrap; lower diameter & double bisection
Fat-tree	varies	2·log N	N/2	full bisection; datacenter standard

Getting the packet there: routing and flow control

Topology says which links exist; routing chooses which ones a given packet actually takes. On a mesh the standard is dimension-order (XY) routing: travel along X until you reach the destination column, then along Y — simple, cheap, and provably deadlock-free. Flow control then decides how a packet advances when links are busy. Old networks used store-and-forward, buffering the whole packet at every hop; modern ones use wormhole flow control, streaming the packet as a train of small flits that snakes through several routers at once, so latency barely grows with distance. Get flow control wrong and packets can wait on each other in a cycle forever — deadlock — which is why routing algorithms are designed to make that impossible.

Computing the metrics

Let's compute diameter and bisection for a mesh versus a torus and watch the wrap-around earn its keep. For a k \times k mesh the two far corners are 2(k-1) hops apart and a vertical cut severs k links; the torus wraps, so the diameter falls to about k and the bisection doubles to 2k (two cuts, front and back of the doughnut).

// Diameter and bisection width for a k x k mesh vs torus. function meshDiameter(k: number): number { return 2 * (k - 1); } function torusDiameter(k: number): number { return 2 * Math.floor(k / 2); } function meshBisection(k: number): number { return k; } function torusBisection(k: number): number { return 2 * k; } for (const k of [4, 8, 16]) { const n = k * k; console.log(`k=${k} (N=${n} nodes):`); console.log(` mesh : diameter ${meshDiameter(k)}, bisection ${meshBisection(k)}`); console.log(` torus: diameter ${torusDiameter(k)}, bisection ${torusBisection(k)}`); } // A shared bus, for contrast: diameter 1 but bisection only 1 — low latency, terrible bandwidth. console.log("bus : diameter 1, bisection 1 (fast for ONE message, hopeless for many)");

Notice the bus line at the end. Its diameter is a perfect 1, yet its bisection is also 1 — a single message flies, but the moment everyone talks at once the whole thing serialises. Low diameter and high bandwidth are different virtues, and the next vignette is a warning built entirely on confusing them.

A plain tree of switches has a fatal flaw: every packet between different branches must climb to a shared root, so the links near the top carry the traffic of the whole machine and become a bottleneck. Charles Leiserson's fat-tree (1985) fixes it by making the links fatter (more parallel cables and switches) the higher you go, so the aggregate bandwidth stays constant at every level — giving full bisection bandwidth, where any half of the machine can talk to the other half at full speed. Nearly every large datacenter fabric (Google, Meta, and classic Clos networks) is a fat-tree for exactly this reason: at scale, all-to-all bandwidth is worth more than saving on cable.

The most common beginner error is to rank networks by diameter alone and declare the one with the fewest hops the winner. A shared bus has diameter 1 — you can't get closer than one hop — yet its bisection bandwidth is a miserable 1, because only a single message uses the wire at a time. Diameter measures latency; bisection bandwidth measures throughput, and they are separate axes. A crossbar has both low diameter and huge bisection but costs O(N^2); a torus compromises on all three. Always ask which metric your workload actually stresses before you pick a shape.

Why topology decides the machine

As node counts explode, the network's scaling law becomes the machine's scaling law. A bus or ring collapses past a few dozen nodes; a mesh keeps links short and cheap but its diameter grows as \sqrt{N}; a fat-tree buys full bandwidth at real cost in cables and switches. Choosing a topology is choosing which of latency, bandwidth and cost you are willing to sacrifice — and at warehouse scale, that choice sets the price and the performance of the entire building.