लिंक-स्टेट रूटिंग प्रोटोकॉल
लिंक-स्टेट रूटिंग प्रोटोकॉल कंप्यूटर संचार के लिए पैकेट-स्विचिंग नेटवर्क में उपयोग किए जाने वाले राउटिंग प्रोटोकॉल के दो मुख्य वर्गों में से एक हैं, अन्य दूरी-वेक्टर रूटिंग प्रोटोकॉल हैं। लिंक-स्टेट रूटिंग प्रोटोकॉल के उदाहरणों में ओपन शॉर्टेस्ट पाथ फ़र्स्ट (ओएसपीएफ) और इंटरमीडिएट सिस्टम से इंटरमीडिएट सिस्टम (IS-IS) सम्मिलित हैं।
लिंक-स्टेट प्रोटोकॉल नेटवर्क में प्रत्येक स्विचिंग नोड द्वारा निष्पादित किया जाता है (यानी, नोड्स जो पैकेट को अग्रेषित करने के लिए तैयार होते हैं; इंटरनेट में, इन्हें राउटर कहा जाता है)। लिंक-स्टेट रूटिंग की मूल अवधारणा यह है कि प्रत्येक नोड एक ग्राफ के रूप में नेटवर्क से संयोजकता का नक्शा बनाता है, जो दिखाता है कि कौन से नोड किस अन्य नोड से जुड़े हैं। इसके बाद प्रत्येक नोड स्वतंत्र रूप से नेटवर्क में हर संभव गंतव्य के लिए उससे अगले सर्वश्रेष्ठ तार्किक पथ की गणना करता है। सर्वोत्तम पथों का प्रत्येक संग्रह तब प्रत्येक नोड की राउटिंग तालिका बनाएगा।
यह दूरी-वेक्टर रूटिंग प्रोटोकॉल के साथ विरोधाभासी है, जो प्रत्येक नोड को अपने रूटिंग टेबल को अपने नेबर के साथ साझा करके काम करता है, लिंक-स्टेट प्रोटोकॉल में नोड्स के बीच पारित होने वाली एकमात्र सूचना संयोजकता से संबंधित है। लिंक-स्टेट एल्गोरिदम को कभी-कभी अनौपचारिक रूप से प्रत्येक राउटर के रूप में वर्णित किया जाता है, "दुनिया को अपने नेबर के बारे में बताते हुए।"
सिंहावलोकन
लिंक-स्टेट रूटिंग प्रोटोकॉल में, प्रत्येक राउटर में संपूर्ण नेटवर्क टोपोलॉजी की जानकारी होती है। इसके बाद प्रत्येक राउटर स्वतंत्र रूप से टोपोलॉजी की स्थानीय जानकारी का उपयोग करके नेटवर्क में हर संभव गंतव्य के लिए उससे सर्वश्रेष्ठ अगली हॉप की गणना करता है। बेस्ट-नेक्स्ट-हॉप्स का कलेक्शन रूटिंग टेबल बनाता है।
यह दूरी-वेक्टर रूटिंग प्रोटोकॉल के साथ विरोधाभासी है, जो प्रत्येक नोड को अपने नेबर्स के साथ रूटिंग टेबल साझा करके काम करता है। लिंक-स्टेट प्रोटोकॉल में, नोड्स के बीच पारित होने वाली एकमात्र जानकारी संयोजकता मानचित्र बनाने के लिए उपयोग की जाने वाली जानकारी है।
लिंक-स्टेट रूटिंग प्रोटोकॉल के उदाहरण:
- ओपन शार्टेस्ट पाथ फर्स्ट (ओएसपीएफ)
- इंटरमीडिएट सिस्टम से इंटरमीडिएट सिस्टम (आईएस-आईएस)
इतिहास
माना जाता है कि कंप्यूटर का पहला अनुकूली रूटिंग नेटवर्क, लिंक-स्टेट रूटिंग को अपने दिल के रूप में उपयोग करते हुए, 1976-1977 के दौरान बर्नार्ड जे हैरिस के नेतृत्व में प्लेसी रडार की एक टीम द्वारा डिजाइन और कार्यान्वित किया गया था; यह प्रोजेक्ट "वेवेल" के लिए था - ब्रिटिश सेना के लिए कंप्यूटर कमांड और कंट्रोल की एक प्रणाली थी।
पहली लिंक-स्टेट रूटिंग अवधारणा को 1979 में जॉन एम. मैकक्विलन (तब बोल्ट, बेरानेक और न्यूमैन) द्वारा एक तंत्र के रूप में प्रकाशित किया गया था, जो नेटवर्क की स्थिति बदलने पर मार्गों की अधिक तेज़ी से गणना करेगा, और इस प्रकार अधिक स्थिर रूटिंग की ओर ले जाएगा।[1][2]
बाद में बीबीएन टेक्नोलॉजीज में काम ने दिखाया कि एक पदानुक्रमित प्रणाली में लिंक-स्टेट तकनीक का उपयोग कैसे करें (यानी, जिसमें नेटवर्क को क्षेत्रों में विभाजित किया गया था) ताकि प्रत्येक स्विचिंग नोड को पूरे नेटवर्क के मानचित्र की आवश्यकता न हो, केवल वह क्षेत्र (क्षेत्र) जिसमें यह सम्मिलित है।
तकनीक को बाद में समकालीन लिंक-स्टेट रूटिंग प्रोटोकॉल आईएस-आईएस और ओएसपीएफ में उपयोग के लिए अनुकूलित किया गया था। सिस्को साहित्य एन्हांस्ड इंटीरियर गेटवे रूटिंग प्रोटोकॉल (ईआईजीआरपी) को "हाइब्रिड" प्रोटोकॉल के रूप में संदर्भित करता है, [उद्धरण वांछित] इस तथ्य के बावजूद कि यह टोपोलॉजी मानचित्रों के बजाय रूटिंग टेबल वितरित करता है। हालाँकि, यह ओएसपीएफ की तरह स्टार्ट-अप पर राउटिंग टेबल को सिंक्रोनाइज़ करता है और विशिष्ट अपडेट केवल तभी भेजता है जब टोपोलॉजी में परिवर्तन होता है।
2004 में, राडिया पर्लमैन ने रूटिंग ब्रिज या ब्रिजेज नामक उपकरणों के साथ लेयर 2 फ्रेम अग्रेषण के लिए लिंक-स्टेट रूटिंग का उपयोग करने का प्रस्ताव दिया। इंटरनेट इंजीनियरिंग टास्क फोर्स ने इसे पूरा करने के लिए ट्रांसपैरेंट इंटरकनेक्शन ऑफ़ लोट्स ऑफ़ लिंक्स (ट्रिल) प्रोटोकॉल का मानकीकरण किया है।[3]
हाल ही में, इस पदानुक्रमित तकनीक को अनुकूलित लिंक स्टेट रूटिंग प्रोटोकॉल (ओएलएसआर) का उपयोग करके वायरलेस मेश नेटवर्क पर लागू किया गया था। जहां कनेक्शन की गुणवत्ता अलग-अलग हो सकती है, संपर्क की गुणवत्ता का उपयोग बेहतर कनेक्शन चुनने के लिए किया जा सकता है। इसका उपयोग कुछ तदर्थ रूटिंग प्रोटोकॉल में किया जाता है जो रेडियो आवृत्ति संचरण का उपयोग करते हैं।
2012 में, आईईईई ने आईईईई 802.1aq सबसे छोटे पथ ब्रिजिंग (एसपीबी) के साथ ईथरनेट अग्रेषण को नियंत्रित करने के लिए आईएस-आईएस के उपयोग के मानकीकरण को पूरा किया और अनुमोदित किया।
मानचित्रों का वितरण
यह विवरण केवल सबसे सरल विन्यास को सम्मिलित करता है; यानी, बिना किसी क्षेत्र के, ताकि सभी नोड्स में पूरे नेटवर्क का नक्शा हो। श्रेणीबद्ध मामला कुछ और जटिल है; विभिन्न प्रोटोकॉल विशिष्टताओं को देखें।
जैसा कि पहले उल्लेख किया गया है, लिंक-स्टेट एल्गोरिथम में पहला मुख्य चरण प्रत्येक नोड को नेटवर्क का मानचित्र देना है। यह कई सहायक चरणों द्वारा किया जाता है।
प्रत्येक नोड के नेबर का निर्धारण
सबसे पहले, प्रत्येक नोड को यह निर्धारित करने की आवश्यकता है कि यह पूरी तरह से काम कर रहे लिंक पर अन्य पोर्ट से जुड़ा है; यह रीचैबिलिटी प्रोटोकॉल का उपयोग करके ऐसा करता है जो समय-समय पर और अलग से अपने प्रत्येक सीधे जुड़े नेबर के साथ चलता है।
मानचित्र के लिए जानकारी का वितरण
अगला, प्रत्येक नोड समय-समय पर (और संयोजकता परिवर्तन के मामले में) संक्षिप्त संदेश भेजता है, लिंक-स्टेट विज्ञापन, जो:
- उस नोड की पहचान करता है जो इसे उत्पन्न कर रहा है।
- अन्य सभी नोड्स (राउटर या नेटवर्क) की पहचान करता है जिससे यह सीधे जुड़ा हुआ है।
- 'अनुक्रम संख्या' सम्मिलित है, जो हर बार स्रोत नोड द्वारा संदेश का एक नया संस्करण बनाने पर बढ़ जाती है।
यह संदेश नेटवर्क पर सभी नोड्स को भेजा जाता है। एक आवश्यक अग्रदूत के रूप में, नेटवर्क में प्रत्येक नोड अपने प्रत्येक नेबर के लिए, उस नोड से प्राप्त अंतिम लिंक-स्टेट संदेश की क्रम संख्या को याद रखता है। जब एक लिंक-स्टेट विज्ञापन एक नोड पर प्राप्त होता है, तो नोड उस लिंक-स्टेट संदेश के स्रोत के लिए संग्रहीत अनुक्रम संख्या को देखता है: यदि यह संदेश नया है (यानी, एक उच्च क्रम संख्या है), तो इसे सहेजा जाता है, अनुक्रम संख्या अपडेट की जाती है, और उस नोड के प्रत्येक नेबर को बारी-बारी से एक प्रति भेजी जाती है। यह प्रक्रिया तेजी से नेटवर्क में प्रत्येक नोड के प्रत्येक नोड के लिंक-स्टेट विज्ञापन के नवीनतम संस्करण की एक प्रति प्राप्त करती है।
लिंक स्टेट एल्गोरिदम चलाने वाले नेटवर्क को पदानुक्रम में भी विभाजित किया जा सकता है जो मार्ग परिवर्तन के दायरे को सीमित करता है। इन सुविधाओं का मतलब है कि लिंक स्टेट एल्गोरिदम बड़े नेटवर्क के लिए बेहतर है।
मानचित्र बनाना
अंत में, हाथ में लिंक-स्टेट विज्ञापनों (नेटवर्क में प्रत्येक नोड से एक) के पूर्ण सेट के साथ, प्रत्येक नोड नेटवर्क के मानचित्र के लिए ग्राफ का उत्पादन करता है। एल्गोरिथ्म लिंक-स्टेट विज्ञापनों के संग्रह पर पुनरावृत्त करता है; प्रत्येक के लिए, यह नेटवर्क के मानचित्र पर लिंक बनाता है, उस नोड से जिसने उस संदेश को भेजा है, उन सभी नोड्स के लिए जो संदेश भेजने वाले नोड के नेबर हैं।
जब तक दोनों छोर सहमत नहीं होते, तब तक किसी भी लिंक को सही ढंग से रिपोर्ट नहीं किया जाता है; यानी अगर नोड रिपोर्ट करता है कि यह दूसरे से जुड़ा हुआ है, लेकिन दूसरा नोड यह रिपोर्ट नहीं करता है कि यह पहले से जुड़ा है, तो एक समस्या है, और लिंक मानचित्र पर सम्मिलित नहीं है।
इस अवस्था के बारे में टिप्पणियाँ
नेबर्स के बारे में जानकारी देने वाले लिंक-स्टेट संदेश की पुनर्गणना की जाती है, और फिर पूरे नेटवर्क में बाढ़ आ जाती है, जब भी नोड और उसके नेबर्स के बीच संयोजकता में कोई बदलाव होता है; जैसे, जब कोई लिंक फेल हो जाता है। इस तरह के किसी भी बदलाव का पता रीचैबिलिटी प्रोटोकॉल द्वारा लगाया जाएगा जो प्रत्येक नोड अपने नेबर्स के साथ चलता है।
रूटिंग टेबल की गणना
जैसा कि प्रारम्भ में उल्लेख किया गया है, लिंक-स्टेट एल्गोरिथम में दूसरा मुख्य चरण मानचित्रों का निरीक्षण करके राउटिंग टेबल बनाना है। इसे फिर से कई चरणों में किया जाता है।
सबसे छोटे पथों की गणना करना
प्रत्येक नोड स्वतंत्र रूप से नेटवर्क में प्रत्येक दूसरे नोड के लिए सबसे छोटा रास्ता निर्धारित करने के लिए मानचित्र पर एक एल्गोरिथ्म चलाता है; सामान्यतः, दिज्क्स्ट्रा के एल्गोरिथ्म के कुछ संस्करण का उपयोग किया जाता है। यह प्रत्येक पथ पर एक लिंक लागत पर आधारित है जिसमें अन्य बातों के अलावा उपलब्ध बैंडविड्थ सम्मिलित है।
नोड दो डेटा संरचनाओं को बनाए रखता है: ट्री डेटा संरचना जिसमें नोड्स होते हैं, और उम्मीदवारों की एक सूची। एल्गोरिथ्म दोनों संरचनाओं के खाली होने से प्रारम्भ होता है; इसके बाद यह पहले नोड में ही जुड़ जाता है। एल्गोरिथ्म का संस्करण फिर दोहराव से निम्नलिखित कार्य करता है:
- सभी नेबर नोड्स जो सीधे नोड से जुड़े होते हैं, उन्हें सिर्फ ट्री में जोड़ा जाता है (किसी भी नोड को छोड़कर जो पहले से ही ट्री या उम्मीदवार सूची में हैं)। बाकी को दूसरी (उम्मीदवार) सूची में जोड़ा जाता है।
- उम्मीदवार सूची में प्रत्येक नोड की तुलना ट्री में पहले से मौजूद प्रत्येक नोड से की जाती है। उम्मीदवार नोड जो पहले से ही ट्री में किसी भी नोड के सबसे करीब है, ट्री में ही ले जाया जाता है और उपयुक्त नेबर नोड से जुड़ा होता है। जब एक नोड को उम्मीदवार सूची से ट्री में ले जाया जाता है, तो इसे उम्मीदवार सूची से हटा दिया जाता है और एल्गोरिथम के बाद के पुनरावृत्तियों में नहीं माना जाता है।
उपरोक्त दो चरणों को तब तक दोहराया जाता है जब तक उम्मीदवार सूची में कोई नोड शेष रहता है। (जब कोई नहीं है, तो नेटवर्क में सभी नोड्स ट्री में जोड़ दिए गए होंगे।) यह प्रक्रिया नेटवर्क में सभी नोड्स वाले ट्री के साथ समाप्त होती है, जिस नोड पर कलन विधि ट्री की जड़ के रूप में चल रहा है। . उस नोड से किसी भी अन्य नोड के लिए सबसे छोटा रास्ता ट्री की जड़ से ट्री में वांछित नोड तक पहुंचने के लिए नोड्स की सूची द्वारा इंगित किया जाता है।
रूटिंग टेबल भरना
सबसे छोटे रास्तों के साथ, अगला चरण रूटिंग टेबल भरना है। किसी भी दिए गए गंतव्य नोड के लिए, उस गंतव्य के लिए सबसे अच्छा पथ वह नोड है जो रूट नोड से पहला कदम है, सबसे छोटे पथ ट्री में शाखा से नीचे है जो वांछित गंतव्य नोड की ओर जाता है। राउटिंग टेबल बनाने के लिए, केवल ट्री पर चलना आवश्यक है, प्रत्येक शाखा के प्रमुख पर नोड की पहचान को याद रखना, और प्रत्येक नोड के लिए राउटिंग टेबल प्रविष्टि भरना जो उस पहचान के साथ आता है।
एल्गोरिथ्म के लिए अनुकूलन
समझने में आसानी के लिए ऊपर वर्णित एल्गोरिथ्म को यथासंभव सरल बनाया गया था। व्यवहार में, कई अनुकूलन हैं जिनका उपयोग किया जाता है।
आंशिक पुनर्गणना
जब भी संयोजकता मानचित्र में कोई परिवर्तन होता है, तो सबसे छोटे-पथ ट्री की पुनर्गणना करना और फिर रूटिंग टेबल को फिर से बनाना आवश्यक होता है। बीबीएन टेक्नोलॉजीज द्वारा कार्य ने पता लगाया कि कैसे ट्री के केवल उस हिस्से की पुनर्गणना की जाए जो मानचित्र में दिए गए परिवर्तन से प्रभावित हो सकता था।इसके अलावा, राउटिंग टेबल को सामान्य रूप से भर दिया जाएगा क्योंकि इसे एक अलग ऑपरेशन बनाने के बजाय सबसे छोटे-पथ के ट्री की गणना की जाती है।
टोपोलॉजी कमी
कुछ मामलों में, एलएसए संदेश उत्पन्न करने वाले नोड्स की संख्या को कम करना उचित है। उदाहरण के लिए, नेटवर्क ग्राफ़ से केवल कनेक्शन वाले नोड को एलएसए संदेश भेजने की आवश्यकता नहीं है, क्योंकि इसके अस्तित्व की जानकारी पहले से ही इसके एकमात्र नेबर के एलएसए संदेश में सम्मिलित हो सकती है। इस कारण से, टोपोलॉजी कमी की रणनीति लागू की जा सकती है, जिसमें केवल नेटवर्क नोड्स का सबसेट एलएसए संदेश उत्पन्न करता है। टोपोलॉजी कमी के लिए दो व्यापक रूप से अध्ययन किए गए दृष्टिकोण हैं:
- मल्टीपॉइंट रिले जो ऑप्टिमाइज्ड लिंक स्टेट रूटिंग प्रोटोकॉल (ओएलएसआर) के आधार पर हैं लेकिन ओएसपीएफ के लिए भी प्रस्तावित हैं [4]
- कनेक्टेड डोमिनेटिंग सेट जिन्हें फिर से ओएसपीएफ के लिए प्रस्तावित किया गया है[5]
फिशआई स्टेट रूटिंग
फिशआई स्टेट रूटिंग (एफएसआर) के साथ एलएसए को उनके प्रसार को प्रतिबंधित करने और नियंत्रण संदेशों के कारण ओवरहेड को सीमित करने के लिए अलग-अलग समय-से-लाइव मूल्यों के साथ भेजा जाता है। इसी अवधारणा का उपयोग हैजी साइटेड लिंक स्टेट रूटिंग प्रोटोकॉल में भी किया जाता है।
विफलता मोड
यदि सभी नोड एक ही मानचित्र से कार्य नहीं कर रहे हैं, तो रूटिंग लूप बन सकते हैं। ये ऐसी स्थितियाँ हैं जिनमें, सरलतम रूप में, दो नेबर नोड्स प्रत्येक को लगता है कि किसी दिए गए गंतव्य के लिए दूसरा सबसे अच्छा रास्ता है। किसी भी नोड पर पहुंचने वाले उस गंतव्य की ओर जाने वाला कोई भी पैकेट दोनों के बीच लूप होगा, इसलिए यह नाम है। दो से अधिक नोड वाले रूटिंग लूप भी संभव है।
ऐसा इसलिए हो सकता है क्योंकि प्रत्येक नोड किसी भी अन्य नोड्स के साथ किसी भी तरह से इंटरैक्ट किए बिना अपने सबसे छोटे पथ के ट्री और इसकी रूटिंग टेबल की गणना करता है। यदि दो नोड अलग-अलग मानचित्रों से प्रारंभ होते हैं, तो संभव है कि ऐसे परिदृश्य हों जिनमें रूटिंग लूप बनाए जाते हैं। कुछ परिस्थितियों में, मल्टी-क्लाउड परिवेश में डिफरेंशियल लूप्स को सक्षम किया जा सकता है। इंटरफ़ेस प्रोटोकॉल में वेरिएबल एक्सेस नोड्स एक साथ एक्सेस नोड समस्या को भी बायपास कर सकते हैं।[6]
ऑप्टीमाइज़्ड लिंक स्टेट रूटिंग प्रोटोकॉल
ऑप्टिमाइज्ड लिंक स्टेट रूटिंग प्रोटोकॉल (ओएलएसआर) लिंक-स्टेट रूटिंग प्रोटोकॉल है जिसे मोबाइल एड हॉक नेटवर्क के लिए अनुकूलित किया गया है जिसका उपयोग अन्य वायरलेस एड-हॉक नेटवर्क पर भी किया जा सकता है)।[7] ओएलएसआर सक्रिय है और मोबाइल तदर्थ नेटवर्क में लिंक-राज्य सूचना को खोजने और प्रसारित करने के लिए हैलो और टोपोलॉजी नियंत्रण (टीसी) संदेशों का उपयोग करता है। हैलो संदेशों का उपयोग करते हुए, प्रत्येक नोड दो-हॉप नेबर जानकारी की खोज करता है और मल्टीपॉइंट रिले (एमपीआर) के एक सेट का चुनाव करता है। एमपीआर अन्य लिंक-स्टेट रूटिंग प्रोटोकॉल से ओएलएसआर को अलग बनाते हैं। अलग-अलग नोड्स नेटवर्क में सभी नोड्स के बारे में अगली-हॉप पथों की गणना करने के लिए टोपोलॉजी जानकारी का उपयोग सबसे कम-हॉप अग्रेषण पथों का उपयोग करते हैं।
यह भी देखें
- 802.1aq शॉर्टेस्ट पाथ ब्रिजिंग
संदर्भ
- ↑ John M. McQuillan, Isaac Richer and Eric C. Rosen, ARPANet Routing Algorithm Improvements, BBN Report No. 3803, Cambridge, April 1978
- ↑ John M. McQuillan, Isaac Richer and Eric C. Rosen, The New Routing Algorithm for the ARPANet, IEEE Trans. on Comm., 28(5), pp. 711–719, 1980
- ↑ Eastlake 3Rd, Donald E.; Senevirathne, Tissa; Ghanwani, Anoop; Dutt, Dinesh; Banerjee, Ayan (May 2014), Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS, doi:10.17487/RFC7176, RFC 7176
- ↑ Nguyen, Dang-Quan; Clausen, Thomas H.; Jacquet, Philippe; Baccelli, Emmanuel (February 2009). "तदर्थ नेटवर्क के लिए ओएसपीएफ बहुबिंदु रिले (एमपीआर) विस्तार". doi:10.17487/RFC5449.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Ogier, Richard; Spagnolo, Phil (August 2009). "कनेक्टेड डोमिनेटिंग सेट (सीडीएस) फ्लडिंग का उपयोग कर ओएसपीएफ का मोबाइल एड हॉक नेटवर्क (एमएएनईटी) विस्तार". doi:10.17487/RFC5614.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Wójcik, R (2016). "इंटरडोमेन मल्टीपाथ ट्रांसमिशन प्रदान करने के तरीकों पर एक सर्वेक्षण". Computer Networks. 108: 233–259. doi:10.1016/j.comnet.2016.08.028.
- ↑ RFC 3626
- 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"
