Exercises — Distance vector routing — RIP, Bellman-Ford, count-to-infinity

Each entry is a triple: destination, cost (cheapest known total cost to that destination), and next-hop (which neighbour to forward through). See Routing Tables and Next-Hop Forwarding.

16 = ∞ (unreachable). The largest valid hop count is 15. The cap exists to bound count-to-infinity.

RIP runs over UDP port 520 and broadcasts its full distance vector every 30 seconds. A route with no update for 180 s (6 periods) is declared dead.

$A$'s neighbours are $B$ (link 4) and $C$ (link 6).

• Via $C$: $c(A,C)+D_C(C)=6+0=6$.
• Via $B$: $c(A,B)+D_B(C)=4+1=5$.
• $D_A(C)=\min (6,5)=5$, next-hop $=\mathbf{B}$.

Why $B$ wins even though $C$ is the destination: the direct link $A\to C$ (6) is more expensive than hopping through $B$ (4+1=5). The cheapest route need not be the direct one.

• Via $Y$: $2+2=4$.
• Via $Z$: $3+0=3$.
• $D_X(Z)=\min (4,3)=3$, next-hop $=\mathbf{Z}$ (the direct link wins this time).

• Via $P$: $5+\infty =\infty$ (adding to infinity stays infinity — no route through a dead-end).
• Via $Q$: $2+7=9$.
• $D(W)=\min (\infty ,9)=9$, next-hop $=\mathbf{Q}$.

Why $B$'s value becomes 3, not ∞: the moment B–C dies, $B$ would set $C=\infty$ — but $A$ had earlier advertised "$D_A(C)=2$". $B$ does not know that $A$'s route to $C$ physically passed through $B$ itself. So $B$ computes "reach $C$ via $A$" $=c(B,A)+D_A(C)=1+2=3$. This is a phantom route that loops $B\to A\to B$. That is the count-to-infinity bug: bad news crawls up one step per exchange.

Dijkstra runs on a router that already holds the entire topology map, so it can see that a link is gone before recomputing — no stale second-hand estimate can survive. DV routers only ever hear local neighbour summaries ($D_v(y)$ numbers) and cannot tell whether that summary secretly loops back through themselves. The missing global view is precisely what lets a phantom route persist and count upward. This is why DV = distributed Bellman-Ford Algorithm while OSPF = local Dijkstra's Algorithm.

Split horizon rule: never advertise a route back to the neighbour you learned it from. $A$ learned $C$ via $B$, so $A$ advertises "$D_A(C)=\infty$" to $B$ (while still telling the outside world 2).

• When B–C dies, $B$ looks for alternatives. Its only other neighbour is $A$, and $A$ has told $B$ that $C=\infty$.
• So $B$ computes via $A$: $1+\infty =\infty$. No phantom route exists.
• $B$ sets $D_B(C)=\infty$ immediately — no counting.

Mechanism: the looping estimate was never injected back to $B$ in the first place, so there is nothing to ping-pong.

It does NOT guarantee safety. Split horizon only breaks 2-node loops (the $A\leftrightarrow B$ ping-pong). In a triangle, bad news can circulate the long way around: when $C$ loses $D$, $A$ might still hold a stale route "$D$ via $B$", and $B$ a stale route "$D$ via $A$" — each learned it from a different neighbour than the one they advertise back to, so split horizon does not silence them. The stale cost then crawls upward around the ring $A\to B\to C\to A$ toward 16. This is exactly why RIP also needs the hard 16-cap plus triggered updates and hold-down timers.

At most $n-1=5$ exchanges. Justification: a direct neighbour of destination $y$ learns the true cost after 1 exchange (it already knows $c(\cdot ,y)$). A node 2 hops away learns after 2 exchanges, and in general a node $k$ hops away after $k$ exchanges. Any shortest path in an $n$-node graph has at most $n-1$ edges (a longer path would revisit a node, and by the Principle of Optimality a shortest path never needs to repeat a node — repeating means a removable loop of non-negative cost). So after $n-1=5$ exchanges, every shortest path is discovered. This is exactly the Bellman-Ford Algorithm iteration bound and connects DV to Dynamic Programming (each exchange = one BF relaxation round).

With those exact symmetric costs it's impossible from $P$: via $Q$ costs $10+10=20>10$ direct, so the direct link (10) wins. To make the 2-hop route win we need $c(P,Q)+c(Q,R)<c(P,R)$. A working redesign: set P—R = 25, keep P—Q = 10, Q—R = 10. Now:

• Direct: $25$.
• Via $Q$: $10+10=20$.
• $D_P(R)=\min (25,20)=20$, next-hop $Q$.

General condition (triangle inequality violation): the direct link $P\to R$ is not on the shortest path exactly when some neighbour $v$ satisfies $c(P,v)+d_v(R)<c(P,R)$. In metric graphs where the triangle inequality holds tightly this never happens; DV routing is what automatically discovers such shortcuts without any node seeing the full graph. Contrast with BGP, which routes on policy (business relationships), not pure cost.

Distance Vector ::: distributed Bellman-Ford — each router keeps (dest, cost, next-hop), shares its whole vector with neighbours only, minimises $c(x,v)+D_v(y)$; suffers count-to-infinity, patched by split horizon, poison reverse, and RIP's 16-cap.