Skip to content
All projects

Research frontiers course, 2024

Compact Routing

An implementation of the Thorup-Zwick routing scheme, where each node stores only about sqrt(n) log n routing entries yet every path it finds is at most 3 times the shortest. Comes with a live visualizer you can click through.

A 6 by 6 grid network on a dark background. The compact route from node 6 to node 3 is drawn in red, detouring through landmark nodes, while a shorter green path goes straight across the top.
  • Each node keeps a routing table of only about sqrt(n) log n entries, not the full n, yet routing stays within 3x of the shortest path.
  • Routing uses nothing but the node's own table and the target's label, exactly as the scheme is defined.
  • A live visualizer rebuilds the whole scheme in the browser, so you can pick a source and target and watch the route form hop by hop.

What it is

A routing scheme answers one question over and over: a packet sitting at some node needs to reach another node, and the current node has to decide which neighbour to forward it to. The simple answer is a full routing table, one entry per possible destination. That is n entries at every node, and in a large network that does not scale.

Compact routing trades a little path length for a lot of table space. I implemented the stretch-3 scheme of Thorup and Zwick, where each node stores only about sqrt(n) log n entries, yet the path a packet actually travels is never more than 3 times the true shortest path. It was a course project on routing in networks, and I built it in Python over NetworkX.

How the scheme works

The whole thing rests on a small random sample. Each node joins a set of landmarks independently with probability 1/sqrt(n), so there are about sqrt(n) of them. Every node then learns two things: the shortest route toward each landmark, and the shortest route toward each node in its own cluster, the nodes that are closer to it than they are to their own nearest landmark. Those two lists are the entire routing table, and together they stay small.

A destination carries a short label of its own: its nearest landmark, and the first hop out of that landmark toward it. That label is the “name-dependent” part, the one piece of global information routing is allowed to use.

A grid with the landmark set in orange and the cluster of one node shaded in violet. Together these two sets are all a node needs to store.

Why the path is never more than 3x

When the destination is a landmark, or sits inside the current node’s cluster, the table already holds the next hop and the packet goes straight there. The interesting case is when it is neither. Then the packet is sent to the destination’s nearest landmark first, using the landmark entries every node keeps, and from that landmark it drops down to the destination using the label.

That single detour is the whole cost. The triangle inequality bounds it: going to the landmark and then to the target is at most 3 times the direct distance, and never worse. So the worst path the scheme can produce is exactly 3x, and most are far better.

The 3x case drawn out: the red route detours up to the target’s landmark and back down, while the green shortest path goes direct.

Building it, then building it again

The Python version is the real implementation: it generates grid or random weighted graphs, runs all-pairs Dijkstra once to pre-process the tables, and then routes using only those tables. A Matplotlib view draws the routed path in red over the true shortest path in green, which is how I first convinced myself the stretch bound held.

Later I rebuilt the entire pipeline a second time in plain JavaScript so it could run in a browser with no install and nothing to download. The live visualizer samples the landmarks, builds every node’s table, and lets you click a source and a target and watch the compact route grow against the shortest path, with the stretch and the average table size updating as you go. Reimplementing it from scratch was the best test of whether I actually understood it.

Checking it

Correctness here has a precise meaning, so I wrote a test for exactly it: over tens of thousands of source and target pairs across grids and random graphs, every routed path has to be a valid walk from source to target, and no path may exceed 3x the shortest. Both the Python and the JavaScript versions pass, with the worst stretch landing at exactly 3.0, right on the bound the theory promises.