DEV Community

Cover image for Routing by Rumor: The Bellman-Ford Distance Vector Algorithm
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Routing by Rumor: The Bellman-Ford Distance Vector Algorithm

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:

  1. Link-State (Global): Every router possesses complete knowledge of the entire network topology and runs Dijkstra's algorithm (e.g., OSPF).
  2. 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) \
Enter fullscreen mode Exit fullscreen mode

Where:

  • D_x(y) is the least-cost distance estimate from router x to destination y.
  • c(x, v) is the physical cost of the direct link connecting x to neighbor v.
  • D_v(y) is the distance vector reported by neighbor v to destination y.
  • The min_v operation evaluates all immediate physical neighbors v ∈ N(x).

2. The Asynchronous Update Loop

Each node x operates autonomously:

  1. It maintains its own distance vector D_x = [D_x(y) : y ∈ V].
  2. Whenever a local link cost c(x, v) changes or node x receives a vector update from a neighbor, it re-evaluates the Bellman-Ford equation.
  3. If D_x(y) changes for any destination y, node x transmits 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:

  • A no longer reaches B directly.
  • But neighbor C previously reported it could reach B in 2 hops (via A!).
  • A inspects C's stale vector and assumes C has an alternative path. A updates its cost to C's cost + 1.
  • C receives A's update and increments its own cost.
  • Packets bounce endlessly between A and C as both routers increment distances to infinity ($16$ in RIP).

Explore interactive network topology graphs and routing table traces at Binary Dose.

Top comments (0)