लिंक-स्टेट रूटिंग प्रोटोकॉल

लिंक-स्टेट रूटिंग प्रोटोकॉल कंप्यूटर संचार के लिए पैकेट-स्विचिंग नेटवर्क में उपयोग किए जाने वाले राउटिंग प्रोटोकॉल के दो मुख्य वर्गों में से एक हैं, अन्य दूरी-वेक्टर रूटिंग प्रोटोकॉल हैं। लिंक-स्टेट रूटिंग प्रोटोकॉल के उदाहरणों में ओपन शॉर्टेस्ट पाथ फ़र्स्ट (ओएसपीएफ) और इंटरमीडिएट सिस्टम से इंटरमीडिएट सिस्टम (IS-IS) शामिल हैं।

लिंक-स्टेट प्रोटोकॉल नेटवर्क में प्रत्येक स्विचिंग नोड द्वारा निष्पादित किया जाता है (यानी, नोड्स जो पैकेट को अग्रेषित करने के लिए तैयार होते हैं; इंटरनेट में, इन्हें राउटर कहा जाता है)। लिंक-स्टेट रूटिंग की मूल अवधारणा यह है कि प्रत्येक नोड एक ग्राफ के रूप में नेटवर्क से कनेक्टिविटी का एक नक्शा बनाता है, जो दिखाता है कि कौन से नोड किस अन्य नोड से जुड़े हैं। इसके बाद प्रत्येक नोड स्वतंत्र रूप से नेटवर्क में हर संभव गंतव्य के लिए उससे अगले सर्वश्रेष्ठ तार्किक पथ की गणना करता है। सर्वोत्तम पथों का प्रत्येक संग्रह तब प्रत्येक नोड की राउटिंग तालिका बनाएगा।

यह दूरी-वेक्टर रूटिंग प्रोटोकॉल के साथ विरोधाभासी है, जो प्रत्येक नोड को अपने रूटिंग टेबल को अपने नेबर के साथ साझा करके काम करता है, एक लिंक-स्टेट प्रोटोकॉल में नोड्स के बीच पारित होने वाली एकमात्र सूचना कनेक्टिविटी से संबंधित है। लिंक-स्टेट एल्गोरिदम को कभी-कभी अनौपचारिक रूप से प्रत्येक राउटर के रूप में वर्णित किया जाता है, "दुनिया को अपने नेबर के बारे में बताते हुए।"

सिंहावलोकन

लिंक-स्टेट रूटिंग प्रोटोकॉल में, प्रत्येक राउटर में संपूर्ण नेटवर्क टोपोलॉजी की जानकारी होती है। इसके बाद प्रत्येक राउटर स्वतंत्र रूप से टोपोलॉजी की स्थानीय जानकारी का उपयोग करके नेटवर्क में हर संभव गंतव्य के लिए उससे सर्वश्रेष्ठ अगली हॉप की गणना करता है। बेस्ट-नेक्स्ट-हॉप्स का कलेक्शन रूटिंग टेबल बनाता है।

यह दूरी-वेक्टर रूटिंग प्रोटोकॉल के साथ विरोधाभासी है, जो प्रत्येक नोड को अपने पड़ोसियों के साथ रूटिंग टेबल साझा करके काम करता है। एक लिंक-स्टेट प्रोटोकॉल में, नोड्स के बीच पारित होने वाली एकमात्र जानकारी कनेक्टिविटी मानचित्र बनाने के लिए उपयोग की जाने वाली जानकारी है।

लिंक-स्टेट रूटिंग प्रोटोकॉल के उदाहरण:

• ओपन शार्टेस्ट पाथ फर्स्ट (ओएसपीएफ)
• इंटरमीडिएट सिस्टम से इंटरमीडिएट सिस्टम (आईएस-आईएस)

इतिहास

माना जाता है कि कंप्यूटर का पहला अनुकूली रूटिंग नेटवर्क, लिंक-स्टेट रूटिंग को अपने दिल के रूप में इस्तेमाल करते हुए, 1976-1977 के दौरान बर्नार्ड जे हैरिस के नेतृत्व में प्लेसी रडार की एक टीम द्वारा डिजाइन और कार्यान्वित किया गया था; यह प्रोजेक्ट "वेवेल" के लिए था - ब्रिटिश सेना के लिए कंप्यूटर कमांड और कंट्रोल की एक प्रणाली थी।

पहली लिंक-स्टेट रूटिंग अवधारणा को 1979 में जॉन एम. मैकक्विलन (तब बोल्ट, बेरानेक और न्यूमैन) द्वारा एक तंत्र के रूप में प्रकाशित किया गया था, जो नेटवर्क की स्थिति बदलने पर मार्गों की अधिक तेज़ी से गणना करेगा, और इस प्रकार अधिक स्थिर रूटिंग की ओर ले जाएगा।

