Distance-Vector Routing and Bellman-Ford

A distance vector at router x is simply the vector $D_x = (D_x(y))_{y \in N}$, one entry per destination $y$ in the network, where $D_x(y)$ is router x's current best-known estimate of the cost of the cheapest path from x to y. Each router maintains such a vector and periodically (or on change) sends its entire vector to each of its directly connected neighbors. This is the defining feature of distance-vector routing: routers exchange estimates of distances, not topology maps, and they trust their neighbors' estimates without verifying the underlying paths. The computational engine behind this exchange is the Bellman-Ford equation. Let $c(x,v)$ be the direct link cost from x to neighbor v (with $c(x,x)=0$), and let $d_x(y)$ denote the true shortest-path cost from x to y. Bellman-Ford's optimality condition states:

with the base case $d_y(y) = 0$. This says the shortest path from x to y must go through some neighbor v of x, and the cost is that neighbor's own shortest-path cost to y plus the cost of the first hop. Distance-vector routing turns this equation into an iterative, distributed fixed-point computation: each router replaces $d_v(y)$ with its neighbor's current best estimate $D_v(y)$, and updates its own estimate accordingly. Over successive rounds, as neighbors' estimates improve, so do everyone's, until (for a static graph with no negative cycles) the vectors stabilize at the true shortest-path costs — this is precisely the guarantee established for the Bellman-Ford algorithm in its centralized, single-source form. The crucial structural difference from link-state routing (e.g., OSPF, Dijkstra-based) is epistemic: a distance-vector router never learns the actual path or the topology beyond one hop — only a cost. This is what makes the protocol lightweight (small messages, no flooding of full topology), but it is also exactly what makes stale information hard to detect and purge, which is the root of count-to-infinity.

Each router x maintains a distance table $D_x(y)$ for every known destination y, and, implicitly or explicitly, the identity of the next hop neighbor achieving that minimum. The protocol runs as an asynchronous, event-driven loop: 1. Initialization. $D_x(x) = 0$. For all other y, $D_x(y) = c(x,y)$ if y is a direct neighbor, else $\infty$. 2. Neighbor exchange. Periodically, and whenever its own vector changes, x sends $D_x$ to every neighbor. 3. Relaxation on receipt. When x receives a vector $D_v$ from neighbor v, it recomputes, for every destination y:

4. Change propagation. If any entry of $D_x$ changed, x forwards its updated vector to its own neighbors, triggering further relaxation elsewhere. 5. The process is a fixed-point iteration: it terminates (for static topology, non-negative costs) when no vector changes in a full round — this is the distributed analog of Bellman-Ford converging after relaxing all edges enough times. This is naturally asynchronous — there is no global clock — but for teaching and analysis it is standard to reason about synchronous rounds, where all routers exchange and update simultaneously, because the round-based argument gives the cleanest convergence bound. ```pseudocode // Distributed Bellman-Ford, run independently at every router x // N(x): set of direct neighbors of x // c(x, v): link cost to neighbor v // D_x[y]: current best-cost estimate from x to destination y // nextHop_x[y]: neighbor to forward packets toward y initialize: D_x[x] = 0 for each known destination y != x: D_x[y] = c(x, y) if y in N(x) else INFINITY nextHop_x[y] = y if y in N(x) else UNDEFINED on receiving vector D_v from neighbor v: changed = false for each destination y in union(D_x.keys, D_v.keys): candidate = c(x, v) + D_v[y] // relax through v if candidate < D_x[y]: D_x[y] = candidate nextHop_x[y] = v changed = true if changed: send D_x to every neighbor in N(x) // propagate improvement on local link cost change to neighbor v (new cost c'): old_cost = c(x, v) c(x, v) = c' for each destination y: if nextHop_x[y] == v: D_x[y] = c(x, v) + D_v[y] // must recompute, v is on the path send D_x to every neighbor in N(x) ``` The routing table used for forwarding packets is derived directly from `nextHop_x`: to send a packet toward y, forward it to `nextHop_x[y]`. Note the pseudocode already highlights the danger point: when a link to v gets worse (or v disappears), x must recompute $D_x(y)$ only using still-valid information — but if x's only alternative route to y was actually through v itself (learned earlier, indirectly), x has no way to detect that, and this is where trouble begins.

