Distance vector routing — RIP, Bellman-Ford, count-to-infinity: Visual walkthrough

This is the visual companion to the parent topic. If a word here feels heavy, it also links out to Bellman-Ford Algorithm, Principle of Optimality and Dynamic Programming.

Step 1 — What is a "network" and a "cost"?

WHAT. Before any math, picture the world routers live in. Draw a few nodes (circles = routers) joined by links (lines = cables). Each link has a cost — a plain number written on the line. Think of cost as "how expensive / slow / how many hops it is to cross this cable."

WHY. A router cannot see the whole drawing. It can only feel the links plugged directly into it — it knows the number on its own cables and nothing else. Everything past that first hop is a rumour it must be told.

PICTURE. Look at the figure: node $A$ (burnt orange) can directly read the cost $2$ on its cable to $B$ and $7$ on its cable to $C$ . The dashed cloud shows everything $A$ cannot see by itself.

Step 2 — Every journey out of $x$ starts by choosing a first neighbour

WHAT. Take any destination $y$ (with $y \neq = x$ ). Whatever the cheapest route is, it has to physically leave $x$ through one of $x$ 's cables — i.e. through one neighbour $v$ .

WHY. There's no teleporting. The very first move of any path is "step onto one neighbouring node." So the giant question "what is the cheapest route to $y$ ?" splits into a small menu of choices: "the cheapest route that starts by going to neighbour $v_{1}$ ," "...that starts with $v_{2}$ ," and so on.

PICTURE. The figure fans out from $A$ : one plum arrow commits to leaving via $B$ , one teal arrow commits to leaving via $C$ . Each arrow is one entry on the menu. The real shortest path is hiding inside one of these branches.

Step 3 — Cost of committing to neighbour $v$

WHAT. Suppose we've decided our route leaves through $v$ . Its total cost is exactly:

$price to step onto v c (x, v) + best v itself can do to reach y d_{v} (y)$

WHY. Once we're standing on $v$ , our history no longer matters — only "how cheaply can $v$ finish the trip to $y$ ?" And by definition the cheapest $v$ can finish is $d_{v} (y)$ . So the whole via- $v$ cost is: the one cable to arrive + $v$ 's own best effort onward.

PICTURE. The figure lays the two pieces end to end like train segments: a short orange segment $c (x, v)$ from $x$ to $v$ , then a longer teal segment $d_{v} (y)$ from $v$ to $y$ . Their lengths literally add.

Step 4 — Pick the cheapest option: the Bellman-Ford equation

WHAT. We don't know in advance which neighbour is best, so we compute the via- $v$ cost for every neighbour and keep the smallest.

$d_{x} (y) = min_{v \in N (x)} {one cable c (x, v) + v ’s best onward d_{v} (y)}$

