Backpressure routing
कतार सिद्धांत में, संभाव्यता के गणितीय सिद्धांत के भीतर एक अनुशासन, बैकप्रेशर रूटिंग एल्गोरिथ्म एक कतार नेटवर्क के आसपास यातायात को निर्देशित करने के लिए एक विधि है जो अधिकतम नेटवर्क थ्रूपुट प्राप्त करता है, जिसे लियापुनोव ड्रिफ्ट की अवधारणाओं का उपयोग करके स्थापित किया जाता है। बैकप्रेशर रूटिंग उस स्थिति पर विचार करता है जहाँ प्रत्येक कार्य नेटवर्क में कई सेवा नोड्स पर जा सकता है। यह अधिकतम-भार अनुसूचना का एक विस्तार है जहाँ प्रत्येक कार्य केवल एक सेवा नोड पर जाता है। परिचय बैकप्रेशर रूटिंग भीड़-भाड़ प्रवणता का उपयोग करके एक बहु-हॉप नेटवर्क पर यातायात को गतिशील रूप से रूट करने के लिए एक एल्गोरिथ्म है। एल्गोरिदम को वायरलेस संचार नेटवर्क पर लागू किया जा सकता है, जिसमें सेंसर नेटवर्क, मोबाइल एड हॉक नेटवर्क (MANETS) और वायरलेस और वायरलाइन घटकों के साथ विषम नेटवर्क शामिल हैं। बैकप्रेशर सिद्धांतों को अन्य क्षेत्रों में भी लागू किया जा सकता है, जैसे कि उत्पाद असेंबली सिस्टम और प्रसंस्करण नेटवर्क के अध्ययन के लिए। यह लेख संचार नेटवर्क पर केंद्रित है, जहाँ कई डेटा धाराओं से पैकेट आते हैं और उन्हें उपयुक्त गंतव्यों तक पहुँचाया जाना चाहिए। बैकप्रेशर एल्गोरिदम निर्धारित समय में काम करता है। हर बार स्लॉट यह उन दिशाओं में डेटा को रूट करने का प्रयास करता है जो पड़ोसी नोड्स के बीच अंतर बैकलॉग को अधिकतम करते हैं। यह दबाव प्रवणता के माध्यम से पाइपों के नेटवर्क के माध्यम से पानी के प्रवाह के समान है। हालांकि, बैकप्रेशर एल्गोरिदम को बहु-वस्तु नेटवर्क (जहां अलग-अलग पैकेटों के अलग-अलग गंतव्य हो सकते हैं) और नेटवर्क पर लागू किया जा सकता है जहां संचरण दरों को (संभवतः समय-परिवर्तनशील) विकल्पों के एक सेट से चुना जा सकता है। बैकप्रेशर एल्गोरिदम की आकर्षक विशेषताएं हैंः (i) यह अधिकतम नेटवर्क थ्रूपुट की ओर ले जाता है, (ii) यह समय-परिवर्तनशील नेटवर्क स्थितियों के लिए काफी मजबूत है, (iii) इसे यातायात आगमन दर या चैनल राज्य संभावनाओं को जाने बिना लागू किया जा सकता है। हालांकि, एल्गोरिथ्म बड़ी देरी पेश कर सकता है, और हस्तक्षेप के साथ नेटवर्क में ठीक से लागू करना मुश्किल हो सकता है। बैकप्रेशर के संशोधन जो देरी को कम करते हैं और कार्यान्वयन को सरल बनाते हैं, उन्हें इम्प्रूविंग डिले और डिस्ट्रिब्यूटेड बैकप्रेशर के तहत नीचे वर्णित किया गया है। बैकप्रेशर रूटिंग का अध्ययन मुख्य रूप से एक सैद्धांतिक संदर्भ में किया गया है। व्यवहार में, तदर्थ वायरलेस नेटवर्क ने आम तौर पर सबसे छोटी पथ गणना या नेटवर्क बाढ़ के आधार पर वैकल्पिक मार्ग निर्धारण विधियों को लागू किया है, जैसे कि तदर्थ ऑन-डिमांड डिस्टेंस वेक्टर रूटिंग (ए. ओ. डी. वी.), भौगोलिक मार्ग निर्धारण और अत्यंत अवसरवादी मार्ग निर्धारण (एक्स. ओ. आर.)। हालांकि, बैकप्रेशर के गणितीय इष्टतम गुणों ने दक्षिणी कैलिफोर्निया विश्वविद्यालय और उत्तरी कैरोलिना राज्य विश्वविद्यालय में वायरलेस टेस्टबेड पर इसके उपयोग के हालिया प्रयोगात्मक प्रदर्शनों को प्रेरित किया है। मूल बैकप्रेशर एल्गोरिदम को टस्सीउलास और एफ्रेमिड्स द्वारा विकसित किया गया था। उन्होंने यादृच्छिक पैकेट आगमन और लिंक चयन विकल्पों के एक निश्चित सेट के साथ एक बहु-हॉप पैकेट रेडियो नेटवर्क पर विचार किया। उनके एल्गोरिदम में एक अधिकतम वजन लिंक चयन चरण और एक अंतर बैकलॉग रूटिंग चरण शामिल था। बैकप्रेशर से संबंधित एक एल्गोरिथ्म, जिसे बहु-वस्तु नेटवर्क प्रवाह की गणना के लिए डिज़ाइन किया गया था, अवेरबुच और लाइटन में विकसित किया गया था। बैकप्रेशर एल्गोरिदम को बाद में नीली, मोदियानो और रोहर्स द्वारा मोबाइल नेटवर्क के लिए शेड्यूलिंग का इलाज करने के लिए बढ़ाया गया था। बैकप्रेशर का गणितीय रूप से लियापुनोव ड्रिफ्ट के सिद्धांत के माध्यम से विश्लेषण किया जाता है, और नेटवर्क उपयोगिता अधिकतमकरण प्रदान करने के लिए प्रवाह नियंत्रण तंत्र के साथ संयुक्त रूप से उपयोग किया जा सकता है। (उपयोगिता अनुकूलन और दंड न्यूनतमकरण के साथ बैकप्रेशर भी देखें)। यह कैसे काम करता है बैकप्रेशर रूटिंग को निर्णय लेने के लिए डिज़ाइन किया गया है जो (मोटे तौर पर) नेटवर्क में कतार बैकलॉग के वर्गों के योग को एक टाइम स्लॉट से दूसरे में कम करता है। इस तकनीक के सटीक गणितीय विकास का वर्णन बाद के खंडों में किया गया है। यह खंड सामान्य नेटवर्क मॉडल और इस मॉडल के संबंध में बैकप्रेशर रूटिंग के संचालन का वर्णन करता है। मल्टी-हॉप कतार नेटवर्क मॉडल एन नोड्स के साथ एक मल्टी-हॉप नेटवर्क पर विचार करें (चित्र देखें। एन = 6) के साथ एक उदाहरण के लिए 1। नेटवर्क निर्धारित समय में काम करता है। प्रत्येक स्लॉट पर, नया डेटा नेटवर्क पर आ सकता है, और सभी डेटा को उसके उचित गंतव्य तक पहुँचाने के प्रयास में रूटिंग और ट्रांसमिशन शेड्यूलिंग निर्णय लिए जाते हैं। नोड के लिए नियत डेटा को कमोडिटी सी डेटा के रूप में लेबल किया जाना चाहिए। प्रत्येक नोड में डेटा को उसकी वस्तु के अनुसार संग्रहीत किया जाता है। और के लिए, नोड एन में वस्तु सी डेटा की वर्तमान राशि होने दें, जिसे कतार बैकलॉग भी कहा जाता है। एक नोड के अंदर कतार बैकलॉग का एक क्लोजअप चित्र में दिखाया गया है। 2. की इकाइयाँ समस्या के संदर्भ पर निर्भर करती हैं। उदाहरण के लिए, बैकलॉग पैकेटों की पूर्णांक इकाइयों को ले सकता है, जो उन मामलों में उपयोगी है जब डेटा को निश्चित लंबाई के पैकेटों में विभाजित किया जाता है। वैकल्पिक रूप से, यह बिट्स की वास्तविक मूल्यवान इकाइयाँ ले सकता है। यह माना जाता है कि सभी और सभी समय स्लॉट टी के लिए, क्योंकि कोई भी नोड अपने लिए नियत डेटा को संग्रहीत नहीं करता है। हर टाइम स्लॉट पर, नोड्स दूसरों को डेटा संचारित कर सकते हैं। एक नोड से दूसरे नोड में प्रेषित होने वाले डेटा को पहले नोड की कतार से हटा दिया जाता है और दूसरे की कतार में जोड़ा जाता है। जो डेटा अपने गंतव्य पर प्रेषित किया जाता है, उसे नेटवर्क से हटा दिया जाता है। डेटा नेटवर्क में बहिर्जात्रीय रूप से भी पहुंच सकता है, और इसे नए डेटा की मात्रा के रूप में परिभाषित किया जाता है जो स्लॉट टी पर नोड एन में आता है जिसे अंततः नोड सी में वितरित किया जाना चाहिए। स्लॉट टी पर लिंक (ए, बी) पर नेटवर्क द्वारा उपयोग की जाने वाली संचरण दर, डेटा की मात्रा का प्रतिनिधित्व करती है जो वर्तमान स्लॉट पर नोड ए से नोड बी में स्थानांतरित हो सकती है। माना संचरण दर मैट्रिक्स। इन संचरण दरों का चयन संभवतः समय-परिवर्तन विकल्पों के एक समूह के भीतर किया जाना चाहिए। विशेष रूप से, नेटवर्क में समय-भिन्न चैनल और नोड गतिशीलता हो सकती है, और यह हर स्थान पर इसकी संचरण क्षमताओं को प्रभावित कर सकता है। इसे मॉडल करने के लिए, एस (टी) नेटवर्क की टोपोलॉजी स्थिति का प्रतिनिधित्व करता है, जो संचरण को प्रभावित करने वाले स्लॉट टी पर नेटवर्क के गुणों को पकड़ता है। आइए टोपोलॉजी अवस्था एस (टी) के तहत उपलब्ध संचरण दर मैट्रिक्स विकल्पों के सेट का प्रतिनिधित्व करें। प्रत्येक स्लॉट टी, नेटवर्क नियंत्रक एस (टी) का निरीक्षण करता है और सेट के भीतर संचरण दरों का चयन करता है। प्रत्येक स्लॉट टी पर किस मैट्रिक्स का चयन करना है, इसका चुनाव अगले उपखंड में वर्णित है। यह समय-परिवर्तनशील नेटवर्क मॉडल पहली बार उस मामले के लिए विकसित किया गया था जब संचरण दर प्रत्येक स्लॉट टी को चैनल स्टेट मैट्रिक्स और एक बिजली आवंटन मैट्रिक्स के सामान्य कार्यों द्वारा निर्धारित किया गया था। मॉडल का उपयोग तब भी किया जा सकता है जब दरें अन्य नियंत्रण निर्णयों, जैसे सर्वर आवंटन, उप-बैंड चयन, कोडिंग प्रकार, आदि द्वारा निर्धारित की जाती हैं। यह मानता है कि समर्थन योग्य संचरण दरें ज्ञात हैं और संचरण में कोई त्रुटि नहीं है। बैकप्रेशर रूटिंग के विस्तारित सूत्रीकरण का उपयोग संभावित चैनल त्रुटियों वाले नेटवर्क के लिए किया जा सकता है, जिसमें वे नेटवर्क भी शामिल हैं जो बहु-प्राप्तकर्ता विविधता के माध्यम से वायरलेस प्रसारण लाभ का फायदा उठाते हैं। बैकप्रेशर नियंत्रण निर्णय प्रत्येक स्लॉट टी बैकप्रेशर नियंत्रक एस (टी) का निरीक्षण करता है और निम्नलिखित 3 चरणों का प्रदर्शन करता हैः सबसे पहले, प्रत्येक लिंक (ए, बी) के लिए, यह उपयोग करने के लिए एक इष्टतम वस्तु का चयन करता है। इसके बाद, यह निर्धारित करता है कि किस मैट्रिक्स का उपयोग करना है। अंत में, यह उस वस्तु की मात्रा को निर्धारित करता है जिसे यह लिंक (ए, बी) पर प्रसारित करेगा (अधिक से अधिक, लेकिन संभवतः कुछ मामलों में कम)। इष्टतम वस्तु का चयन प्रत्येक नोड अपने वर्तमान पड़ोसियों में अपने स्वयं के कतार बैकलॉग और बैकलॉग का निरीक्षण करता है। नोड ए का एक वर्तमान पड़ोसी एक नोड बी ऐसा है कि वर्तमान स्लॉट पर एक गैर-शून्य संचरण दर चुनना संभव है। इस प्रकार, पड़ोसियों को सेट द्वारा निर्धारित किया जाता है। चरम स्थिति में, एक नोड में पड़ोसियों के रूप में सभी एन-1 अन्य नोड हो सकते हैं। हालांकि, ऐसे सेटों का उपयोग करना आम है जो नोड्स के बीच संचरण को रोकते हैं जो एक निश्चित भौगोलिक दूरी से अधिक से अलग होते हैं, या जिनमें एक निश्चित सीमा से नीचे एक प्रचारित संकेत शक्ति होती है। इस प्रकार, पड़ोसियों की संख्या का एन-1 से बहुत कम होना विशिष्ट है। चित्र में उदाहरण। 1 लिंक कनेक्शन द्वारा पड़ोसियों को दर्शाता है, ताकि नोड 5 में पड़ोसी 4 और 6 हों। उदाहरण पड़ोसियों के बीच एक सममित संबंध का सुझाव देता है (ताकि यदि 5 4 का पड़ोसी है, तो 4 5 का पड़ोसी है), लेकिन सामान्य रूप से ऐसा होने की आवश्यकता नहीं है। किसी दिए गए नोड के पड़ोसियों का समूह आउटगोइंग लिंक के सेट को निर्धारित करता है जिसका उपयोग वर्तमान स्लॉट पर संचरण के लिए किया जा सकता है। प्रत्येक आउटगोइंग लिंक (ए, बी) के लिए, इष्टतम वस्तु को उस वस्तु के रूप में परिभाषित किया जाता है जो निम्नलिखित अंतर बैकलॉग मात्रा को अधिकतम करती हैः इष्टतम वस्तु चुनने में किसी भी संबंध को मनमाने ढंग से तोड़ा जाता है। एक उदाहरण चित्र में दिखाया गया है। 2. उदाहरण यह मानता है कि प्रत्येक कतार में वर्तमान में केवल 3 वस्तुएँ हैंः लाल, हरा और नीला, और इन्हें पैकेटों की पूर्णांक इकाइयों में मापा जाता है। निर्देशित लिंक (1,2) पर ध्यान केंद्रित करते हुए, अंतर बैकलॉग हैंः इसलिए, स्लॉट टी पर लिंक (1,2) पर भेजने के लिए इष्टतम वस्तु हरित वस्तु है। दूसरी ओर, स्लॉट टी पर रिवर्स लिंक (2,1) पर भेजने के लिए इष्टतम वस्तु नीली वस्तु है। एक बार प्रत्येक लिंक (ए, बी) के लिए इष्टतम वस्तुओं का निर्धारण हो जाने के बाद, नेटवर्क नियंत्रक निम्नलिखित भारों की गणना करता हैः वजन लिंक (ए, बी) के लिए इष्टतम वस्तु से जुड़े अंतर बैकलॉग का मूल्य है, जिसे अधिकतम 0 से जोड़ा जाता है। नियंत्रक तब संचरण दरों को निम्नलिखित अधिकतम-भार समस्या के समाधान के रूप में चुनता है (मनमाने ढंग से संबंधों को तोड़ना): अधिकतम-भार निर्णय के एक उदाहरण के रूप में, मान लीजिए कि वर्तमान स्लॉट टी पर, 6 नोड नेटवर्क के प्रत्येक लिंक पर अंतर बैकलॉग दिए गए लिंक भार की ओर ले जाते हैंः जबकि सेट में संभावित संचरण दर मैट्रिक्स की एक अनगिनत अनंत संख्या हो सकती है, सरलता के लिए मान लीजिए कि वर्तमान टोपोलॉजी स्थिति केवल 4 संभावित विकल्पों को स्वीकार करती हैः वर्तमान टोपोलॉजी स्थिति एस (टी) के तहत 4 संभावित संचरण दर चयनों का चित्रण। विकल्प (ए) एकल लिंक (1,5) को संचरण दर के साथ सक्रिय करता है। अन्य सभी विकल्प दो लिंक का उपयोग करते हैं, जिसमें प्रत्येक सक्रिय लिंक पर 1 की संचरण दर होती है। इन चार संभावनाओं को मैट्रिक्स के रूप में दर्शाया गया हैः ध्यान दें कि नोड 6 इनमें से किसी भी संभावना के तहत न तो भेज सकता है और न ही प्राप्त कर सकता है। यह उत्पन्न हो सकता है क्योंकि नोड 6 वर्तमान में संचार सीमा से बाहर है। 4 संभावनाओं में से प्रत्येक के लिए दरों का भारित योग हैः विकल्प (ए): विकल्प (बी): विकल्प (ग): विकल्प (घ): चूंकि 12 के अधिकतम वजन के लिए एक टाई है, इसलिए नेटवर्क नियंत्रक किसी भी विकल्प या विकल्प को चुनकर मनमाने ढंग से टाई को तोड़ सकता है। रूटिंग चर को अंतिम रूप देना मान लीजिए कि अब प्रत्येक कड़ी के लिए इष्टतम वस्तुएं निर्धारित की गई हैं, और संचरण दर भी निर्धारित की गई हैं। यदि किसी दिए गए लिंक (ए, बी) पर इष्टतम वस्तु के लिए अंतर बैकलॉग नकारात्मक है, तो वर्तमान स्लॉट पर इस लिंक पर कोई डेटा स्थानांतरित नहीं किया जाता है। अन्यथा, नेटवर्क इस लिंक पर वस्तु डेटा की इकाइयाँ भेजने की पेशकश करता है। यह प्रत्येक लिंक (ए, बी) और प्रत्येक वस्तु सी के लिए रूटिंग चर को परिभाषित करके किया जाता है, जहांः का मूल्य स्लॉट टी पर लिंक (ए, बी) पर वस्तु सी डेटा को दी गई संचरण दर को दर्शाता है। हालाँकि, नोड्स में उनके सभी आउटगोइंग लिंक पर प्रस्तावित दरों पर संचरण का समर्थन करने के लिए एक निश्चित वस्तु पर्याप्त नहीं हो सकती है। यह नोड एन और कमोडिटी सी के लिए स्लॉट टी पर उत्पन्न होता है यदिः इस मामले में, सभी डेटा भेजे जाते हैं, और प्रस्तावित दरों के अप्रयुक्त भागों को भरने के लिए शून्य डेटा का उपयोग किया जाता है, वास्तविक डेटा और शून्य डेटा को संबंधित आउटगोइंग लिंक पर मनमाने ढंग से आवंटित किया जाता है (प्रस्तावित दरों के अनुसार)। इसे कतार के नीचे की स्थिति कहा जाता है। इस तरह के अंडरफ्लो नेटवर्क के थ्रूपुट या स्थिरता गुणों को प्रभावित नहीं करते हैं। सहज रूप से, ऐसा इसलिए है क्योंकि कम प्रवाह केवल तभी उत्पन्न होता है जब संचारित करने वाले नोड में कम मात्रा में बैकलॉग होता है, जिसका अर्थ है कि नोड को अस्थिरता का खतरा नहीं है। विलंब में सुधार बैकप्रेशर एल्गोरिदम किसी भी पूर्व-निर्दिष्ट पथ का उपयोग नहीं करता है। पथ गतिशील रूप से सीखे जाते हैं, और विभिन्न पैकेटों के लिए अलग-अलग हो सकते हैं। देरी बहुत बड़ी हो सकती है, विशेष रूप से जब सिस्टम को हल्के से लोड किया जाता है ताकि गंतव्य की ओर डेटा को धकेलने के लिए पर्याप्त दबाव न हो। उदाहरण के लिए, मान लीजिए कि एक पैकेट नेटवर्क में प्रवेश करता है, और कुछ भी कभी प्रवेश नहीं करता है। यह पैकेट नेटवर्क के माध्यम से एक पागल चलना ले सकता है और कभी भी अपने गंतव्य पर नहीं पहुंच सकता है क्योंकि कोई दबाव प्रवणता नहीं बनती है। यह थ्रूपुट इष्टतमता या बैकप्रेशर के स्थिरता गुणों का खंडन नहीं करता है क्योंकि नेटवर्क में किसी भी समय अधिकतम एक पैकेट होता है और इसलिए यह मामूली रूप से स्थिर होता है (0 की डिलीवरी दर प्राप्त करना, आगमन दर के बराबर)। पूर्व-निर्दिष्ट पथों के एक समूह पर बैकप्रेशर को लागू करना भी संभव है। यह क्षमता क्षेत्र को सीमित कर सकता है, लेकिन ऑर्डर डिलीवरी और देरी में सुधार कर सकता है। क्षमता क्षेत्र को प्रभावित किए बिना देरी में सुधार करने का एक अन्य तरीका एक उन्नत संस्करण का उपयोग करना है जो पूर्वाग्रहों को वांछित दिशाओं की ओर जोड़ता है। इस तरह के पूर्वाग्रह के अनुकरण ने महत्वपूर्ण विलंब सुधार दिखाए हैं। ध्यान दें कि बैकप्रेशर के लिए कतारों पर फर्स्ट-इन-फर्स्ट-आउट (एफआईएफओ) सेवा की आवश्यकता नहीं होती है। यह देखा गया है कि लास्ट-इन-फर्स्ट-आउट (एल. आई. एफ. ओ.) सेवा थ्रूपुट को प्रभावित किए बिना, अधिकांश पैकेटों के लिए देरी में नाटकीय रूप से सुधार कर सकती है। वितरित बैकप्रेशर ध्यान दें कि एक बार संचरण दरों का चयन हो जाने के बाद, मार्ग निर्धारण निर्णय चर की गणना एक सरल वितरित तरीके से की जा सकती है, जहां प्रत्येक नोड को केवल अपने और अपने पड़ोसियों के बीच कतार बैकलॉग अंतर के ज्ञान की आवश्यकता होती है। हालांकि, संचरण दरों के चयन के लिए ईक्यूएस में अधिकतम वजन की समस्या के समाधान की आवश्यकता होती है। (1)-(2)। विशेष मामले में जब चैनल ऑर्थोगोनल होते हैं, तो एल्गोरिथ्म का एक प्राकृतिक वितरित कार्यान्वयन होता है और प्रत्येक नोड पर अलग-अलग निर्णयों तक कम हो जाता है। हालांकि, अधिकतम वजन की समस्या अंतर-चैनल हस्तक्षेप वाले नेटवर्क के लिए एक केंद्रीकृत नियंत्रण समस्या है। केंद्रीकृत तरीके से भी इसे हल करना बहुत मुश्किल हो सकता है। संकेत-से-शोर-प्लस-हस्तक्षेप अनुपात (एस. आई. एन. आर.) द्वारा निर्धारित लिंक दरों के साथ हस्तक्षेप नेटवर्क के लिए एक वितरित दृष्टिकोण यादृच्छिककरण का उपयोग करके किया जा सकता है। प्रत्येक नोड यादृच्छिक रूप से प्रत्येक स्लॉट टी को संचारित करने का निर्णय लेता है (एक "शून्य" पैकेट को संचारित करना यदि वर्तमान में उसके पास भेजने के लिए एक पैकेट नहीं है)। वास्तविक संचरण दर, और भेजने के लिए संबंधित वास्तविक पैकेट, 2-चरणीय हाथ मिलाने द्वारा निर्धारित किए जाते हैंः पहले चरण में, यादृच्छिक रूप से चयनित ट्रांसमीटर नोड्स एक वास्तविक संचरण के समानुपाती संकेत शक्ति के साथ एक पायलट संकेत भेजते हैं। दूसरे चरण में, सभी संभावित रिसीवर नोड्स परिणामी हस्तक्षेप को मापते हैं और उस जानकारी को ट्रांसमीटरों को वापस भेजते हैं। सभी आउटगोइंग लिंक (एन, बी) के लिए एस. आई. एन. आर. स्तर तब सभी नोड्स एन के लिए ज्ञात होते हैं, और प्रत्येक नोड एन इस जानकारी के आधार पर इसके और चर का निर्णय ले सकता है। परिणामी थ्रूपुट आवश्यक रूप से इष्टतम नहीं है। हालांकि, यादृच्छिक संचरण प्रक्रिया को चैनल अवस्था प्रक्रिया के एक हिस्से के रूप में देखा जा सकता है (बशर्ते कि नल पैकेटों को अंडरफ्लो के मामलों में भेजा जाता है, ताकि चैनल अवस्था प्रक्रिया पिछले निर्णयों पर निर्भर न हो)। इसलिए, इस वितरित कार्यान्वयन का परिणामी थ्रूपुट सभी रूटिंग और शेड्यूलिंग एल्गोरिदम के वर्ग पर इष्टतम है जो इस तरह के यादृच्छिक प्रसारण का उपयोग करते हैं। वैकल्पिक वितरित कार्यान्वयनों को मोटे तौर पर दो वर्गों में समूहीकृत किया जा सकता हैः प्रथम श्रेणी के एल्गोरिदम अधिकतम वजन की समस्या के लिए निरंतर गुणक कारक सन्निकटन पर विचार करते हैं, और स्थिर-कारक थ्रूपुट परिणाम देते हैं। एल्गोरिदम का दूसरा वर्ग समय के साथ अधिकतम वजन की समस्या के समाधान को अद्यतन करने के आधार पर अधिकतम वजन की समस्या के योगात्मक सन्निकटन पर विचार करता है। इस द्वितीय श्रेणी में एल्गोरिदम को स्थिर चैनल स्थितियों और लंबे (अक्सर गैर-बहुपद) अभिसरण समय की आवश्यकता होती है, हालांकि वे उचित धारणाओं के तहत अधिकतम थ्रूपुट प्राप्त कर सकते हैं। अतिरिक्त सन्निकटन अक्सर बैकप्रेशर की इष्टतमता साबित करने के लिए उपयोगी होते हैं जब पुरानी कतार बैकलॉग जानकारी के साथ लागू किया जाता है (नीली पाठ का अभ्यास 4.10 देखें)। ल्यपुनोव ड्रिफ्ट के माध्यम से गणितीय निर्माण यह खंड दर्शाता है कि कैसे बैकप्रेशर एल्गोरिथ्म एक स्लॉट से दूसरे स्लॉट में कतार बैकलॉग के वर्गों के योग में परिवर्तन पर एक सीमा को लालच से कम करने के प्राकृतिक परिणाम के रूप में उत्पन्न होता है। निर्णय बाधाओं और कतार अद्यतन समीकरण को नियंत्रित करें एन नोड्स के साथ एक बहु-हॉप नेटवर्क पर विचार करें, जैसा कि उपरोक्त खंड में वर्णित है। प्रत्येक स्लॉट टी, नेटवर्क नियंत्रक टोपोलॉजी अवस्था एस (टी) का निरीक्षण करता है और निम्नलिखित बाधाओं के अधीन संचरण दरों और रूटिंग चरों का चयन करता हैः एक बार जब ये रूटिंग चर निर्धारित हो जाते हैं, तो प्रसारण किए जाते हैं (यदि आवश्यक हो तो निष्क्रिय भरने का उपयोग करके), और परिणामी कतार बैकलॉग निम्नलिखित को संतुष्ट करते हैंः नई वस्तु सी डेटा की यादृच्छिक मात्रा कहां है जो स्लॉट टी पर नोड एन पर बाहर से आती है, और क्या स्लॉट टी पर लिंक (एन, बी) पर वस्तु सी ट्रैफिक को आवंटित संचरण दर है। ध्यान दें कि वस्तु सी डेटा की मात्रा से अधिक हो सकता है जो वास्तव में स्लॉट टी पर लिंक (ए, बी) पर प्रेषित होता है। ऐसा इसलिए है क्योंकि नोड एन में पर्याप्त बैकलॉग नहीं हो सकता है। इसी कारण से, ईक्यू। (6) समानता के बजाय एक असमानता है, क्योंकि स्लॉट टी पर वस्तु सी से नोड एन के वास्तविक अंतर्जात आगमन से अधिक हो सकती है। ईक्यू की एक महत्वपूर्ण विशेषता है। (6) यह है कि यह तब भी लागू होता है जब निर्णय चर को कतार बैकलॉग से स्वतंत्र रूप से चुना जाता है। यह माना जाता है कि सभी स्लॉट टी और सभी के लिए, क्योंकि कोई भी कतार अपने लिए नियत डेटा को संग्रहीत नहीं करती है। लियापुनोव ड्रिफ्ट वर्तमान कतार बैकलॉग के मैट्रिक्स के रूप में परिभाषित करें। निम्नलिखित गैर-नकारात्मक फलन को परिभाषित करें, जिसे लियापुनोव फलन कहा जाता हैः यह कतार बैकलॉग के वर्गों का योग है (बाद के विश्लेषण में सुविधा के लिए केवल 1/2 से गुणा किया जाता है)। उपरोक्त योग सभी n, c का योग करने के समान है क्योंकि सभी और सभी स्लॉट t के लिए सशर्त लियापुनोव बहाव को परिभाषित किया गया हैः ध्यान दें कि निम्नलिखित असमानता सभी के लिए है,: कतार अद्यतन समीकरण (Eq. (6)) और उपरोक्त असमानता का उपयोग करते हुए, यह दिखाना मुश्किल नहीं है कि सभी स्लॉट टी के लिए और किसी भी एल्गोरिथ्म के तहत संचरण और मार्ग परिवर्तनशील चुनने के लिए औरः जहां बी एक परिमित स्थिरांक है जो आगमन के दूसरे क्षणों और संचरण दरों के अधिकतम संभव दूसरे क्षणों पर निर्भर करता है। योग को बदलकर ड्रिफ्ट बाउंड को कम करना बैकप्रेशर एल्गोरिथ्म को प्रत्येक स्लॉट टी का निरीक्षण करने और ड्रिफ्ट बाउंड Eq के दाहिने हाथ की ओर को चुनने और कम करने के लिए डिज़ाइन किया गया है। (7)। क्योंकि बी एक स्थिरांक है और स्थिरांक हैं, यह अधिकतम करने के बराबर हैः जहां सीमित राशियों को अधिकतम निर्णय को प्रकाशित करने के लिए अपेक्षाओं के माध्यम से आगे बढ़ाया गया है। अवसरवादी रूप से किसी अपेक्षा को अधिकतम करने के सिद्धांत द्वारा, उपरोक्त अपेक्षा को उसके अंदर के कार्य को अधिकतम करके अधिकतम किया जाता है (अवलोकन को देखते हुए)। इस प्रकार, कोई व्यक्ति Eqs चुनता है और बाधाओं के अधीन होता है। (3)-(5) अधिकतम करनाः यह तुरंत स्पष्ट नहीं है कि कौन से निर्णय उपरोक्त को अधिकतम करते हैं। इसे राशियों को बदलकर प्रकाशित किया जा सकता है। वास्तव में, उपरोक्त अभिव्यक्ति नीचे के समान हैः भार को नोड ए और बी के बीच वस्तु सी का वर्तमान अंतर बैकलॉग कहा जाता है। विचार निर्णय चर का चयन करना है ताकि उपरोक्त भारित राशि को अधिकतम किया जा सके, जहां भार अंतर बैकलॉग हैं। सहज रूप से, इसका मतलब है कि बड़े अंतर बैकलॉग की दिशा में बड़ी दरों का आवंटन करना। स्पष्ट रूप से किसी को कभी भी चुनना चाहिए। इसके अलावा, एक विशेष लिंक के लिए दिए जाने पर, यह दिखाना मुश्किल नहीं है कि इष्टतम चयन, Eqs के अधीन हैं। (3)-(5), निम्नलिखित रूप में निर्धारित किए जाते हैंः पहले उस वस्तु को ढूंढें जो लिंक (ए, बी) के लिए अंतर बैकलॉग को अधिकतम करती है। यदि लिंक (ए, बी) के लिए अधिकतम अंतर बैकलॉग नकारात्मक है, तो लिंक (ए, बी) पर सभी वस्तुओं के लिए असाइन करें। अन्यथा, इस लिंक पर वस्तु के लिए पूर्ण लिंक दर और अन्य सभी वस्तुओं के लिए शून्य दर आवंटित करें। इस विकल्प के साथ, यह इस प्रकार हैः स्लॉट टी (अधिकतम 0 के साथ) पर लिंक (ए, बी) के लिए इष्टतम वस्तु का अंतर बैकलॉग कहां हैः यह केवल चुनने के लिए रहता है। यह निम्नलिखित को हल करके किया जाता हैः उपरोक्त समस्या Eqs में अधिकतम वजन की समस्या के समान है। (1)-(2)। बैकप्रेशर एल्गोरिदम के लिए अधिकतम वजन निर्णयों का उपयोग करता है, और फिर ऊपर वर्णित अधिकतम अंतर बैकलॉग के माध्यम से रूटिंग चर का चयन करता है। बैकप्रेशर एल्गोरिदम का एक उल्लेखनीय गुण यह है कि यह केवल देखे गए टोपोलॉजी स्टेट एस (टी) और उस स्लॉट के लिए कतार बैकलॉग के आधार पर हर स्लॉट टी को लालच से कार्य करता है। इस प्रकार, इसे आगमन दर या स्थलविज्ञान स्थिति संभावनाओं के ज्ञान की आवश्यकता नहीं है। प्रदर्शन विश्लेषण यह खंड बैकप्रेशर एल्गोरिदम की थ्रूपुट इष्टतमता को साबित करता है। सरलता के लिए, वह परिदृश्य जहाँ घटनाएँ स्वतंत्र और समान रूप से वितरित होती हैं (अर्थात) ओवर स्लॉट पर विचार किया जाता है, हालांकि एक ही एल्गोरिथ्म को non-i.i.d में काम करते हुए दिखाया जा सकता है। परिदृश्य (नीचे Non-i.i.d के तहत देखें। संचालन और सार्वभौमिक समय-निर्धारण)। गतिशील आगमन स्लॉट टी पर बहिर्जात आगमन का मैट्रिक्स होना चाहिए। मान लीजिए कि यह मैट्रिक्स स्वतंत्र है और समान रूप से वितरित है (अर्थात) सीमित दूसरे क्षणों के साथ और साधनों के साथः यह माना जाता है कि सभी के लिए, जैसा कि कोई डेटा नहीं आता है जो अपने लिए नियत है। इस प्रकार, आगमन दरों का मैट्रिक्स गैर-ऋणात्मक वास्तविक संख्याओं का एक मैट्रिक्स है, जिसमें विकर्ण पर शून्य होते हैं। नेटवर्क क्षमता क्षेत्र मान लीजिए कि स्थलविज्ञान अवस्था एस (टी) अर्थात डी है। संभाव्यताओं के साथ स्लॉट पर (यदि एस (टी) वास्तविक-मूल्यवान प्रविष्टियों के साथ वैक्टर के एक अनगिनत अनंत सेट में मान लेता है, तो एक संभाव्यता वितरण है, न कि एक संभाव्यता द्रव्यमान फलन)। नेटवर्क के लिए एक सामान्य एल्गोरिथ्म प्रत्येक स्लॉट टी में एस (टी) का निरीक्षण करता है और ईक्यूएस में बाधाओं के अनुसार संचरण दर और रूटिंग चर चुनता है। (3)-(5)। नेटवर्क क्षमता क्षेत्र सभी आगमन दर मैट्रिक्स के सेट का समापन है जिसके लिए एक एल्गोरिथ्म मौजूद है जो नेटवर्क को स्थिर करता है। सभी कतारों की स्थिरता का तात्पर्य है कि नेटवर्क में यातायात की कुल इनपुट दर अपने गंतव्य पर वितरित डेटा की कुल दर के समान है। यह दिखाया जा सकता है कि क्षमता क्षेत्र में किसी भी आगमन दर मैट्रिक्स के लिए, एक स्थिर और यादृच्छिक एल्गोरिथ्म है जो केवल एस (टी) पर आधारित निर्णय चर और प्रत्येक स्लॉट टी का चयन करता है (और इसलिए कतार बैकलॉग से स्वतंत्र रूप से) जो सभी के लिए निम्नलिखित परिणाम देता हैः ऐसा स्थिर और यादृच्छिक एल्गोरिथ्म जो केवल एस (टी) पर निर्णय लेता है, उसे एस-ओनली एल्गोरिथ्म कहा जाता है। यह मान लेना अक्सर उपयोगी होता है कि यह आंतरिक है, ताकि एक ऐसा हो कि, जहाँ 1 यदि है, और शून्य अन्य है। उस स्थिति में, एक एस-ओनली एल्गोरिथ्म है जो सभी के लिए निम्नलिखित देता हैः एक तकनीकी आवश्यकता के रूप में, यह माना जाता है कि संचरण दरों के दूसरे क्षण इन दरों को चुनने के लिए किसी भी एल्गोरिथ्म के तहत सीमित हैं। यह मामूली रूप से तब लागू होता है जब एक सीमित अधिकतम दर होती है। एस-ओनली एल्गोरिदम से तुलना करना क्योंकि बैकप्रेशर एल्गोरिदम प्रत्येक स्लॉट टी का निरीक्षण करता है और एस (टी) निर्णय चुनता है और ड्रिफ्ट बाउंड ईक्यू के दाहिने हाथ की ओर को कम करता है। (7), हमारे पासः Eqs को संतुष्ट करने वाले कोई भी वैकल्पिक निर्णय कहाँ और कहाँ हैं। (3)-(5), यादृच्छिक निर्णयों सहित। अब मान लीजिए। फिर एक एस-ओनली एल्गोरिथ्म मौजूद है जो ईक्यू को संतुष्ट करता है। (8)। इसे Eq के दाहिने हाथ की ओर प्लग करना। (10) और यह ध्यान में रखते हुए कि इस एस-ओनली एल्गोरिथ्म के तहत दी गई सशर्त अपेक्षा बिना शर्त अपेक्षा के समान है (क्योंकि एस (टी) यानी आईडी है। स्लॉट पर, और एस-ओनली एल्गोरिथ्म वर्तमान कतार बैकलॉग से स्वतंत्र है) उपजः इस प्रकार, एक द्विघात लियापुनोव फ़ंक्शन का बहाव सभी स्लॉट टी के लिए एक स्थिर बी से कम या बराबर है। यह तथ्य, इस धारणा के साथ कि कतार आगमन ने दूसरे क्षणों को सीमित किया है, सभी नेटवर्क कतारों के लिए निम्नलिखित का संकेत देता हैः औसत कतार के आकार की मजबूत समझ के लिए, कोई यह मान सकता है कि आगमन दर आंतरिक है, इसलिए एक ऐसा Eq है। (9) कुछ वैकल्पिक एस-केवल एल्गोरिदम के लिए लागू होता है। Eq को प्लग करना। (9) Eq के दाहिने हाथ की ओर। (10) उपजः जिससे कोई तुरंत प्राप्त करता है (देखें): यह औसत कतार का आकार सीमा बढ़ती जाती है क्योंकि क्षमता क्षेत्र की सीमा की दूरी शून्य हो जाती है। यह आगमन दर और सेवा दर के साथ एकल एम/एम/1 कतार के समान गुणात्मक प्रदर्शन है, जहां औसत कतार का आकार आनुपातिक है। उपरोक्त सूत्रीकरण Non-i.i.d का विस्तार। संचालन और सार्वभौमिक समय-निर्धारण उपरोक्त विश्लेषण मान लिया जाता है अर्थात। सादगी के लिए गुण। हालांकि, उसी बैकप्रेशर एल्गोरिदम को non-i.i.d में मजबूती से काम करते हुए दिखाया जा सकता है। परिस्थितियाँ। जब आगमन प्रक्रियाएँ और टोपोलॉजी अवस्थाएँ एर्गोडिक होती हैं, लेकिन जरूरी नहीं कि वे ए. डी. हों, तो बैकप्रेशर तब भी प्रणाली को स्थिर करता है। अधिक सामान्य रूप से, एक सार्वभौमिक समय निर्धारण दृष्टिकोण का उपयोग करते हुए, इसे मनमाने ढंग से (संभवतः गैर-एर्गोडिक) नमूना पथों के लिए स्थिरता और इष्टतम गुण प्रदान करने के लिए दिखाया गया है। उपयोगिता अनुकूलन और पेनल्टी न्यूनतमकरण के साथ बैकप्रेशर को ड्रिफ्ट-प्लस-पेनल्टी तकनीक के माध्यम से प्रवाह नियंत्रण के साथ संयोजन में काम करने के लिए दिखाया गया है। यह तकनीक लालच से प्रवाह और भारित दंड अभिव्यक्ति के योग को अधिकतम करती है। पेनल्टी को एक पैरामीटर V द्वारा भारित किया जाता है जो एक प्रदर्शन ट्रेडऑफ़ निर्धारित करता है। यह तकनीक सुनिश्चित करती है कि थ्रूपुट उपयोगिता इष्टतमता के ओ (1/वी) के भीतर हो जबकि औसत देरी ओ (वी) हो। इस प्रकार, उपयोगिता को मनमाने ढंग से इष्टतमता के करीब धकेल दिया जा सकता है, औसत देरी में एक संबंधित व्यापार के साथ। समान गुणों को औसत शक्ति न्यूनीकरण और अधिक सामान्य नेटवर्क विशेषताओं के अनुकूलन के लिए दिखाया जा सकता है। नेटवर्क उपयोगिता को अधिकतम करते हुए कतारों को स्थिर करने के लिए वैकल्पिक एल्गोरिदम को द्रव मॉडल विश्लेषण, संयुक्त द्रव विश्लेषण और लैग्रेंज गुणक विश्लेषण, उत्तल अनुकूलन और यादृच्छिक प्रवणता का उपयोग करके विकसित किया गया है। ये दृष्टिकोण ओ (1/वी), ओ (वी) उपयोगिता-विलंब परिणाम प्रदान नहीं करते हैं। ए. ओ. डी. वी. डाइवर्सिटी बैकप्रेशर रूटिंग (डी. आई. वी. बी. ए. आर.) ड्रिफ्ट प्लस पेनल्टी एक्स. ओ. आर. जियोग्राफिक रूटिंग एडहॉक रूटिंग प्रोटोकॉल की सूची लियापुनोव अनुकूलन संदर्भ प्राथमिक स्रोत एल. टास्सियुलास और ए. एफ्रेमिड्स, "मल्टीहॉप रेडियो नेटवर्क में अधिकतम थ्रूपुट के लिए बाधित कतार प्रणाली और समय निर्धारण नीतियों के स्थिरता गुण", स्वचालित नियंत्रण पर आई. ई. ई. ई. लेनदेन, वॉल्यूम। 37, नहीं। 12, पीपी। 1936-1948, दिसंबर 1992। एल. जॉर्जियडिस, एम. जे. नीली, और एल. टस्सीउलास, "रिसोर्स एलोकेशन एंड क्रॉस-लेयर कंट्रोल इन वायरलेस नेटवर्क्स", फाउंडेशन एंड ट्रेंड्स इन नेटवर्किंग, वॉल्यूम। 1, नहीं। 1, पीपी। 1-149,2006। एम. जे. नीली। संचार और कतार प्रणाली के अनुप्रयोग के साथ यादृच्छिक नेटवर्क अनुकूलन, "मॉर्गन और क्लेपूल, 2010। नेटवर्किंग एल्गोरिदम कतार सिद्धांत रूटिंग एल्गोरिदम