Distance vector routing — RIP, Bellman-Ford, count-to-infinity: Worked examples

Before we start, one promise: every symbol used here was defined in the parent, but we restate the three we lean on hardest so you never have to scroll away.

The scenario matrix

Distance vector routing has a finite family of situations. If you can do one of each row, you can do all of them.

#	Case class	What makes it different	Hit by
C1	Basic min over 2+ neighbours	pick cheapest of several via-options	Ex 1
C2	Direct link vs indirect wins	the direct link is not the answer	Ex 2
C3	Multi-round convergence to steady state	tables change over several exchanges	Ex 3
C4	Tie between two next-hops	$min$ has two equal arguments	Ex 4
C5	Unreachable / $\infty$ input (degenerate)	a neighbour reports $\infty$ ; base cases	Ex 5
C6	Link break → count-to-infinity (2-node)	bad news travels slowly; RIP 16-cap	Ex 6
C7	Split horizon fixes / limiting behaviour	the 2-node loop is killed	Ex 7
C8	3-node loop where split horizon FAILS	the exam twist / worst case	Ex 8
C9	Real-world word problem (RIP timers)	30 s / 180 s / hop-count reasoning	Ex 9

We now walk every cell.

Ex 1 — C1: basic minimum over several neighbours

Forecast: guess which neighbour wins before computing. (Cheap link ≠ cheap total!)

Cost via $B$ : $c (A, B) + D_{A}^{(B)} (Z) = 2 + 3 = 5$ . Why this step? Total = price to step onto $B$ + best price $B$ knows to finish.
Cost via $D$ : $1 + 9 = 10$ . Why? $D$ 's link is cheapest but $D$ is far from $Z$ — the sum is what matters.
Cost via $E$ : $5 + 1 = 6$ . Why? Expensive link, but $E$ is almost at $Z$ .
Take the minimum: $d_{A} (Z) = min (5, 10, 6) = 5$ , next-hop $= B$ . Why? Bellman-Ford keeps the single cheapest option.

Verify: $5 < 10$ and $5 < 6$ , so $B$ is genuinely smallest. Notice the cheapest link ( $D$ , cost 1) lost — the answer is the cheapest total, exactly as the $min$ demands. ✔

Ex 2 — C2: direct link is NOT the winner

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

Forecast: there's a direct wire $A \to C$ of cost 7. Do you take it? Guess.

Neighbours of $A$ : $B$ (link 2) and $C$ (link 7). Look at the figure: two ways out of $A$ . Why? Every path from $A$ must leave through some direct neighbour.
Via $C$ (direct): $c (A, C) + d_{C} (C) = 7 + 0 = 7$ . Why $d_{C} (C) = 0$ ? A node reaches itself for free — base case.
Via $B$ : $c (A, B) + d_{B} (C) = 2 + 3 = 5$ . Why? $B$ advertised it reaches $C$ for 3, so total is $2 + 3$ .
Minimum: $d_{A} (C) = min (7, 5) = 5$ , next-hop $= B$ . Why B? The two-hop detour beats the direct wire.

Verify: trace the winning path $A 2 B 3 C = 5$ . The direct link (7) is strictly worse, so a "direct link always wins" intuition is false — the red path in the figure is the cheap one. ✔

Ex 3 — C3: multi-round convergence

Forecast: how many exchanges before $A$ knows the true cost to $D$ ? Guess a number.

Round 0 (know only yourself): everyone has $d_{x} (x) = 0$ , all else $\infty$ . Why? A router only knows its own link costs and that it reaches itself for free.
Round 1 (learn direct neighbours): each node adds its neighbours. $C$ learns $d_{C} (D) = 1$ . $A$ still has $d_{A} (D) = \infty$ — $D$ is 3 hops away, too far. Why? Info ripples one hop per exchange.
Round 2: $B$ hears $C$ 's " $D$ at 1", so $d_{B} (D) = c (B, C) + 1 = 2$ . $A$ still $\infty$ . Why? $D$ is now 2 hops from $B$ — reachable for $B$ , not yet for $A$ .
Round 3: $A$ hears $B$ 's " $D$ at 2", so $d_{A} (D) = c (A, B) + 2 = 3$ . Why? $A$ is 3 hops from $D$ ; it converges on exchange 3.