बाद में बीबीएन टेक्नोलॉजीज में काम ने दिखाया कि एक पदानुक्रमित प्रणाली में लिंक-स्टेट तकनीक का उपयोग कैसे करें (यानी, जिसमें नेटवर्क को क्षेत्रों में विभाजित किया गया था) ताकि प्रत्येक स्विचिंग नोड को पूरे नेटवर्क के मानचित्र की आवश्यकता न हो, केवल वह क्षेत्र (क्षेत्र) जिसमें यह शामिल है।

तकनीक को बाद में समकालीन लिंक-स्टेट रूटिंग प्रोटोकॉल आईएस-आईएस और ओएसपीएफ में उपयोग के लिए अनुकूलित किया गया था। सिस्को साहित्य एन्हांस्ड इंटीरियर गेटवे रूटिंग प्रोटोकॉल (ईआईजीआरपी) को "हाइब्रिड" प्रोटोकॉल के रूप में संदर्भित करता है, [उद्धरण वांछित] इस तथ्य के बावजूद कि यह टोपोलॉजी मानचित्रों के बजाय रूटिंग टेबल वितरित करता है। हालाँकि, यह ओएसपीएफ की तरह स्टार्ट-अप पर राउटिंग टेबल को सिंक्रोनाइज़ करता है और विशिष्ट अपडेट केवल तभी भेजता है जब टोपोलॉजी में परिवर्तन होता है।

2004 में, राडिया पर्लमैन ने रूटिंग ब्रिज या ब्रिजेज नामक उपकरणों के साथ लेयर 2 फ्रेम अग्रेषण के लिए लिंक-स्टेट रूटिंग का उपयोग करने का प्रस्ताव दिया। इंटरनेट इंजीनियरिंग टास्क फोर्स ने इसे पूरा करने के लिए ट्रांसपैरेंट इंटरकनेक्शन ऑफ़ लोट्स ऑफ़ लिंक्स (ट्रिल) प्रोटोकॉल का मानकीकरण किया है।

हाल ही में, इस पदानुक्रमित तकनीक को अनुकूलित लिंक स्टेट रूटिंग प्रोटोकॉल (ओएलएसआर) का उपयोग करके वायरलेस मेश नेटवर्क पर लागू किया गया था। जहां कनेक्शन की गुणवत्ता अलग-अलग हो सकती है, संपर्क की गुणवत्ता का उपयोग बेहतर कनेक्शन चुनने के लिए किया जा सकता है। इसका उपयोग कुछ तदर्थ रूटिंग प्रोटोकॉल में किया जाता है जो रेडियो आवृत्ति संचरण का उपयोग करते हैं।

2012 में, आईईईई ने आईईईई 802.1aq सबसे छोटे पथ ब्रिजिंग (एसपीबी) के साथ ईथरनेट अग्रेषण को नियंत्रित करने के लिए आईएस-आईएस के उपयोग के मानकीकरण को पूरा किया और अनुमोदित किया।

नक्शों का वितरण

यह विवरण केवल सबसे सरल विन्यास को शामिल करता है; यानी, बिना किसी क्षेत्र के, ताकि सभी नोड्स में पूरे नेटवर्क का एक नक्शा हो। पदानुक्रमित मामला कुछ अधिक जटिल है; विभिन्न प्रोटोकॉल विनिर्देशों को देखें।

जैसा कि पहले उल्लेख किया गया है, लिंक-स्टेट एल्गोरिथम में पहला मुख्य चरण प्रत्येक नोड को नेटवर्क का एक नक्शा देना है। यह कई सहायक चरणों के साथ किया जाता है।

प्रत्येक नोड के पड़ोसियों का निर्धारण

सबसे पहले, प्रत्येक नोड को यह निर्धारित करने की आवश्यकता है कि यह पूरी तरह से काम करने वाले लिंक पर अन्य बंदरगाहों से जुड़ा हुआ है; यह रीचैबिलिटी प्रोटोकॉल का उपयोग करके ऐसा करता है जो समय-समय पर और अलग-अलग अपने सीधे जुड़े पड़ोसियों के साथ चलता है।

नक्शे के लिए सूचना का वितरण

अगला, प्रत्येक नोड समय-समय पर (और कनेक्टिविटी परिवर्तन के मामले में) एक छोटा संदेश भेजता है, लिंक-स्टेट विज्ञापन, जो:

