Distance-Vector Routing, Bellman-Ford, and Convergence Problems

Distance-Vector Routing

The distance-vector algorithm is distributed: each node receives information from one or more directly attached neighbors, performs a calculation, and then distributes the results back to its neighbors.

The distance-vector algorithm is derived from the Bellman-Ford equation $d_x(y) = \min_v\{c(x, v) + d_v(y)\}$, where $d_x(y)$ is the least cost from x to y, $c(x, v)$ is the cost from x to its neighbor v, and $d_v(y)$ is the cost from neighbor v to destination y.

The equation is intuitive: if x first goes to neighbor v and then follows v's least-cost path to y, the cost is $c(x, v) + d_v(y)$. x only needs to choose the neighbor that minimizes this sum, and that neighbor is also x's next hop toward y.

The only information a node has is the cost of the links to its directly attached neighbors and the information it receives from those neighbors. Each node waits for updates from any of its neighbors.

Each node x maintains three things: the cost $c(x, v)$ of the link to each neighbor v; its own distance vector $\mathbf{D}_x = [D_x(y): y \in N]$, its estimate of its least cost to every destination; and the latest distance vector $\mathbf{D}_v$ received from each neighbor. The algorithm runs as follows:

Initialization:
    for each destination y: D_x(y) = c(x, y) (∞ if not a neighbor), D_x(x) = 0
    send D_x to all neighbors
Loop:
    wait (until a directly attached link cost changes or a neighbor's vector arrives)
    for each destination y: D_x(y) = min_v{c(x, v) + D_v(y)}
    if any value in D_x changed, send the new D_x to all neighbors

Distance-vector routing is iterative (exchanges continue until there is no new information), asynchronous (nodes need not compute in lockstep), and self-terminating (nodes stop sending when nothing changes).

Link-Cost Changes and Count-to-Infinity

When a link cost decreases, the "good news" spreads quickly: each node that computes a smaller cost immediately tells its neighbors, and the network converges in a few rounds.

Increases behave differently. Consider three nodes x, y, z with $c(x, y) = 4$, $c(y, z) = 1$, and $c(z, x) = 50$. Initially $D_y(x) = 4$ (direct) and $D_z(x) = 5$ (through y). Now $c(x, y)$ rises to 60:

1. y detects the change and computes with the $D_z(x) = 5$ that z advertised earlier: $D_y(x) = \min\{60 + 0, 1 + 5\} = 6$, so it now routes to x through z. But z's path to x goes through y, so a routing loop has formed.
2. z receives y's new vector, computes $D_z(x) = \min\{50 + 0, 1 + 6\} = 7$, and advertises it to y.
3. y computes 8, z computes 9, … the two take turns adding 1.

These exchanges repeat more than forty times, until z finds that the cost through y exceeds 50 and switches to its direct link to x. If $c(z, x)$ were also huge or the link did not exist, the cost would keep growing forever. This is the count-to-infinity problem.

Poisoned reverse prevents such loops between two nodes: if z routes through y to reach x, z advertises $D_z(x) = \infty$ to y. y then never chooses to route back through z; in the example, y immediately computes $D_y(x) = 60$ and the network converges quickly. Poisoned reverse cannot, however, fix loops involving three or more nodes.

Comparing Link-State and Distance-Vector Routing

Both are used in the Internet: OSPF is based on link state and RIP on distance vectors. RIP uses hop count as its cost, with a maximum of 15 hops; 16 means unreachable ("infinity"), which caps count-to-infinity.