Kurose and Ross, Computer Networking: A Top-Down Approach, sections 5.1 and 5.2.2, cross-checked against RFC 2453 (RIP Version 2; RIP is the Routing Information Protocol), a distance-vector protocol whose specification describes split horizon (never advertising a route back to the neighbor it was learned from) with poisoned reverse (advertising it back as infinity instead), and treats a metric of 16 as infinity. Every update sequence below was simulated in code.
Learn the equation and say it in words. Then redo the three-router examples on paper, one update per line.
The picture: asking the neighbors for directions#
Picture yourself in a town with no map. You know how long each road to a next-door town takes. Each next-door friend sends you a list: “From here, I can reach Z in 9 minutes, Y in 4.”
To find your own best time to Z, you add your road to each friend onto that friend’s time to Z, and keep the smallest total. Then you send your new list to your own neighbors, and they do the same.
That is distance-vector routing. Nobody has the whole map. Answers spread one neighbor at a time until every list stops changing.
Vocabulary, before anything uses it#
| Term | What it means |
|---|---|
| c(x, v) | The cost of the direct link from node x to its neighbor v. |
| dx(y) | The true least cost of a path from node x to node y. |
| Dx(y) | Node x’s current estimate of that least cost. It may be wrong until the network settles. |
| Distance vector, Dx | The list of node x’s estimates to every destination: [Dx(y) for every y]. |
| Next hop | The neighbor on the first link of the best path. |
| Converge | To settle: every node’s estimates stop changing and equal the true least costs. |
| Routing loop | Two or more routers each forward packets for a destination to the next one in a circle, so the packets go round and round. |
| Count-to-infinity | After a link gets worse, routers raise their estimates in small steps, one exchange at a time, instead of jumping to the right answer. |
| Poisoned reverse | If x reaches y through neighbor z, x tells z that its distance to y is ∞. RIP calls this “split horizon with poisoned reverse”. |
The Bellman-Ford equation#
Everything in distance-vector routing comes from one equation:
dx(y) = minv { c(x, v) + dv(y) }
Read it like this: “my cheapest cost to y is, over all my neighbors v, the smallest value of (my link to v) plus (v’s cheapest cost to y)”.
Why is it true? Any path from x to y must leave x over a link to some neighbor. From there, the best possible is that neighbor’s own least cost. The neighbor that gives the minimum is the next hop, which goes into the forwarding table.
Three routers, P, Q and R. The links cost c(P, Q) = 3, c(Q, R) = 1 and c(P, R) = 21. Q knows its cost to R is 1, and R’s cost to itself is 0. P works out its cost to R:
DP(R) = min { c(P, Q) + DQ(R), c(P, R) + DR(R) } = min { 3 + 1, 21 + 0 } = 4.
The minimum came from Q, so P’s forwarding table sends traffic for R to Q, not over the direct link that costs 21.
How the algorithm runs#
Each node x keeps three things: the cost c(x, v) of each of its own links, its own distance vector Dx, and the latest distance vector it has heard from each neighbor. Then it loops forever:
- Wait until a neighbor sends a new distance vector, or one of x’s own link costs changes.
- Recompute Dx(y) for every destination y, using the Bellman-Ford equation.
- If anything changed, send the new vector to every neighbor.
So the algorithm is distributed: each node works only with what its neighbors tell it. It is iterative: it repeats until nothing changes, then stops by itself. It is asynchronous: nodes do not run in lockstep.
| Router | Before any exchange | After one exchange |
|---|---|---|
| P | 0, 3, 21 | 0, 3, 4 |
| Q | 3, 0, 1 | 3, 0, 1 |
| R | 21, 1, 0 | 4, 1, 0 |
P lowers its cost to R from 21 to 4 (through Q), and R lowers its cost to P to 4 in the same way: min{1 + 3, 21 + 0} = 4. A second exchange changes nothing: the network has converged.
When a link cost changes: good news and bad news#
When one of a router’s own links changes cost, it recomputes and tells its neighbors if its vector changed. How fast things settle depends on whether the news is good or bad. Watch only each router’s distance to P.
Good news travels fast
Start from the converged network, where Q reaches P for 3 (direct) and R reaches P for 4 (through Q). Now c(P, Q) drops from 3 to 1.
- Step 0: Q recomputes: min{1 + 0, 1 + 4} = 1, direct. Q tells R.
- Step 1: R recomputes: min{21 + 0, 1 + 1} = 2, through Q. R tells Q.
- Step 2: Q recomputes: still 1. Nothing changed, so nothing is sent. Done.
Bad news travels slowly
Start again from the converged network. Now c(P, Q) jumps from 3 to 50. The right answer is R direct (21) and Q through R (22). Here is what happens:
| Step | Who updates | Calculation | New distance to P |
|---|---|---|---|
| 0 | Q | min{50 + 0, 1 + 4} | 5, through R |
| 1 | R | min{21 + 0, 1 + 5} | 6, through Q |
| 2 | Q | min{50 + 0, 1 + 6} | 7, through R |
| 3 | R | min{21 + 0, 1 + 7} | 8, through Q |
| … | … | each step adds 1 to the other router’s estimate | … |
| 15 | R | min{21 + 0, 1 + 19} | 20, through Q |
| 16 | Q | min{50 + 0, 1 + 20} | 21, through R |
| 17 | R | min{21 + 0, 1 + 21} | 21, direct |
| 18 | Q | min{50 + 0, 1 + 21} | 22, through R |
The trouble starts at step 0. R’s old estimate of 4 was a path through Q, but Q cannot tell that. So Q routes through R while R routes through Q: a routing loop, where a packet for P bounces between them. Each exchange raises the estimates by only 1, and it takes 18 updates before the loop breaks (R switches to its direct link at step 17) and 19 before every estimate is correct. This slow climb is the count-to-infinity problem. If there were no P–R link at all, the estimates would climb forever.
Poisoned reverse, and where it stops working#
The fix for the two-router loop is simple. If R reaches P through Q, R tells Q: “my distance to P is ∞”. The lie stops Q from routing to P through R.
Replay the bad news with poisoned reverse. Before the change, R routes to P through Q, so R has been telling Q its distance to P is ∞.
- Step 0: Q recomputes: min{50 + 0, 1 + ∞} = 50, direct. Q tells R.
- Step 1: R recomputes: min{21 + 0, 1 + 50} = 21, direct. R no longer uses Q, so it now tells Q the truth: 21.
- Step 2: Q recomputes: min{50 + 0, 1 + 21} = 22, through R. Now Q poisons its route back toward R. Done.
Three updates instead of 19, and no loop.
Link state vs distance vector#
Exams often ask for this comparison.
| Link state (Dijkstra) | Distance vector (Bellman-Ford) | |
|---|---|---|
| What each router knows | The whole map: every link and its cost | Only its own link costs and its neighbors’ vectors |
| Message complexity | High: O(nE) messages for n nodes and E links; every cost change must reach every node | Lower: messages go only between neighbors, and only when a vector changes |
| Speed of convergence | O(n²) computation once the map is in; can oscillate with load-based costs | Varies; routing loops can form while it settles, and bad news causes count-to-infinity |
| Robustness | A faulty router can only lie about its own links, and each router computes its own table | A faulty router can advertise wrong costs to every destination, and the error spreads |
| Protocol example | OSPF (Open Shortest Path First) | RIP (Routing Information Protocol) |
In distance-vector routing each router applies Dx(y) = minv{c(x, v) + Dv(y)} to its neighbors’ vectors and passes on any change, so it is distributed, iterative and asynchronous; good news spreads fast, bad news can count to infinity through a routing loop, and poisoned reverse fixes only two-router loops.
Practice#
For every update, write the full min{ } with one term per neighbor before picking the answer.
- Write the Bellman-Ford equation and say in words what each part means.
- Router M has three neighbors: c(M, J) = 2, c(M, K) = 7, c(M, L) = 4. It has just received these vectors (costs to J, K, L, Z): J sends (0, 5, 3, 6); K sends (5, 0, 2, 1); L sends (3, 2, 0, 3). Compute M’s distance vector and the next hop for each destination.
- In the three-router network (c(P, Q) = 3, c(Q, R) = 1, c(P, R) = 21), the cost of P–Q falls from 3 to 2. What are Q’s and R’s new distances to P, and how many updates does it take?
- Same network, with poisoned reverse turned on and nothing changed yet. What does R tell Q about its distance to P, and what does Q tell R?
- Suppose c(P, R) were 101 instead of 21, poisoned reverse is off, and c(P, Q) rises from 3 to 500. Where do Q and R end up, and roughly how long does it take?
- Why does poisoned reverse not prevent a routing loop through three routers?
- Give one advantage of distance vector over link state, and one advantage of link state over distance vector.
Solutions#
Find the first line where your working split from the solution, and redo the problem from that line. Do not just read the answer and nod.
- dx(y) = minv{c(x, v) + dv(y)}. The least cost from x to y is found by trying every neighbor v: add the cost of x’s link to v and v’s least cost to y, and keep the smallest total. The v that wins is the next hop.
- To J: 2 via J. To K: 6 via L. To L: 4 via L. To Z: 7 via L. K: min{2 + 5, 7 + 0, 4 + 2} = min{7, 7, 6} = 6, so the direct link (7) loses. L: min{2 + 3, 7 + 2, 4 + 0} = 4. Z: min{2 + 6, 7 + 1, 4 + 3} = 7. J: min{2 + 0, 7 + 5, 4 + 3} = 2.
- Q: 2, direct. R: 3, through Q. Two updates. Q: min{2 + 0, 1 + 4} = 2. R: min{21 + 0, 1 + 2} = 3. Q then recomputes 2 again and sends nothing.
- R tells Q ∞; Q tells R 3. R reaches P through Q, so it poisons that route toward Q. Q reaches P directly, not through R, so it tells R its true cost.
- R ends at 101 direct and Q at 102 through R, after 99 updates. The estimates climb by 1 per update (5, 6, 7, …) until R’s direct link at 101 beats going through Q.
- Each router poisons only its own next hop. Say Q routes through R, R through S, and S through Q. Q poisons R, R poisons S, and S poisons Q. But each router still hears a finite, stale cost from its own next hop, the router ahead of it in the circle (Q hears a finite cost from R, because R routes through S, not Q), so the loop keeps feeding itself.
- Distance vector: fewer messages, sent only between neighbors. Link state: faster, more robust convergence. Each router computes its own table from the full map, so there is no count-to-infinity and a faulty router cannot spread wrong costs everywhere.
Test-readiness checklist#
- ☐ I can write the Bellman-Ford equation and explain every symbol in it.
- ☐ I can compute a router’s new distance vector and next hops from its neighbors’ vectors.
- ☐ I can explain what distributed, iterative and asynchronous mean for this algorithm.
- ☐ I can show why good news spreads in a couple of updates and bad news can count to infinity.
- ☐ I can apply poisoned reverse to a two-router example and say why it fails for longer loops.
- ☐ I can compare link state and distance vector on messages, convergence and robustness.
Before trusting a neighbor’s estimate in a count-to-infinity question, ask: does that estimate go through me? If it does, that is the loop.
Frequently asked questions#
What is the Bellman-Ford equation?
It says the least cost from x to y is the minimum, over every neighbor v of x, of the cost of the link from x to v plus v's least cost to y. Written d_x(y) = min over v of c(x, v) + d_v(y). The neighbor that gives the minimum is the next hop.
What is the count-to-infinity problem?
When a link cost rises, routers can keep trusting a neighbor's old estimate that actually runs through themselves. They form a routing loop and raise their estimates in small steps, taking many rounds to settle, or never settling if no other path exists.
What is poisoned reverse?
If router x reaches a destination through neighbor z, x tells z that its own distance to that destination is infinity. This stops z from routing back through x and breaks two-router loops. It does not stop loops involving three or more routers.
What is the difference between link-state and distance-vector routing?
In link state every router learns the full map and runs Dijkstra itself; it needs more messages but errors stay local. In distance vector routers only swap estimates with neighbors; it needs fewer messages but can loop and count to infinity.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.
Test yourself on this topic
The free networking practice app has 10 questions on this guide and 500 across the whole course, each with an explanation for every answer. Offline, no ads, no account.
Practise this topic →