Recall warm-up
- In Distance Vector routing, does Router B’s advertised distance D_B(C) = 2 tell Router A whether B’s path goes through A or C?
Stuck? Peek at 3.4.2 Distance Vector routing & the Bellman-Ford equation
- Bellman-Ford:
Dₓ(y) = min_{v ∈ N(x)} { c(x, v) + D_v(y) }. - DV message: contains
[(y, Dₓ(y))]for all destinations y; sent only to immediate neighbours. - If the current next-hop's distance increases, recompute that branch before taking the minimum.
- Bellman-Ford:
- Which field in the IPv4 header prevents a packet caught in a routing loop from circulating forever?
Stuck? Peek at 3.2.1 IPv4 header fields: HLEN, Total Length, TTL, Protocol & Checksum
- Base header = 20 B (`HLEN = 5`); Max header = 60 B (`HLEN = 15`, max 40 B options).
- Multipliers: `Header = 4 × HLEN`, `Total Length = Header + Payload` (max 65,535 B), `Offset × 8 = start byte`.
- Per-hop changes: Every router decrements TTL by 1 (drops if 0) and recomputes Header Checksum (which covers IP header only).
- If link B–C fails and B mistakenly sends packets for C to A while A sends packets for C to B, what happens to those packets?
Stuck? Peek at 1.2.2 Packet switching: store-and-forward, datagrams, statistical multiplexing
- Packet switching: packets with headers; no reservation; full link rate while sending.
- Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
- Datagram: each packet routed independently; may reorder; robust to failures.
- Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.
The Hook
Why is hiding the path inside a Distance Vector dangerous? Consider three routers in a line: A —(1)— B —(1)— C. Initially B reaches C in 1 hop, and A reaches C via B in 2 hops. Suddenly the link B–C snaps!
B looks at its neighbour A and sees that A advertised D_A(C) = 2. Because B doesn't know that A's route goes through B itself, B thinks: "Great! I can reach C via A in 1 + 2 = 3 hops!" Next, A hears 3 from B and updates its own cost to 1 + 3 = 4. They bounce back and forth — 3, 4, 5, 6, … — counting all the way to infinity!
Predict First
In A —(1)— B —(1)— C, suppose instead the link A–B had cost 1 and B–C was newly repaired (cost dropped from ∞ to 1). How many exchanges does it take for good news to reach A, versus when B–C breaks and they must count up to 16?
When B–C comes up (good news), B learns cost 1 immediately and tells A (cost 2) in just 1 exchange! When B–C breaks (bad news), each exchange increases the bogus cost by only 1 (3, 4, 5, …, 16), taking 14 exchanges! In DV: "Good news travels fast; bad news travels slow."
Core Concept
Tracing the Count-to-Infinity Loop
On A —(1)— B —(1)— C, before failure: D_B(C) = 1 (via C) and D_A(C) = 2 (via B). Now link B–C fails (cost = ∞) and routers update turn-by-turn:
- Step 1 (B updates): Direct link to C is ∞, but A's last advertisement was
D_A(C) = 2. So B setsD_B(C) = 1 + 2 = 3 (via A)— a routing loopB ⇄ Ais born! - Step 2 (A updates): Since A's next hop to C is B, A must update to
D_A(C) = 1 + 3 = 4 (via B). - Step 3 (B updates): B updates from A to
D_B(C) = 1 + 4 = 5 (via A), and so on forever!
| Event / Step | D_A(C) (Next Hop) | D_B(C) (Next Hop) | What is happening? |
|---|---|---|---|
| Before failure | 2 (via B) | 1 (via C) | Valid shortest paths to C |
| Link B–C fails; Step 1 (B updates) | 2 (via B) | 3 (via A) | B is fooled by A’s echo of B’s own old route! |
| Step 2 (A updates from B) | 4 (via B) | 3 (via A) | A’s route goes via B, so A adds 1 + 3 = 4 |
| Step 3 (B updates from A) | 4 (via B) | 5 (via A) | B adds 1 + 4 = 5 |
| … continues … | 14 → 16 (∞) | 15 → 16 (∞) | Only stops when both hit the "infinity" ceiling (16)! |
Defining "Infinity = 16" in RIP
To stop routers from counting forever when a destination is unreachable, Distance Vector protocols like RIP define a small integer ceiling as "infinity":
Infinity = 16 (meaning "unreachable"). Therefore, the maximum valid path cost (hop count) in RIP is 15, and RIP cannot be used in networks whose diameter exceeds 15 hops.The Fixes: Split Horizon & Poison Reverse (and their limit)
Why did B get fooled? Because A advertised its route to C back to B, the very neighbour from whom A learned it! Two rules prevent 2-node loops:
- Split Horizon: If router A routes to destination C via neighbour B, then A omits C completely when sending its distance vector to B.
- Split Horizon with Poison Reverse: If router A routes to C via neighbour B, then A explicitly advertises
D_A(C) = ∞ (16)to B ("poisoning" the reverse path).
Important GATE caveat: Split Horizon and Poison Reverse completely cure 2-node loops (A ⇄ B), because B sees D_A(C) = ∞ and immediately sets D_B(C) = ∞ in 1 step! However, they CANNOT prevent 3-node (or larger) loops (e.g., a triangle A–B–C connected to D via C).
| Mechanism | What A tells B about C (when A routes to C via B) | Result when B–C breaks | Fixes 3+ node loops? |
|---|---|---|---|
| Plain Distance Vector | Advertises D_A(C) = 2 | Count-to-infinity (3, 4, 5, …, 16) | No |
| Split Horizon | Omits C from DV sent to B | B has no alternate route → D_B(C) = ∞ immediately! | No (fails on ≥ 3-node cycles) |
| Poison Reverse | Advertises D_A(C) = ∞ (16) to B | B computes min(∞, 1+∞) = ∞ immediately! | No (fails on ≥ 3-node cycles) |
Putting it together
- When a link fails in plain Distance Vector routing, routers can fool each other with stale echoed routes and count up to infinity.
- RIP bounds this by defining 16 as infinity, limiting valid networks to at most 15 hops.
- Split Horizon and Poison Reverse stop 2-node loops immediately by hiding or poisoning routes sent back to the next-hop neighbour.
Visual
Worked Examples
In RIP, what hop count represents "infinity" (unreachable), and what is the maximum number of hops a valid path can have?
Show the full solution
Infinity = 16; maximum valid hop count = 16 − 1 = 15 hops.
In A —(1)— B —(1)— C without Split Horizon, initially D_A(C) = 2 and D_B(C) = 1. Link B–C breaks, and B and A update alternately (B first, then A, then B, …). Write the sequence of values taken by D_B(C) until it reaches 16.
Show the full solution
• Update 1 (B): 1 + 2 = 3
• Update 2 (A): 1 + 3 = 4
• Update 3 (B): 1 + 4 = 5
• Update 4 (A): 6, Update 5 (B): 7, …, Update 13 (B): 15, Update 14 (A): 16, Update 15 (B): 16.
So D_B(C) takes the odd values 3, 5, 7, 9, 11, 13, 15, 16!
Suppose link A–B has cost 5 and link B–C has cost 1 (so initially D_B(C) = 1 via C, and D_A(C) = 6 via B), with infinity = 16 and no Split Horizon. If link B–C fails and B updates first, then A, then B, what values do D_B(C) and D_A(C) take on each step?
Show the full solution
Each step adds the link cost c(A, B) = 5!
• Initial: D_A(C) = 6, D_B(C) = 1.
• Step 1 (B updates from A's 6): D_B(C) = 5 + 6 = 11 (via A).
• Step 2 (A updates from B's 11): D_A(C) = 5 + 11 = 16 (∞)!
• Step 3 (B updates from A's 16): D_B(C) = min(16, 5 + 16) = 16 (∞)!
Because c(A,B) = 5 is large, it reaches 16 in just 3 steps!
GATE Traps
- Poison Reverse does NOT poison every neighbour! It ONLY poisons the specific neighbour that is X's current next hop for that destination.
- Split Horizon / Poison Reverse do NOT solve 3-node routing loops! If A & B both route to D via C, and A–B is connected, when C–D breaks, C tells A & B that D is ∞, but A may still advertise its old route (via C, not via B!) to B, triggering count-to-infinity around the A–B–C triangle.
Memory Hook
Good news sprints; bad news counts by 1s to 16. Never sell a rumour back to the neighbour who sold it to you (Split Horizon / Poison Reverse)!
Connect the Dots
Why did Distance Vector suffer from count-to-infinity in the first place? Because no router could see the whole graph! Next question (3.4.4): What if every router broadcast its own direct link costs to everyone so every router could build the complete map and compute shortest paths locally?
Self-Test
- NAT
In the RIP routing protocol (which defines infinity as 16), what is the maximum number of hops a valid reachable path can have?
Write your answer before opening the key.
- MCQ
Router X’s current shortest path to destination D has cost 4 and uses neighbour Y as the next hop. Router X also has another neighbour Z. Under Split Horizon with Poison Reverse, what distance to D does Router X advertise to Y and to Z?
- 4 to Y, and 4 to Z
- ∞ to Y, and ∞ to Z
- ∞ to Y, and 4 to Z
- 4 to Y, and ∞ to Z
- NAT
Consider A —(3)— B —(1)— C without Split Horizon. Initially D_B(C) = 1 (via C) and D_A(C) = 4 (via B). When link B–C fails, B updates its table first using A’s old advertisement, and then A updates its table using B’s new advertisement. What is A’s new distance D_A(C) after A updates?
Write your answer before opening the key.
- MSQ
Which of the following statements about the Count-to-Infinity problem are TRUE?
- It occurs in Distance Vector routing when a link fails or its cost increases.
- In Distance Vector routing, "good news" (cost decrease) propagates fast, whereas "bad news" (link failure) propagates slowly without loop prevention.
- Split Horizon with Poison Reverse completely eliminates all possible routing loops of 3 or more nodes.
- Setting infinity = 16 bounds how long a 2-node loop can count before declaring the destination unreachable.
Rule Card
- Count-to-infinity: Bad news (link failure) causes neighbours to bounce increasing costs back and forth; RIP caps this with infinity = 16 (max valid hops = 15).
- Split Horizon: Do not advertise a route back to the next-hop neighbour v*.
- Poison Reverse: Advertise
Dₓ(y) = ∞to the next-hop neighbour v* (fixes 2-node loops, not 3+ node loops).
Concept Ledger
- count-to-infinity
- infinity = 16 (RIP)
- split horizon
- poison reverse
- good news fast / bad news slow
Answer Vault
Try the questions first. Open when you are ready to check.
Warm-up answers
- No — a distance vector reports only the numerical distance, not the path or next hop.
- The 8-bit TTL (Time to Live) field, which is decremented at every router hop.
- They bounce back and forth between A and B in a routing loop until their TTL reaches 0.
Self-test answers
- 15 — Since 16 means unreachable (infinity), the largest valid hop count is 15.
- C — Because X routes to D via Y, X poisons the advertisement to Y (sending ∞) while advertising its true distance (4) to all other neighbours such as Z.
- A: That is plain Distance Vector without Poison Reverse.
- B: Z is not X’s next hop to D, so Z receives the normal distance 4.
- D: Backwards: you poison the next-hop neighbour Y, not Z.
- 10 — First B updates: D_B(C) = c(B,A) + D_A(C) = 3 + 4 = 7 (via A). Next A updates: D_A(C) = c(A,B) + D_B(C) = 3 + 7 = 10 (via B).
- ABD — Count-to-infinity happens on bad news (link failure/cost increase) and is bounded by 16 in RIP. Split Horizon / Poison Reverse only guarantee loop freedom for 2-node loops, NOT 3+ node loops.
- C: 3-node and larger loops can still occur even with Split Horizon and Poison Reverse.
Flashcards
- What does "Good news travels fast, bad news travels slow" mean in Distance Vector routing?
Reveal answer
A link cost decrease propagates at 1 hop per round, whereas a link failure causes routers to count up slowly to infinity. - Why is infinity set to 16 in RIP, and what limit does that impose?
Reveal answer
To stop count-to-infinity loops quickly; it limits the maximum valid path length to 15 hops. - State the Poison Reverse rule.
Reveal answer
If router X routes to destination Y via neighbour V, X advertises D_X(Y) = ∞ (16) to V. - Does Poison Reverse prevent loops involving 3 or more routers?
Reveal answer
No — it only eliminates 2-node loops.
Exam shortcuts
- Step Increment Rule in Count-to-Infinity: In a 2-node loop across link
(A, B)of weight w, each alternating update adds +w to the previous node's cost (starting fromD_B¹(C) = w + D_A⁰(C)). — questions where link A–B has weight w > 1. - Poison Reverse Direction Check: If X routes to Z via Y, X sends
D_X(Z) = ∞to Y, but still sends its trueD_X(Z)to all other neighbours W ≠ Y! — GATE questions asking what X advertises to each of its neighbours under Poison Reverse.