Routing algorithms और convergence
लक्ष्य और मॉडल
Shortest routes निकालना, forwarding और routing अलग पहचानना तथा distributed जानकारी का convergence समझना लक्ष्य है। Link costs nonnegative मानें और topology स्पष्ट रखें। Cost आवश्यक नहीं कि भौतिक दूरी हो। Forwarding, installed table से packet का outgoing interface चुनता है; routing यह table बनाती है। Shortest path में link costs का योग न्यूनतम होता है, routers की संख्या आवश्यक नहीं।
1. Dijkstra से shortest paths
Link-state routing में flooded advertisements से हर router topology database बनाता है और अपने को root मानकर shortest paths निकालता है। Dijkstra में सबसे छोटी tentative distance वाला unsettled vertex finalize होता है। फिर उसके edges relax होते हैं: d(v)=min(d(v),d(u)+w(u,v))। Nonnegative costs के कारण finalized distance optimal है। Predecessor path में source के बाद पहला पड़ोसी next hop बनता है। बराबर costs पर कई सही trees हो सकते हैं; एक निश्चित next hop के लिए tie-breaking rule चाहिए।
हल किया undirected उदाहरण: AB=2, AC=5, BC=1, BD=6, CD=2। A से शुरुआत में B=2,C=5,D=infinity। B finalize करने पर C=3 और D=8, दोनों B के रास्ते। C finalize करने पर D=5 हो जाता है। फिर D finalize होता है। Paths A-B, A-B-C और A-B-C-D हैं; सबका पहला hop B है। AC का सीधा edge होने से वही सस्ता route नहीं बन जाता। D की distance को2+1+2=5 से जाँचें।
2. Distance vector और Bellman–Ford
Distance-vector router पूरे graph के बजाय पड़ोसियों से destinations की costs प्राप्त करता है। नियम है D_x(y)=min_v[c(x,v)+D_v(y)], जहाँ v पड़ोसी है। न्यूनतम देने वाला पड़ोसी next hop है। Advertisement में अपने router से उस पड़ोसी तक का local cost शामिल नहीं होता। Self-distance0 और सीधे जुड़े destinations शुरुआती जानकारी देते हैं; बाकी infinity होते हैं। Updates periodic या triggered हो सकते हैं और एक साथ पहुँचना जरूरी नहीं।
उदाहरण: X से A का cost3 और B का cost1 है। Z के लिए A,4 तथा B,8 advertise करता है। कुल candidates7 और9 हैं; A के रास्ते7 चुनें। बाद में B,2 advertise करे तो B के रास्ते कुल3 चुनेंगे। केवल advertisement छोटा देखना पर्याप्त नहीं, local link cost भी जोड़ना है। स्थिर topology और updates के पहुँचने की उपयुक्त assumptions में convergence हो सकता है; बीच में tables असंगत रह सकती हैं।
3. Failure, loop और count to infinity
Unit links वाली A-B-C line में destination A लें। पहले B की distance1 और C की2 है। AB टूटने के बाद B को C का पुराना advertisement2 मिले तो वह C के रास्ते झूठी distance3 मान सकता है, जबकि C का रास्ता B से जाता है। फिर C,4 और B,5 सीखते हैं। यही count to infinity है: advertisement में पूरी dependency path न होने से खराब खबर धीरे फैलती है।
Split horizon सीखे हुए route को उसी interface पर वापस advertise नहीं करता। Poison reverse उसे वापस infinite metric के साथ advertise करता है। Triggered updates बदलाव जल्दी भेजते हैं। ये उपाय मदद करते हैं, लेकिन poison reverse तीन या अधिक routers वाले हर loop को नहीं मिटाता। Finite infinity counting की सीमा और उपयोगी path metric की सीमा दोनों तय करती है। जब तक protocol निर्दिष्ट न हो, infinity को किसी खास संख्यात्मक threshold से न बदलें।
Link-state में बदली local जानकारी flood होती है और paths फिर निकाले जाते हैं। इसमें neighbor-distance counting वाला वही कारण नहीं होता, पर हर asynchronous transition में तुरंत loop-free होने की गारंटी नहीं है। Databases अलग समय पर बदल सकती हैं और tables भी अलग समय पर install हो सकती हैं। Convergence में failure detection, dissemination, computation और installation का समय जुड़ता है।
4. सुरक्षित flooding
Uncontrolled flooding में arrival link को छोड़कर eligible outgoing links पर copies जाती हैं। Cycles में lifetime limit और duplicate suppression के बिना copies दोहरती रहती हैं। Hop limit lifetime सीमित करता है। Source identifier और sequence number से पहले process की गई सूचना पहचानी जाती है। Freshness नियम पुराने advertisement को नए पर overwrite करने से रोकते हैं। जिन protocols में reliability चाहिए वहाँ उनके नियम के अनुसार acknowledgments और retransmission होते हैं। Flooding, एक Ethernet LAN के broadcast का दूसरा नाम नहीं है।
First-seen-only forwarding में प्रत्येक identified advertisement एक बार process होता है। Exact transmission count इस पर निर्भर है कि duplicates को acknowledgment मिलता है या नहीं, reverse links exclude हैं या नहीं और simultaneous arrivals का क्रम क्या है। पहले ये नियम लिखें। Data replication घटाने के लिए shortest-path tree उपयोगी हो सकता है, पर उसे बनाना और बनाए रखना अलग कार्य है।
5. Design distinctions और सामान्य गलतियाँ
Static routes configure किए जाते हैं; dynamic protocols exchanges से बदलाव सीखते हैं। एक administrative system के भीतर और अलग systems के बीच routing की policy जरूरतें अलग हैं। न्यूनतम mathematical cost वाला path जरूरी नहीं कि operator policy के अनुकूल हो। Interdomain routing को global Dijkstra न मानें। यहाँ shortest paths, flooding, distance vectors और link state पर ध्यान है; protocol configuration विस्तार दायरे से बाहर है।
Topology जानकारी और निकले route को अलग रखें: link-state advertisement links बताता है, distance vector destinations की distances। गणना में हर पड़ोसी का कुल candidate लिखें और पहला hop बचाकर रखें। Convergence में केवल metrics नहीं, वास्तविक next-hop dependencies बनाएँ। Positive costs transient loops नहीं रोकते। Hop limit घूमते packet को रोकता है, routing table की गलती ठीक नहीं करता।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. हल किए graph में A से D की न्यूनतम cost क्या है?
A. 3 B. 5 C. 7 D. 8
उत्तर: B
A: 3 से C तक पहुँचते हैं, D तक नहीं।
B: B और C से2+1+2=5 मिलता है।
C: A-C-D का cost7 है, पर न्यूनतम नहीं।
D: A-B-D का cost8 अधिक है।
P02. X से P का cost2 और Q का5 है। Z की advertised distances क्रमशः8 और1 हैं। कौन सा route चुनेगा?
A. P से, cost8 B. P से, cost10 C. Q से, cost1 D. Q से, cost6
उत्तर: D
A: Local cost2 छूट गया।
B: 10 सही candidate है, पर6 से अधिक है।
C: Local cost5 छूट गया।
D: 2+8=10 और5+1=6 की तुलना करें।
P03. किसी route के next-hop पड़ोसी को poison reverse क्या advertise करता है?
A. Infinite metric वाला route B. पूरा topology database C. केवल destination का MAC D. Zero metric वाला route
उत्तर: A
A: Infinite metric से पड़ोसी इसे इस router के रास्ते finite विकल्प नहीं मानता।
B: Topology flooding link-state का व्यवहार है।
C: MAC resolution, poison reverse नहीं है।
D: Zero गलत ढंग से शून्य cost दिखाता है।
P04. Flooding में duplicate पहचानने के लिए कौन सी जोड़ी सीधे उपयोगी है?
A. Destination address और packet का आकार B. Source identifier और sequence number C. Link cost और interface की गति D. Checksum और propagation delay
उत्तर: B
A: अलग packets की destination और size समान हो सकती है।
B: दोनों मिलकर source के खास advertisement को पहचानते हैं।
C: इनसे दोहराया advertisement नहीं पहचाना जाता।
D: यह जोड़ी खास advertisement की पहचान नहीं देती।
P05. Link-state convergence के बारे में कौन सा कथन सही है?
A. सभी routers हमेशा एक साथ routes install करते हैं B. Hop limit असंगत tables ठीक करता है C. बदलाव के दौरान अस्थायी forwarding loops हो सकते हैं D. Topology की कोई जानकारी नहीं भेजी जाती
उत्तर: C
A: Update और installation का समय अलग हो सकता है।
B: Hop limit packet का जीवन सीमित करता है, table नहीं सुधारता।
C: Database और installation के अलग समय से अस्थायी असंगति हो सकती है।
D: Link-state जानकारी प्रसारित होती है।
P06. Dijkstra के सामान्य finalization तर्क के लिए कौन सी assumption जरूरी है?
A. हर link की cost बराबर हो B. Graph केवल tree हो C. हर destination एक hop दूर हो D. Link costs nonnegative हों
उत्तर: D
A: अलग-अलग nonnegative costs मान्य हैं।
B: Cycles हो सकते हैं।
C: Multihop paths भी निकलते हैं।
D: Negative edge होने पर सबसे छोटी tentative distance को अंतिम मानने का तर्क टूट सकता है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Computer Networks syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन