रूटींग एल्गोरिदम

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

Definition

एक रूटिंग एल्गोरिदम एक प्रक्रिया है जो एक भारित ग्राफ (weighted graph) के रूप में प्रतिरूपित नेटवर्क के माध्यम से सबसे कम लागत वाले (या अन्यथा पसंदीदा) पथों को निर्धारित करती है, जिससे फॉरवर्डिंग निर्णय उत्पन्न होते हैं जिनका उपयोग राउटर पैकेटों को उनके गंतव्यों की ओर ले जाने के लिए करते हैं।

Scope

यह विषय उन एल्गोरिदम को शामिल करता है जो फॉरवर्डिंग तालिकाओं को भरते हैं: लिंक लागत के साथ एक नेटवर्क का ग्राफ मॉडल; वैश्विक रूप से साझा टोपोलॉजी के साथ डाइकस्ट्रा के सबसे छोटे-पथ एल्गोरिदम का उपयोग करके लिंक-स्टेट रूटिंग; पड़ोसी एक्सचेंजों के साथ वितरित बेलमैन-फोर्ड गणना का उपयोग करके दूरी-वेक्टर रूटिंग; उनके अभिसरण व्यवहार और विकृतियाँ जैसे कि काउंट-टू-इन्फिनिटी समस्या; और स्केलेबिलिटी के लिए पदानुक्रमित रूटिंग। यह एल्गोरिदम को अमूर्त रूप से मानता है, ठोस प्रोटोकॉल (OSPF, RIP, BGP) और उनके इंट्रा/इंटर-डोमेन संगठन को रूटिंग-प्रोटोकॉल विषय पर छोड़ देता है।

Core questions

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

Key concepts

• भारित नेटवर्क ग्राफ
• सबसे कम लागत वाले पथ
• लिंक-स्टेट रूटिंग
• डाइकस्ट्रा का एल्गोरिदम
• दूरी-वेक्टर रूटिंग
• बेलमैन-फोर्ड समीकरण
• काउंट-टू-इन्फिनिटी समस्या
• स्प्लिट होराइजन और पॉइज़न्ड रिवर्स
• पदानुक्रमित रूटिंग

Key theories

लिंक-स्टेट रूटिंग (डाइकस्ट्रा)

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

दूरी-वेक्टर रूटिंग (बेलमैन-फोर्ड)

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

पदानुक्रमित रूटिंग

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

Clinical relevance

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

History

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

Debates

लिंक-स्टेट बनाम दूरी-वेक्टर रूटिंग

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

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

काउंट-टू-इन्फिनिटी समस्या क्या है?

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

लिंक-स्टेट और दूरी-वेक्टर दोनों का उपयोग क्यों किया जाता है?

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