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

This page assumes you have seen none of the notation in the parent note. We build each symbol, one at a time, each on top of the last. If a word or squiggle appears in the parent topic and you cannot yet explain it out loud, it lives here.

0. The picture everything sits on: a network as dots and lines

Before any symbol, fix the picture in your head.

Look at the figure. $A$, $B$, $C$ are dots. The lines are wires. The number next to each line is that link's cost. That is the entire world distance-vector routing operates in: dots, lines, and numbers on the lines. Everything below is bookkeeping about this picture.

Why do we need "cost" at all? Because "shortest" has to mean something countable. Sometimes cost = number of hops (RIP), sometimes it stands for delay or congestion. It is just a price tag so we can compare two routes and say which is cheaper.

1. The letters $x$, $y$, $v$ — who is who

The parent note throws around $x$, $y$, $v$. These are not magic — they are just roles a dot can play in one sentence.

The same physical router can be $x$ in one sentence and $v$ in the next — it depends whose point of view we take. Think of $x$ = the person speaking, $y$ = the place they want to go, $v$ = a friend standing right next to them.

2. $N(x)$ — the set of my neighbours

A set is just a bag of things with no repeats. If $A$ is wired to both $B$ and $C$, then $N(A)=\{B,C\}$ — read aloud as "the neighbours of A are B and C."

Why the topic needs this. A router can only measure the price to dots it is directly wired to. Everything further away must be heard about second-hand. So $N(x)$ is precisely the list of routers $x$ is allowed to talk to and directly measure. It is the boundary of what a router can know first-hand.

3. $c(x,v)$ — the price of one hop

Point at the figure again: $c(A,B)$ is literally the number printed on the line between $A$ and $B$. Nothing hidden. If there is no direct wire, $c(x,v)$ is not a one-hop cost at all — you would have to go through others, and that is what the whole algorithm computes.

4. $d_x(y)$ — the cheapest total cost, "me → there"

Now the star symbol.

Careful — this is different from $c(x,y)$:

• $c(x,y)$ = one wire, one hop (only if they are neighbours).
• $d_x(y)$ = the best whole journey, possibly through many dots.

In the figure, the direct wire $A\to C$ costs $7$ (that is $c(A,C)$), but the two-hop journey $A\to B\to C$ costs $2+3=5$. So $d_A(C)=5$, not $7$. The little arrows trace the winning path in green.

Two special values you must always keep in mind (every case matters):

5. $\infty$ — the symbol for "can't get there"

Why the topic leans on this. When we take the cheapest of several options, an unreachable option must never win. Tagging it $\infty$ guarantees the minimum ignores it. Later, RIP replaces this abstract $\infty$ with the concrete number 16 — a deliberate, finite stand-in so the count-to-infinity loop can only climb 16 steps instead of forever.

6. $\min$ — "pick the smallest"

Example: $\min \{7,5\}=5$. When we also write ${\min }_{v\in N(x)}$, the little "$v\in N(x)$" underneath reads "for every neighbour $v$" — so it means "try each neighbour, compute a number for each, then keep the smallest."

7. Putting the symbols together — reading the Bellman-Ford line

Now you can read the parent's headline equation with no mystery:

Every piece is something you now own: $x$=me, $y$=there, $v$=a neighbour, $N(x)$=all my neighbours, $c(x,v)$=one-hop price, $d_v(y)$=neighbour's best onward cost, $\min$=keep smallest. That is the whole topic in one line.

8. Capital $D$ vs little $d$ — belief vs truth

The parent quietly switches between $d_x(y)$ and $D_x(y)$. This is not a typo; it is the heart of "distributed."

And $D_x^{(v)}(y)$ is "the latest value of $v$'s estimate $D_v(y)$ that reached $x$ in a message." The superscript $(v)$ means "as reported by $v$." Why this distinction is essential: the count-to-infinity bug is exactly the gap between $D$ (belief) and $d$ (truth) — routers keep trusting old $D$ values that no longer match reality after a link breaks.

9. The distance vector itself — a table, drawn

The figure shows $A$'s table. The next-hop column is the neighbour $A$ hands the packet to first — it is the $v$ that won the $\min$. This is why the algorithm stores not just the winning cost but who it won through: forwarding needs an address to send to right now, and that is covered in Routing Tables and Next-Hop Forwarding.

10. Where the deeper ideas come from

Two phrases in the parent point at bigger machinery you should recognise by name:

This is the reason the Bellman-Ford equation is even allowed to reuse $d_v(y)$ — see Principle of Optimality and its parent idea Dynamic Programming. Solving a problem ($d_x$) by reusing answers to smaller sub-problems ($d_v$) is exactly what dynamic programming is.

The equation itself, run all at once with a full map instead of gossip, is the classic Bellman-Ford Algorithm. Its cousin for the same "shortest path" goal — but needing the whole map and non-negative costs — is Dijkstra's Algorithm, which powers Link-State Routing (OSPF). And the transport that carries RIP's gossip is UDP. The internet-scale relative of all this is BGP.

The prerequisite map

Read top to bottom: the picture of dots and lines gives us $c$ and $N$; those plus $\infty$ define $d$; $\min$ plus $d$ plus optimality assemble the Bellman-Ford equation; add "belief vs truth" and the table, and you have the full topic.

Equipment checklist

Say each answer out loud before revealing. If any is shaky, re-read its section.