Routing by Rumor: The Bellman-Ford Distance Vector Algorithm
In internetwork routing, the fundamental challenge is computing the least-cost path from any source to any destination across an arbitrary graph of interconnected routers.
Routing algorithms fall into two classical paradigms:
- Link-State (Global): Every router possesses complete knowledge of the entire network topology and runs Dijkstra's algorithm (e.g., OSPF).
- Distance-Vector (Decentralized): Routers possess zero global topology knowledge. They know only the costs to their direct physical neighbors and exchange distance estimates asynchronously (e.g., RIP).
Because routers rely entirely on second-hand information from neighbors, Distance Vector is frequently called Routing by Rumor.
1. The Bellman-Ford Equation
The mathematical engine of Distance Vector routing is the Bellman-Ford relation:
D_x(y) = min_v \ c(x, v) + D_v(y) \
Where:
-
D_x(y)is the least-cost distance estimate from routerxto destinationy. -
c(x, v)is the physical cost of the direct link connectingxto neighborv. -
D_v(y)is the distance vector reported by neighborvto destinationy. - The
min_voperation evaluates all immediate physical neighborsv ∈ N(x).
2. The Asynchronous Update Loop
Each node x operates autonomously:
- It maintains its own distance vector
D_x = [D_x(y) : y ∈ V]. - Whenever a local link cost
c(x, v)changes or nodexreceives a vector update from a neighbor, it re-evaluates the Bellman-Ford equation. - If
D_x(y)changes for any destinationy, nodextransmits its updated vector to all its direct neighbors.
3. The Pathological Flaw: Count-to-Infinity
While Distance Vector handles improving link costs rapidly (good news travels fast), it reacts disastrously to link failures (bad news travels slow).
When a link between A and B breaks:
-
Ano longer reachesBdirectly. - But neighbor
Cpreviously reported it could reachBin 2 hops (viaA!). -
AinspectsC's stale vector and assumesChas an alternative path.Aupdates its cost toC's cost+ 1. -
CreceivesA's update and increments its own cost. - Packets bounce endlessly between
AandCas both routers increment distances to infinity ($16$ in RIP).
Explore interactive network topology graphs and routing table traces at Binary Dose.
Top comments (0)