WHY the $min$ ? "Cheapest" means "smallest number." The $min_{v}$ symbol simply says: try each neighbour $v$ from the set $N (x)$ (all of $x$ 's direct neighbours), and grab the lowest total. This is the tool that chooses — no other operation compares a whole set and returns the smallest.

PICTURE. The figure shows a little bar chart: one bar per neighbour, height = its via-cost. A plum highlight marks the shortest bar — that height is $d_{x} (y)$ , and that neighbour becomes the next-hop.

Step 5 — Why is keeping only the minimum actually correct?

WHAT. We only stored $d_{v} (y)$ (a single number) for each neighbour, throwing away the details of how $v$ gets to $y$ . Is that safe?

WHY — the Principle of Optimality. Yes, because a shortest path's pieces are themselves shortest. Suppose the true best route is $x \to v \to \dots \to y$ . Cut off the first hop; the remaining tail $v \to \dots \to y$ must be $v$ 's own shortest route to $y$ . If it weren't, we could swap in a cheaper tail and beat our supposed "shortest" total — a contradiction.

PICTURE. The figure shows a full path with the tail highlighted. A little "swap-in a cheaper tail?" balloon is crossed out — it would contradict optimality. So the single number $d_{v} (y)$ is all we ever need from $v$ .

Step 6 — The distributed twist: rumours instead of truth

WHAT. In a real router, $x$ does not know the true $d_{v} (y)$ . It only has the latest number $v$ told it, which we write $D_{x}^{(v)} (y)$ . So the router actually runs:

$D_{x} (y) \leftarrow min_{v} {c (x, v) + last rumour from v D_{x}^{(v)} (y)}$

WHY. Neighbours broadcast their whole vector every so often (in RIP, every 30 s over UDP port 520). Between broadcasts $x$ works off possibly-stale numbers. When any $D_{x} (\cdot)$ changes, $x$ re-broadcasts, and the wave continues.

PICTURE. The figure shows the same $A$ – $B$ – $C$ line as three rounds of message passing. Round 0: only nodes touching $C$ know its cost. Round 1: their neighbours learn. Round 2: everyone within 2 hops knows. Knowledge spreads one hop per exchange.

Step 7 — Edge case: good news is fast, bad news is slow

WHAT. So far every rumour improved things. Now watch a link die. On the line $A$ – $B$ – $C$ (all costs 1), the cable $B$ – $C$ snaps.

WHY it breaks. $B$ should now say " $C$ is unreachable." But $A$ just told $B$ "I reach $C$ at cost 2" — and $B$ has forgotten that $A$ 's route to $C$ went back through $B$ . So $B$ believes a phantom path and computes $1 + 2 = 3$ . Then $A$ trusts $B$ 's $3$ and jumps to $4$ . They ping-pong upward.

PICTURE. The figure traces the disaster: the broken $B$ – $C$ cable in red, and a curling arrow showing $B \to A \to B$ , the loop the phantom route secretly contains. Beside it, the climbing numbers $3, 4, 5, 6, \dots \to 16$ .

Step 8 — The fix in a picture: split horizon

WHAT. Rule: never advertise a route back to the neighbour you learned it from. Since $A$ learned $C$ via $B$ , $A$ tells $B$ that " $C = \infty$ " (poison reverse states it out loud as cost $16$ ).

WHY. This deletes the phantom option before it can be chosen. When $B$ – $C$ dies, $B$ looks for an alternative, sees only $A$ 's honest " $\infty$ ", and immediately marks $C$ unreachable — no climb.

PICTURE. The figure contrasts the two worlds: on the left, $A$ 's stale " $2$ " leaks back and starts the climb; on the right, split horizon shows $A$ sending " $\infty$ " back to $B$ , so the bad number is never injected.

The one-picture summary

Everything above, compressed: split the journey by first neighbour (Step 2) → each option costs one cable + a reported onward cost (Step 3) → take the $min$ (Step 4), justified by optimality (Step 5) → run it on rumours (Step 6) → beware phantom loops on link death (Step 7) → cure with split horizon + a $16$ -cap (Step 8).

Recall Feynman retelling — say it in plain words

Imagine everyone in a city only knows how far their next-door neighbours claim to be from a landmark. To find your own distance, you ask each neighbour "how far are you, and how far is my cable to you?" — add those two numbers, and keep the smallest answer. That "keep the smallest" is safe because the tail of a shortest trip is itself a shortest trip, so a single number per neighbour is all you need. Neighbours shout their numbers periodically, so knowledge spreads one street per round; after enough rounds the whole city is correct. The one danger: if a road closes, someone might repeat your own old number back to you as if it were a fresh route, and the two of you bounce a phantom distance higher and higher. Two cures: never quote a route back to whoever told you it (split horizon), and declare "16 = unreachable" so any leftover bouncing stops fast.

Recall Quick self-check

Which operation actually chooses the next-hop in Bellman-Ford? ::: The $min$ over neighbours — it returns the smallest via-cost, and the neighbour that achieved it becomes the next-hop. Why can neighbour $v$ send just one number instead of its whole map? ::: Principle of optimality — only $d_{v} (y)$ (its best onward cost) can matter to $x$ ; the internal path details never change $x$ 's decision. In count-to-infinity, is the Bellman-Ford $min$ wrong? ::: No — it correctly minimises poisoned input. The bug is a phantom route fed back to its source; fix the data with split horizon.

Related: Routing Tables and Next-Hop Forwarding · Link-State Routing (OSPF) · BGP