Distance-Vector Routing and Count-to-Infinity

Two ways to solve the same puzzle

In the previous guide you watched link-state routing work: every router floods its local link costs to everyone, so each one ends up holding a complete copy of the network graph, then runs Dijkstra's algorithm privately to compute shortest paths. It is a study group where everyone shares their notes and then each student solves the whole exam alone. Distance-vector routing takes the exact opposite stance, and it is worth pausing on how radical that is.

A distance-vector router never sees the map. It knows only two things: the cost of the links to its immediate neighbours, and what those neighbours have told it. From that scrap, each router keeps a little table, its distance vector, holding one number per destination: my best guess at the cost to reach there. It does not know the path, only the cost and which neighbour to hand the packet to. Then, periodically, it tells its neighbours its whole vector, and listens to theirs, and that is the entire conversation. The puzzle is the same as before, find the least-cost paths across the network, but here nobody ever holds the answer; the answer emerges from gossip.

The Bellman-Ford idea: ask your neighbours

The engine underneath is the Bellman-Ford equation, and stated plainly it is almost obvious. Suppose I want my cheapest cost to reach some far-off destination D. I cannot see the whole route, but I can reason locally: for any neighbour N, one candidate route is the cost of my link to N, plus whatever N says its own cheapest cost to D is. My best cost to D is simply the smallest such candidate over all my neighbours. In words: the cheapest way to reach D is to step to my best neighbour and then take their cheapest way to D.

Bellman-Ford, the neighbour's-eye view

  cost_x(D) = min over each neighbour N of [ c(x, N) + cost_N(D) ]

  c(x, N)      = cost of my own link to neighbour N  (I know this)
  cost_N(D)    = N's advertised cheapest cost to D   (N told me this)

Example, router X reaching D, with two neighbours A and B:
  link X->A costs 1,  A advertises cost 4 to D   =>  candidate 1 + 4 = 5
  link X->B costs 2,  B advertises cost 2 to D   =>  candidate 2 + 2 = 4
  cost_x(D) = min(5, 4) = 4,  next hop = B

Now run this as a living process across the network. Each router starts knowing only its direct links and infinity for everything else. It applies Bellman-Ford to its neighbours' latest vectors, and whenever its own vector changes, it advertises the new one to its neighbours. They recompute, maybe change, and re-advertise, and the updates ripple outward like news spreading through a town. With nothing going wrong, this settles down, every router's vector stops changing, and it has converged on the true least-cost paths, without any single router ever having seen the map. That quiet, distributed convergence is genuinely beautiful.

Good news travels fast, bad news travels slow

Here is where the elegance cracks. Distance-vector has a famous asymmetry: good news (a link got cheaper, or a new shortcut appeared) propagates quickly, but bad news (a link or a destination went away) can propagate agonisingly slowly, and in the worst case it triggers the count-to-infinity problem. The root cause is that a router believes its neighbours without knowing why they believe what they believe. A neighbour says cost 4 to D, and you trust it, never suspecting that the neighbour's route to D might actually run back through you.

Picture three routers in a line, A reaching destination D through B, and C also reaching D through B. So A thinks 'D costs 2, go via B' and C thinks 'D costs 2, go via B'. Now the link from B straight to D breaks. B notices D is gone and sets its cost to infinity. But before B can tell anyone, A pipes up with its old advertisement: 'I can reach D at cost 2!' B believes A (it has no idea A's route went through B in the first place) and happily concludes 'I'll reach D via A, at cost 3.' B advertises 3, C updates to 4, A then sees B is now 3 and bumps itself to 4, and the two of them ping-pong upward, 5, 6, 7, slowly counting their way toward infinity, all chasing a destination that no longer exists. This is the routing loop in slow motion.

Partial cures: poison the lie at the source

If the disease is a router advertising a route back to the very neighbour the route depends on, the obvious medicine is to stop doing that. This is split horizon: if I reach D through neighbour B, I do not tell B that I can reach D at all. I never advertise a route back in the direction I learned it. In the three-router story, A would simply stay silent toward B about D, so B never hears that tempting false 'cost 2' and never starts the climb.

A slightly stronger variant is split horizon with poison reverse: instead of staying silent, A actively tells B 'my cost to D is infinity', poisoning the route so B cannot possibly be tempted. Both tricks help, and real protocols use them. But here is the honest, important caveat: these are partial cures, not a guarantee. Split horizon kills the two-router loop reliably, yet a loop involving three or more routers in a circle can still count to infinity, because the lie travels the long way around the loop rather than straight back. Distance-vector's slow convergence on bad news is a real, residual weakness, not a bug you can fully patch.

1. A router boots knowing only the cost to each directly attached neighbour; every other destination starts at infinity.
2. It periodically sends its whole distance vector to each neighbour (and also right after its own vector changes).
3. On receiving a neighbour's vector, it applies Bellman-Ford: for each destination, take that neighbour's advertised cost plus the link cost to it, and keep the minimum.
4. Before advertising, it applies split horizon (and optionally poison reverse) so it never feeds a route back toward the neighbour it depends on.
5. If its vector changed, it advertises again; the ripple continues until every vector stops changing, the network has converged.

Which one wins? Neither, and that is the point

It is tempting to declare link-state the winner because distance-vector has count-to-infinity. Resist that. Each design pays a different price. Link-state demands that every router flood updates to the whole area and store the complete map, which costs memory and flooding traffic that grows with the network; its upside is fast, loop-free convergence. Distance-vector is wonderfully frugal, a router only ever talks to neighbours and stores one number per destination, but it pays with slow convergence on failures and the count-to-infinity hazard.

These are not just textbook curiosities; they map straight onto the two real interior gateway protocols you meet next. RIP is distance-vector, simple and limited, with that hop count of 16 as infinity. OSPF is link-state, heavier but scalable, and it is what large networks actually run inside. There is even a third family built on the distance-vector idea, path-vector, which advertises the entire path rather than just a cost, so a router can spot and reject any route that loops back through itself, that is how the protocol holding the whole Internet together avoids count-to-infinity, but that belongs to a later rung on routing between domains.

Step back and the shape of this rung is clear. Both algorithms attack the same graph problem, both compute least-cost paths, and both feed the same humble forwarding table that the data plane consults per packet. They just disagree about who knows what. Link-state says know everything, compute alone; distance-vector says know your neighbours, compute together. The next guide takes these two ideas and shows them dressed in their real protocol clothes, RIP and OSPF, running in actual networks today.