Routing Algorithms
The control plane is the part of the network layer that decides where packets should go. It builds the forwarding tables that the data plane then consults, once per packet, to move traffic at line rate.
Control plane vs data plane
- Data plane - the fast, local, per-packet action inside a single router: look up the destination in the forwarding table, send the packet out the right port. Measured in nanoseconds, usually done in hardware.
- Control plane - the network-wide computation that builds those forwarding tables. Routers run routing algorithms, exchange reachability information, and converge on a consistent view of best paths. Measured in seconds to minutes, done in software.
A routing algorithm's job is to find least-cost paths through a graph where nodes are routers and edge weights are link costs. Two classic families dominate.
Link-state routing (Dijkstra)
In a link-state protocol, every router floods the state of its own links to the entire network. Because each router ends up with the complete map, it can compute shortest paths to every destination independently using Dijkstra's algorithm.
Dijkstra grows a set of settled nodes whose shortest distance from the source is final. Each step, it settles the nearest unsettled node, then relaxes that node's neighbours - a candidate distance replaces the old one whenever it is smaller.
Step through Dijkstra below. The source is u; each click settles the next-nearest
router and grows the shortest-path tree (highlighted edges).
| Node | Cost | Path |
|---|---|---|
| u | 0 | u |
| v | ∞ | v |
| w | ∞ | w |
| x | ∞ | x |
| y | ∞ | y |
| z | ∞ | z |
Link-state works because each router has a global view of the topology. Every router runs the same algorithm on the same map, so they all agree on the shortest paths - no back-and-forth negotiation is needed once the maps have flooded.
Worked example: Dijkstra by hand on a small graph
Take a graph with five nodes - u, v, w, x, y - and these edge weights:
| Edge | Weight |
|---|---|
| u - v | 2 |
| u - x | 1 |
| x - v | 2 |
| x - w | 3 |
| v - w | 3 |
| w - y | 1 |
Running Dijkstra from source u, tracking the settled set N' and each node's
current best-known distance:
| Step | N' (settled) | D(v) | D(w) | D(x) | D(y) |
|---|---|---|---|---|---|
| 0 | {u} | 2 (u-v) | inf | 1 (u-x) | inf |
| 1 | {u, x} | 2 (still u-v) | 4 (u-x-w, 1+3) | 1 | inf |
| 2 | {u, x, v} | 2 | 4 (u-x-w still cheaper than u-v-w=2+3=5) | 1 | inf |
| 3 | {u, x, v, w} | 2 | 4 | 1 | 5 (u-x-w-y, 4+1) |
| 4 | {u, x, v, w, y} | 2 | 4 | 1 | 5 |
At step 0 only u's direct neighbours have finite distance. At step 1, x (the
cheapest unsettled node, distance 1) is settled, and relaxing its edges lowers
D(w) from infinity to 4 via u -> x -> w. At step 2, v is settled; relaxing
v - w proposes 2 + 3 = 5 for w, but the existing 4 is already cheaper, so
D(w) stays put - this is the "only replace if smaller" relaxation rule in
action. The algorithm finishes with the shortest distance from u to every other
node, and the edges used to reach each one form the shortest-path tree.
Distance-vector routing (Bellman-Ford)
A distance-vector router has no map. It knows only the cost to its direct neighbours, and it periodically tells each neighbour its current best-known distance to every destination - its distance vector. Each router updates its own vector using the Bellman-Ford equation:
Dx(y) = min over neighbours v of ( c(x, v) + Dv(y) )
"My cheapest cost to y is the cheapest, over all my neighbours v, of the cost to
reach v plus v's advertised cost to y." When a router's vector changes, it
tells its neighbours, and the change ripples outward until the network converges.
| Link-state | Distance-vector | |
|---|---|---|
| Algorithm | Dijkstra | Bellman-Ford |
| What each router knows | Full topology map | Only direct link costs + neighbours' vectors |
| What is exchanged | Link states (flooded to all) | Distance vectors (to neighbours only) |
| Convergence | Fast, computed locally | Iterative, ripples hop by hop |
| Example protocol | OSPF | RIP |
Because distance-vector routers trust their neighbours' summaries without seeing the underlying topology, a link failure can trigger the count-to-infinity problem: two routers keep advertising slowly increasing costs to each other through a path that no longer exists, converging only very slowly. Fixes like split horizon and poisoned reverse mitigate it, but link-state protocols sidestep the issue entirely by giving every router the real map.