• उस नोड की पहचान करता है जो इसे उत्पन्न कर रहा है।
• अन्य सभी नोड्स (राउटर या नेटवर्क) की पहचान करता है जिससे यह सीधे जुड़ा हुआ है।
• एक 'अनुक्रम संख्या' शामिल है, जो हर बार स्रोत नोड द्वारा संदेश का एक नया संस्करण बनाने पर बढ़ जाती है।

यह संदेश नेटवर्क पर सभी नोड्स को भेजा जाता है। एक आवश्यक अग्रदूत के रूप में, नेटवर्क में प्रत्येक नोड अपने प्रत्येक पड़ोसी के लिए, उस नोड से प्राप्त अंतिम लिंक-स्टेट संदेश की क्रम संख्या को याद रखता है। जब एक लिंक-स्टेट विज्ञापन एक नोड पर प्राप्त होता है, तो नोड उस लिंक-स्टेट संदेश के स्रोत के लिए संग्रहीत अनुक्रम संख्या को देखता है: यदि यह संदेश नया है (यानी, एक उच्च क्रम संख्या है), तो इसे सहेजा जाता है , अनुक्रम संख्या अपडेट की जाती है, और उस नोड के प्रत्येक पड़ोसी को बारी-बारी से एक प्रति भेजी जाती है। यह प्रक्रिया तेजी से नेटवर्क में प्रत्येक नोड के प्रत्येक नोड के लिंक-स्टेट विज्ञापन के नवीनतम संस्करण की एक प्रति प्राप्त करती है।

लिंक स्टेट एल्गोरिदम चलाने वाले नेटवर्क को पदानुक्रम में भी विभाजित किया जा सकता है जो मार्ग परिवर्तन के दायरे को सीमित करता है। इन सुविधाओं का मतलब है कि लिंक स्टेट एल्गोरिदम बड़े नेटवर्क के लिए बेहतर है।

नक्शा बनाना

अंत में, लिंक-स्टेट विज्ञापनों (नेटवर्क में प्रत्येक नोड से एक) के पूर्ण सेट के साथ, प्रत्येक नोड नेटवर्क के मानचित्र के लिए ग्राफ का उत्पादन करता है। एल्गोरिथम लिंक-स्टेट विज्ञापनों के संग्रह पर पुनरावृति करता है; हर एक के लिए, यह नेटवर्क के मानचित्र पर लिंक बनाता है, उस नोड से जिसने उस संदेश को भेजा है, उन सभी नोड्स के लिए जो वह संदेश इंगित करता है कि भेजने वाले नोड के पड़ोसी हैं।

किसी भी लिंक को सही ढंग से रिपोर्ट नहीं किया गया माना जाता है जब तक कि दोनों छोर सहमत न हों; यानी, यदि एक नोड रिपोर्ट करता है कि यह दूसरे से जुड़ा हुआ है, लेकिन दूसरा नोड रिपोर्ट नहीं करता है कि यह पहले से जुड़ा हुआ है, तो एक समस्या है, और लिंक मानचित्र पर शामिल नहीं है।

इस चरण के बारे में नोट्स

पड़ोसियों के बारे में जानकारी देने वाले लिंक-स्टेट संदेश की फिर से गणना की जाती है, और फिर पूरे नेटवर्क में बाढ़ आ जाती है, जब भी नोड और उसके पड़ोसियों के बीच कनेक्टिविटी में बदलाव होता है; उदाहरण के लिए, जब कोई लिंक विफल हो जाता है। ऐसे किसी भी परिवर्तन का पता रीचैबिलिटी प्रोटोकॉल द्वारा लगाया जाएगा जो प्रत्येक नोड अपने पड़ोसियों के साथ चलता है।

रूटिंग टेबल की गणना

जैसा कि शुरू में उल्लेख किया गया है, लिंक-स्टेट एल्गोरिथम में दूसरा मुख्य चरण मानचित्रों का निरीक्षण करके राउटिंग टेबल का उत्पादन करना है। यह फिर से कई चरणों के साथ किया जाता है।

सबसे छोटे रास्तों की गणना

प्रत्येक नोड स्वतंत्र रूप से नेटवर्क में हर दूसरे नोड के लिए सबसे छोटी पथ समस्या निर्धारित करने के लिए मानचित्र पर एक एल्गोरिथ्म चलाता है; आमतौर पर दिज्क्स्ट्रा के एल्गोरिथ्म के कुछ प्रकार का उपयोग किया जाता है। यह प्रत्येक पथ में एक लिंक लागत पर आधारित है जिसमें अन्य चीजों के साथ उपलब्ध बैंडविड्थ शामिल है।

