We know from the
Two great algorithmic families solve this, and the split between them is one of the most beautiful either/ors in networking. In link-state routing, everyone learns the whole map and each computes shortest paths alone. In distance-vector routing, nobody ever sees the whole map; routers only trade distance estimates with their neighbours and the right answer emerges from the gossip. Same goal, opposite philosophies — "tell everyone the local facts" versus "tell your neighbours your conclusions."
Both algorithms model the network as a weighted graph: routers are nodes, links are edges, and each edge has a cost (delay, inverse bandwidth, an admin's number). "Best path" means least total cost. Here is the small network we'll reason about throughout — hover the steps to build it up and reveal a shortest path.
A link-state router's motto is tell the truth about your neighbourhood, to the entire network. Each router:
Because every router has identical, complete information, they all compute consistent routes. This is how
OSPF (Open Shortest Path First), the workhorse of enterprise networks, operates. Dijkstra
grows a tree of confirmed-shortest nodes outward from the source, always confirming the nearest
not-yet-confirmed node next — on our graph it would confirm x (cost 1), then v
(2), then y (2), and so on, until z is nailed at cost 4 via
u→x→y→z.
Because the only thing each router announces is the state of its own links — who its neighbours are and what the links to them cost. It never announces routes or conclusions, just raw local facts. Every router then assembles the same jigsaw from everyone's link-state pieces and does its own thinking. Contrast this with distance-vector, where routers announce distances (their conclusions) rather than link facts — the names capture exactly what gets advertised.
Distance-vector routers never build a map. Each knows only the cost to its direct neighbours, and keeps a vector of its current best-known distance to every destination. Periodically it sends that whole vector to its neighbours, and updates its own estimates using what it hears. The update is the celebrated Bellman–Ford equation:
Read it aloud: my cheapest distance from x to y is the best I can do
over all my neighbours v — the cost to reach that neighbour,
The demo runs one Bellman–Ford relaxation round at a router, then iterates to convergence on a line of routers, so you can watch the estimates ripple outward one hop per round:
Watch u's distance to z improve round by round as the good news creeps in one
hop at a time — first u learns its neighbours, then its neighbours' neighbours, until the true cost 4
settles. That "one hop per round" propagation is the crux of distance-vector's biggest weakness.
Distance-vector's charm — routers trust neighbours' conclusions without seeing why — is also its curse. Good news travels fast; bad news travels agonisingly slowly. When a link fails, a router may still hear an old, now-invalid low distance echoed back from a neighbour who learned it through the failed router in the first place, and believe it. Each round they nudge their estimates up by one, bouncing the stale route between them — 4, 5, 6, 7… — creeping toward infinity. This is the notorious count-to-infinity problem, and it can leave a routing loop festering for many rounds after a failure.
Two partial cures are worth knowing:
The trap is assuming distance-vector reacts to a broken link as quickly as it reacts to a new, better one. It does not. When a shorter path appears, a single round of updates spreads the good news outward and everyone benefits immediately. But when a link breaks, a router can keep believing a phantom low-cost route because a neighbour is still parroting the old distance — a distance that was only ever valid via the now-dead link. The two mislead each other, incrementing 3→4→5→6… over many rounds until the count finally reaches the "infinity" threshold and the route is declared dead. Link-state does not suffer this: because every router holds the whole map, a failed link is simply erased from the map and Dijkstra instantly recomputes correct paths — no phantom echoes to chase. If you see slow convergence and transient loops after a failure, suspect a distance-vector protocol counting to infinity.
The trade-offs fall out directly from what each algorithm knows and shares:
| Link-state (OSPF) | Distance-vector (RIP) | |
|---|---|---|
| What each router knows | the whole topology map | only distances via its neighbours |
| What it advertises | its own link states, flooded to all | its full distance vector, to neighbours only |
| Local algorithm | Dijkstra (shortest-path tree) | Bellman–Ford update |
| Convergence | fast; a failure is erased from the map at once | can be slow — count-to-infinity after failures |
| Message overhead | small LSAs, but flooded network-wide | bigger vectors, but only to neighbours |
| Memory | stores the entire map (heavier) | stores only its own vectors (lighter) |
| Robustness to bad data | a router computes its own routes; harder to poison | trusts neighbours' conclusions; a lie propagates |
Neither wins outright. Link-state converges fast and resists bad information, at the cost of every router storing the whole map and flooding updates. Distance-vector is lightweight and simple — perfect for small, stable networks — but pays for its locality with slow, loop-prone convergence when things break. Both are intra-domain protocols, run inside a single administrative network. Routing between networks answers to a completely different master — policy — which is the subject of BGP in the next lesson.