राउटिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 80: Line 80:


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


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


उपयोग किए गए एकल-एजेंट मॉडल में, उदाहरण के लिए, टर्मिनल पर [[ स्वचालित निर्देशित वाहन ]]ों (एजीवी) को रूट करने के लिए, प्रत्येक वाहन के लिए एक बुनियादी ढांचे के एक ही हिस्से के एक साथ उपयोग को रोकने के लिए आरक्षण किया जाता है। इस दृष्टिकोण को संदर्भ-जागरूक रूटिंग के रूप में भी जाना जाता है।<ref>Jonne Zutt, Arjan J.C. van Gemund, Mathijs M. de Weerdt, and Cees Witteveen (2010). [http://www.st.ewi.tudelft.nl/~mathijs/publications/intinfra09.pdf Dealing with Uncertainty in Operational Transport Planning]. In R.R. Negenborn and Z. Lukszo and H. Hellendoorn (Eds.) Intelligent Infrastructures, Ch. 14, pp. 355–382. Springer.</ref>
उदाहरण के लिए, एकल-एजेंट मॉडल में, टर्मिनल पर [[ स्वचालित निर्देशित वाहन |स्वचालित निर्देशित वाहनों]] (AGVs) को रूट करने के लिए, प्रत्येक वाहन के लिए बुनियादी ढांचे के एक ही हिस्से के साथ उपयोग को रोकने के लिए आरक्षण किया जाता है। इस दृष्टिकोण को कॉन्टेक्स्ट अवेयर रूटिंग भी कहा जाता है।<ref>Jonne Zutt, Arjan J.C. van Gemund, Mathijs M. de Weerdt, and Cees Witteveen (2010). [http://www.st.ewi.tudelft.nl/~mathijs/publications/intinfra09.pdf Dealing with Uncertainty in Operational Transport Planning]. In R.R. Negenborn and Z. Lukszo and H. Hellendoorn (Eds.) Intelligent Infrastructures, Ch. 14, pp. 355–382. Springer.</ref>


इंटरनेट को स्वायत्त प्रणाली (इंटरनेट) (एएस) जैसे इंटरनेट सेवा प्रदाताओं (आईएसपी) में विभाजित किया गया है, जिनमें से प्रत्येक अपने नेटवर्क से जुड़े मार्गों को नियंत्रित करता है। रूटिंग कई स्तरों पर होती है। सबसे पहले, एएस-स्तरीय पथ [[ सीमा गेटवे प्रोटोकॉल | सीमा गेटवे प्रोटोकॉल]] प्रोटोकॉल के माध्यम से चुने जाते हैं जो एएस के अनुक्रम का उत्पादन करते हैं जिसके माध्यम से पैकेट प्रवाहित होते हैं। प्रत्येक एएस के पास कई रास्ते हो सकते हैं, जो निकटस्थएएस द्वारा पेश किए जाते हैं, जिसमें से चुनना है। ये रूटिंग निर्णय अक्सर इन निकटस्थएएस के साथ व्यावसायिक संबंधों से संबंधित होते हैं,<ref>Matthew Caesar and [[Jennifer Rexford]]. [http://www.cs.princeton.edu/~jrex/papers/policies.pdf BGP routing policies in ISP networks]. IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dec 2005.</ref> जो पथ गुणवत्ता या विलंबता से असंबंधित हो सकता है। दूसरा, एक बार एएस-लेवल पाथ चुने जाने के बाद, चुनने के लिए अक्सर कई संबंधित राउटर-लेवल पाथ होते हैं। यह आंशिक रूप से देय है, क्योंकि दो आईएसपी कई कनेक्शनों के माध्यम से जुड़े हो सकते हैं। एकल राउटर-स्तरीय पथ चुनने में, प्रत्येक ISP के लिए [[ गर्म-आलू रूटिंग | गर्म-आलू रूटिंग]] को नियोजित करना सामान्य अभ्यास है: उस पथ के साथ ट्रैफ़िक भेजना जो ISP के अपने नेटवर्क के माध्यम से दूरी को कम करता है - भले ही वह पथ गंतव्य तक कुल दूरी को बढ़ाता हो।
इंटरनेट को स्वायत्त प्रणाली (इंटरनेट) (ASs) जैसे इंटरनेट सेवा प्रदाताओं (ISPs) में विभाजित किया गया है, जिनमें से प्रत्येक अपने नेटवर्क से जुड़े मार्गों को नियंत्रित करता है। रूटिंग कई स्तरों पर होती है। सबसे पहले, ASs-स्तरीय पथ [[ सीमा गेटवे प्रोटोकॉल | सीमा गेटवे प्रोटोकॉल]] प्रोटोकॉल के माध्यम से चुने जाते हैं जो एएस के अनुक्रम का उत्पादन करते हैं जिसके माध्यम से पैकेट प्रवाहित होते हैं। प्रत्येक ASs के पास कई रास्ते हो सकते हैं, जो निकटस्थ ASs द्वारा पेश किए जाते हैं, जिसमें से चुनना है। ये रूटिंग निर्णय अक्सर इन निकटस्थ ASs के साथ व्यावसायिक संबंधों से संबंधित होते हैं,<ref>Matthew Caesar and [[Jennifer Rexford]]. [http://www.cs.princeton.edu/~jrex/papers/policies.pdf BGP routing policies in ISP networks]. IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dec 2005.</ref> जो पथ गुणवत्ता या विलंबता से संबंधित हो सकता है। दूसरा, एक बार AS-लेवल पथ का चयन हो जाने के बाद, अक्सर कई संबंधित रूटर-स्तरीय पथ होते हैं। यह आंशिक रूप से देय है, क्योंकि दो ISPs कई कनेक्शन के माध्यम से जुड़े हो सकते हैं। एकल रूटर-स्तरीय पथ का चयन करने में, प्रत्येक ISP के लिए हॉट-पोटेटो रूटिंग को नियोजित करना सामान्य अभ्यास है: इस मार्ग पर यातायात भेजना जो ISP's के अपने नेटवर्क के माध्यम से दूरी को कम करता है - भले ही वह मार्ग गंतव्य तक की कुल दूरी को बढ़ाता है। 


उदाहरण के लिए, दो आईएसपी, ए और बी पर विचार करें। प्रत्येक की [[ न्यूयॉर्क शहर ]] में उपस्थिति है, जो विलंबता के साथ एक तेज़ लिंक से जुड़ा हुआ है। {{val|5|ul=ms}}—और प्रत्येक की लंदन में उपस्थिति 5 एमएस लिंक से जुड़ी हुई है। मान लें कि दोनों ISP के पास ट्रांस-अटलांटिक लिंक हैं जो उनके दो नेटवर्क को कनेक्ट करते हैं, लेकिन A<nowiki/> के लिंक में विलंबता 100 ms और B<nowiki/> की विलंबता 120 ms है। A<nowiki/> के लंदन नेटवर्क में किसी स्रोत से B<nowiki/> के न्यूयॉर्क नेटवर्क में गंतव्य तक संदेश भेजते समय, A लंदन में B को तुरंत संदेश भेजने का विकल्प चुन सकता है। यह ए को महंगे ट्रांस-अटलांटिक लिंक के साथ भेजने का काम बचाता है, लेकिन संदेश को 125 एमएस विलंबता का अनुभव करने का कारण बनता है जब अन्य मार्ग 20 एमएस तेज होता।
उदाहरण के लिए, दो ISPs, A और B पर विचार करें। प्रत्येक की[[ न्यूयॉर्क शहर | न्यू यॉर्क]] में उपस्थिति है, जो विलंबता 5 ms के साथ तेज़ लिंक से जुड़ा और प्रत्येक की लंदन में {{val|5|ul=ms}} लिंक से जुड़ी उपस्थिति है। मान लीजिए कि दोनों ISP के पास ट्रांस-अटलांटिक लिंक हैं जो उनके दो नेटवर्क को जोड़ते हैं, लेकिन A के लिंक में विलंबता 100 ms और B की विलंबता 120 ms है। A के लंदन नेटवर्क में स्रोत से B के न्यूयॉर्क नेटवर्क में गंतव्य के लिए संदेश रूट करते समय, A तुरंत लंदन में B को संदेश भेजने का विकल्प चुन सकता है। यह A को महंगे ट्रांस-अटलांटिक लिंक के साथ भेजने का काम बचाता है, लेकिन संदेश को 125 ms विलंबता का अनुभव करने का कारण बनता जब अन्य रूट 20 ms तेज होता है।


इंटरनेट मार्गों के 2003 के एक मापन अध्ययन में पाया गया कि, निकटस्थISP के जोड़े के बीच, 30% से अधिक पथों ने हॉट-पोटैटो रूटिंग के कारण विलंबता को बढ़ा दिया है, जिसमें 5% पथों में कम से कम 12 ms की देरी हुई है। एएस-स्तरीय पथ चयन के कारण मुद्रास्फीति, जबकि पर्याप्त, मुख्य रूप से स्वार्थी रूटिंग नीतियों के बजाय विलंबता के लिए प्रत्यक्ष रूप से अनुकूलित करने के लिए एक तंत्र की कमी के लिए बीजीपी को जिम्मेदार ठहराया गया था। यह भी सुझाव दिया गया था कि, एक उपयुक्त तंत्र मौजूद होने पर, आईएसपी हॉट-पोटैटो रूटिंग का उपयोग करने के बजाय विलंबता को कम करने के लिए सहयोग करने के इच्छुक होंगे।<ref>Neil Spring, Ratul Mahajan, and Thomas Anderson. [http://www.cs.washington.edu/research/networking/rocketfuel/papers/sigcomm2003.pdf Quantifying the Causes of Path Inflation]. Proc. [[SIGCOMM]] 2003.</ref> ऐसा तंत्र बाद में उन्हीं लेखकों द्वारा प्रकाशित किया गया था, पहले दो आईएसपी के मामले में<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2005-nexit.pdf Negotiation-Based Routing Between Neighboring ISPs]. Proc. [[NSDI]] 2005.</ref> और फिर वैश्विक मामले के लिए।<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2007-wiser.pdf Mutually Controlled Routing with Independent ISPs]. Proc. [[NSDI]] 2007.</ref>
इंटरनेट रूट के 2003 के मापन अध्ययन में पाया गया कि, निकटस्थ ISPs के जोड़े के बीच, 30% से अधिक पथों ने हॉट-पोटैटो रूटिंग के कारण विलंबता को बढ़ा दिया है, जिसमें 5% पथों में कम से कम 12 ms की देरी हुई है। AS-स्तरीय पथ चयन के कारण मुद्रास्फीति, जबकि पर्याप्त, मुख्य रूप से स्वार्थी रूटिंग नीतियों के बजाय विलंबता के लिए प्रत्यक्ष रूप से अनुकूलित करने के लिए तंत्र की कमी के लिए BGP's को जिम्मेदार ठहराया गया था। यह भी सुझाव दिया गया था कि, उपयुक्त तंत्र मौजूद होने पर, ISPs हॉट-पोटैटो रूटिंग का उपयोग करने के बजाय विलंबता को कम करने के लिए सहयोग करने के इच्छुक होंगे।<ref>Neil Spring, Ratul Mahajan, and Thomas Anderson. [http://www.cs.washington.edu/research/networking/rocketfuel/papers/sigcomm2003.pdf Quantifying the Causes of Path Inflation]. Proc. [[SIGCOMM]] 2003.</ref> ऐसा तंत्र बाद में उन्हीं लेखकों द्वारा प्रकाशित किया गया था, पहले दो ISPs के मामले में<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2005-nexit.pdf Negotiation-Based Routing Between Neighboring ISPs]. Proc. [[NSDI]] 2005.</ref> और फिर वैश्विक मामले के लिए।<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2007-wiser.pdf Mutually Controlled Routing with Independent ISPs]. Proc. [[NSDI]] 2007.</ref>




Revision as of 00:09, 23 January 2023

This article is about पैकेट स्विचिंग नेटवर्क में रूटिंग. For other uses, see राउटिंग (disambiguation).

रूटिंग नेटवर्क में या एकाधिक नेटवर्क के बीच या उसके पार ट्रैफ़िक के लिए पथ चयन करने की प्रक्रिया है। मोटे तौर पर, रूटिंग कई प्रकार के नेटवर्क में किया जाता है, जिसमें सर्किट-स्विच्ड नेटवर्क, जैसे पब्लिक स्विच्ड टेलीफोन नेटवर्क (PSTN) और कंप्यूटर नेटवर्क, जैसे इंटरनेट शामिल है।

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

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

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

वितरण योजनाएँ

रूटिंग योजनाएँ संदेश देने के तरीके में भिन्न होती हैं:

  • यूनिकस्ट, प्रेषक और गंतव्य के बीच एक से एक जुड़ाव का उपयोग करके एकल विशिष्ट नोड को संदेश देता है: प्रत्येक गंतव्य ऐड्रेस विशिष्ट रूप से एकल रिसीवर समापन बिंदु की पहचान करता है।
  • ब्रॉडकास्ट वन-टू-ऑल एसोसिएशन का उपयोग करके नेटवर्क में सभी नोड्स को संदेश भेजता है; प्रेषक से एकल डेटाग्राम (या पैकेट) को प्रसारण ऐड्रेस से जुड़े सभी संभवतः कई समापन बिंदुओं पर भेजा जाता है। प्रसारण के दायरे में सभी प्राप्तकर्ताओं तक पहुंचने के लिए नेटवर्क स्वचालित रूप से डेटाग्राम को दोहराता है, जो आम तौर पर पूरा नेटवर्क उपनेट होता है।
  • मल्टीकास्ट नोड्स के समूह को संदेश देता है जिसने एक-से-अनेक-में-अनेक या अनेक-से-कई-अनेक संगठनों का उपयोग करके संदेश प्राप्त करने में रुचि व्यक्त की है; कई प्राप्तकर्ताओं को एकल संचरण में डेटाग्राम एक साथ रूट किए जाते हैं। जरूरी नहीं कि सभी, सुलभ नोड्स के मल्टीकास्ट प्रसारण से भिन्न होता है जिसमें गंतव्य ऐड्रेस सबसेट निर्दिष्ट करता है।
  • एनीकास्ट नोड्स के समूह में से किसी एक को संदेश देता है, आम तौर पर एक-से-एक-कई संपर्क का उपयोग करके स्रोत के निकटतम जहां डेटाग्राम संभावित रिसीवर के समूह के किसी एक सदस्य को रूट किए जाते हैं। जो सभी एक ही गंतव्य ऐड्रेस से पहचाने जाते हैं। रूटिंग एल्गोरिथ्म समूह से एकल रिसीवर का चयन करता है जिसके आधार पर कुछ दूरी या लागत माप के अनुसार निकटतम होता है।

यूनिकास्ट इंटरनेट पर संदेश वितरण का प्रमुख रूप है। यह लेख यूनिकास्ट रूटिंग एल्गोरिदम पर केंद्रित है।

टोपोलॉजी वितरण

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

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

दूरी वेक्टर एल्गोरिदम

Main article: दूरी-वेक्टर रूटिंग प्रोटोकॉल

दूरी वेक्टर एल्गोरिदम बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग करते हैं। यह दृष्टिकोण नेटवर्क में प्रत्येक नोड के बीच लिंक में से प्रत्येक के लिए लागत संख्या निर्धारित करता है। नोड्स बिंदु A से बिंदु B तक जानकारी भेजते हैं जो सबसे कम कुल लागत में परिणाम देता है। अर्थात उपयोग किए गए नोड्स के बीच लिंक की लागत का योग।

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

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

लिंक-राज्य एल्गोरिदम

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

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

उपयुक्त लिंक स्टेट रूटिंग एल्गोरिथम

Main article: उपयुक्त लिंक स्टेट रूटिंग एल्गोरिथम

मोबाइल एडहॉक नेटवर्क के लिए उपयुक्त लिंक-स्टेट रूटिंग एल्गोरिथ्म, उपयुक्त लिंक स्टेट रूटिंग प्रोटोकॉल (OLSR) है।[1] OLSR सक्रिय है, यह मोबाइल एड हॉक नेटवर्क के माध्यम से लिंक-स्टेट जानकारी की खोज और प्रसार के लिए हैलो और टोपोलॉजी कंट्रोल (TC) संदेशों का उपयोग करता है। हैलो संदेश का उपयोग करते हुए, प्रत्येक नोड 2-hop निकटस्थ जानकारी का पता लगाता है और मल्टीपॉइंट रिले (MPRs) का सेट चुनता है। MPRs अन्य लिंक-स्टेट रूटिंग प्रोटोकॉल से OLSR को अलग करता है।

पथ-वेक्टर प्रोटोकॉल

Main article: पाथ-वेक्टर रूटिंग प्रोटोकॉल

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

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

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


पथ चयन

पथ चयन में सर्वोत्तम मार्ग का चयन (या भविष्यवाणी) करने के लिए कई मार्गों पर मेट्रिक्स (नेटवर्किंग) लागू करना शामिल है। अधिकांश रूटिंग एल्गोरिदम एक समय में केवल एक नेटवर्क पथ का उपयोग करते हैं। मल्टीपाथ रूटिंग और विशेष रूप से समान लागत वाली मल्टी-पाथ रूटिंग तकनीकें कई वैकल्पिक रास्तों के उपयोग को सक्षम बनाती हैं।

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

ओवरलैपिंग या बराबर मार्गों के मामले में, रूटिंग तालिका में किन मार्गों को स्थापित करना है, यह तय करने के लिए एल्गोरिदम निम्नलिखित तत्वों को प्राथमिकता क्रम में मानते हैं:

  1. उपसर्ग की लंबाई: एक लंबे सबनेट मास्क के साथ एक मैचिंग रूट टेबल प्रविष्टि हमेशा पसंद की जाती है क्योंकि यह गंतव्य को अधिक सटीक रूप से निर्दिष्ट करती है।
  2. Metrics (नेटवर्किंग): समान रूटिंग प्रोटोकॉल के माध्यम से सीखे गए मार्गों की तुलना करते समय, निम्न मीट्रिक को प्राथमिकता दी जाती है। अलग-अलग रूटिंग प्रोटोकॉल से सीखे गए रूट के बीच मेट्रिक्स की तुलना नहीं की जा सकती।
  3. प्रशासनिक दूरी : विभिन्न रूटिंग प्रोटोकॉल और स्थिर कॉन्फ़िगरेशन जैसे विभिन्न स्रोतों से रूट तालिका प्रविष्टियों की तुलना करते समय, एक कम प्रशासनिक दूरी एक अधिक विश्वसनीय स्रोत और इस प्रकार एक पसंदीदा मार्ग का संकेत देती है।

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

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

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

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

बड़ी प्रणालियों में, उपकरणों के बीच इतने सारे कनेक्शन होते हैं, और वे कनेक्शन इतनी बार-बार बदलते हैं, कि किसी एक डिवाइस के लिए यह जानना भी संभव नहीं है कि सभी डिवाइस एक-दूसरे से कैसे जुड़े हैं, उनके माध्यम से एक पूर्ण पथ की गणना करना तो दूर की बात है। ऐसी प्रणालियाँ आम तौर पर हॉप (नेटवर्किंग)#नेक्स्ट हॉप|नेक्स्ट-हॉप रूटिंग का उपयोग करती हैं।

अधिकांश प्रणालियाँ नियतात्मक गतिशील रूटिंग एल्गोरिथम का उपयोग करती हैं। जब कोई उपकरण किसी विशेष अंतिम गंतव्य के लिए एक रास्ता चुनता है, तो वह उपकरण हमेशा उस गंतव्य के लिए एक ही रास्ता चुनता है जब तक कि वह ऐसी जानकारी प्राप्त नहीं कर लेता है जिससे उसे लगता है कि कोई अन्य रास्ता बेहतर है।

कुछ रूटिंग एल्गोरिदम एक पैकेट के लिए अपने मूल स्रोत से अपने अंतिम गंतव्य तक जाने के लिए सबसे अच्छा लिंक खोजने के लिए नियतात्मक एल्गोरिदम का उपयोग नहीं करते हैं। इसके बजाय, पैकेट सिस्टम में कंजेशन हॉट स्पॉट से बचने के लिए, कुछ एल्गोरिदम एक यादृच्छिक एल्गोरिथ्म का उपयोग करते हैं- वैलिएंट का प्रतिमान- जो एक बेतरतीब ढंग से चुने गए मध्यवर्ती गंतव्य के लिए मार्ग बनाता है, और वहां से उसके वास्तविक अंतिम गंतव्य तक।[4][5] कई शुरुआती टेलीफोन स्विचों में, 1ESS स्विच#स्विचिंग फैब्रिक के माध्यम से पथ की शुरुआत का चयन करने के लिए अक्सर एक रेंडमाइज़र का उपयोग किया जाता था।

जिस एप्लिकेशन के लिए पथ चयन किया गया है, उसके आधार पर विभिन्न मीट्रिक का उपयोग किया जा सकता है। उदाहरण के लिए, वेब अनुरोधों के लिए कोई वेब पेज लोड समय को कम करने के लिए न्यूनतम विलंबता पथ का उपयोग कर सकता है, या बल्क डेटा ट्रांसफर के लिए नेटवर्क पर लोड को संतुलित करने और थ्रुपुट बढ़ाने के लिए कम से कम उपयोग किए जाने वाले पथ का चयन कर सकता है। एक लोकप्रिय पथ चयन उद्देश्य यातायात प्रवाह के औसत समापन समय और कुल नेटवर्क बैंडविड्थ खपत को कम करना है। हाल ही में, एक पथ चयन मीट्रिक प्रस्तावित किया गया था जो चयन मीट्रिक के रूप में प्रति पथ किनारों पर निर्धारित बाइट्स की कुल संख्या की गणना करता है।[6] इस नए प्रस्ताव सहित कई पथ चयन मेट्रिक्स का अनुभवजन्य विश्लेषण उपलब्ध कराया गया है।[7]


एकाधिक एजेंट

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

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

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

इंटरनेट को स्वायत्त प्रणाली (इंटरनेट) (ASs) जैसे इंटरनेट सेवा प्रदाताओं (ISPs) में विभाजित किया गया है, जिनमें से प्रत्येक अपने नेटवर्क से जुड़े मार्गों को नियंत्रित करता है। रूटिंग कई स्तरों पर होती है। सबसे पहले, ASs-स्तरीय पथ सीमा गेटवे प्रोटोकॉल प्रोटोकॉल के माध्यम से चुने जाते हैं जो एएस के अनुक्रम का उत्पादन करते हैं जिसके माध्यम से पैकेट प्रवाहित होते हैं। प्रत्येक ASs के पास कई रास्ते हो सकते हैं, जो निकटस्थ ASs द्वारा पेश किए जाते हैं, जिसमें से चुनना है। ये रूटिंग निर्णय अक्सर इन निकटस्थ ASs के साथ व्यावसायिक संबंधों से संबंधित होते हैं,[9] जो पथ गुणवत्ता या विलंबता से संबंधित हो सकता है। दूसरा, एक बार AS-लेवल पथ का चयन हो जाने के बाद, अक्सर कई संबंधित रूटर-स्तरीय पथ होते हैं। यह आंशिक रूप से देय है, क्योंकि दो ISPs कई कनेक्शन के माध्यम से जुड़े हो सकते हैं। एकल रूटर-स्तरीय पथ का चयन करने में, प्रत्येक ISP के लिए हॉट-पोटेटो रूटिंग को नियोजित करना सामान्य अभ्यास है: इस मार्ग पर यातायात भेजना जो ISP's के अपने नेटवर्क के माध्यम से दूरी को कम करता है - भले ही वह मार्ग गंतव्य तक की कुल दूरी को बढ़ाता है।

उदाहरण के लिए, दो ISPs, A और B पर विचार करें। प्रत्येक की न्यू यॉर्क में उपस्थिति है, जो विलंबता 5 ms के साथ तेज़ लिंक से जुड़ा और प्रत्येक की लंदन में 5 ms लिंक से जुड़ी उपस्थिति है। मान लीजिए कि दोनों ISP के पास ट्रांस-अटलांटिक लिंक हैं जो उनके दो नेटवर्क को जोड़ते हैं, लेकिन A के लिंक में विलंबता 100 ms और B की विलंबता 120 ms है। A के लंदन नेटवर्क में स्रोत से B के न्यूयॉर्क नेटवर्क में गंतव्य के लिए संदेश रूट करते समय, A तुरंत लंदन में B को संदेश भेजने का विकल्प चुन सकता है। यह A को महंगे ट्रांस-अटलांटिक लिंक के साथ भेजने का काम बचाता है, लेकिन संदेश को 125 ms विलंबता का अनुभव करने का कारण बनता जब अन्य रूट 20 ms तेज होता है।

इंटरनेट रूट के 2003 के मापन अध्ययन में पाया गया कि, निकटस्थ ISPs के जोड़े के बीच, 30% से अधिक पथों ने हॉट-पोटैटो रूटिंग के कारण विलंबता को बढ़ा दिया है, जिसमें 5% पथों में कम से कम 12 ms की देरी हुई है। AS-स्तरीय पथ चयन के कारण मुद्रास्फीति, जबकि पर्याप्त, मुख्य रूप से स्वार्थी रूटिंग नीतियों के बजाय विलंबता के लिए प्रत्यक्ष रूप से अनुकूलित करने के लिए तंत्र की कमी के लिए BGP's को जिम्मेदार ठहराया गया था। यह भी सुझाव दिया गया था कि, उपयुक्त तंत्र मौजूद होने पर, ISPs हॉट-पोटैटो रूटिंग का उपयोग करने के बजाय विलंबता को कम करने के लिए सहयोग करने के इच्छुक होंगे।[10] ऐसा तंत्र बाद में उन्हीं लेखकों द्वारा प्रकाशित किया गया था, पहले दो ISPs के मामले में[11] और फिर वैश्विक मामले के लिए।[12]