Distance-vector routing finds shortest paths across a network where no router ever sees the whole map. Each router keeps a distance vector — its lowest known cost to every destination — and periodically tells its direct neighbours that vector. Each router folds in what its neighbours report to improve its own estimates, until nobody's table changes any more: the network has converged. It's the Bellman-Ford algorithm run in a distributed, gossip-like way.
The Bellman-Ford update
Let c(x, v) be the cost of router x's direct link to neighbour v, and Dᵥ(y) be v's reported best cost to destination y. Router x updates its own estimate with: Dₓ(y) = min over neighbours v of [ c(x, v) + Dᵥ(y) ]. In words: my best cost to `y` is the cheapest of 'hop to a neighbour, then that neighbour's best path to `y`'. This is the relax step — adopt a route whenever going through a neighbour beats your current best.
1Each router starts knowing only the cost to its direct neighbours; everything else is infinity.
2Every router sends its current vector to each neighbour (periodically, or when it changes).
3On receiving a neighbour v's vector, apply the Bellman-Ford rule for every destination y.
4If any estimate improved, record the neighbour v as the next hop and share the updated vector.
5Repeat. Good news travels one hop per round, so the network converges in O(diameter) rounds.
RIP, the canonical example
The Routing Information Protocol is plain distance-vector: the cost metric is simply hop count, vectors are broadcast every 30 seconds, and the network diameter is capped because 16 hops means 'unreachable' (infinity). It's small and simple — fine for modest networks, outgrown by large ones.
The count-to-infinity problem
Distance-vector's weakness shows when a link fails. Bad news spreads slowly: a router may still hear an *old*, now-invalid low cost echoed back from a neighbour and believe a path exists through it. The two then bounce inflated estimates back and forth, the cost creeping up one step per round — slowly counting toward infinity before everyone finally agrees the destination is gone.
Partial fixes, not cures
Split horizon (don't advertise a route back to the neighbour you learned it from) and poison reverse (advertise it back with cost = infinity) curb many count-to-infinity loops, and defining infinity as a small number like 16 bounds how long the counting can run. They help but don't eliminate every case — which is why link-state protocols, where each router learns the whole topology, win on large networks.
OperationTimeSpace
Convergence (good news) · one hop spread per roundO(diameter) roundsO(neighbours × destinations)
Convergence (link failure) · count-to-infinity; bounded by defining ∞up to O(infinity) rounds—
Check yourself
What is the 'count-to-infinity' problem in distance-vector routing?
