6.1Distance vector routing
The idea
In distance vector routing each router tells its neighbours its whole table (destination and distance). A router picks the neighbour that gives the smallest total: the Bellman-Ford update.
Think of it like this: Asking friends for directions: each friend tells you only how far they are from town, and you add the distance to that friend.
Why it exists
GATE compares DV with link state and asks about count-to-infinity.
How it works
- Start: each router knows only its direct links.
- Each round: cost(x to y) = min over neighbours k of [cost(x, k) + cost(k to y)].
- Repeat until no table changes (at most n − 1 rounds).
- Problem: when a link fails, two routers can feed each other stale routes and count up to infinity. Split horizon (do not advertise a route back to its source) breaks the two-router loop.
Worked example: A - B - C, B-C fails.
Without split horizon A still tells B "I reach C in 2", B believes it and sets 3, then A sets 4, and so on to infinity. With split horizon A never advertises C to B.
Now play with it
- →Pick router A and step through rounds to see the table fill in.
- →Switch split horizon on and off in the second table.
Link costs: A-B = 2, A-C = 5, B-C = 1, B-D = 4, C-D = 1, D-E = 3. Each round, every router recomputes its table from its neighbours' tables.
| destination | cost | next hop |
|---|---|---|
| A | 0 | A |
| B | 2 | B |
| C | 5 | C |
| D | ∞ | - |
| E | ∞ | - |
After round 0 a router only knows its direct neighbours. After at most n − 1 rounds all tables are final (Bellman-Ford).
Count to infinity. Line A - B - C, all links cost 1. The B-C link fails. Infinity is 16 (as in RIP).
| step | B to C | A to C | what happened |
|---|---|---|---|
| 0 | 1 | 2 | Before the failure: B-C costs 1, A reaches C through B at cost 2. |
| 1 | inf | 2 | B-C fails. B has no route to C yet. |
| 2 | 3 | 2 | B hears A's old advertisement (A to C = 2) and sets B to C = 2 + 1 = 3. |
| 2 | 3 | 4 | A hears B's new value (3) and sets A to C = 3 + 1 = 4. |
| 3 | 5 | 4 | B hears A's old advertisement (A to C = 4) and sets B to C = 4 + 1 = 5. |
| 3 | 5 | 6 | A hears B's new value (5) and sets A to C = 5 + 1 = 6. |
| 4 | 7 | 6 | B hears A's old advertisement (A to C = 6) and sets B to C = 6 + 1 = 7. |
| 4 | 7 | 8 | A hears B's new value (7) and sets A to C = 7 + 1 = 8. |
| 5 | 9 | 8 | B hears A's old advertisement (A to C = 8) and sets B to C = 8 + 1 = 9. |
| 5 | 9 | 10 | A hears B's new value (9) and sets A to C = 9 + 1 = 10. |
| 6 | 11 | 10 | B hears A's old advertisement (A to C = 10) and sets B to C = 10 + 1 = 11. |
| 6 | 11 | 12 | A hears B's new value (11) and sets A to C = 11 + 1 = 12. |
| 7 | 13 | 12 | B hears A's old advertisement (A to C = 12) and sets B to C = 12 + 1 = 13. |
| 7 | 13 | 14 | A hears B's new value (13) and sets A to C = 13 + 1 = 14. |
| 8 | 15 | 14 | B hears A's old advertisement (A to C = 14) and sets B to C = 14 + 1 = 15. |
| 8 | 15 | 16 (∞) | A hears B's new value (15) and sets A to C = 15 + 1 = 16. |
Check yourself
Distance vector routing uses
Exam notes (the dense version)
Each router keeps a table of (destination, cost, next hop) and periodically sends its whole table to its neighbours. On receiving a neighbour's vector it applies Bellman-Ford: cost(via k) = cost(to k) + k's cost to destination. It needs only local knowledge but converges slowly ("bad news travels slowly"): after a link failure two routers can keep increasing a cost until infinity (count to infinity). Fixes: split horizon (do not advertise a route back to where you learned it), poison reverse, and a small infinity (RIP uses 16).
Previous year questions: Routing & Congestion Control (3)
PYQs are grouped by topic, so this is the full set for Routing & Congestion Control; try the ones that match this subtopic. Open all 3 on the topic page.