एक नोड दो डेटा संरचनाओं को बनाए रखता है: एक ट्री डेटा संरचना जिसमें नोड्स होते हैं, और उम्मीदवारों की एक सूची। एल्गोरिथ्म दोनों संरचनाओं के खाली होने से शुरू होता है; इसके बाद यह पहले नोड में ही जुड़ जाता है। एक लालची एल्गोरिथ्म का संस्करण फिर दोहराव से निम्नलिखित कार्य करता है:

• सभी पड़ोसी नोड्स जो सीधे नोड से जुड़े होते हैं, उन्हें सिर्फ पेड़ में जोड़ा जाता है (किसी भी नोड को छोड़कर जो पहले से ही पेड़ या उम्मीदवार सूची में हैं)। बाकी को दूसरी (उम्मीदवार) सूची में जोड़ा जाता है।
• उम्मीदवार सूची में प्रत्येक नोड की तुलना ट्री में पहले से मौजूद प्रत्येक नोड से की जाती है। उम्मीदवार नोड जो पहले से ही पेड़ में किसी भी नोड के सबसे करीब है, पेड़ में ही ले जाया जाता है और उपयुक्त पड़ोसी नोड से जुड़ा होता है। जब एक नोड को उम्मीदवार सूची से पेड़ में ले जाया जाता है, तो इसे उम्मीदवार सूची से हटा दिया जाता है लालची एल्गोरिदम के बाद के पुनरावृत्तियों में नहीं माना जाता है।

उपरोक्त दो चरणों को तब तक दोहराया जाता है जब तक उम्मीदवार सूची में कोई नोड शेष रहता है। (जब कोई नहीं है, तो नेटवर्क में सभी नोड्स ट्री में जोड़ दिए गए होंगे।) यह प्रक्रिया नेटवर्क में सभी नोड्स वाले ट्री के साथ समाप्त होती है, जिस नोड पर कलन विधि ट्री की जड़ के रूप में चल रहा है। . उस नोड से किसी भी अन्य नोड के लिए सबसे छोटा रास्ता पेड़ की जड़ से पेड़ में वांछित नोड तक पहुंचने के लिए नोड्स की सूची द्वारा इंगित किया जाता है।

रूटिंग टेबल भरना

हाथ में सबसे छोटे रास्तों के साथ, अगला कदम राउटिंग टेबल भरना है। किसी भी दिए गए गंतव्य नोड के लिए, उस गंतव्य के लिए सबसे अच्छा पथ वह नोड है जो रूट नोड से पहला कदम है, सबसे छोटे पथ वाले पेड़ में शाखा के नीचे जो वांछित गंतव्य नोड की ओर जाता है। राउटिंग टेबल बनाने के लिए, केवल पेड़ पर चलना आवश्यक है, प्रत्येक शाखा के प्रमुख पर नोड की पहचान को याद रखना, और प्रत्येक नोड के लिए राउटिंग टेबल प्रविष्टि भरना जो उस पहचान के साथ आता है।

एल्गोरिथ्म के लिए अनुकूलन

समझने में आसानी के लिए ऊपर वर्णित एल्गोरिथ्म को यथासंभव सरल बनाया गया था। व्यवहार में, कई अनुकूलन हैं जिनका उपयोग किया जाता है।

आंशिक पुनर्गणना

जब भी कनेक्टिविटी मानचित्र में कोई परिवर्तन होता है, तो सबसे छोटे-पथ ट्री की पुनर्गणना करना और फिर रूटिंग टेबल को फिर से बनाना आवश्यक होता है। बीबीएन टेक्नोलॉजीज द्वारा कार्य ने पता लगाया कि कैसे पेड़ के केवल उस हिस्से की पुनर्गणना की जाए जो मानचित्र में दिए गए परिवर्तन से प्रभावित हो सकता था। इसके अलावा, राउटिंग टेबल को सामान्य रूप से भर दिया जाएगा क्योंकि इसे एक अलग ऑपरेशन बनाने के बजाय सबसे छोटे-पथ के पेड़ की गणना की जाती है।

टोपोलॉजी कमी

कुछ मामलों में एलएसए संदेशों को उत्पन्न करने वाले नोड्स की संख्या को कम करना उचित है। उदाहरण के लिए, नेटवर्क ग्राफ से केवल एक कनेक्शन वाले नोड को एलएसए संदेश भेजने की आवश्यकता नहीं है, क्योंकि इसके अस्तित्व की जानकारी पहले से ही इसके एकमात्र पड़ोसी के एलएसए संदेश में शामिल हो सकती है। इस कारण से एक टोपोलॉजी कमी की रणनीति लागू की जा सकती है, जिसमें नेटवर्क नोड्स का केवल एक सबसेट एलएसए संदेश उत्पन्न करता है। टोपोलॉजी में कमी के लिए व्यापक रूप से अध्ययन किए गए दो दृष्टिकोण हैं:

