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

WHAT is Distance Vector Routing?

Contrast this with Link-State routing (OSPF), where every router knows the whole topology. DV trades global knowledge for simplicity: "tell only neighbours, tell them everything."

WHY share with neighbours only? Because a router can only physically measure the cost to its direct neighbours (link cost). Everything beyond that must be learned second-hand. So information ripples outward, one hop per exchange.

HOW: deriving the Bellman-Ford update from scratch

Let $d_x(y)$ = the cheapest cost from node $x$ to node $y$. Let $c(x,v)$ = the cost of the direct link from $x$ to its neighbour $v$.

Step 1 — first principles. Any path from $x$ to $y$ (with $y\neq x$) must leave $x$ through some neighbour $v$. Once you commit to leaving via $v$, the best you can do afterward is $d_v(y)$ (the best $v$ itself can do to reach $y$).

Step 2 — cost of going via $v$. $\text{cost via } v = c(x,v) + d_v(y)$ Why this step? The total = (price to step onto $v$) + (best price $v$ knows to finish the journey).

Step 3 — pick the best neighbour. Since we want the cheapest path and we don't know which neighbour is best, we minimise over all neighbours:

Why is this correct? It's just the principle of optimality: a shortest path's sub-paths are also shortest. If the best route to $y$ goes $x\to v\to\ldots\to y$, then the $v\to\ldots\to y$ portion must itself be $v$'s shortest route to $y$ — otherwise we could swap in a cheaper tail and beat our own "shortest" path (contradiction).

The distributed twist: node $x$ doesn't compute $d_v(y)$ itself — $v$ tells $x$ its current estimate $D_v(y)$ in its distance-vector message. So in practice each router runs: $D_x(y) \leftarrow \min_{v}\{\, c(x,v) + D_x^{(v)}(y)\,\}$ where $D_x^{(v)}(y)$ is the latest estimate of $d_v(y)$ that $x$ received from $v$. Whenever any $D_x(\cdot)$ changes, $x$ broadcasts its new vector to neighbours.

RIP — the real-world DV protocol

Key RIP facts (WHY they exist):

The Count-to-Infinity Problem

HOW it happens (WHY each step): Consider A — B — C, all link costs 1.

• Steady state: $B$ reaches $C$ at cost 1 (direct); $A$ reaches $C$ at cost 2 via B.
• The link B–C breaks.
• $B$ should now see $C$ as unreachable. But $A$ recently told $B$: "I can reach C at cost 2!" — $B$ doesn't know $A$'s route to C went through B itself.
• So $B$ concludes: "I'll reach C via A: cost $= 1 + 2 = 3$." (WRONG — that path loops $B\to A\to B$.)
• $B$ tells $A$ "C is at 3", so $A$ updates to "C via B at $1+3 = 4$"… and they ping-pong: 5, 6, 7 … up to 16 = ∞.

The root cause: a router advertises a route back to the very neighbour it learned it from.

Fixes

Worked Example 1 — one Bellman-Ford update

Network: A—B=2, B—C=3, A—C=7. Find $A$'s cost to $C$.

• $A$'s neighbours: $B$ (cost 2) and $C$ (cost 7).
• Via $C$: $c(A,C)+d_C(C) = 7 + 0 = 7$. Why? Direct link to the destination.
• Via $B$: $c(A,B)+d_B(C) = 2 + 3 = 5$. Why? $B$ already advertised it reaches $C$ at 3.
• $d_A(C) = \min(7,5) = \mathbf{5}$, next-hop $= B$. Why B? It's the cheaper of the two options.

Worked Example 2 — count-to-infinity trace

A—B—C, costs 1. Link B–C dies. Tables for "cost to C":

Why this is the disaster: until they hit 16, packets to C loop A↔B forever.

Worked Example 3 — split horizon prevents it

Same break, with split horizon: $A$ learned C via B, so $A$ advertises "C = ∞" to $B$. Now when B–C dies, $B$ has no false alternative (A told it ∞), so $B$ immediately marks C unreachable. Why it works: the looping estimate was never injected back.

Flashcards

Connections

• Link-State Routing (OSPF) — global-map alternative using Dijkstra's Algorithm
• Bellman-Ford Algorithm — the graph-theory core (also handles negative edges, unlike Dijkstra)
• Principle of Optimality / Dynamic Programming — why sub-paths of shortest paths are shortest
• BGP — a path-vector protocol; advertises full AS-paths to cure count-to-infinity at scale
• UDP — transport RIP relies on (port 520)
• Routing Tables and Next-Hop Forwarding

Concept Map

Hinglish (regional understanding)