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

4.3.15 · Coding › Computer Networks

KYA hai Distance Vector Routing?

Isse Link-State routing (OSPF) se compare karo, jisme har router poori topology jaanta hai. DV global knowledge ki jagah simplicity choose karta hai: "sirf neighbours ko batao, sab kuch batao."

Sirf neighbours ke saath share kyun? Kyunki ek router physically sirf apne direct neighbours ka cost measure kar sakta hai (link cost). Usse aage ki sab cheez doosre se sun ke seekhni padti hai. Toh information dhire dhire bahar failti hai, ek hop per exchange.

KAISE: Bellman-Ford update scratch se derive karna

Maano $d_{x} (y)$ = node $x$ se node $y$ tak ka sabse sasta cost. Maano $c (x, v)$ = $x$ ke neighbour $v$ tak ka direct link cost.

Step 1 — first principles. $x$ se $y$ tak ka koi bhi path (jab $y \neq = x$ ) kisi na kisi neighbour $v$ se hoke guzrega. Jab aap $v$ se jaane ka decision le lete ho, toh uske baad best aap $d_{v} (y)$ kar sakte ho (jo $v$ khud $y$ tak pahunchne ka best kar sakta hai).

Step 2 — $v$ se jaane ka cost. $cost via v = c (x, v) + d_{v} (y)$ Yeh step kyun? Total = ( $v$ tak pahunchne ki kimat) + ( $v$ ke paas journey finish karne ki best kimat).

Step 3 — best neighbour choose karo. Kyunki hum sabse sasta path chahte hain aur pata nahi kaun sa neighbour best hai, hum sab neighbours par minimise karte hain:

Yeh correct kyun hai? Yeh sirf optimality ka principle hai: ek shortest path ke sub-paths bhi shortest hote hain. Agar $y$ tak best route $x \to v \to \dots \to y$ jaata hai, toh $v \to \dots \to y$ portion khud $v$ ka $y$ tak shortest route hona chahiye — warna hum ek sasta tail swap kar ke apne hi "shortest" path ko beat kar sakte hain (contradiction).

Distributed twist: node $x$ khud $d_{v} (y)$ compute nahi karta — $v$ apne distance-vector message mein $x$ ko apna current estimate $D_{v} (y)$ batata hai. Toh practically har router yeh chalata hai: $D_{x} (y) \leftarrow min_{v} {c (x, v) + D_{x}^{(v)} (y)}$ jahan $D_{x}^{(v)} (y)$ woh latest estimate hai jo $x$ ne $v$ se receive ki hai $d_{v} (y)$ ke liye. Jab bhi koi $D_{x} (\cdot)$ change hota hai, $x$ apna naya vector neighbours ko broadcast karta hai.

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

RIP — real-world DV protocol

Key RIP facts (WHY woh hain):

Feature	Value	Kyun
Metric	hop count (1 per link)	simple, bandwidth measurement ki zaroorat nahi
Max valid cost	15	16 ka cost = ∞ (unreachable) → count-to-infinity ko cap karta hai
Update period	har 30 s	periodic full-vector broadcast to neighbours
Route timeout	180 s	agar 6 periods mein koi update nahi, route dead declare
Transport	UDP 520	lightweight; missing updates agli period mein fix ho jaate hain

Count-to-Infinity Problem

KAISE hota hai (HAR STEP KYUN): Socho A — B — C, sab link costs 1.

Steady state: $B$ $C$ tak cost 1 pe pahunchta hai (direct); $A$ $C$ tak cost 2 pe pahunchta hai B ke zariye.
Link B–C toot jaata hai.
$B$ ko ab $C$ ko unreachable dekhna chahiye. Lekin $A$ ne haal hi mein $B$ ko bataya tha: "Main C tak cost 2 pe pahunch sakta hoon!" — $B$ ko nahi pata ki $A$ ka C ka route B se hi hoke jaata tha.
Toh $B$ sochta hai: "Main C tak A se jaaunga: cost $= 1 + 2 = 3$ ." (GALAT — woh path loop karta hai $B \to A \to B$ .)
$B$ $A$ ko batata hai "C 3 pe hai", toh $A$ update karta hai "C via B cost $1 + 3 = 4$ pe"… aur woh ping-pong karte hain: 5, 6, 7 … 16 = ∞ tak.

Root cause: ek router route wapas usi neighbour ko advertise karta hai jisse usne seekha tha.

Fixes

Worked Example 1 — ek Bellman-Ford update

Network: A—B=2, B—C=3, A—C=7. $A$ ka $C$ tak cost nikalo.

$A$ ke neighbours: $B$ (cost 2) aur $C$ (cost 7).
$C$ se: $c (A, C) + d_{C} (C) = 7 + 0 = 7$ . Kyun? Destination tak direct link.
$B$ se: $c (A, B) + d_{B} (C) = 2 + 3 = 5$ . Kyun? $B$ ne already advertise kiya tha ki woh $C$ tak 3 pe pahunchta hai.
$d_{A} (C) = min (7, 5) = 5$ , next-hop $= B$ . B kyun? Dono options mein yeh sasta hai.

