4.3.16
Socho ki ek desh ke har sheher ne baaki sabko postcard bheji jisme sirf apni roads describe ki hain (kaun se neighbors tak pahunch sakte hain aur cost kya hai). Jab ek baar har sheher ne saari postcards collect kar li, toh woh apne aap poora naqsha bana sakta hai, aur phir kahin bhi shortest route compute kar sakta hai.
Yahi hai link state routing: har router poori topology seekh leta hai aur independently ek shortest-path algorithm chalata hai. Isko distance-vector se compare karo, jahan routers sirf apni best distances ka "gossip" karte hain aur blindly apne neighbors par bharosa karte hain.
Intuition Woh problem jo yeh solve karta haiPurane distance-vector protocols (RIP) count-to-infinity se suffer karte hain: jab koi link mar jaati hai, routers kaafi rounds tak ek doosre ko galat distances ke baare mein "convince" karte rehte hain aur looping hoti hai. Ilaaj yeh hai ki summaries par trust karna band karo aur har router ko raw map dedo. Poore map ke saath, har router locally routes compute karta hai — belief ki slow propagation nahi, fast convergence, aur loop-free results kyunki sabhi ek hi map use karte hain.
OSPF (Open Shortest Path First) Internet ka standard intra-domain (IGP) implementation hai is idea ka: ek open standard, directly IP ke upar chalta hai (protocol 89), areas, authentication, aur equal-cost multipath support karta hai.
Intuition Flooding ko sequence numbers KYUN chahiyeAgar ek router sirf har LSP jo woh dekhta hai usse forward karta rahe, toh copies hamesha bounce karti rahengi. Fix: har LSP ek sequence number aur ek age carry karta hai. Ek router har source ka sirf newest (highest sequence) LSP rakhta hai, use sab links par forward karta hai siwaaye jahan se woh aaya, aur purani/duplicate copies discard kar deta hai. Age stale info ko eventually expire hone deta hai.
Intuition Yeh KYUN kaam karta hai (greedy invariant)Hum ek source s S Key claim : woh unfinalized node u sabse chhota tentative distance hai, uska final shortest distance already aa chuka hai.
Kyun? u S ≥ 0 u sirf isliye kyunki edge weights non-negative hain.
Procedure:
d [ s ] = 0 d [ others ] = ∞ S = ∅ u ∈ / S d [ u ] u S u Tab tak repeat karo jab tak S
Binary heap ke saath complexity: O (( V + E ) log V )
Graph (undirected, costs):
A–B = 2, A–C = 5, B–C = 1, B–D = 7, C–D = 3. Source = A.
Step
Finalized
d[A]
d[B]
d[C]
d[D]
init
{}
0
∞
∞
∞
pick A
{A}
0
2 5 ∞
pick B (min=2)
{A,B}
0
2
3 (via B:2+1)9 (2+7)
pick C (min=3)
{A,B,C}
0
2
3
6 (3+3)
pick D (min=6)
all
0
2
3
6
B pehle KYUN pick kiya? Min tentative = 2 → finalized. Yeh step kyun? Greedy invariant guarantee karta hai ki B tak koi chhota path exist nahi karta.C 5→3 KYUN ho gaya? B ki edge relax karne par: d [ B ] + 1 = 3 < 5 Kyun? Path A→B→C, A→C direct se better hai.D = 6 kyun, 9 kyun nahi? C finalize hone ke baad, C→D relax karo: 3 + 3 = 6 < 9 Kyun? C se jaana B se jaane se sasta hai.
A se final shortest paths: B(2), C(3, via B), D(6, via B,C).
Maano router A ki Dijkstra ke baad table: D tak pahunchne ke liye, first hop B hai (kyunki path A→B→C→D hai).
Sirf next hop kyun store karo, poora path kyun nahi? Yeh step kyun? Forwarding hop-by-hop hoti hai; A ko sirf yeh jaanna chahiye ki packet kaunse neighbor ko dena hai. B ko apna khud ka next hop pata hoga, aur aage bhi aise hi. Yahi destination → next-hop forwarding table hai.
Common mistake "Dijkstra negative link costs ke saath kaam karta hai"Kyun sahi lagta hai: relaxation rule general lagti hai — bas min lo. Kyun galat hai: greedy finalization assume karti hai ki jab ek node ka tentative distance sabse chhota ho, toh woh kabhi improve nahi ho sakta. Ek baad mein aane wala negative edge already-finalized distance ko shrink kar sakta hai. Fix: negative weights ke liye Bellman–Ford use karo. OSPF link costs hamesha positive hote hain, isliye wahan Dijkstra valid hai.
Common mistake "Link state = distance vector, bas faster"Kyun sahi lagta hai: dono shortest paths produce karte hain. Kyun galat hai: distance-vector computed distances share karta hai (Bellman–Ford, count-to-infinity ke liye vulnerable); link state raw topology share karta hai aur har router akela compute karta hai (Dijkstra). Alag information, alag failure modes. Fix: yaad rakho LS = "sabke paas map hai"; DV = "apne neighbors se poocho."
Common mistake "LSPs ek neighbor ko bheje jaate hain jaise ek routing update"Kyun sahi lagta hai: RIP mein updates neighbor-to-neighbor jaate hain. Fix: LSPs poore network mein reliably flood kiye jaate hain, taaki har router ek identical map bana sake.
Common mistake Relax karte waqt already-finalized nodes ko skip karna bhool jaanaKyun sahi lagta hai: har neighbor ko relax karna harmless lagta hai. Fix: yeh galat nahi hai, sirf wasteful hai; finalized nodes kabhi improve nahi hote, isliye standard implementations unhe skip karti hain.
Recall Khud test karo (answers chhupao)
Link state routing ke 5 steps kya hain?
Dijkstra ko non-negative weights KYUN chahiye?
Ek LSP mein kya hota hai?
Flooding ko sequence numbers KYUN chahiye?
OSPF kiske upar chalta hai (protocol)?
Link state routing mein har router kya flood karta hai? Apna Link State Packet (LSP): apni ID aur (neighbor, link-cost) pairs ki list.
Assembled topology par har router kaunsa algorithm chalta hai? Dijkstra's shortest-path algorithm, khud ko source maanke.
Dijkstra mein relaxation rule batao. d [ v ] = min ( d [ v ] , d [ u ] + w ( u , v ))
Dijkstra ke edge weights non-negative KYUN hone chahiye? Kyunki greedy step assume karta hai ki ek finalized node ki distance kabhi decrease nahi ho sakti; ek negative edge baad mein use shorten kar sakta hai, correctness tod ke.
Distance-vector ki kaunsi problem link state avoid karta hai? Count-to-infinity / slow convergence aur routing loops.
OSPF ka full form kya hai aur yeh kahan chalta hai? Open Shortest Path First; ek intra-domain IGP jo directly IP ke upar chalta hai (protocol number 89).
LSPs sequence numbers aur age KYUN carry karte hain? Sirf newest copy rakhne ke liye, infinite flooding loops rokne ke liye, aur stale topology info expire karne ke liye.
Binary heap ke saath Dijkstra ki time complexity? O (( V + E ) log V )
Forwarding table mein har router actually kya store karta hai? Destination → next-hop (shortest path par pehla neighbor), poora path nahi.
Ek line mein LS vs DV? LS = poora map share karo, akele compute karo (Dijkstra); DV = computed distances share karo, neighbors par bharosa karo (Bellman–Ford).
Recall Feynman: ek 12 saal ke bachche ko explain karoHar router sabko ek chhoti si chit bhejta hai jisme likha hota hai "mere paas wali roads aur unki lambai ye hai." Jab sabne sabki chits padh li, toh har ek poora sheher ka naqsha bana leta hai. Phir, ek clever rule use karke, har router har jagah ka shortest rasta figure out karta hai — hamesha sabse kareeb wali incomplete jagah ko pehle pick karte hue, jaise maze explore karna hamesha sabse nazdik wale unexplored kamre mein qadam rakhke. Kyunki sab ek hi naqsha use karte hain, koi packets circles mein nahi bhejta.
"HELLO, Make an LSP, Flood it, Then Dijkstra" → H-M-F-T-D : Help My Friends Take Directions.
Dijkstra ke liye: "Sabse kareeb wala pick karo, lock karo, uski roads relax karo."
Distance Vector Routing — alternative (Bellman–Ford, count-to-infinity)Dijkstra's Algorithm — graph algorithm jo yahan reuse hoti haiBellman–Ford Algorithm — jab weights negative ho sakti hainFlooding — reliable LSP distribution mechanismOSPF Areas — link state ko bade networks par scale karnaBGP — inter-domain routing (path-vector, intra-domain OSPF se contrast)Routing Table vs Forwarding Table
keeps newest, expires stale
Discover neighbors and costs