1. ऑप्टिमाइज्ड लिंक स्टेट रूटिंग प्रोटोकॉल # मल्टीपॉइंट रिले जो ऑप्टिमाइज्ड लिंक स्टेट रूटिंग प्रोटोकॉल (ओएलएसआर) के आधार पर हैं लेकिन ओएसपीएफ के लिए भी प्रस्तावित हैं
2. जुड़ा हुआ हावी सेट जो फिर से OSPF के लिए प्रस्तावित किए गए हैं

फिशआई स्टेट रूटिंग

फिशआई स्टेट रूटिंग (एफएसआर) के साथ एलएसए को उनके प्रसार को प्रतिबंधित करने और नियंत्रण संदेशों के कारण ओवरहेड को सीमित करने के लिए अलग-अलग टाइम-टू-लाइव मूल्यों के साथ भेजा जाता है। इसी अवधारणा का उपयोग हेज़ी साइटेड लिंक स्टेट रूटिंग प्रोटोकॉल में भी किया जाता है।

विफलता मोड

यदि सभी नोड बिल्कुल एक ही मानचित्र से काम नहीं कर रहे हैं, तो रूटिंग लूप बन सकते हैं। ये ऐसी स्थितियाँ हैं जिनमें, सबसे सरल रूप में, दो पड़ोसी नोड्स प्रत्येक को लगता है कि किसी दिए गए गंतव्य के लिए दूसरा सबसे अच्छा मार्ग है। किसी भी नोड पर पहुंचने वाले उस गंतव्य की ओर जाने वाला कोई भी पैकेट दोनों के बीच लूप करेगा, इसलिए नाम। दो से अधिक नोड्स वाले रूटिंग लूप भी संभव हैं।

ऐसा इसलिए हो सकता है क्योंकि प्रत्येक नोड किसी भी अन्य नोड्स के साथ किसी भी तरह से बातचीत किए बिना अपने सबसे छोटे पथ के पेड़ और इसकी रूटिंग तालिका की गणना करता है। यदि दो नोड अलग-अलग नक्शों से शुरू होते हैं, तो ऐसे परिदृश्य संभव हैं जिनमें रूटिंग लूप बनाए जाते हैं। कुछ परिस्थितियों में, मल्टी क्लाउड वातावरण में डिफरेंशियल लूप को सक्षम किया जा सकता है। इंटरफ़ेस प्रोटोकॉल में वेरिएबल एक्सेस नोड्स एक साथ एक्सेस नोड समस्या को भी बायपास कर सकते हैं।

अनुकूलित लिंक स्टेट रूटिंग प्रोटोकॉल

ऑप्टिमाइज्ड लिंक स्टेट रूटिंग प्रोटोकॉल (ओएलएसआर) एक लिंक-स्टेट रूटिंग प्रोटोकॉल है जो मोबाइल तदर्थ नेटवर्क के लिए अनुकूलित है (जिसका उपयोग अन्य वायरलेस तदर्थ नेटवर्क पर भी किया जा सकता है)। OLSR सक्रिय है और मोबाइल तदर्थ नेटवर्क में लिंक-स्टेट जानकारी को खोजने और प्रसारित करने के लिए हैलो और टोपोलॉजी कंट्रोल (TC) संदेशों का उपयोग करता है। हैलो संदेशों का उपयोग करते हुए, प्रत्येक नोड दो-हॉप पड़ोसी जानकारी की खोज करता है और बहु बिंदु रिले (एमपीआर) का एक सेट चुनता है। MPRs OLSR को अन्य लिंक-स्टेट रूटिंग प्रोटोकॉल से अलग बनाते हैं। अलग-अलग नोड्स नेटवर्क में सभी नोड्स के बारे में अगली-हॉप पथों की गणना करने के लिए टोपोलॉजी जानकारी का उपयोग करते हैं, जो शॉर्ट-हॉप फ़ॉरवर्डिंग पथों का उपयोग करते हैं।

यह भी देखें

• IEEE 802.1aq|802.1aq सबसे छोटा पाथ ब्रिजिंग

संदर्भ

• Josh Seeger and Atul Khanna, Reducing Routing Overhead in a Growing DDN, MILCOMM '86, IEEE, 1986
• Radia Perlman “Rbridges: Transparent Routing”, Infocom 2004.

अग्रिम पठन

• Section "Link-State Versus Distance Vector" in the Chapter "Routing Basics" in the Cisco "Internetworking Technology Handbook"