Worked Example 2 — count-to-infinity trace

A—B—C, costs 1. Link B–C toot jaata hai. "C tak cost" ke tables:

Exchange	$D_{B} (C)$	$D_{A} (C)$	Kyun
break se pehle	1 (direct)	2 (via B)	steady state
break, no split horizon	3 (via A!)	2	B $A$ ke stale "2" par trust karta hai
agli baar	3	4 (via B)	A, B ke "3" par trust karta hai
…	5	6	ping-pong
eventually	16=∞	16=∞	RIP cap rok deta hai

Yeh disaster kyun hai: jab tak woh 16 nahi hit karte, C ke packets A↔B mein forever loop hote hain.

Worked Example 3 — split horizon rokta hai

Same break, split horizon ke saath: $A$ ne C B ke zariye seekha tha, toh $A$ $B$ ko "C = ∞" advertise karta hai. Ab jab B–C toot ta hai, $B$ ke paas koi false alternative nahi (A ne use ∞ bataya), toh $B$ turant C ko unreachable mark karta hai. Kyun kaam karta hai: looping estimate kabhi inject hi nahi hua wapas.

Flashcards

What equation does distance vector routing implement?

Bellman-Ford equation

d_{x} (y) = min_{v} {c (x, v) + d_{v} (y)}

, distributed/asynchronously chalaya jaata hai.

In DV routing, what does each router send and to whom?

Apna poora distance vector (dest→cost ka table), sirf directly connected neighbours ko.

What metric and transport does RIP use?

Metric = hop count (1 per link); UDP port 520 par chalta hai.

In RIP, what cost value means "unreachable"?

16 (yaani 16 = infinity); max valid hop count 15 hai.

What is count-to-infinity?

Ek link toot ne ke baad, routers stale route estimates ko aage-peeche bounce karte hain, cost ko step-by-step ∞ ki taraf badhate hue ("bad news slowly travel karti hai").

Root cause of count-to-infinity?

Ek router route wapas usi neighbour ko advertise karta hai jisse usne originally seekha tha.

What is split horizon?

Kisi route ko kabhi bhi usi neighbour ko advertise mat karo jisse tumne seekha (2-node loops todta hai).

What is poison reverse?

Aisi route ko explicitly cost 16 (∞) ke saath wapas advertise karo instead of omit karne ke.

Why doesn't split horizon fully solve count-to-infinity?

Yeh sirf 2-node loops rokta hai; 3+ routers ke loops phir bhi infinity tak count kar sakte hain, isliye 16-cap phir bhi chahiye.

How many exchanges until DV converges in an n-node network (no failures)?

Zyada se zyada n−1, kyunki har exchange correct info ek extra hop tak pahunchaata hai.

RIP route timeout period?

180 s (route dead declare hota hai agar 6 × 30s periods mein koi update nahi).

Why does "good news travel fast but bad news slow"?

Ek sasta naya route ek step mein adopt ho jaata hai; ek tuta route isliye persist karta hai kyunki neighbours stale optimistic costs echo karte rehte hain.

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ek line mein bachche hain, har ek sirf apne saath wale se whisper kar sakta hai. Tum chahte ho ki sabko pata chale "candy shop kitne steps door hai." Jo bachcha shop par hai woh kehta hai "0 steps." Uska neighbour "0" sunke kehta hai "Main 1 step hoon." Har bachcha bas apne sunne wale sabse chhote number mein 1 add karke aage bhejta hai. Jald hi sabko apni distance pata chal jaati hai — bina kisi ne poori map dekhe! Problem yeh hai: agar shop achanak band ho jaaye, ek bachcha phir bhi purana "Main shop ke paas hoon" whisper sun sakta hai ek doost se jiska raasta usse hoke gaya tha. Toh woh sochta hai "oh, main doost ke zariye shop jaaunga!" — lekin uska doost usse hoke ja raha tha. Woh 1, 1, 1 add karte rehte hain… forever count karte hain. Yeh rule ki "kisi doost ko woh route mat batao jo tumne usi doost se seekha" unhe saath mein silly hone se rokta hai.

Connections

Link-State Routing (OSPF) — global-map alternative jo Dijkstra's Algorithm use karta hai
Bellman-Ford Algorithm — graph-theory core (negative edges bhi handle karta hai, unlike Dijkstra)
Principle of Optimality / Dynamic Programming — kyun shortest paths ke sub-paths bhi shortest hote hain
BGP — ek path-vector protocol; scale par count-to-infinity theek karne ke liye full AS-paths advertise karta hai
UDP — transport jis par RIP depend karta hai (port 520)
Routing Tables and Next-Hop Forwarding