Trace the relaxation explicitly for the figure above: initially A only knows the direct link to C costs 5. After receiving B's vector announcing $D_B(C)=1$, A applies the update rule with $v=B$:

A now routes traffic to C through B at cost 2, cheaper than the direct link — a correct discovery made without A ever seeing the A–B–C path explicitly, only the numbers.

Per-router work. Each relaxation step for one received vector costs $O(|Y|)$ where $|Y|$ is the number of known destinations (routers), since every entry is compared once. Sending a vector costs $O(|Y|)$ space and bandwidth per message. Over the whole network, total message complexity to reach convergence is bounded by (number of rounds) × (number of edges) × $O(|Y|)$, since each edge carries at most one vector exchange per round in the synchronous model.

Convergence bound. Consider the synchronous-round abstraction: in round $k$, every router has correctly computed $D_x(y)$ for all destinations $y$ whose true shortest path from $x$ uses at most $k$ hops. This is provable by induction on $k$, exactly mirroring the correctness proof of centralized Bellman-Ford:

• Base case ($k=0$): $D_x(x)=0$ is trivially correct (0-hop path).
• Inductive step: assume all routers have correct costs for all destinations reachable within $k-1$ hops after round $k-1$. In round $k$, router x relaxes through every neighbor v. If the true shortest path from x to y has exactly $k$ hops, it can be written as $x \to v \to \dots \to y$ where the suffix from v is a shortest path of $k-1$ hops. By the inductive hypothesis, $D_v(y)$ is already correct after round $k-1$, so x's relaxation $c(x,v) + D_v(y)$ recovers the true shortest-path cost in round $k$.

Since any shortest path in a graph with $N$ routers has at most $N-1$ edges (a simple path visits at most $N$ distinct routers), all vectors converge to correct shortest-path costs within $N-1$ synchronous rounds, for static topologies with non-negative edge costs and no changes during convergence. This is identical to the $O(N \cdot E)$ time bound of centralized Bellman-Ford, since each of the $N-1$ rounds relaxes every edge once.

Space. Each router stores $O(|Y|)$ entries — linear in the number of destinations, independent of the total number of links, which is the key structural advantage over link-state routing (which must store the entire topology, $O(E)$ per router).

Where correctness breaks: dynamic topology. The proof above assumes the topology is fixed while convergence proceeds. When a link cost increases or a link fails mid-computation, the argument fails, because a router's "correct" cost from a stale round may have been derived from a path that no longer exists, and nothing forces that stale value to be recognized as invalid. This is exactly the count-to-infinity problem. Consider three routers in a line, $A - B - C$, all costs 1, so $D_A(C)=2$ via $B$, and suppose $B$'s only route to $C$ is the direct link. If the link $B$–$C$ fails:

• $B$ immediately sets $D_B(C) = \infty$ using its direct knowledge — correct so far.
• But before $B$ can broadcast this, or concurrently, $A$ (still holding stale information $D_A(C)=2$) sends its vector to $B$.
• $B$ relaxes: $D_B(C) \leftarrow \min(\infty,\ c(B,A) + D_A(C)) = \min(\infty, 1+2) = 3$.
• $B$ now believes it can reach $C$ via $A$ at cost 3 — even though $A$'s route to $C$ was through B in the first place. This is a routing loop: packets from $B$ to $C$ go to $A$, which sends them right back to $B$.
• $A$ then hears $B$'s new (wrong) vector $D_B(C)=3$, and updates $D_A(C) \leftarrow \min(2, 1+3)=2$... but eventually as more rounds pass and stale paths get exhausted, both $A$ and $B$ ratchet their estimate up by roughly 1 or 2 per round: 3, 4, 5, 6, … This slow climb toward $\infty$ is exactly counting to infinity — the network's shared but wrong belief in a phantom path decays only one relaxation step at a time.

The fundamental reason: distance-vector protocols convey only a number, not a path. A neighbor cannot tell whether the distance it hears is derived, transitively, from information that originated at itself. Link-state routing avoids this entirely because every router floods the actual topology, so each router computes shortest paths from full, verifiable information rather than trusting derived numbers — a tradeoff worth remembering when comparing the two paradigms.