Verify: the true shortest path $A \to B \to C \to D$ has cost $1 + 1 + 1 = 3$ . ✔ With $n = 4$ nodes, convergence took $n - 1 = 3$ exchanges — exactly the Bellman-Ford iteration bound the parent promised.

Ex 4 — C4: a tie between next-hops

Forecast: two equal totals are coming — will the router be confused?

Via $B$ : $4 + 1 = 5$ .
Via $C$ : $2 + 3 = 5$ . Why compute both? $min$ needs every argument; we don't pre-guess.
Minimum: $d_{A} (Z) = min (5, 5) = 5$ . Why still a valid answer? A tie means two shortest paths exist — the cost is unambiguous even if the route isn't.
Next-hop: implementation picks one (usually the incumbent, to avoid route flapping). Why not both? A simple routing table stores one next-hop per destination; keeping the current one prevents needless churn.

Verify: both totals equal 5, and $5$ is the smallest possible — either path is genuinely shortest. No contradiction. ✔

Ex 5 — C5: degenerate inputs ( $\infty$ and self)

Forecast: does an $\infty$ report poison the answer?

Via $B$ : $2 + \infty = \infty$ . Why? Adding a finite link cost to "unreachable" is still unreachable — you can't finish the journey.
Via $C$ : $5 + 4 = 9$ . Why? This is a real, finite route.
Minimum: $d_{A} (Z) = min (\infty, 9) = 9$ , next-hop $= C$ . Why $C$ ? $min$ silently discards the $\infty$ branch; the good route survives.
Self-cost: $d_{A} (A) = 0$ by definition (base case), never computed via the formula. Why special-cased? The $min$ recursion would loop forever on yourself; the base case stops it.

Verify: treat $\infty$ as a huge sentinel (in RIP, $16$ ). $min (16, 9) = 9$ ✔, and $0$ is the free self-cost ✔. An unreachable neighbour cannot worsen an existing good route — it can only fail to help.

Ex 6 — C6: link break → count-to-infinity (2-node)

Forecast: $B$ lost its wire to $C$ . Will it correctly say " $C$ unreachable"? Guess.

Break: $B$ 's direct route to $C$ vanishes. But $A$ recently told $B$ " $C$ at 2". Why is that dangerous? $A$ 's "2" secretly routed through $B$ , but $B$ can't see that.
$B$ recomputes: $d_{B} (C) = c (B, A) + D_{B}^{(A)} (C) = 1 + 2 = 3$ via $A$ . Why wrong? This path is $B \to A \to B \to \dots$ — a loop. The figure's red arrow bounces back.
$B$ tells $A$ " $C$ at 3": $A$ updates $d_{A} (C) = 1 + 3 = 4$ . Why? $A$ trusts $B$ 's newest number blindly.
Ping-pong: $B \to 5$ , $A \to 6$ , … climbing by 2 each full round. Why so slow? "Bad news travels slowly" — no one has authoritative " $C$ is gone" info.
RIP cap: as soon as a value reaches $16$ , RIP declares $C$ unreachable, halting the loop. Why 16? $16 = \infty$ by definition, bounding an otherwise infinite climb.

Verify: the sequence of $d_{B} (C)$ is $3, 5, 7, 9, 11, 13, 15$ then $\geq 16 \Rightarrow \infty$ . Count the steps: from $3$ to $15$ in $+ 2$ jumps is $7$ values, so it caps after $⌈(16 - 3) /2 ⌉ = 7$ increments on $B$ 's side. Finite, but wastefully so. ✔

Ex 7 — C7: split horizon fixes it (limiting behaviour)

Forecast: what does $A$ advertise to $B$ about $C$ now?

Recall the rule: never advertise a route back to the neighbour you learned it from. Why? That neighbour is on the path — telling it back creates the loop.
$A$ learned $C$ via $B$ , so $A$ advertises " $C = \infty$ " to $B$ . Why $\infty$ ? From $B$ 's viewpoint, $A$ offers no independent route to $C$ .
Link B–C dies. $B$ looks for alternatives: its only other neighbour $A$ says " $C = \infty$ ". Why does this help? The stale "2" that fed the loop in Ex 6 is now absent.
$B$ immediately sets $d_{B} (C) = \infty$ and propagates the truth. Why fast? No false alternative exists → no ping-pong → good news (of the death) travels at full speed.