Split horizon with poisoned reverse. A partial fix: if router $X$ routes to destination $Y$ via neighbor $Z$, then $X$ advertises $D_X(Y) = \infty$ back to $Z$ specifically (rather than omitting the entry, which is plain split horizon, or reporting the true value). The reasoning: $Z$ should never think it can reach $Y$ through $X$, since $X$'s own path to $Y$ depends on $Z$. In the two-router loop above, this breaks the pathology immediately: $B$ tells $A$ "my cost to $C$ is $\infty$" (since $B$ reaches $C$, when it can, only via the direct link, not via $A$) — wait, more precisely, $A$ tells $B$ "my cost to $C$ is $\infty$" since $A$'s route to $C$ is via $B$. This prevents $B$ from ever being fooled into thinking $A$ offers an independent path to $C$. However, poisoned reverse only breaks two-router cycles. For loops spanning three or more routers, count-to-infinity can still occur, because the poisoning information is local (per-neighbor) and does not propagate transitively fast enough to catch longer cyclic dependencies before stale advertisements circulate. This is the honest limit of the fix — it is a mitigation of the most common case, not a proof of loop-freedom in general.

Take a 4-router topology: $A - B - C - D$ in a line (costs 1 each), plus a direct link $A-D$ with cost 10 (a "long way around" backup). All routers converge normally first; then the $A$–$B$ link fails, and we trace the count-to-infinity behavior without poisoned reverse, followed by the mitigated version.

Steady state before failure (shortest paths, cost 1 per hop along the line):

Every router's path to $D$ actually threads through the line, since $3 < 10$ (the direct A–D backup link is more expensive and unused).

Failure event: the $B$–$C$ link goes down. $B$ immediately marks $D_B(C) = \infty$ directly, but recall $B$'s route to $D$ went through $C$, so $B$'s stale table said $D_B(D) = 2$. Without poisoned reverse, trace round by round (synchronous model, vectors exchanged each round):

This is the count-to-infinity signature: many rounds of small increments before the network admits the truth. In real RIP deployments this could take dozens of update cycles (RIP's slow ~30-second timer makes this minutes of real time), during which packets to $D$ genuinely loop between $A$ and $B$, consuming bandwidth and never arriving.

With poisoned reverse: because $B$'s route to $D$ goes through $C$, $B$ was already advertising $D_B(D) = \infty$ specifically to $C$ (irrelevant here since $C$ still uses its own direct connection) — but more importantly, the mitigation to watch is $A$'s advertisement to $B$: since $A$ routes to $D$ via $B$, $A$ tells $B$ "my cost to $D$ is $\infty$." When $B$'s direct route to $C$ vanishes, $B$ looks at what $A$ told it — $\infty$ — and cannot mistakenly count $A$ as an alternate path. $B$ correctly and immediately concludes $D$ is unreachable through its current neighbors except via the poisoned path, and falls back to advertising $\infty$ itself, or waits for the network to route around via the true A–D link, in a single round rather than a slow climb. The two-router mutual-deception loop is eliminated at the source.

The Bellman-Ford recurrence traces to dynamic programming and shortest-path research in the 1950s, later adapted wholesale into networking as routers needed distributed, resource-light shortest-path computation without global topology knowledge.

Distance-vector routing underlies RIP, still used in small enterprise and legacy networks for its simplicity, and historically shaped IGRP and its successor EIGRP (which layers Diffusing Update Algorithm logic atop distance-vector ideas specifically to prevent count-to-infinity by requiring routers to confirm loop-freedom before switching routes). The count-to-infinity problem and its partial fixes are a standard case study in distributed systems courses because they illustrate a broader theme: distributed algorithms that rely on trusting derived, aggregated information (rather than raw, verifiable facts) are inherently vulnerable to stale-data loops — the same class of issue that appears in cache-coherence protocols and gossip-based consensus systems. Understanding this tradeoff is also the natural bridge to Inter-Domain Routing with BGP: BGP is a path-vector protocol, an explicit response to exactly this weakness. Instead of exchanging bare distances, BGP routers exchange the entire AS-path traversed, so a router can directly detect and discard any advertisement that already contains itself — eliminating count-to-infinity-style loops by construction rather than by heuristic patching. Understanding why distance-vector protocols are fragile is thus the conceptual prerequisite for appreciating why BGP's design choice (full path, not just cost) is not extra overhead but a necessary correctness mechanism at Internet scale.

Ask the tutor: Can you walk through why poisoned reverse fails specifically in a 3-router ring topology, with a full round-by-round trace?