Verify: compare with Ex 6. There, $B$ had a fake option ( $1 + 2 = 3$ ); here that option is $1 + \infty = \infty$ , so $min$ yields $\infty$ on the first recompute. Convergence in 1 step instead of 7. ✔

Ex 8 — C8: the exam twist — 3-node loop where split horizon FAILS

Forecast: the parent's mistake-callout warned this. Guess why the 2-node fix isn't enough here.

Steady state: $d_{C} (Z) = 1$ ; $d_{A} (Z) = d_{B} (Z) = 2$ (both via $C$ ). See the figure's three routers. Why? $A \to C \to Z$ and $B \to C \to Z$ each cost $1 + 1 = 2$ .
Split horizon at $A, B$ : $A$ learned $Z$ via $C$ , so $A$ hides $Z$ from $C$ — but $A$ still advertises " $Z$ at 2" to $B$ (it did not learn $Z$ from $B$ ). Likewise $B \to A$ . Why is that the loophole? Split horizon only silences the neighbour on the path ( $C$ ); the sideways neighbour still hears the stale 2.
Link C–Z dies. $C$ sees $Z$ gone, but $B$ told $C$ " $Z$ at 2" (allowed — $B$ didn't learn it from $C$ … wait, $B$ did!). The failure comes from a longer route: $C$ can go $C \to A \to Z$ using $A$ 's stale "2": $d_{C} (Z) = 1 + 2 = 3$ . Why does the loop survive? Bad news must travel around the triangle; each hop re-injects a slightly larger stale estimate.
The three routers now chase each other $3 \to 4 \to 5 \dots$ around the loop, up to $16 = \infty$ . Why split horizon can't stop it: split horizon breaks 2-node loops; a 3-node loop routes the lie the long way, past the one silenced neighbour.

Verify: the true post-break cost is $d_{A} (Z) = d_{B} (Z) = d_{C} (Z) = \infty$ (nothing reaches $Z$ anymore). Any finite climbing value ( $3, 4, 5, \dots$ ) is provably wrong — there is no path to $Z$ at all once C–Z is cut. Only the $16$ -cap (plus poison reverse / hold-down timers) forces the truth. ✔ This is exactly the parent's steel-man: split horizon is necessary, not sufficient.

Ex 9 — C9: real-world word problem (RIP timers)

Forecast: does one lost packet kill a route? Guess yes/no first.

(a) Timeout fires at $t = 180$ s. Why? RIP declares a route dead if no update arrives within the 180 s timeout window.
(b) Missed updates $= 180/30 = 6$ . Why 6? Updates come every 30 s; $180 = 6 \times 30$ , so 6 consecutive missed broadcasts trigger the timeout.
(c) No — the route survives one lost packet. Why? RIP runs over UDP (port 520), which does not retransmit. A single loss is tolerated because the next periodic update (at $t = 60$ s) refreshes the timer long before the 180 s deadline.
Design insight: the 180 s timeout $= 6 \times$ the 30 s period deliberately gives slack. Why? It survives several lost updates before over-reacting — matching UDP's lossy, retransmit-free nature.

Verify: $180/30 = 6$ ✔. One loss at $t = 30$ s leaves the next update at $t = 60 s < 180 s$ , so the timer resets and the route lives ✔. The timers are consistent: timeout is an integer multiple of the period.

Recall Quick self-test

Which cell is hardest and why? ::: C8 — split horizon fixes 2-node loops but a 3-node loop routes stale info the long way, so count-to-infinity survives until the 16-cap. In Ex 1, why did the cheapest link ( $D$ , cost 1) lose? ::: Because $D$ was far from $Z$ ; Bellman-Ford minimises the total $c (x, v) + D (y)$ , not the link alone. In Ex 5, why can an $\infty$ report never worsen a good route? ::: $min$ discards the $\infty$ branch; adding a finite link cost to $\infty$ stays $\infty$ , so it only fails to help. In Ex 9, why does one lost update not kill the route? ::: RIP over UDP is lossy but the 180 s timeout equals 6 update periods, so the next 30 s broadcast refreshes the timer.

Related vault topics: Bellman-Ford Algorithm, Dijkstra's Algorithm, Principle of Optimality, Dynamic Programming, Link-State Routing (OSPF), Routing Tables and Next-Hop Forwarding, BGP, UDP.