बैकप्रेशर रूटिंग: Difference between revisions

Latest revision as of 11:41, 3 July 2023

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

परिचय

पश्चदाब परिसंचरण संकुलन प्रवणता का उपयोग करके बहुपद नेटवर्क पर गतिकत: ट्रैफ़िक के परिसंचरण के लिए एक कलनविधि है। कलनविधि वायरलेस संचार नेटवर्क पर प्रयुक्त किया जा सकता है, जिसमें वायरलेस सेंसर नेटवर्क, मोबाइल एडहॉक नेटवर्क (एमएएनईटीएस) और वायरलेस और वायरलाइन घटकों के साथ विषमांगी जालक्रम सम्मिलित हैं।^[2]^[3]

पश्चदाब सिद्धांतों को अन्य क्षेत्रों जैसे उत्पाद संयोजन तंत्र और प्रसंस्करण नेटवर्क के अध्ययन में भी प्रयुक्त किया जा सकता है।^[4] यह लेख संचार नेटवर्क पर केंद्रित है, जहां विविध डाटा प्रवाह से पैकेट प्राप्त किए जाते हैं और उन्हें उपयुक्त गंतव्यों तक वितरण किया जाना चाहिए। पश्चदाब कलनविधि निर्धारित समय में संचालित होता है। प्रत्येक निर्धारित समय में यह डेटा को उन दिशाओं में संचारित करने का प्रयास करता है जो निकटवर्ती बिंदुओं के मध्य अवकल बैकलॉग को अधिकतम करते हैं। यह उसी प्रकार है जिस प्रकार दबाव प्रवणताओं के माध्यम से पाइपों के एक नेटवर्क के माध्यम से जल प्रवाहित होता है। यद्यपि, पश्चदाब कलनविधि को बहु-पण्य नेटवर्क (जहां विभिन्न पैकेट के विभिन्न गंतव्य हो सकते हैं) तथा उन नेटवर्क पर प्रयुक्त किया जा सकता है जहां संचरण दरों को विकल्पों के एक समुच्चय (संभवतः समय-भिन्न) से चयन किया जा सकता है। पश्चदाब कलनविधि की आकर्षक विशेषताएं हैं: (i) यह अधिकतम नेटवर्क प्रवाह क्षमता की ओर ले जाता है, (ii) यह समय-भिन्न नेटवर्क स्थितियों के लिए संभवतः सुदृढ़ है, (iii) इसे ट्रैफ़िक आगमन दर या चैनल स्थिति की संभावनाओं अनभिज्ञ होते हुए भी परिपालित किया जा सकता है। यद्यपि, कलनविधि अधिक विलंब क्रमादेशन कर सकता है तथा हस्तक्षेप वाले नेटवर्क में सटीक रूप से परिपालित करना कठिन हो सकता है। पश्चदाब के संशोधन जो विलंब को क्षीण करें और परिपालन को सरल बनाएं, वे विलंब में सुधार और वितरित पश्चदाब के अंतर्गत वर्णित हैं।

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

उत्पत्ति

मूल पश्चदाब कलनविधि को टैसियुलास और एफ़्रेमाइड्स द्वारा विकसित किया गया था।^[2]उन्होंने यादृच्छिक पैकेट आगमन और लिंक चयन विकल्पों के एक निश्चित समुच्चय के साथ बहुपद पैकेट रेडियो नेटवर्क पर विचार किया। उनके कलनविधि में अधिकतम-भार लिंक चयन अवस्था और अंतरात्मक संचित कार्य परिसंचरण चरण सम्मिलित थे। अवरबच और लैटों में बहु-पण्य नेटवर्क प्रवाह की गणना के लिए अभिकल्पित पश्चदाब से संबंधित कलनविधि विकसित किया गया था। ^[8]तत्पश्चात् नीली, मोदियानो और रोहर्स द्वारा पश्चदाब कलनविधि का विस्तार किया गया जिससे कि मोबाइल नेटवर्क के लिए अनुसूचीयन का विवेचन किया जा सके।^[9] लायपुनोव बहाव के सिद्धांत के माध्यम से पश्चदाब का गणितीय विश्लेषण किया जाता है और नेटवर्क उपयोगिता अधिकतमकरण प्रदान करने के लिए प्रवाह नियंत्रण तंत्र के साथ संयुक्त रूप से उपयोग किया जा सकता है। (उपयोगिता इष्टमीकरण और दंड न्यूनीकरण के साथ पश्चदाब भी देखें )।^[10]^[11]^[3]^[12]^[13]

यह कैसे काम करता है

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

बहुपद पंक्तियन नेटवर्क मॉडल

चित्र संख्या 1: एक 6-बिंदु बहु प्लुति नेटवर्क। बिंदुओं के मध्य के तीर वर्तमान निकटवर्तियों को दर्शाते हैं।

N बिंदु् के साथ बहुपद नेटवर्क पर विचार करें (N = 6 के साथ उदाहरण के लिए चित्र संख्या 1 देखें )।

नेटवर्क निर्धारित समय $t\in \{0,1,2,\ldots \}$ में संचालित होता है। प्रत्येक व्याकरणिक स्थान पर, नया डेटा नेटवर्क में आ सकता है और सभी डेटा को उसके उचित गंतव्य तक वितरण करने के प्रयास में परिसंचरण और संचारण अनुसूचीयन हेतु निर्णय लिए जाते हैं। मान लें बिंदु $c\in \{1,\dots ,N\}$ के लिए नियत डेटा पण्य c डेटा के रूप में अंकित किया गया है। प्रत्येक बिंदु में डेटा को उसके पण्य के अनुसार संग्रहित किया जाता है। $n\in \{1,\ldots ,N\}$ और $c\in \{1,\ldots ,N\}$ के लिए, मान लें $Q_{n}^{(c)}(t)$ बिंदु n में पण्य c डेटा की वर्तमान मात्रा है, जिसे पंक्तिबद्ध संचित कार्य भी कहा जाता है। एक बिंदु के भीतर क्यू बैकलॉग का निकट चित्रण चित्र 2 में दर्शाया गया है। $Q_{n}^{(c)}(t)$ की इकाइयाँ समस्या के संदर्भ पर निर्भर करता है। उदाहरण के लिए, संचित कार्य पैकेट की पूर्णांक इकाइयाँ ले सकता है, जो उन स्थितियों में उपयोगी होता है जब डेटा को निश्चित लंबाई के पैकेट में विभाजित किया जाता है। वैकल्पिक रूप से, यह बिट्स की वास्तविक मूल्य इकाइयाँ ले सकता है। यह अनुमानित किया गया है कि सभी $c\in \{1,\ldots ,N\}$ और सभी समयावधि t के लिए $Q_{c}^{(c)}(t)=0$ है, क्योंकि कोई भी बिंदु स्वयं के लिए निर्धारित डेटा संग्रहीत नहीं करता। प्रत्येक समयावधि में, बिंदु अन्य को डेटा संचारित कर सकते हैं। डेटा जो एक बिंदु से अन्य में प्रेषित होता है, उसे प्रथम बिंदु की पंक्तिबद्ध से हटा दिया जाता है और द्वितीय बिंदु की पंक्तिबद्ध में संयुक्त किया जाता है। अपने गंतव्य तक संचारित होने वाले डेटा को नेटवर्क से हटा दिया जाता है। डेटा नेटवर्क में बाह्यतः रूप से आगमन भी कर सकता है, और $A_{n}^{(c)}(t)$ को व्याकरणिक स्थान t पर बिंदु n में आगन्तुक नए डेटा की मात्रा के रूप में परिभाषित किया गया है जिसे अंततः बिंदु c को वितरित किया जाना चाहिए।

मान लें $\mu _{ab}(t)$ व्याकरणिक स्थान t पर लिंक (a,b) पर नेटवर्क द्वारा उपयोग की जाने वाली संचारण दर है, जो वर्तमान व्याकरणिक स्थान पर बिंदु a से बिंदु b में स्थानांतरित किए जा सकने वाले डेटा की मात्रा का प्रतिनिधित्व करती है। मान लें $(\mu _{ab}(t))$ संचरण दर मैट्रिक्स है। इन संचरण दरों को संभवतः समय-भिन्न विकल्पों के समुच्चय के भीतर चयन किया जाना चाहिए। विशेष रूप से, नेटवर्क में समय-भिन्न चैनल और बिंदु गतिशीलता हो सकती है, और यह प्रत्येक व्याकरणिक स्थान की संचरण क्षमताओं को प्रभावित कर सकती है। इसे मॉडल करने के लिए, मान लें S(t) नेटवर्क की सांस्थितिकी स्थिति का प्रतिनिधित्व करता है, जो संचरण को प्रभावित करने हेतु व्याकरणिक स्थान t पर नेटवर्क के गुणधर्मों को प्रग्रहण करें। मान लें $\Gamma _{S(t)}$ सांस्थितिकी स्थिति S(t) के अंतर्गत उपलब्ध संचरण दर मैट्रिक्स विकल्पों के समुच्चय का प्रतिनिधित्व करते हैं। प्रत्येक व्याकरणिक स्थान t, नेटवर्क नियंत्रक S(t) का निरीक्षण करते हैं और समुच्चय $\Gamma _{S(t)}$ के भीतर संचरण दरों $(\mu _{ab}(t))$ का चयन करता है। किस $(\mu _{ab}(t))$ मैट्रिक्स को प्रत्येक व्याकरणिक स्थान t पर चयन किया जाए इस विकल्प को आगामी उपखंड में वर्णित किया गया है।

यह समय-भिन्न नेटवर्क मॉडल सर्वप्रथम उस स्थिति के लिए विकसित किया गया था जब प्रत्येक व्याकरणिक स्थान t के संचरण दरों को चैनल स्थिति आव्यूह और विद्युत् आवंटन आव्यूह के सामान्य कार्यों द्वारा निर्धारित किया गया था।^[9] मॉडल का उपयोग तब भी किया जा सकता है जब दरें अन्य नियंत्रण निर्णयों जैसे सर्वर आवंटन, उप-बंध चयन, कोडिंग प्रकार और इत्यादि द्वारा निर्धारित की जाती हैं। यह अभिगृहीत करता है कि सहायक संचरण दर ज्ञात हैं और कोई संचरण त्रुटि नहीं है। बहु-रिसीवर विविधता के माध्यम से वायरलेस प्रसारण लाभ का समुपयोजन करने वाले नेटवर्क सहित संभाव्य चैनल त्रुटियों वाले नेटवर्क के लिए पश्चदाब परिसंचरण के विस्तारित सूत्रीकरण का उपयोग किया जा सकता है।^[1]

पश्चदाब नियंत्रण निर्णय

प्रत्येक व्याकरणिक स्थान t पश्चदाब नियंत्रक S(t) का निरीक्षण करता है और निम्नलिखित 3 चरणों का पालन करता है:

सर्वप्रथम, प्रत्येक सम्बंध (a, b) के लिए, यह उपयोग के लिए इष्टतम पण्य $c_{ab}^{opt}(t)$ का चयन करता है।
इसके उपरांत, यह निर्धारित करता है कि $\Gamma _{S(t)}$ में क्या $(\mu _{ab}(t))$ मैट्रिक्स का उपयोग किया जा सकता है।
अंत में, यह पण्य $c_{ab}^{opt}(t)$ की मात्रा निर्धारित करता है जो यह लिंक (a, b) पर संचारित करेगा (अधिकतम $\mu _{ab}(t)$ पर लेकिन संभवतः कुछ स्थितियों में न्यूनतम पर होता है)।

इष्टतम पण्य का चयन

प्रत्येक बिंदु अपने स्वयं के पंक्तिबद्ध संचित कार्य और अपने वर्तमान प्रतिवेशी में संचित कार्य का निरीक्षण करता है। बिंदु a का वर्तमान प्रतिवेशी बिंदु b है इस प्रकार कि वर्तमान व्याकरणिक स्थान पर एक गैर-शून्य संचरण दर $\mu _{ab}(t)$ का चयन करना संभव है। इस प्रकार, प्रतिवेशियों को समुच्चय $\Gamma _{S(t)}$ द्वारा निर्धारित किया जाता है। चरम स्थिति में, एक बिंदु में प्रतिवेशी के रूप में सभी N-1 अन्य बिंदु हो सकते हैं। यद्यपि, समुच्चय $\Gamma _{S(t)}$ का उपयोग करना सामान्य है जो एक निश्चित भौगोलिक दूरी से अधिक पृथक्‍कृत किए गए बिंदुओं के मध्य प्रसारण को प्रतिबन्धित करते हैं, या जिनकी निश्चित सीमा के नीचे एक प्रसारित संकेत सामर्थ्य होगी। इस प्रकार, प्रतिवेशियों की संख्या N-1 से अधिक न्यून होना सामान्य है। चित्र संख्या 1 में उदाहरण संबंध कनेक्शन द्वारा प्रतिवेशियों का व्याख्या करते है, इस प्रकार कि बिंदु 5 में प्रतिवेशी 4 और 6 है। उदाहरण प्रतिवेशियों के मध्य सममित संबंध का सुझाव देता है (जिससे कि यदि 5, 4 का प्रतिवेशी है, तो 4, 5 का प्रतिवेशी है), लेकिन सामान्यतः ऐसा होना आवश्यक नहीं है।

किसी दिए गए बिंदु के निकटवर्तियों का सम्मुच्चय बर्हिगामी सम्बंध के सम्मुच्चय को निर्धारित करता है जिसका उपयोग वह वर्तमान व्याकरणिक स्थान पर संचारण के लिए कर सकता है। प्रत्येक बर्हिगामी सम्बंध $(a,b)$ के लिए इष्टतम पण्य $c_{ab}^{opt}(t)$ को पण्य $c\in \{1,\ldots ,N\}$ के रूप में परिभाषित किया गया है जो निम्नलिखित अवकल बैकलॉग मात्रा को अधिकतम करता है:

Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)

इष्टतम पण्य का चयन करने में किसी भी संबंध को स्वेच्छतः विघटित कर दिया जाता है।

A closeup of nodes 1 and 2. लिंक (1,2) पर भेजने के लिए इष्टतम वस्तु हरी वस्तु है।

चित्र संख्या 2: बिंदु 1 और 2 का क्लोज़अप। निर्देशित सम्बंध (1,2) प्रेषित करने के लिए इष्टतम पण्य का रंग हरा है। दूसरी दिशा में प्रेषित करने के लिए इष्टतम पण्य (सम्बंध (2,1) पर) का रंग नीला है।

एक उदाहरण चित्र संख्या 2 में प्रदर्शित किया गया है। उदाहरण के लिए, वह कल्पना करता है कि प्रत्येक पंक्ति के पास वर्तमान में लाल, हरा और नीला केवल 3 पण्य हैं और इन्हें पैकेट की पूर्णांक इकाइयों में मापा जाता है। निर्देशित सम्बंध (1,2) पर ध्यान केंद्रित करने से अवकल बैकलॉग हैं:

Q_{1}^{({\text{red}})}(t)-Q_{2}^{({\text{red}})}(t)=1

Q_{1}^{({\text{green}})}(t)-Q_{2}^{({\text{green}})}(t)=2

Q_{1}^{({\text{blue}})}(t)-Q_{2}^{({\text{blue}})}(t)=-1

इसलिए, व्याकरणिक स्थान t पर सम्बंध (1,2) प्रेषित करने के लिए इष्टतम पण्य का रंग हरा है। दूसरी ओर, व्याकरणिक स्थान t पर उत्क्रमित सम्बंध (2,1) प्रेषित करने के लिए इष्टतम पण्य का रंग नीला है।

μ_ab(t) आव्यूह का चयन करना

एक बार प्रत्येक सम्बंध $(a,b)$ के लिए इष्टतम पण्य निर्धारित हो जाने पर नेटवर्क नियंत्रक निम्नलिखित भार $W_{ab}(t)$ की गणना करता है:

W_{ab}(t)=\max \left[Q_{a}^{(c_{ab}^{\mathrm {opt} }(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0\right]

भार $W_{ab}(t)$ सम्बंध $(a,b)$ के लिए इष्टतम पण्य से संबद्ध अवकल बैकलॉग मान है, जो 0 से अधिकतम है। तत्पश्चात नियंत्रक निम्नलिखित अधिकतम-भार समस्या (स्वेच्छतः संबंधों को तोड़ना) के समाधान के रूप में संचारण दरों का चयन करता है:

{\text{(Eq. 1)}}\qquad {\text{Maximize: }}\sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)

{\text{(Eq. 2)}}\qquad {\text{Subject to: }}(\mu _{ab}(t))\in \Gamma _{S(t)}

अधिकतम-भार निर्णय के एक उदाहरण के रूप में मान लीजिए कि वर्तमान व्याकरणिक स्थान t पर 6 नेटवर्क बिंदु के प्रत्येक सम्बंध पर अवकल बैकलॉग द्वारा दिए गए संबद्ध भार $W_{ab}(t)$ की ओर जाता है:

(W_{ab}(t))=\left[{\begin{array}{cccccc}0&2&1&1&6&0\\1&0&1&2&5&6\\0&7&0&0&0&0\\1&0&1&0&0&0\\1&0&7&5&0&0\\0&0&0&0&5&0\end{array}}\right]

जबकि सेट $\Gamma _{S(t)}$ एक बेशुमार अनंत संख्या हो सकती है संभव संचरण दर मैट्रिसेस, सादगी के लिए मान लें कि वर्तमान टोपोलॉजी राज्य केवल 4 संभावितों को स्वीकार करता है विकल्प:

\Gamma _{S(t)}=\{{\boldsymbol {\mu }}_{a},{\boldsymbol {\mu }}_{b},{\boldsymbol {\mu }}_{c},{\boldsymbol {\mu }}_{d}\}

वर्तमान सांस्थिति स्थिति s(t) के अंतर्गत 4 संभावित संचरण दर चयनों का चित्रण। विकल्प (a) $\mu _{15}=2$ की संचरण दर के साथ एकल सम्बंध (1,5) को सक्रिय करता है। अन्य सभी विकल्प प्रत्येक सक्रिय सम्बंध पर 1 की संचारण दर के साथ दो सम्बंधों का प्रयोग करते हैं।

इन चार संभावनाओं को मैट्रिक्स रूप में निम्न द्वारा दर्शाया गया है:

{\boldsymbol {\mu }}_{a}=\left[{\begin{array}{cccccc}0&0&0&0&2&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{b}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&1&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right]

{\boldsymbol {\mu }}_{c}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\1&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{d}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\end{array}}\right]

ध्यान दें कि बिंदु 6 इनमें से किसी भी संभावना के अंतर्गत न तो प्रेषित कर सकता है और न ही प्राप्त कर सकता है। यह उत्पन्न हो सकता है क्योंकि वर्तमान में बिंदु 6 संचार सीमा से बाहर है। 4 संभावनाओं में से प्रत्येक के लिए दरों का भारित योग इस प्रकार है:

विकल्प (a): $\sum _{ab}W_{ab}(t)\mu _{ab}(t)=12$ .
विकल्प (b): $\sum _{ab}W_{ab}(t)\mu _{ab}(t)=1$ .
विकल्प (c): $\sum _{ab}W_{ab}(t)\mu _{ab}(t)=1$ .
विकल्प (d): $\sum _{ab}W_{ab}(t)\mu _{ab}(t)=12$ .

क्योंकि 12 के अधिकतम वजन के लिए एक टाई है, नेटवर्क नियंत्रक टाई को मनमाने ढंग से तोड़ सकता है कोई भी विकल्प चुनना ${\boldsymbol {\mu }}_{a}$ या विकल्प ${\boldsymbol {\mu }}_{d}$ .

रूटिंग वेरिएबल्स को अंतिम रूप देना

अब मान लीजिए कि प्रत्येक सम्बन्ध के लिए इष्टतम पण्य $c_{ab}^{opt}(t)$ निर्धारित की गई हैं तथा संचरण दरें $(\mu _{ab}(t))$ भी निर्धारित की गई हैं। यदि किसी दिए गए सम्बंध $(a,b)$ पर इष्टतम पण्य के लिए अवकल बैकलॉग नकारात्मक है तो वर्तमान व्याकरणिक स्थान पर इस लिंक पर कोई डेटा स्थानांतरित नहीं किया जाता है। अन्यथा, नेटवर्क इस लिंक पर पण्य $c_{ab}^{\mathrm {opt} }(t)$ डेटा की $\mu _{ab}(t)$ इकाइयां प्रेषित करने की चेष्टा करता है। यह प्रत्येक सम्बंध $(a,b)$ और प्रत्येक पण्य c के लिए परिसंचरण चर $\mu _{ab}^{(c)}(t)$ को परिभाषित करके किया जाता है, जहाँ:

\mu _{ab}^{(c)}(t)={\begin{cases}\mu _{ab}(t)&{\text{ if }}c=c_{ab}^{opt}(t){\text{ and }}Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t)\geq 0\\0&{\text{ otherwise}}\end{cases}}

$\mu _{ab}^{(c)}(t)$ का मान व्याकरणिक स्थान t पर संबन्ध $(a,b)$ पर पण्य c डेटा को दी जाने वाली संचरण दर को दर्शाता है। हालाँकि, बिंदुओं में उनके सभी बहिर्गामी संबन्ध पर प्रस्तावित दरों पर संचारण का समर्थन करने के लिए एक विशेष पण्य पर्याप्त नहीं हो सकती है। यह बिंदु n और पण्य c के लिए व्याकरणिक स्थान t पर उत्पन्न होता है यदि:

Q_{n}^{(c)}(t)<\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)

इस स्थिति में, सभी $Q_{n}^{(c)}(t)$ डेटा प्रेषित किया जाता है और शून्य डेटा का उपयोग प्रस्तावित दरों के अप्रयुक्त भागों का भरण करने के लिए किया जाता है, वास्तविक डेटा और शून्य डेटा को स्वेच्छतः संबंधित बहिर्गामी लिंक (प्रस्तावित दरों के अनुसार) पर आवंटित किया जाता है। इसे क्यू अंडरफ्लो स्थिति कहा जाता है। इस प्रकार के अधःप्रवाह नेटवर्क के प्रवाह क्षमता या स्थिरता गुणों को प्रभावित नहीं करते हैं। सहज रूप से, इसका कारण यह है कि अधःप्रवाह केवल तभी उत्पन्न होता है जब प्रेषणी बिंदु में कम मात्रा में बैकलॉग होता है जिसका अर्थ है कि बिंदु अस्थिरता के विपत्ति में नहीं है।

विलंब में सुधार

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

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

वितरित पश्चदाब

ध्यान दें कि संचरण दर $(\mu _{ab}(t))$ चयनित होने पर, परिसंचरण निर्णय चर $\mu _{ab}^{(c)}(t)$ सामान्य वितरित प्रक्रिया से गणना की जा सकती है, जहां प्रत्येक बिंदु को केवल स्वयं और उनके प्रतिवेशियों के मध्य पंक्तिबद्ध संचित कार्य विभेदक के ज्ञान की आवश्यकता होती है। यद्यपि, संचरण दरों के चयन के लिए समीकरण (1)-(2) में अधिकतम-भार समस्या के समाधान की आवश्यकता होती है।विशेष स्थिति में जब चैनल लांबिक होते हैं, कलनविधि में एक प्राकृतिक वितरित कार्यान्वयन होता है और प्रत्येक बिंदु पर पृथक निर्णयों को न्यूनतम करता है। यद्यपि, अधिकतम-भार समस्या अंतर चैनल व्यतिकरण वाले नेटवर्क के लिए एक केंद्रीकृत नियंत्रण समस्या है। केंद्रीकृत प्रक्रिया से भी इसे हल करना अधिक कठिन हो सकता है।

सिग्नल-टू-नॉइज़-प्लस-इंटरफेरेंस अनुपात (एसआईएनआर) द्वारा निर्धारित लिंक दरों के साथ व्यतिकरण नेटवर्क के लिए एक वितरित दृष्टिकोण यादृच्छिककरण का उपयोग करके किया जा सकता है।^[9] प्रत्येक बिंदु अव्यवस्थिततः प्रत्येक व्याकरणिक स्थान t को प्रसारित करने का निर्णय लेता है (यदि वर्तमान में प्रेषित करने के लिए पैकेट नहीं है तो "शून्य" पैकेट प्रेषण किया जाता है)। वास्तविक संचरण दर, और प्रेषित करने के लिए संबंधित वास्तविक पैकेट, 2-चरणीय हैंडशेक द्वारा निर्धारित किए जाते हैं: प्राथमिक चरण पर, अव्यवस्थिततः चयनित प्रेषक बिंदु वास्तविक संचरण के आनुपातिक संकेत सामर्थ्य के साथ एक पायलट संकेत प्रेषित करते हैं। द्वितीय चरण पर, सभी संभावित रिसीवर बिंदु परिणामी व्यतिकरण को मापते हैं और उस सूचना को पुनः प्रेषक को भेजते हैं। सभी आउटगोइंग लिंक (n, b) के लिए एसआईएनआर स्तर तब सभी बिंदु्स n के लिए ज्ञात होता है, और प्रत्येक बिंदु n इस सूचना के आधार पर अपने $\mu _{nb}(t)$ और $(\mu _{nb}^{(c)}(t))$ चरों के निर्णय ले सकते हैं। परिणामी संदेश प्रवाह आवश्यक रूप से इष्टतम नहीं है। यद्यपि, अव्यवस्थित संचरण प्रक्रिया को चैनल स्थिति प्रक्रिया के एक भाग के रूप में देखा जा सकता है (किंतु अशक्त पैकेट अंडरफ़्लो के स्थितियों में भेजे जाते हैं, ताकि चैनल स्थिति प्रक्रिया पूर्व निर्णयों पर निर्भर न हो)। इसलिए, इस वितरित कार्यान्वयन का परिणामी संदेश प्रवाह सभी परिसंचरण और अनुसूचीयन कलनविधि के वर्ग पर इष्टतम है जो इस प्रकार के यादृच्छिक प्रसारण का उपयोग करते हैं।

वैकल्पिक वितरित परिपालन को प्रायः दो वर्गों में विभाजित किया जा सकता है: कलनविधि की प्रथम श्रेणी अधिकतम-भार समस्या के निरंतर गुणक कारक अनुमानों पर विचार करती है, और निरंतर-कारक साद्यांत परिणाम उत्पन्न करती है। कलनविधि की द्वितीय श्रेणी समय के साथ अधिकतम-भार समस्या के समाधान को अद्यतन करने के आधार पर, अधिकतम-भार समस्या के योगात्मक अनुमानों पर विचार करती है।

इस द्वितीय श्रेणी में कलनविधि को स्थिर चैनल की स्थिति और दीर्घ (प्रायः गैर-बहुपद) अभिसरण समय की आवश्यकता हो सकती है, यद्यपि वे उपयुक्त धारणाओं के अंतर्गत अधिकतम साद्यांत प्राप्त कर सकते हैं।^[15]^[4]^[13]अप्रचलित पंक्तिबद्ध संचित कार्य जानकारी के साथ परिपालित किए जाने पर पश्चदाब की इष्टतमता सिद्ध करने के लिए योगात्मक सन्निकटन प्रायः उपयोगी होते हैं (नीली पाठ का अभ्यास 4.10 देखें)।^[13]

लयपुनोव बहाव के माध्यम से गणितीय निर्माण

यह भाग प्रदर्शित करता है कि एक व्याकरणिक स्थान से दूसरे व्याकरणिक स्थान में क्यू बैकलॉग के वर्गों के योग में परिवर्तन पर बाध्यता को कम करने के स्वाभाविक परिणाम के रूप में पश्चदाब एल्गोरिदम कैसे उत्पन्न होता है।^[9]^[3]

नियंत्रण निर्णय बाध्यताएं और पंक्ति अद्यतन समीकरण

उपरोक्त खंड में वर्णित N बिंदु के साथ एक बहुपद नेटवर्क पर विचार करें। प्रत्येक व्याकरणिक स्थान t नेटवर्क नियंत्रक सांस्थिति स्थिति S(t) को प्रेक्षित करता है तथा निम्नलिखित बाधाओं के अधीन संचरण दर $(\mu _{ab}(t))$ परिसंचरण चर राशि $(\mu _{ab}^{(c)}(t))$ का चयन करता है:

{\text{(Eq. 3)}}\qquad (\mu _{ab}(t))\in \Gamma _{S(t)}

{\text{(Eq. 4)}}\qquad 0\leq \mu _{ab}^{(c)}(t)\qquad \forall a,b,c,\forall t

{\text{(Eq. 5)}}\qquad \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)\leq \mu _{ab}(t)\qquad \forall (a,b),\forall t

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

{\text{(Eq. 6)}}\qquad Q_{n}^{(c)}(t+1)\leq \max \left[Q_{n}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t),0\right]+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)+A_{n}^{(c)}(t)

जहाँ $A_{n}^{(c)}(t)$ नए पण्य c डेटा की यादृच्छिक मात्रा है जो वाह्य रूप से व्याकरणिक स्थान t पर बिंदु n पर आता है और $\mu _{nb}^{(c)}(t)$ व्याकरणिक स्थान t से संबद्ध $(a,b)$ पर पण्य c परिवहन के लिए आवंटित संचरण दर है। ध्यान दें कि $\mu _{nb}^{(c)}(t)$ पण्य c डेटा की मात्रा से अधिक हो सकता है जो वस्तुतः व्याकरणिक स्थान t से संबद्ध $(a,b)$ पर प्रसारित होता है। ऐसा इसलिए है क्योंकि बिंदु n में पर्याप्त संचित कार्य नहीं हो सकता है। इसी कारण से समीकरण (6) एक समानता की जगह एक असमानता है क्योंकि व्याकरणिक स्थान t पर बिंदु n के लिए पण्य c के वास्तविक अंतर्जात आगमन से $\sum _{a=1}^{N}\mu _{an}^{(c)}(t)$ अधिक हो सकता है। समीकरण (6) की एक महत्वपूर्ण विशेषता यह है कि यद्यपि $\mu _{ab}^{(c)}(t)$ निर्णय चर क्यू बैकलॉग से स्वतंत्र रूप से चुने गए हों।

यह माना जाता है कि सभी व्याकरणिक स्थान t और सभी $c\in \{1,\ldots ,N\}$ के लिए $Q_{c}^{(c)}(t)=0$ क्योंकि कोई क्रमित डेटा को स्वयं के लिए नियत नहीं करता है।

लायपुनोव बहाव

${\boldsymbol {Q}}(t)=(Q_{n}^{(c)}(t))$ को वर्तमान क्यू बैकलॉग के आव्यूह के रूप में परिभाषित करें। निम्नलिखित गैर-नकारात्मक फलन को परिभाषित करें जिसे लायपुनोव फलन कहा जाता है:

$L(t)={\frac {1}{2}}\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)^{2}$

यह क्यू बैकलॉग के वर्गों का योग है (तत्पश्चात विश्लेषण में सुविधा के लिए केवल 1/2 से गुणन )। उपरोक्त राशि सभी n, c के योग के समान है जैसे कि $n\neq c$ क्योंकि सभी $c\in \{1,\ldots ,N\}$ और सभी व्याकरणिक स्थान t के लिए $Q_{c}^{(c)}(t)=0$ .

सशर्त लायपुनोव बहाव $\Delta (t)$ परिभाषित किया गया है:

\Delta (t)=E\left[L(t+1)-L(t)\mid {\boldsymbol {Q}}(t)\right]

ध्यान दें कि निम्नलिखित असमानता सभी $q\geq 0$ , $a\geq 0$ , $b\geq 0$ के लिए प्रयुक्त होती है:

(\max[q-b,0]+a)^{2}\leq q^{2}+b^{2}+a^{2}+2q(a-b)

क्यू अद्यतन समीकरण (6) को अधिकोरन करके और उपरोक्त असमानता का उपयोग करके यह प्रदर्शित करना मुश्किल नहीं है कि सभी व्याकरणिक स्थान t के लिए तथा किसी भी कलनविधि के अंतर्गत संचारण और परिसंचरण चर $(\mu _{ab}(t))$ और $(\mu _{ab}^{(c)}(t))$ का चयन करने के लिए:^[3]

{\text{(Eq. 7)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)|{\boldsymbol {Q}}(t)\right]

जहां B एक परिमित स्थिरांक है जो आगमन के दूसरे क्षणों और संचरण दरों के अधिकतम संभव दूसरे क्षणों पर निर्भर करता है।

राशियों का स्विचन करके धारा को सीमित करना

पश्चदाब एल्गोरिदम को ${\boldsymbol {Q}}(t)$ और S(t) प्रत्येक व्याकरणिक स्थान t का निरीक्षण करने के लिए रचना की गयी है तथा धारा बाध्य समीकरण (7) के दक्षिण पक्ष को न्यूनतम करने के लिए $(\mu _{ab}(t))$ और $(\mu _{ab}^{(c)}(t))$ का चयन करें। क्योंकि B और $\lambda _{n}^{(c)}$ स्थिरांक हैं, इसलिए यह अधिकतम करने के लिए है:

E\left[\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]|{\boldsymbol {Q}}(t)\right]

जहाँ अधिकतमीकरण निर्णय को स्पष्ट करने के लिए अपेक्षा द्वारा परिमित योग को प्रेरित किया गया है। समयानुवर्ती रूप से एक अपेक्षा अधिकतमीकरण सिद्धांत द्वारा, उपरोक्त अपेक्षा को उसके अंदर के कार्य का अधिकतमीकरण करके बढाया जाता है (दिए गए प्रेक्षित ${\boldsymbol {Q}}(t)$ , $S(t)$ )। इस प्रकार, अधिकतम करने के लिए समीकरण (3) - (5) की बाध्यताओं के अधीन $(\mu _{ab}(t))$ और $(\mu _{ab}^{(c)}(t))$ का चयन करता है:

\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]

यह तत्काल स्पष्ट नहीं है कि कौन से निर्णय उपरोक्त को अधिकतम करते हैं। राशियों का स्विचन करके इसे स्पष्ट किया जा सकता है। वास्तव में, उपरोक्त व्यंजक नीचे के समान है:

\sum _{a=1}^{N}\sum _{b=1}^{N}\sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]

भार $Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)$ को बिंदु a और b के मध्य पण्य c का वर्तमान अवकल बैकलॉग कहा जाता है। विचार यह है कि निर्णय चर $(\mu _{ab}^{(c)}(t))$ का चयन किया जाए जिससे कि उपरोक्त भारित राशि को अधिकतम किया जा सके जहाँ भार अंतरात्मक बैकलॉग हैं। सहज रूप से इसका अर्थ है बड़े अंतर वाले बैकलॉग की दिशा में बड़ी दरों का आवंटन।

जब कभी भी $Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)<0$ हो तो स्पष्ट रूप से $\mu _{ab}^{(c)}(t)=0$ का चयन करना चाहिए। इसके अतिरिक्त, किसी विशेष सम्बन्ध $(a,b)$ के लिए दिए गए $\mu _{ab}(t)$ को यह प्रदर्शित करना मुश्किल नहीं है कि समीकरण (3) - (5) के अधीन इष्टतम $\mu _{ab}^{(c)}(t)$ चयन निम्नानुसार निर्धारित किए गए हैं: सर्वप्रथम पण्य $c_{ab}^{opt}(t)\in \{1,\ldots ,N\}$ खोजें जो सम्बंध $(a,b)$ के लिए अवकल बैकलॉग को अधिकतम करता है। यदि अधिकतमीकरण अवकल बैकलॉग सम्बंध $(a,b)$ के लिए नकारात्मक है, तो सम्बंध $(a,b)$ पर $c\in \{1,\ldots ,N\}$ सभी वस्तुओं के लिए $\mu _{ab}^{(c)}(t)=0$ निर्दिष्ट करें। अन्यथा, इस सम्बंध पर पण्य $c_{ab}^{opt}(t)$ को पूर्ण लिंक दर $\mu _{ab}(t)$ तथा अन्य सभी पण्य के लिए शून्य दर आवंटित करें। इस विकल्प के साथ यह इस प्रकार है:

\sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]=\mu _{ab}(t)W_{ab}(t)

जहाँ $W_{ab}(t)$ व्याकरणिक स्थान t(0 के साथ अधिकतम) पर सम्बन्ध $(a,b)$ के लिए इष्टतम पण्य का अवकल बैकलॉग है:

W_{ab}(t)=\max[Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0]

केवल $(\mu _{ab}(t))\in \Gamma _{S(t)}$ का चयन करना शेष है। यह निम्नलिखित को हल करके किया जाता है:

\mathrm {Maximize:} \sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)

\mathrm {Subjectto:} (\mu _{ab}(t))\in \Gamma _{S(t)}

उपरोक्त समस्या समीकरण (1)-(2) में अधिकतम भार समस्या के समान है। पश्चदाब एल्गोरिदम $(\mu _{ab}(t))$ के लिए अधिकतम भार निर्णय का उपयोग करता है तथा तत्पश्चात उपरोक्त वर्णित अधिकतम अवकल बैकलॉग के माध्यम से संचरण चर $(\mu _{ab}^{(c)}(t))$ का चयन करता है।

पश्चदाब कलनविधि का एक उल्लेखनीय गुण यह है कि यह केवल देखी गई सांस्थिति स्थिति S(t) के आधार पर व्याकरणिक स्थान टी पर लोलुपता से कार्य करता है और उस व्याकरणिक स्थान के लिए क्यू बैकलॉग ${\boldsymbol {Q}}(t)$ पर कार्य करता है। इस प्रकार, इसे आगमन दर $(\lambda _{n}^{(c)})$ या सांस्थिति अवस्था की संभावनाओं $\pi _{S}=Pr[S(t)=S]$ के ज्ञान की आवश्यकता नहीं है।

निष्पादन विश्लेषण

यह भाग पश्चदाब एल्गोरिथम की साद्यांत इष्टतमता को सिद्ध करता है।^[3]^[13]सरलता के लिए उस परिदृश्य पर विचार किया जाता है जहाँ घटनाएँ स्वतंत्र तथा व्याकरणिक स्थान पर समान रूप से वितरित (i.i.d.) होती हैं, हालाँकि समान कलनविधि को गैर-i.i.d परिदृश्यों में कार्य करने के लिए प्रदर्शित किया जा सकता है (गैर-i.i.d. ऑपरेशन और सार्वभौमिक अनुसूचीकरण के अंतर्गत नीचे देखें)।

गतिक आगमन

मान लें कि $(A_{n}^{(c)}(t))$ व्याकरणिक स्थान t पर बहिर्जात आगमन का आव्यूह है। मान लें कि यह आव्यूह स्वतंत्र और समान रूप से वितरित (i.i.d.) व्याकरणिक स्थान पर परिमित दूसरे क्षणों तथा साधनों के साथ है:

\lambda _{n}^{(c)}=E\left[A_{n}^{(c)}(t)\right]

यह माना जाता है कि सभी $c\in \{1,\ldots ,N\}$ के लिए $\lambda _{c}^{(c)}=0$ क्योंकि स्वयं के लिए नियत कोई डेटा प्राप्त नहीं होता है। इस प्रकार, आगमन दर $(\lambda _{n}^{(c)})$ का आव्यूह विकर्ण पर शून्य के साथ गैर-ऋणात्मक वास्तविक संख्याओं का $N\times N$ आव्यूह है।

नेटवर्क क्षमता क्षेत्र

मान लें कि टोपोलॉजी स्थिति S(t) i.i.d है। संभावनाओं के साथ व्याकरणिक स्थान्स पर $\pi _{S}=Pr[S(t)=S]$ (यदि एस (टी) वास्तविक मूल्यवान प्रविष्टियों वाले वैक्टरों के अनगिनत अनंत सेट में मान लेता है, तब $\pi _{S}$ संभाव्यता वितरण है, संभाव्यता द्रव्यमान समारोह नहीं)। नेटवर्क के लिए एक सामान्य एल्गोरिद्म S(t) प्रत्येक व्याकरणिक स्थान t को देखता है और ट्रांसमिशन दरों को चुनता है $(\mu _{ab}(t))$ और रूटिंग चर $(\mu _{ab}^{(c)}(t))$ Eq में बाधाओं के अनुसार। (3) - (5)। नेटवर्क क्षमता क्षेत्र $\Lambda$ सभी आगमन दर आव्यूहों के सेट का समापन है $(\lambda _{n}^{(c)})$ जिसके लिए एक कलनविधि मौजूद है जो नेटवर्क को स्थिर करता है। सभी कतारों की स्थिरता का अर्थ है कि नेटवर्क में ट्रैफ़िक की कुल इनपुट दर अपने गंतव्य तक पहुँचाए गए डेटा की कुल दर के समान है। यह दिखाया जा सकता है कि किसी भी आगमन दर मैट्रिक्स के लिए $(\lambda _{n}^{(c)})$ क्षमता क्षेत्र में $\Lambda$ , एक स्थिर और यादृच्छिक एल्गोरिदम है जो निर्णय चर चुनता है $(\mu _{ab}^{*}(t))$ और $(\mu _{ab}^{*(c)}(t))$ प्रत्येक व्याकरणिक स्थान टी केवल एस (टी) पर आधारित है (और इसलिए क्यू बैकलॉग से स्वतंत्र) जो सभी के लिए निम्नलिखित देता है $n\neq c$ :^[9]^[13]

{\text{(Eq. 8)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq 0

इस तरह के एक स्थिर और यादृच्छिक एल्गोरिदम जो केवल एस (टी) पर निर्णय लेते हैं, एस-ओनली एल्गोरिदम कहलाते हैं। यह मान लेना अक्सर उपयोगी होता है $(\lambda _{n}^{(c)})$ का आंतरिक है $\Lambda$ , ताकि वहाँ एक है $\epsilon >0$ ऐसा है कि $(\lambda _{n}^{(c)}+\epsilon 1_{n}^{(c)})\in \Lambda$ , कहाँ $1_{n}^{(c)}$ 1 है अगर $n\neq c$ , और शून्य। उस स्थिति में, एक एस-ओनली एल्गोरिथम है जो सभी के लिए निम्नलिखित उत्पन्न करता है $n\neq c$ :

{\text{(Eq. 9)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq -\epsilon

तकनीकी आवश्यकता के रूप में, यह माना जाता है कि संचरण दर के दूसरे क्षण $\mu _{ab}(t)$ इन दरों को चुनने के लिए किसी भी एल्गोरिदम के तहत परिमित हैं। यह तुच्छ रूप से धारण करता है यदि कोई अधिकतम अधिकतम दर है $\mu _{max}$ .

केवल-एस एल्गोरिदम की तुलना

क्योंकि पश्चदाब कलनविधि ${\boldsymbol {Q}}(t)$ और S(t) प्रत्येक व्याकरणिक स्थान t को देखता है और बाध्य धारा समीकरण (7) के दाहिने हाथ की ओर कम करने के लिए $(\mu _{ab}(t))$ और $(\mu _{ab}^{(c)}(t))$ निर्णय का चयन करता है। हमें प्राप्त है:

{\text{(Eq. 10)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)|{\boldsymbol {Q}}(t)\right]

जहाँ $(\mu _{ab}^{*}(t))$ और $(\mu _{ab}^{*(c)}(t))$ कोई वैकल्पिक निर्णय हैं जो समीकरण (3) - (5) को संतुष्ट करते हैं जिसमें यादृच्छिक निर्णय सम्मिलित हैं।

अब $(\lambda _{n}^{(c)})\in \Lambda$ मान लीजिए। तब एक केवल-S एल्गोरिथम उपस्थित होता है जो समीकरण (8) को संतुष्ट करता है। इसे समीकरण (10) के दाईं ओर यह देखते हुए प्लग करना कि इस केवल-S एल्गोरिथम के अंतर्गत ${\boldsymbol {Q}}(t)$ अशर्त अपेक्षा (क्योंकि S(t) आई.आई.डी. व्याकरणिक स्थान पर है और S-only एल्गोरिथम वर्तमान क्यू बैकलॉग से स्वतंत्र है) के समान है, प्राप्त:

\Delta (t)\leq B\,

इस प्रकार द्विघात लायपुनोव फलन का आशय सभी व्याकरणिक स्थान t के लिए नियतांक B से कम या उसके समान है। यह तथ्य इस धारणा के साथ है कि पंक्ति आगमन ने दूसरे क्षणों को सीमित कर दिया है, सभी नेटवर्क पंक्ति के लिए निम्नलिखित का अर्थ है:^[16]

\lim _{t\rightarrow \infty }{\frac {Q_{n}^{(c)}(t)}{t}}=0{\text{ with probability 1}}

सामान्य पंक्ति आकार की सुदृढ़ ज्ञान के लिए, आगमन दर $(\lambda _{n}^{(c)})$ , $\Lambda$ के आंतरिक माना जा सकता हैं इसलिए वहाँ एक $\epsilon >0$ है जो समीकरण (9) कुछ वैकल्पिक S-ओनली कलनविधि के लिए है। समीकरण (9) को समीकरण (10) के दाएँ पक्ष में लगाने पर यह प्राप्त होता है:

\Delta (t)\leq B-\epsilon \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)

जिससे तत्काल प्राप्त हो जाता है (देखें^[3]^[13]):

\limsup _{t\rightarrow \infty }{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{n=1}^{N}\sum _{c=1}^{N}E\left[Q_{n}^{(c)}(\tau )\right]\leq {\frac {B}{\epsilon }}

जैसे-जैसे क्षमता क्षेत्र $\Lambda$ की सीमा से दूरी $\epsilon$ शून्य हो जाती है, यह औसत पंक्ति का आकार बढ़ता जाता है। यह आगमन दर $\lambda$ और सेवा दर $\mu$ के साथ एकल M/M/1 पंक्ति के समान गुणात्मक प्रदर्शन है जहां औसत पंक्ति का आकार $1/\epsilon$ के समानुपाती होता है जहां $\epsilon =\mu -\lambda$ होता है।

उपरोक्त सूत्रीकरण का विस्तार

गैर-आई.आई.डी. संचालन और सार्वभौमिक अनुसूचीयन

उपरोक्त विश्लेषण सरलता के लिए आई.आई.डी. गुणों को मानता है। हालाँकि समान पश्चदाब कलनविधि को गैर-आईआईडी स्थितियों में मजबूती से संचालित होते प्रदर्शित किया जा सकता है। जब आगमन प्रक्रियाएँ और सांस्थिति स्थितियाँ अभ्यतिप्राय होती हैं किन्तु आवश्यक नहीं कि आई.आई.डी. हो, जब भी $(\lambda _{n}^{(c)})\in \Lambda$ होता है तो पश्चदाब प्रणाली को स्थिर कर देता है।^[9] सामान्यतः सार्वभौमिक अनुसूचीयन दृष्टिकोण का उपयोग करके इसे यादृच्छिक (संभवतः गैर-एर्गोडिक) प्रतिदर्श पथ के लिए स्थिरता और इष्टतमता गुण प्रदान करने के लिए प्रदर्शित किया गया है।^[17]

उपयोगिता इष्टतमीकरण और दंड न्यूनतमकरण के साथ पश्चदाब

पश्चदाब को ड्रिफ्ट प्लस पेनल्टी तकनीक के माध्यम से प्रवाह नियंत्रण के साथ मिलकर काम करते दिखाया गया है।^[10]^[11]^[3] यह तकनीक लोलुपता से बहाव के योग और भारित दंड अभिव्यक्ति को अधिकतम कर देती है। दंड को एक पैरामीटर V द्वारा भारित किया जाता है जो एक निष्पादन ट्रेडऑफ़ निर्धारित करता है। यह तकनीक सुनिश्चित करती है कि प्रवाह क्षमता उपयोगिता इष्टतमता के O(1/V) के भीतर है जबकि औसत विलंब O(V) है। इस प्रकार, उपयोगिता को औसत विलंब में संबंधित ट्रेडऑफ़ के साथ स्वेच्छतः से इष्टतमता के समीप धकेला जा सकता है। समान गुण औसत बिजली न्यूनीकरण और ^[18]अधिक सामान्य नेटवर्क विशेषताओं के अनुकूलन के लिए दिखाए जा सकते हैं।^[13]

नेटवर्क उपयोगिता को अधिकतम करते हुए पंक्तियों को स्थिर करने के लिए वैकल्पिक एल्गोरिदम को द्रव मॉडल विश्लेषण,^[12]संयुक्त द्रव विश्लेषण और लैग्रेंज गुणक विश्लेषण,^[19] उत्तल अनुकूलन,^[20] और स्टोकेस्टिक ग्रेडिएंट्स का उपयोग करके विकसित किया गया है।^[21] ये दृष्टिकोण O(1/V), O(V) उपयोगिता-विलंब परिणाम प्रदान नहीं करते हैं।

यह भी देखें

एओडीवी
विविधता बैकप्रेशर रूटिंग (डीआईवीबीएआर)^[1]
ईएक्सओआर
भौगोलिक परिसंचरण
तदर्थ रूटिंग प्रोटोकॉल की सूची
लायपुनोव इष्टतमीकरण

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, no. 5, pp. 862-881, July 2009.
↑ ^2.0 ^2.1 L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, vol. 1, no. 1, pp. 1-149, 2006.
↑ ^4.0 ^4.1 L. Jiang and J. Walrand. Scheduling and Congestion Control for Wireless and Processing Networks, Morgan & Claypool, 2010.
↑ A. Sridharan, S. Moeller, and B. Krishnamachari, "Making Distributed Rate Control using Lyapunov Drifts a Reality in Wireless Sensor Networks," 6th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), April 2008.
↑ A. Warrier, S. Janakiraman, S. Ha, and I. Rhee, "DiffQ: Practical Differential Backlog Congestion Control for Wireless Networks," Proc. IEEE INFOCOM, Rio de Janeiro, Brazil, 2009.
↑ ^7.0 ^7.1 S. Moeller, A. Sridharan, B. Krishnamachari, and O. Gnawali, "Routing Without Routes: The Backpressure Collection Protocol," Proc. 9th ACM/IEEE Intl. Conf. on Information Processing in Sensor Networks (IPSN), April 2010.
↑ B. Awerbuch and T. Leighton, "A Simple Local-Control Approximation Algorithm for Multicommodity Flow," Proc. 34th IEEE Conf. on Foundations of Computer Science, Oct. 1993.
↑ ^9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.5 ^9.6 M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic Power Allocation and Routing for Time Varying Wireless Networks," IEEE Journal on Selected Areas in Communications, vol. 23, no. 1, pp. 89-103, January 2005.
↑ ^10.0 ^10.1 M. J. Neely. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time Varying Channels. Ph.D. Dissertation, Massachusetts Institute of Technology, LIDS. November 2003.
↑ ^11.0 ^11.1 M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005.
↑ ^12.0 ^12.1 A. Stolyar, "Maximizing Queueing Network Utility subject to Stability: Greedy Primal-Dual Algorithm," Queueing Systems, vol. 50, no. 4, pp. 401-457, 2005.
↑ ^13.0 ^13.1 ^13.2 ^13.3 ^13.4 ^13.5 ^13.6 M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.
↑ L. Huang, S. Moeller, M. J. Neely, and B. Krishnamachari, "LIFO-Backpressure Achieves Near Optimal Utility-Delay Tradeoff," Proc. WiOpt, May 2011.
↑ E. Modiano, D. Shah, and G. Zussman, "Maximizing throughput in wireless networks via gossiping," Proc. ACM SIGMETRICS, 2006.
↑ M. J. Neely, "Queue Stability and Probability 1 Convergence via Lyapunov Optimization," Journal of Applied Mathematics, vol. 2012, doi:10.1155/2012/831909.
↑ M. J. Neely, "Universal Scheduling for Networks with Arbitrary Traffic, Channels, and Mobility," Proc. IEEE Conf. on Decision and Control (CDC), Atlanta, GA, Dec. 2010.
↑ M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006
↑ A. Eryilmaz and R. Srikant, "Fair Resource Allocation in Wireless Networks using Queue-Length-Based Scheduling and Congestion Control," Proc. IEEE INFOCOM, March 2005.
↑ X. Lin and N. B. Shroff, "Joint Rate Control and Scheduling in Multihop Wireless Networks," Proc. of 43rd IEEE Conf. on Decision and Control, Paradise Island, Bahamas, Dec. 2004.
↑ J. W. Lee, R. R. Mazumdar, and N. B. Shroff, "Opportunistic Power Scheduling for Dynamic Multiserver Wireless Systems," IEEE Transactions on Wireless Communications, vol. 5, no.6, pp. 1506–1515, June 2006.

प्राथमिक स्रोत

एल. तस्सिउलास और ए. एफ़्रेमाइड्स, मल्टीहॉप रेडियो नेटवर्क में अधिकतम थ्रूपुट के लिए विवश क्यूइंग सिस्टम और शेड्यूलिंग नीतियों की स्थिरता गुण, स्वचालित नियंत्रण पर IEEE लेनदेन, वॉल्यूम। 37, नहीं. 12, पीपी. 1936-1948, दिसंबर 1992.
एल. जोर्जियाडिस, एम.जे. नीली, और एल. तासीउलास, संसाधन आवंटन और वायरलेस नेटवर्क में क्रॉस-लेयर नियंत्रण, नेटवर्किंग में नींव और रुझान, वॉल्यूम। 1, नहीं। 1, पीपी। 1–149, 2006।
एम जे नीली। स्टोचैस्टिक नेटवर्क ऑप्टिमाइजेशन विथ एप्लीकेशन टू कम्युनिकेशन एंड क्यूइंग सिस्टम्स, मॉर्गन एंड क्लेपूल, 2010।

श्रेणी:नेटवर्किंग एल्गोरिदम श्रेणी:पंक्ति सिद्धांत श्रेणी:रूटिंग एल्गोरिथम

[neely-divbar-journal-1] 1.0 ^1.1 ^1.2 ^1.3 M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, no. 5, pp. 862-881, July 2009.

[tass-radio-nets-2] 2.0 ^2.1 L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.

[now-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, vol. 1, no. 1, pp. 1-149, 2006.

[jiang-walrand-book-4] 4.0 ^4.1 L. Jiang and J. Walrand. Scheduling and Congestion Control for Wireless and Processing Networks, Morgan & Claypool, 2010.

[avinash-backpressure-5] A. Sridharan, S. Moeller, and B. Krishnamachari, "Making Distributed Rate Control using Lyapunov Drifts a Reality in Wireless Sensor Networks," 6th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), April 2008.

[rhee-backpressure2-6] A. Warrier, S. Janakiraman, S. Ha, and I. Rhee, "DiffQ: Practical Differential Backlog Congestion Control for Wireless Networks," Proc. IEEE INFOCOM, Rio de Janeiro, Brazil, 2009.

[moeller-LIFO-7] 7.0 ^7.1 S. Moeller, A. Sridharan, B. Krishnamachari, and O. Gnawali, "Routing Without Routes: The Backpressure Collection Protocol," Proc. 9th ACM/IEEE Intl. Conf. on Information Processing in Sensor Networks (IPSN), April 2010.

[leighton-backpressure-8] B. Awerbuch and T. Leighton, "A Simple Local-Control Approximation Algorithm for Multicommodity Flow," Proc. 34th IEEE Conf. on Foundations of Computer Science, Oct. 1993.

[neely-power-network-jsac-9] 9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.5 ^9.6 M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic Power Allocation and Routing for Time Varying Wireless Networks," IEEE Journal on Selected Areas in Communications, vol. 23, no. 1, pp. 89-103, January 2005.

[neely-thesis-10] 10.0 ^10.1 M. J. Neely. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time Varying Channels. Ph.D. Dissertation, Massachusetts Institute of Technology, LIDS. November 2003.

[neely-fairness-infocom05-11] 11.0 ^11.1 M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005.

[stolyar-greedy-12] 12.0 ^12.1 A. Stolyar, "Maximizing Queueing Network Utility subject to Stability: Greedy Primal-Dual Algorithm," Queueing Systems, vol. 50, no. 4, pp. 401-457, 2005.

[sno-text-13] 13.0 ^13.1 ^13.2 ^13.3 ^13.4 ^13.5 ^13.6 M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.

[longbo-LIFO-wiopt-14] L. Huang, S. Moeller, M. J. Neely, and B. Krishnamachari, "LIFO-Backpressure Achieves Near Optimal Utility-Delay Tradeoff," Proc. WiOpt, May 2011.

[modiano-distributed-15] E. Modiano, D. Shah, and G. Zussman, "Maximizing throughput in wireless networks via gossiping," Proc. ACM SIGMETRICS, 2006.

[lyap-opt-jam-16] M. J. Neely, "Queue Stability and Probability 1 Convergence via Lyapunov Optimization," Journal of Applied Mathematics, vol. 2012, doi:10.1155/2012/831909.

[neely-universal-scheduling-cdc2010-17] M. J. Neely, "Universal Scheduling for Networks with Arbitrary Traffic, Channels, and Mobility," Proc. IEEE Conf. on Decision and Control (CDC), Atlanta, GA, Dec. 2010.

[neely-energy-it-18] M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006

[atilla-fairness-19] A. Eryilmaz and R. Srikant, "Fair Resource Allocation in Wireless Networks using Queue-Length-Based Scheduling and Congestion Control," Proc. IEEE INFOCOM, March 2005.

[lin-shroff-cdc04-20] X. Lin and N. B. Shroff, "Joint Rate Control and Scheduling in Multihop Wireless Networks," Proc. of 43rd IEEE Conf. on Decision and Control, Paradise Island, Bahamas, Dec. 2004.

[lee-stochastic-scheduling-21] J. W. Lee, R. R. Mazumdar, and N. B. Shroff, "Opportunistic Power Scheduling for Dynamic Multiserver Wireless Systems," IEEE Transactions on Wireless Communications, vol. 5, no.6, pp. 1506–1515, June 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Anonymous

Search

बैकप्रेशर रूटिंग: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:41, 3 July 2023

Contents

परिचय

उत्पत्ति

यह कैसे काम करता है

बहुपद पंक्तियन नेटवर्क मॉडल

पश्चदाब नियंत्रण निर्णय

इष्टतम पण्य का चयन

μ_ab(t) आव्यूह का चयन करना

रूटिंग वेरिएबल्स को अंतिम रूप देना

विलंब में सुधार

वितरित पश्चदाब

लयपुनोव बहाव के माध्यम से गणितीय निर्माण

नियंत्रण निर्णय बाध्यताएं और पंक्ति अद्यतन समीकरण

लायपुनोव बहाव

राशियों का स्विचन करके धारा को सीमित करना

निष्पादन विश्लेषण

गतिक आगमन

नेटवर्क क्षमता क्षेत्र

केवल-एस एल्गोरिदम की तुलना

उपरोक्त सूत्रीकरण का विस्तार

गैर-आई.आई.डी. संचालन और सार्वभौमिक अनुसूचीयन

उपयोगिता इष्टतमीकरण और दंड न्यूनतमकरण के साथ पश्चदाब

यह भी देखें

संदर्भ

प्राथमिक स्रोत

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
-{{For|the term "back pressure" in describing fluid flow in piping and air vent systems|पश्चदाब}}
+[[ कतार सिद्धांत |पंक्तियन सिद्धांत]] में, प्रायिकता के गणितीय सिद्धांत के भीतर के भीतर एक अनुशासन, '''पश्चदाब परिसंचरण (बैकप्रेशर रूटिंग)''' एल्गोरिदम एक पंक्तियन नेटवर्क के चारों ओर यातायात को निर्देशित करने की एक विधि है , जो अधिकतम नेटवर्क प्रवाह क्षमता प्राप्त करता है,<ref name="neely-divbar-journal" /> जिसे लायपुनोव बहाव की अवधारणाओं का उपयोग करके स्थापित किया गया है। पश्चदाब परिसंचरण उस स्थिति पर विचार करती है जहां प्रत्येक कार्य नेटवर्क में एकाधिक सेवा बिंदुओं पर जा सकता है। यह [[ अधिकतम वजन निर्धारण |मैक्स-वेट शेड्यूलिंग(अधिकतम-भार नियोजन)]] का विस्तार है जहां प्रत्येक कार्य केवल एक सेवा बिंदु पर निरीक्षण करता है।
-[[ कतार सिद्धांत |कतार सिद्धांत]] में, गणितीय संभाव्यता सिद्धांत के भीतर एक अनुशासन, बैकप्रेशर रूटिंग एल्गोरिदम एक क्यूइंग नेटवर्क के आसपास ट्रैफ़िक को निर्देशित करने की एक विधि है जो अधिकतम नेटवर्क थ्रूपुट प्राप्त करता है,<ref name="neely-divbar-journal" />जिसे Lyapunov अनुकूलन की अवधारणाओं का उपयोग करके स्थापित किया गया है। बैकप्रेशर रूटिंग उस स्थिति पर विचार करता है जहां प्रत्येक कार्य नेटवर्क में कई सर्विस नोड्स पर जा सकता है। यह [[ अधिकतम वजन निर्धारण ]] का विस्तार है जहां प्रत्येक कार्य केवल एक सेवा नोड पर जाता है।
 == परिचय ==
-बैकप्रेशर रूटिंग कंजेशन ग्रेडिएंट्स का उपयोग करके मल्टी-हॉप नेटवर्क पर गतिशील रूप से ट्रैफ़िक को रूट करने के लिए एक एल्गोरिथ्म है। एल्गोरिथ्म वायरलेस संचार नेटवर्क पर लागू किया जा सकता है, जिसमें [[वायरलेस सेंसर नेटवर्क]], [[मोबाइल तदर्थ नेटवर्क]] (मोबाइल तदर्थ नेटवर्क), और वायरलेस और वायरलाइन घटकों के साथ विषम नेटवर्क शामिल हैं।<ref name=tass-radio-nets>L. Tassiulas and A. Ephremides,
+पश्चदाब परिसंचरण संकुलन प्रवणता का उपयोग करके बहुपद नेटवर्क पर गतिकत: ट्रैफ़िक के परिसंचरण के लिए एक कलनविधि है। कलनविधि वायरलेस संचार नेटवर्क पर प्रयुक्त किया जा सकता है, जिसमें [[वायरलेस सेंसर नेटवर्क]], [[मोबाइल तदर्थ नेटवर्क|मोबाइल एडहॉक नेटवर्क (एमएएनईटीएस)]] और वायरलेस और वायरलाइन घटकों के साथ विषमांगी जालक्रम सम्मिलित हैं।<ref name=tass-radio-nets>L. Tassiulas and A. Ephremides,
 "Stability Properties of Constrained Queueing Systems and
 Scheduling Policies for Maximum Throughput in Multihop
@@ Line 13: / Line 11: @@
 ''Foundations and Trends in Networking'', vol. 1, no. 1, pp. 1-149, 2006.
 </ref>
-बैकप्रेशर सिद्धांतों को अन्य क्षेत्रों में भी लागू किया जा सकता है, जैसे कि अध्ययन के लिए
-उत्पाद असेंबली सिस्टम और प्रोसेसिंग नेटवर्क।<ref name=jiang-walrand-book>
+पश्चदाब सिद्धांतों को अन्य क्षेत्रों जैसे उत्पाद संयोजन तंत्र और प्रसंस्करण नेटवर्क के अध्ययन में भी प्रयुक्त किया जा सकता है।<ref name="jiang-walrand-book">
 L. Jiang and J. Walrand. ''Scheduling and Congestion Control for Wireless and Processing Networks'',
 Morgan & Claypool, 2010.
-</ref>
+</ref> यह लेख संचार नेटवर्क पर केंद्रित है, जहां विविध डाटा प्रवाह से पैकेट प्राप्त किए जाते हैं और उन्हें उपयुक्त गंतव्यों तक वितरण किया जाना चाहिए। पश्चदाब कलनविधि निर्धारित समय में संचालित होता है। प्रत्येक निर्धारित समय में यह डेटा को उन दिशाओं में संचारित करने का प्रयास करता है जो निकटवर्ती बिंदुओं के मध्य अवकल बैकलॉग को अधिकतम करते हैं। यह उसी प्रकार है जिस प्रकार दबाव प्रवणताओं के माध्यम से पाइपों के एक नेटवर्क के माध्यम से जल प्रवाहित होता है। यद्यपि, पश्चदाब कलनविधि को बहु-पण्य नेटवर्क (जहां विभिन्न पैकेट के विभिन्न गंतव्य हो सकते हैं) तथा उन नेटवर्क पर प्रयुक्त किया जा सकता है जहां संचरण दरों को विकल्पों के एक समुच्चय (संभवतः समय-भिन्न) से चयन किया जा सकता है। पश्चदाब कलनविधि की आकर्षक विशेषताएं हैं: (i) यह अधिकतम नेटवर्क प्रवाह क्षमता की ओर ले जाता है, (ii) यह समय-भिन्न नेटवर्क स्थितियों के लिए संभवतः सुदृढ़ है, (iii) इसे ट्रैफ़िक आगमन दर या चैनल स्थिति की संभावनाओं अनभिज्ञ होते हुए भी परिपालित किया जा सकता है। यद्यपि, कलनविधि अधिक विलंब क्रमादेशन कर सकता है तथा हस्तक्षेप वाले नेटवर्क में सटीक रूप से परिपालित करना कठिन हो सकता है। पश्चदाब के संशोधन जो विलंब को क्षीण करें और परिपालन को सरल बनाएं, वे विलंब में सुधार और वितरित पश्चदाब के अंतर्गत वर्णित हैं।
-यह लेख संचार नेटवर्क पर केंद्रित है,
-जहां कई डेटा स्ट्रीम से पैकेट आते हैं और
-उपयुक्त स्थलों पर पहुंचाना चाहिए। बैकप्रेशर
-एल्गोरिथ्म स्लॉटेड समय में काम करता है। हर बार स्लॉट में यह डेटा को उस दिशा में रूट करना चाहता है
-पड़ोसी नोड्स के बीच अंतर बैकलॉग को अधिकतम करें। यह कैसे पानी के समान है
-दबाव प्रवणताओं के माध्यम से पाइपों के एक नेटवर्क के माध्यम से बहती है। हालांकि, बैकप्रेशर एल्गोरिदम
-मल्टी-कमोडिटी नेटवर्क पर लागू किया जा सकता है (जहां अलग-अलग पैकेट के अलग-अलग गंतव्य हो सकते हैं),
-और नेटवर्क के लिए जहां ट्रांसमिशन दरों का चयन किया जा सकता है
-(संभवतः समय-भिन्न) विकल्पों के एक सेट से। आकर्षक विशेषताएं
-बैकप्रेशर एल्गोरिथम हैं: (i) यह अधिकतम नेटवर्क थ्रूपुट की ओर ले जाता है, (ii)
-यह समय-भिन्न नेटवर्क स्थितियों के लिए काफी मजबूत है, (iii) यह
-ट्रैफ़िक आगमन दरों या चैनल स्थिति को जाने बिना लागू किया जा सकता है
-संभावनाओं। हालाँकि, एल्गोरिथ्म बड़ी देरी का परिचय दे सकता है, और हो सकता है
-हस्तक्षेप वाले नेटवर्क में सटीक रूप से लागू करना मुश्किल हो सकता है। का संशोधन
-बैकप्रेशर जो देरी को कम करता है और कार्यान्वयन को आसान बनाता है, नीचे वर्णित हैं
-#देरी में सुधार और #वितरित बैकप्रेशर के तहत।
-बैकप्रेशर रूटिंग का अध्ययन मुख्य रूप से सैद्धांतिक रूप से किया गया है
+पश्चदाब परिसंचरण का मुख्य रूप से सैद्धांतिक संदर्भ में अध्ययन किया गया है। कार्यप्रणाली में, एड हॉक वायरलेस नेटवर्क ने विशिष्ट रूप से लघुतम पथ संगणना या नेटवर्क फ्लडिंग जैसे एड हॉक ऑन-डिमांड डिस्टेंस वेक्टर परिसंचरण (एओडीवी), भौगोलिक परिसंचरण और अत्यंत समयानुवर्ती परिसंचरण (एक्सओआर), के आधार पर वैकल्पिक परिसंचरण विधियों को परिपालित किया है। यद्यपि, पश्चदाब के गणितीय इष्टतमत्व गुणधर्मों ने दक्षिणी कैलिफोर्निया विश्वविद्यालय और उत्तरी कैरोलिना स्टेट विश्वविद्यालय में वायरलेस टेस्टबेड पर इसके उपयोग के वर्तमान प्रयोगात्मक प्रदर्शनों को प्रेरित किया है।<ref name=avinash-backpressure>
-प्रसंग। व्यवहार में, तदर्थ वायरलेस नेटवर्क में आमतौर पर
-शॉर्टेस्ट के आधार पर वैकल्पिक रूटिंग विधियों को लागू किया
-पथ संगणना या नेटवर्क बाढ़, जैसे
-तदर्थ [[तदर्थ ऑन-डिमांड दूरी वेक्टर रूटिंग]]| तदर्थ ऑन-डिमांड डिस्टेंस वेक्टर रूटिंग (AODV),
-[[भौगोलिक रूटिंग]], और [[ExOR (वायरलेस नेटवर्क प्रोटोकॉल)]] (ExOR)।
-हालाँकि, बैकप्रेशर की गणितीय इष्टतमता गुण
-इसके उपयोग के हाल के प्रायोगिक प्रदर्शनों को प्रेरित किया है
-दक्षिणी कैलिफोर्निया विश्वविद्यालय में वायरलेस टेस्टबेड पर
-और उत्तरी कैरोलिना स्टेट यूनिवर्सिटी में।<ref name=avinash-backpressure>
 A. Sridharan, S. Moeller, and B. Krishnamachari,
 "Making Distributed Rate Control using Lyapunov Drifts a Reality in Wireless Sensor Networks,"
@@ Line 55: / Line 28: @@
 === उत्पत्ति ===
-मूल बैकप्रेशर एल्गोरिथम को टैसियुलास और एफ़्रेमाइड्स द्वारा विकसित किया गया था।<ref name=tass-radio-nets/>उन्होंने [[मल्टी-हॉप रूटिंग]] | मल्टी-हॉप पैकेट रेडियो नेटवर्क पर यादृच्छिक पैकेट आगमन और लिंक चयन विकल्पों के एक निश्चित सेट पर विचार किया। उनके एल्गोरिदम में अधिकतम-भार लिंक चयन चरण और अंतर बैकलॉग रूटिंग चरण शामिल था।
+मूल पश्चदाब कलनविधि को टैसियुलास और एफ़्रेमाइड्स द्वारा विकसित किया गया था।<ref name=tass-radio-nets/>उन्होंने यादृच्छिक पैकेट आगमन और लिंक चयन विकल्पों के एक निश्चित समुच्चय के साथ बहुपद पैकेट रेडियो नेटवर्क पर विचार किया। उनके कलनविधि में अधिकतम-भार लिंक चयन अवस्था और अंतरात्मक संचित कार्य परिसंचरण चरण सम्मिलित थे। अवरबच और लैटों में बहु-पण्य नेटवर्क प्रवाह की गणना के लिए अभिकल्पित पश्चदाब से संबंधित कलनविधि विकसित किया गया था। <ref name=leighton-backpressure>
-बैकप्रेसर से संबंधित एक एल्गोरिदम,
-मल्टी-कमोडिटी कंप्यूटिंग के लिए डिज़ाइन किया गया
-नेटवर्क प्रवाह, Awerbuch और Leighton में विकसित किया गया था।<ref name=leighton-backpressure>
 B. Awerbuch and T. Leighton, "A Simple Local-Control Approximation Algorithm for Multicommodity Flow," Proc. 34th IEEE Conf.
 on Foundations of Computer Science, Oct. 1993.
-</ref>
+</ref>तत्पश्चात् नीली, मोदियानो और रोहर्स द्वारा पश्चदाब कलनविधि का विस्तार किया गया जिससे कि मोबाइल नेटवर्क के लिए अनुसूचीयन का विवेचन किया जा सके।<ref name=neely-power-network-jsac>
-बैकप्रेशर एल्गोरिथम को बाद में नेली, मोडियानो और रोहर्स द्वारा मोबाइल नेटवर्क के लिए शेड्यूलिंग का इलाज करने के लिए बढ़ाया गया था।<ref name=neely-power-network-jsac>
 M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic Power Allocation and Routing
 for Time Varying Wireless Networks," ''IEEE Journal on Selected Areas in Communications'', vol. 23, no. 1, pp. 89-103,
 January 2005.
-</ref>
+</ref> लायपुनोव बहाव के सिद्धांत के माध्यम से पश्चदाब का गणितीय विश्लेषण किया जाता है और नेटवर्क उपयोगिता अधिकतमकरण प्रदान करने के लिए प्रवाह नियंत्रण तंत्र के साथ संयुक्त रूप से उपयोग किया जा सकता है। (उपयोगिता इष्टमीकरण और दंड न्यूनीकरण के साथ पश्चदाब भी देखें )।<ref name=neely-thesis>
-बैकप्रेशर का गणितीय रूप से लाइपुनोव अनुकूलन के सिद्धांत के माध्यम से विश्लेषण किया जाता है, और नेटवर्क उपयोगिता अधिकतमकरण प्रदान करने के लिए प्रवाह नियंत्रण तंत्र के साथ संयुक्त रूप से उपयोग किया जा सकता है।<ref name=neely-thesis>
 M. J. Neely. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time Varying Channels.
 Ph.D. Dissertation, Massachusetts Institute of Technology, LIDS. November 2003.
@@ Line 82: / Line 50: @@
 Morgan & Claypool, 2010.
 </ref>
-(यूटिलिटी ऑप्टिमाइज़ेशन और पेनल्टी न्यूनीकरण के साथ #बैकप्रेशर भी देखें)।
 == यह कैसे काम करता है ==
-बैकप्रेशर रूटिंग को निर्णय लेने के लिए डिज़ाइन किया गया है जो (मोटे तौर पर) क्यू बैकलॉग के वर्गों के योग को कम करता है
+पश्चदाब परिसंचरण को निर्णय लेने के लिए अभिकल्पित किया गया है जो (प्रायः) नेटवर्क में क्यू बैकलॉग (पंक्तिबद्ध संचित कार्य) के वर्गों के योग को एक समयावधि से अन्य तक न्यूनतमीकरण करता है। इस तकनीक का सटीक गणितीय विकास पश्चातवर्ती खंडों में वर्णित है। यह खंड सामान्य नेटवर्क मॉडल और इस मॉडल के संबंध में पश्चदाब परिसंचरण के संचालन का वर्णन करता है।
-नेटवर्क में एक समयावधि से दूसरे समय तक। इस तकनीक का सटीक गणितीय विकास में वर्णित है
-बाद के खंड। यह खंड सामान्य नेटवर्क मॉडल और सम्मान के साथ बैकप्रेशर रूटिंग के संचालन का वर्णन करता है
-इस मॉडल को।
-=== मल्टी-हॉप क्यूइंग नेटवर्क मॉडल ===
+=== बहुपद पंक्तियन नेटवर्क मॉडल ===
-[[File:Bp-6-node-network.jpg|frame|alt=A 5-नोड मल्टीहॉप नेटवर्क|अंजीर। 1: एक 6-नोड मल्टीहॉप नेटवर्क। नोड्स के बीच तीर दिखाता है
+[[File:Bp-6-node-network.jpg|frame|alt=A 5-नोड मल्टीहॉप नेटवर्क|चित्र संख्या 1: एक 6-बिंदु बहु प्लुति नेटवर्क। बिंदुओं के मध्य के तीर वर्तमान निकटवर्तियों को दर्शाते हैं।]]N बिंदु् के साथ बहुपद नेटवर्क पर विचार करें (N = 6 के साथ उदाहरण के लिए चित्र संख्या 1 देखें )।
-वर्तमान पड़ोसी।]]एन नोड्स के साथ एक बहु-हॉप नेटवर्क पर विचार करें (एन = 6 के साथ उदाहरण के लिए चित्र 1 देखें)।
+नेटवर्क निर्धारित समय <math>t \in \{0, 1, 2, \ldots\}</math>  में संचालित होता है। प्रत्येक व्याकरणिक स्थान पर, नया डेटा नेटवर्क में आ सकता है और सभी डेटा को उसके उचित गंतव्य तक वितरण करने के प्रयास में परिसंचरण और संचारण अनुसूचीयन हेतु निर्णय लिए जाते हैं। मान लें बिंदु <math>c \in \{1, \dots, N\}</math> के लिए नियत डेटा पण्य c डेटा के रूप में अंकित किया गया है। प्रत्येक बिंदु में डेटा को उसके पण्य के अनुसार संग्रहित किया जाता है। <math>n \in \{1, \ldots, N\}</math> और <math>c \in \{1, \ldots, N\}</math> के लिए, मान लें <math>Q_n^{(c)}(t)</math> बिंदु n में पण्य c डेटा की वर्तमान मात्रा है, जिसे पंक्तिबद्ध संचित कार्य भी कहा जाता है। एक बिंदु के भीतर क्यू बैकलॉग का निकट चित्रण चित्र 2 में दर्शाया गया है। <math>Q_n^{(c)}(t)</math> की इकाइयाँ समस्या के संदर्भ पर निर्भर करता है। उदाहरण के लिए, संचित कार्य पैकेट की पूर्णांक इकाइयाँ ले सकता है, जो उन स्थितियों में उपयोगी होता है जब डेटा को निश्चित लंबाई के पैकेट में विभाजित किया जाता है। वैकल्पिक रूप से, यह बिट्स की वास्तविक मूल्य इकाइयाँ ले सकता है। यह अनुमानित किया गया है कि सभी <math>c \in \{1, \ldots, N\}</math> और सभी समयावधि t के लिए <math>Q_c^{(c)}(t)=0</math> है, क्योंकि कोई भी बिंदु स्वयं के लिए निर्धारित डेटा संग्रहीत नहीं करता। प्रत्येक समयावधि में, बिंदु अन्य को डेटा संचारित कर सकते हैं। डेटा जो एक बिंदु से अन्य में प्रेषित होता है, उसे प्रथम बिंदु की पंक्तिबद्ध से हटा दिया जाता है और द्वितीय बिंदु की पंक्तिबद्ध में संयुक्त किया जाता है। अपने गंतव्य तक संचारित होने वाले डेटा को नेटवर्क से हटा दिया जाता है। डेटा नेटवर्क में बाह्यतः रूप से आगमन भी कर सकता है, और <math>A_n^{(c)}(t)</math> को व्याकरणिक स्थान t पर बिंदु n में आगन्तुक नए डेटा की मात्रा के रूप में परिभाषित किया गया है जिसे अंततः बिंदु c को वितरित किया जाना चाहिए।
-नेटवर्क में काम करता है
-स्लॉटेड समय <math>t \in \{0, 1, 2, \ldots\}</math>. हर स्लॉट पर नया डेटा आ सकता है
-नेटवर्क, और रूटिंग और ट्रांसमिशन शेड्यूलिंग निर्णय लिए जाते हैं
-सभी डेटा को उसके उचित गंतव्य तक पहुंचाने के प्रयास में। नियत डेटा दें
-नोड के लिए <math>c \in \{1, \dots, N\}</math> कमोडिटी सी डेटा के रूप में लेबल किया जाना चाहिए। प्रत्येक नोड में डेटा को उसकी वस्तु के अनुसार संग्रहीत किया जाता है। के लिए <math>n \in \{1, \ldots, N\}</math> और <math>c \in \{1, \ldots, N\}</math>, होने देना <math>Q_n^{(c)}(t)</math> नोड एन में कमोडिटी सी डेटा की वर्तमान मात्रा हो, जिसे क्यू बैकलॉग भी कहा जाता है। एक नोड के अंदर क्यू बैकलॉग का क्लोज़अप चित्र 2 में दिखाया गया है।
-की इकाइयां <math>Q_n^{(c)}(t)</math> समस्या के संदर्भ पर निर्भर करता है।
-उदाहरण के लिए, बैकलॉग पैकेट की पूर्णांक इकाइयाँ ले सकता है, जो उन मामलों में उपयोगी होता है जब डेटा को निश्चित लंबाई के पैकेट में विभाजित किया जाता है। वैकल्पिक रूप से, यह बिट्स की वास्तविक मूल्यवान इकाइयां ले सकता है। यह मान लिया है कि <math>Q_c^{(c)}(t)=0</math> सभी के लिए <math>c \in \{1, \ldots, N\}</math> और सभी टाइम स्लॉट टी, क्योंकि कोई भी नोड डेटा को अपने लिए निर्धारित नहीं करता है। प्रत्येक टाइमलॉट, नोड दूसरों को डेटा संचारित कर सकते हैं। डेटा जो एक नोड से दूसरे नोड में प्रेषित होता है, उसे पहले नोड की कतार से हटा दिया जाता है और दूसरे नोड की कतार में जोड़ दिया जाता है। अपने डेस्टिनेशन पर ट्रांसमिट होने वाले डेटा को नेटवर्क से हटा दिया जाता है। डेटा भी बाहरी रूप से नेटवर्क में आ सकता है, और <math>A_n^{(c)}(t)</math> स्लॉट टी पर नोड एन में आने वाले नए डेटा की मात्रा के रूप में परिभाषित किया गया है जो अंततः होना चाहिए
-नोड सी को वितरित किया जाएगा।
-होने देना <math>\mu_{ab}(t)</math> स्लॉट टी पर लिंक (ए, बी) पर नेटवर्क द्वारा उपयोग की जाने वाली ट्रांसमिशन दर हो, यह वर्तमान स्लॉट पर नोड ए से नोड बी में स्थानांतरित किए जा सकने वाले डेटा की मात्रा का प्रतिनिधित्व करता है। होने देना <math>(\mu_{ab}(t))</math> संचरण दर मैट्रिक्स हो। इन संचरण दरों को संभवतः समय-भिन्न विकल्पों के एक सेट के भीतर चुना जाना चाहिए। विशेष रूप से,
+मान लें <math>\mu_{ab}(t)</math> व्याकरणिक स्थान t पर लिंक (a,b) पर नेटवर्क द्वारा उपयोग की जाने वाली संचारण दर है, जो वर्तमान व्याकरणिक स्थान पर बिंदु a से बिंदु b में स्थानांतरित किए जा सकने वाले डेटा की मात्रा का प्रतिनिधित्व करती है। मान लें <math>(\mu_{ab}(t))</math> संचरण दर मैट्रिक्स है। इन संचरण दरों को संभवतः समय-भिन्न विकल्पों के समुच्चय के भीतर चयन किया जाना चाहिए। विशेष रूप से, नेटवर्क में समय-भिन्न चैनल और बिंदु गतिशीलता हो सकती है, और यह प्रत्येक व्याकरणिक स्थान की संचरण क्षमताओं को प्रभावित कर सकती है। इसे मॉडल करने के लिए, मान लें S(t) नेटवर्क की सांस्थितिकी स्थिति का प्रतिनिधित्व करता है, जो संचरण को प्रभावित करने हेतु व्याकरणिक स्थान t पर नेटवर्क के गुणधर्मों को प्रग्रहण करें। मान लें <math>\Gamma_{S(t)}</math> सांस्थितिकी स्थिति S(t) के अंतर्गत उपलब्ध संचरण दर मैट्रिक्स विकल्पों के समुच्चय का प्रतिनिधित्व करते हैं। प्रत्येक व्याकरणिक स्थान t, नेटवर्क नियंत्रक S(t) का निरीक्षण करते हैं और समुच्चय <math>\Gamma_{S(t)}</math> के भीतर संचरण दरों <math>(\mu_{ab}(t))</math> का चयन करता है। किस <math>(\mu_{ab}(t))</math> मैट्रिक्स को प्रत्येक व्याकरणिक स्थान t पर चयन किया जाए इस विकल्प को आगामी उपखंड में वर्णित किया गया है।
-नेटवर्क में समय-भिन्न चैनल और नोड हो सकते हैं
-गतिशीलता, और यह इसकी संचरण क्षमताओं को हर स्लॉट को प्रभावित कर सकता है।
-इसे मॉडल करने के लिए, एस (टी) नेटवर्क की टोपोलॉजी स्थिति का प्रतिनिधित्व करते हैं, जो कैप्चर करता है
-स्लॉट टी पर नेटवर्क के गुण जो ट्रांसमिशन को प्रभावित करते हैं। होने देना <math>\Gamma_{S(t)}</math> सेट का प्रतिनिधित्व करें
-टोपोलॉजी राज्य एस (टी) के तहत उपलब्ध संचरण दर मैट्रिक्स विकल्प।
-प्रत्येक स्लॉट टी, नेटवर्क नियंत्रक एस (टी) को देखता है और ट्रांसमिशन चुनता है
-दरें <math>(\mu_{ab}(t))</math> सेट के भीतर <math>\Gamma_{S(t)}</math>.
-जिसका चुनाव <math>(\mu_{ab}(t))</math> आव्यूह
-प्रत्येक स्लॉट टी पर चयन करने के लिए अगले उपधारा में वर्णित किया गया है।
-यह समय-भिन्न नेटवर्क मॉडल पहली बार मामले के लिए विकसित किया गया था जब प्रत्येक स्लॉट टी को चैनल राज्य मैट्रिक्स के सामान्य कार्यों और बिजली आवंटन मैट्रिक्स द्वारा निर्धारित किया गया था।<ref name=neely-power-network-jsac/>  मॉडल का उपयोग तब भी किया जा सकता है जब दरें अन्य नियंत्रण निर्णयों द्वारा निर्धारित की जाती हैं, जैसे सर्वर आवंटन, उप-बैंड चयन, कोडिंग प्रकार, और इसी तरह। यह मानता है कि सहायक संचरण दर ज्ञात हैं और कोई संचरण त्रुटि नहीं है। बहु-रिसीवर विविधता के माध्यम से वायरलेस प्रसारण लाभ का फायदा उठाने वाले नेटवर्क सहित संभाव्य चैनल त्रुटियों वाले नेटवर्क के लिए बैकप्रेशर रूटिंग के विस्तारित फॉर्मूलेशन का उपयोग किया जा सकता है।<ref name=neely-divbar-journal>M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, no. 5, pp. 862-881, July 2009.</ref>
+यह समय-भिन्न नेटवर्क मॉडल सर्वप्रथम उस स्थिति के लिए विकसित किया गया था जब प्रत्येक व्याकरणिक स्थान t के संचरण दरों को चैनल स्थिति आव्यूह और विद्युत् आवंटन आव्यूह के सामान्य कार्यों द्वारा निर्धारित किया गया था।<ref name=neely-power-network-jsac/> मॉडल का उपयोग तब भी किया जा सकता है जब दरें अन्य नियंत्रण निर्णयों जैसे सर्वर आवंटन, उप-बंध चयन, कोडिंग प्रकार और इत्यादि द्वारा निर्धारित की जाती हैं। यह अभिगृहीत करता है कि सहायक संचरण दर ज्ञात हैं और कोई संचरण त्रुटि नहीं है। बहु-रिसीवर विविधता के माध्यम से वायरलेस प्रसारण लाभ का समुपयोजन करने वाले नेटवर्क सहित संभाव्य चैनल त्रुटियों वाले नेटवर्क के लिए पश्चदाब परिसंचरण के विस्तारित सूत्रीकरण का उपयोग किया जा सकता है।<ref name=neely-divbar-journal>M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, no. 5, pp. 862-881, July 2009.</ref>
-=== बैकप्रेसर नियंत्रण निर्णय ===
+=== पश्चदाब नियंत्रण निर्णय ===
-प्रत्येक स्लॉट टी बैकप्रेशर नियंत्रक एस (टी) को देखता है और निम्नलिखित 3 चरणों का पालन करता है:
+प्रत्येक व्याकरणिक स्थान t पश्चदाब नियंत्रक S(t) का निरीक्षण करता है और निम्नलिखित 3 चरणों का पालन करता है:
-* सबसे पहले, प्रत्येक लिंक (ए, बी) के लिए, यह एक इष्टतम वस्तु का चयन करता है <math>c_{ab}^{opt}(t)</math> उपयोग करने के लिए।
+* सर्वप्रथम, प्रत्येक सम्बंध (a, b) के लिए, यह उपयोग के लिए इष्टतम पण्य <math>c_{ab}^{opt}(t)</math> का चयन करता है।
-* अगला, यह निर्धारित करता है कि क्या <math>(\mu_{ab}(t))</math> मैट्रिक्स में <math>\Gamma_{S(t)}</math> उपयोग करने के लिए।
+* इसके उपरांत, यह निर्धारित करता है कि <math>\Gamma_{S(t)}</math> में क्या  <math>(\mu_{ab}(t))</math>मैट्रिक्स का उपयोग किया जा सकता है।
-* अंत में, यह वस्तु की मात्रा निर्धारित करता है <math>c_{ab}^{opt}(t)</math> यह लिंक (ए, बी) पर संचारित होगा (ज्यादा से ज्यादा <math>\mu_{ab}(t)</math>, लेकिन संभवतः कुछ मामलों में कम हो रहा है)।
+* अंत में, यह पण्य  <math>c_{ab}^{opt}(t)</math> की मात्रा निर्धारित करता है जो यह लिंक (a, b) पर संचारित करेगा (अधिकतम <math>\mu_{ab}(t)</math> पर लेकिन संभवतः कुछ स्थितियों में न्यूनतम पर होता है)।
-==== इष्टतम वस्तु का चयन ====
+==== इष्टतम पण्य का चयन ====
-प्रत्येक नोड अपनी कतार के बैकलॉग और अपने वर्तमान में बैकलॉग को देखता है
+प्रत्येक बिंदु अपने स्वयं के पंक्तिबद्ध संचित कार्य और अपने वर्तमान प्रतिवेशी में संचित कार्य का निरीक्षण करता है। बिंदु a का वर्तमान प्रतिवेशी बिंदु b है इस प्रकार कि वर्तमान व्याकरणिक स्थान पर एक गैर-शून्य संचरण दर <math>\mu_{ab}(t)</math>  का चयन करना संभव है। इस प्रकार, प्रतिवेशियों को समुच्चय <math>\Gamma_{S(t)}</math>द्वारा निर्धारित किया जाता है। चरम स्थिति में, एक बिंदु में प्रतिवेशी के रूप में सभी N-1 अन्य बिंदु हो सकते हैं। यद्यपि, समुच्चय <math>\Gamma_{S(t)}</math> का उपयोग करना सामान्य है जो एक निश्चित भौगोलिक दूरी से अधिक पृथक्‍कृत किए गए बिंदुओं के मध्य प्रसारण को प्रतिबन्धित करते हैं, या जिनकी निश्चित सीमा के नीचे एक प्रसारित संकेत सामर्थ्य होगी। इस प्रकार, प्रतिवेशियों की संख्या N-1 से अधिक न्यून होना सामान्य है। चित्र संख्या 1 में उदाहरण संबंध कनेक्शन द्वारा प्रतिवेशियों का व्याख्या करते है, इस प्रकार कि बिंदु 5 में प्रतिवेशी 4 और 6 है। उदाहरण प्रतिवेशियों के मध्य सममित संबंध का सुझाव देता है (जिससे कि यदि 5, 4 का प्रतिवेशी है, तो 4, 5 का प्रतिवेशी है), लेकिन सामान्यतः ऐसा होना आवश्यक नहीं है।
-पड़ोसियों। नोड ए का वर्तमान पड़ोसी एक नोड बी है जैसे कि इसे चुनना संभव है
-गैर-शून्य संचरण दर <math>\mu_{ab}(t)</math> वर्तमान स्लॉट पर।
-इस प्रकार, पड़ोसियों को सेट द्वारा निर्धारित किया जाता है <math>\Gamma_{S(t)}</math>. चरम मामले में, ए
-नोड में पड़ोसी के रूप में सभी N − 1 अन्य नोड हो सकते हैं। हालाँकि, सेट का उपयोग करना आम है <math>\Gamma_{S(t)}</math> जो एक निश्चित भौगोलिक दूरी से अधिक अलग किए गए नोड्स के बीच प्रसारण को रोकते हैं,
-या जिसकी एक निश्चित सीमा के नीचे प्रचारित सिग्नल शक्ति होगी।
-इस प्रकार, यह पड़ोसियों की संख्या के लिए विशिष्ट है
-N − 1 से बहुत कम होना। चित्र 1 में उदाहरण पड़ोसियों को लिंक कनेक्शन द्वारा दिखाता है, ताकि नोड 5 में पड़ोसी 4 और 6 हों। उदाहरण पड़ोसियों के बीच एक सममित संबंध का सुझाव देता है (ताकि यदि 5, 4 का पड़ोसी हो, तो 4 5 का पड़ोसी है), लेकिन यह सामान्य रूप से मामला नहीं होना चाहिए।
 किसी दिए गए बिंदु के निकटवर्तियों का सम्मुच्चय बर्हिगामी सम्बंध के सम्मुच्चय को निर्धारित करता है जिसका उपयोग वह वर्तमान व्याकरणिक स्थान पर संचारण के लिए कर सकता है। प्रत्येक बर्हिगामी सम्बंध <math>(a,b)</math> के लिए इष्टतम पण्य <math>c_{ab}^{opt}(t)</math>  को पण्य <math>c \in \{1, \ldots, N\}</math> के रूप में परिभाषित किया गया है जो निम्नलिखित अवकल बैकलॉग मात्रा को अधिकतम करता है:
@@ Line 139: / Line 79: @@
 इष्टतम पण्य का चयन करने में किसी भी संबंध को स्वेच्छतः विघटित कर दिया जाता है।
-[[File:Bp-optimal-commodity-selection.jpg|frame|alt=A closeup of nodes 1 and 2. लिंक (1,2) पर भेजने के लिए इष्टतम वस्तु हरी वस्तु है। |अंजीर। 2: नोड 1 और 2 का क्लोजअप।
+[[File:Bp-optimal-commodity-selection.jpg|frame|alt=A closeup of nodes 1 and 2. लिंक (1,2) पर भेजने के लिए इष्टतम वस्तु हरी वस्तु है। |चित्र संख्या 2: बिंदु 1 और 2 का क्लोज़अप। निर्देशित सम्बंध (1,2) प्रेषित करने के लिए इष्टतम पण्य का रंग हरा है। दूसरी दिशा में प्रेषित करने के लिए इष्टतम पण्य (सम्बंध (2,1) पर)  का रंग नीला है।]]एक उदाहरण चित्र संख्या 2 में प्रदर्शित किया गया है। उदाहरण के लिए, वह कल्पना करता है कि प्रत्येक पंक्ति के पास वर्तमान में लाल, हरा और नीला केवल 3 पण्य हैं और इन्हें पैकेट की पूर्णांक इकाइयों में मापा जाता है। निर्देशित सम्बंध (1,2) पर ध्यान केंद्रित करने से अवकल बैकलॉग हैं:
-लिंक (1,2) पर भेजने के लिए इष्टतम वस्तु हरी वस्तु है। दूसरी दिशा में भेजने के लिए इष्टतम वस्तु (लिंक (2,1) पर) नीली वस्तु है।]]एक उदाहरण चित्र संख्या 2 में प्रदर्शित किया गया है। उदाहरण के लिए, वह कल्पना करता है कि प्रत्येक पंक्ति के पास वर्तमान में लाल, हरा और नीला केवल 3 पण्य हैं और इन्हें पैकेट की पूर्णांक इकाइयों में मापा जाता है। निर्देशित सम्बंध (1,2) पर ध्यान केंद्रित करने से अवकल बैकलॉग हैं:
 : <math>
 Q_1^{(\text{red})}(t) - Q_2^{(\text{red})}(t) = 1
@@ Line 235: / Line 174: @@
 ==== रूटिंग वेरिएबल्स को अंतिम रूप देना ====
-अब मान लीजिए कि इष्टतम वस्तुओं <math>c_{ab}^{opt}(t)</math>
+अब मान लीजिए कि प्रत्येक सम्बन्ध के लिए इष्टतम पण्य <math>c_{ab}^{opt}(t)</math> निर्धारित की गई हैं तथा संचरण दरें <math>(\mu_{ab}(t))</math> भी निर्धारित की गई हैं। यदि किसी दिए गए सम्बंध <math>(a,b)</math> पर इष्टतम पण्य के लिए अवकल बैकलॉग नकारात्मक है तो वर्तमान व्याकरणिक स्थान पर इस लिंक पर कोई डेटा स्थानांतरित नहीं किया जाता है। अन्यथा, नेटवर्क इस लिंक पर पण्य <math>c_{ab}^\mathrm{opt}(t)</math> डेटा की <math>\mu_{ab}(t)</math> इकाइयां प्रेषित करने की चेष्टा करता है। यह प्रत्येक सम्बंध <math>(a,b)</math> और प्रत्येक पण्य c के लिए परिसंचरण चर <math>\mu_{ab}^{(c)}(t)</math> को परिभाषित करके किया जाता है, जहाँ:
-प्रत्येक लिंक और ट्रांसमिशन के लिए निर्धारित किया गया है
-दरें <math>(\mu_{ab}(t))</math> भी निर्धारित किया गया है।
-यदि दिए गए लिंक (ए, बी) पर इष्टतम वस्तु के लिए अंतर बैकलॉग ऋणात्मक है, तो कोई डेटा स्थानांतरित नहीं किया जाता है
-वर्तमान स्लॉट पर इस लिंक पर। अन्यथा, नेटवर्क भेजने की पेशकश करता है <math>\mu_{ab}(t)</math> वस्तु की इकाइयाँ <math>c_{ab}^\mathrm{opt}(t)</math>
-इस लिंक पर डेटा। यह रूटिंग वेरिएबल्स को परिभाषित करके किया जाता है
-<math>\mu_{ab}^{(c)}(t)</math> प्रत्येक लिंक के लिए (ए, बी) और
-प्रत्येक वस्तु सी, जहां:
 : <math>
@@ Line 250: / Line 182: @@
                              \end{cases}
 </math>
-का मान है <math>\mu_{ab}^{(c)}(t)</math> लिंक पर कमोडिटी सी डेटा को दी जाने वाली ट्रांसमिशन दर का प्रतिनिधित्व करता है
+<math>\mu_{ab}^{(c)}(t)</math> का मान व्याकरणिक स्थान t पर संबन्ध <math>(a,b)</math> पर पण्य c डेटा को दी जाने वाली संचरण दर को दर्शाता है। हालाँकि, बिंदुओं में उनके सभी बहिर्गामी संबन्ध पर प्रस्तावित दरों पर संचारण का समर्थन करने के लिए एक विशेष पण्य पर्याप्त नहीं हो सकती है। यह बिंदु n और पण्य c के लिए व्याकरणिक स्थान t पर उत्पन्न होता है यदि:
-(ए, बी) स्लॉट टी पर।
-हालाँकि, ट्रांसमिशन का समर्थन करने के लिए नोड्स के पास एक निश्चित वस्तु के लिए पर्याप्त नहीं हो सकता है
-उनके सभी आउटगोइंग लिंक्स पर प्रस्तावित दरों पर। यह नोड एन और कमोडिटी सी के लिए स्लॉट टी पर उत्पन्न होता है यदि:
 : <math>
 Q_n^{(c)}(t) < \sum_{b=1}^N\mu_{nb}^{(c)}(t)
 </math>
-इस मामले में, सभी <math>Q_n^{(c)}(t)</math> डेटा भेजा जाता है, और अशक्त डेटा का उपयोग प्रस्तावित दरों के अप्रयुक्त भागों को भरने के लिए किया जाता है,
+इस स्थिति में, सभी <math>Q_n^{(c)}(t)</math> डेटा प्रेषित किया जाता है और शून्य डेटा का उपयोग प्रस्तावित दरों के अप्रयुक्त भागों का भरण करने के लिए किया जाता है, वास्तविक डेटा और शून्य डेटा को स्वेच्छतः संबंधित बहिर्गामी लिंक (प्रस्तावित दरों के अनुसार) पर आवंटित किया जाता है। इसे क्यू अंडरफ्लो स्थिति कहा जाता है। इस प्रकार के अधःप्रवाह नेटवर्क के प्रवाह क्षमता या स्थिरता गुणों को प्रभावित नहीं करते हैं। सहज रूप से, इसका कारण यह है कि अधःप्रवाह केवल तभी उत्पन्न होता है जब प्रेषणी बिंदु में कम मात्रा में बैकलॉग होता है जिसका अर्थ है कि बिंदु अस्थिरता के विपत्ति में नहीं है।
-संबंधित आउटगोइंग लिंक्स (प्रस्तावित दरों के अनुसार) पर मनमाने ढंग से वास्तविक डेटा और अशक्त डेटा आवंटित करना।
-इसे क्यू अंडरफ्लो स्थिति कहा जाता है। इस तरह के अंडरफ्लो थ्रूपुट को प्रभावित नहीं करते हैं
-या नेटवर्क की स्थिरता गुण। सहज रूप से, यह अंडरफ्लो के कारण है
-केवल तभी उत्पन्न होता है जब संचारण नोड में बैकलॉग की मात्रा कम होती है, जिसका अर्थ है
-नोड को अस्थिरता का खतरा नहीं है।
-=== देरी में सुधार ===
+=== विलंब में सुधार ===
-बैकप्रेशर एल्गोरिथम किसी भी पूर्व-निर्दिष्ट पथ का उपयोग नहीं करता है। रास्ते सीखे जाते हैं
+पश्चदाब कलनविधि किसी भी पूर्व-निर्दिष्ट पथ का उपयोग नहीं करता है। पथ गतिकत: अर्हत किए जाते हैं और विभिन्न पैकेटों के लिए भिन्न हो सकते हैं। विलंब अधिक विशाल हो सकता है, विशेष रूप से जब सिस्टम लघुभारित हो ताकि डेटा को गंतव्य की ओर प्रसारित करने के लिए पर्याप्त दबाव न हो। उदाहरण के लिए, मान लें कि एक पैकेट नेटवर्क में प्रवेश करता है और इसके अलावा कुछ भी प्रवेश नहीं करता है। यह पैकेट नेटवर्क के माध्यम से चक्कर लगा सकता है और अपने गंतव्य पर कभी आगमन नहीं हो सकता क्योंकि कोई दबाव प्रवणता नहीं बनती है। यह पश्चदाब की साद्यांत इष्टतमता या स्थिरता गुणों का खंडन नहीं करता है क्योंकि नेटवर्क में किसी भी समय अधिकतम एक पैकेट होता है और इसलिए तुच्छ रूप से स्थिर होता है (आगमन दर के समान 0 वितरण दर प्राप्त करना)।
-गतिशील रूप से, और विभिन्न पैकेटों के लिए भिन्न हो सकते हैं। देरी बहुत बड़ी हो सकती है, खासकर जब सिस्टम हल्का हो
-लोड किया गया ताकि गंतव्य की ओर डेटा पुश करने के लिए पर्याप्त दबाव न हो। उदाहरण के तौर पर, एक पैकेट मान लीजिए
-नेटवर्क में प्रवेश करता है, और कुछ भी कभी प्रवेश नहीं करता है। यह पैकेट नेटवर्क के माध्यम से चक्कर लगा सकता है और कभी नहीं पहुंचेगा
-अपने गंतव्य पर क्योंकि कोई दबाव प्रवणता नहीं बनती है। यह थ्रूपुट इष्टतमता या स्थिरता का खंडन नहीं करता है
-बैकप्रेशर के गुण क्योंकि नेटवर्क में किसी भी समय अधिकतम एक पैकेट होता है और इसलिए तुच्छ रूप से स्थिर होता है (0 की डिलीवरी दर प्राप्त करना, आगमन दर के बराबर)।
-पूर्व-निर्दिष्ट पथों के एक सेट पर बैकप्रेशर लागू करना भी संभव है। यह क्षमता क्षेत्र को प्रतिबंधित कर सकता है, लेकिन इन-ऑर्डर में सुधार कर सकता है
+पूर्व-निर्दिष्ट पथों के एक समुच्चय पर पश्चदाब परिपालित करना भी संभव है। यह क्षमता क्षेत्र को प्रतिबंधित कर सकता है, लेकिन व्यवस्थित वितरण और विलंब में सुधार कर सकता है। क्षमता क्षेत्र को प्रभावित किए बिना विलंब में सुधार करने का एक अन्य तरीका एक उन्नत संस्करण का उपयोग करना है जो लिंक भार को वांछित दिशाओं की ओर ले जाता है।<ref name=neely-power-network-jsac/> इस प्रकार के पूर्वाग्रह के अनुकरण ने महत्वपूर्ण विलंब सुधार दिखाया है।<ref name=neely-divbar-journal/><ref name=now/>ध्यान दें कि पंक्तिबद्ध में पश्चदाब के लिए क्रय क्रम मूल्यन विधि (एफआईएफओ) सेवा की आवश्यकता नहीं होती है। यह प्रेक्षित किया गया है कि क्रय उत्क्रम मूल्यन विधि (एलआईएफओ) सेवा संदेश प्रवाह को प्रभावित किए रहित, भारी बहुमत पैकेटों के लिए विलंब में नाटकीय रूप से सुधार कर सकती है।<ref name=moeller-LIFO>
-वितरण और देरी। क्षमता क्षेत्र को प्रभावित किए बिना देरी में सुधार करने का एक और तरीका है, एन्हांस्ड का उपयोग करना
-संस्करण जो पूर्वाग्रहों को वांछित दिशाओं की ओर जोड़ता है।<ref name=neely-power-network-jsac/>  इस तरह के पक्षपात के अनुकरण ने महत्वपूर्ण देरी में सुधार दिखाया है।<ref name=neely-divbar-journal/><ref name=now/>ध्यान दें कि बैकप्रेशर को कतारों में फर्स्ट-इन-फर्स्ट-आउट (FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स)) सेवा की आवश्यकता नहीं है। यह देखा गया है
-लास्ट-इन-फर्स्ट-आउट (एलआईएफओ (कंप्यूटिंग)) सेवा नाटकीय रूप से पैकेटों के विशाल बहुमत के लिए देरी में सुधार कर सकती है,
-थ्रूपुट को प्रभावित किए बिना।<ref name=moeller-LIFO>
 S. Moeller, A. Sridharan, B. Krishnamachari,  and O. Gnawali,
 "Routing Without Routes: The Backpressure Collection Protocol,"
@@ Line 287: / Line 202: @@
 Proc. WiOpt, May 2011.
 </ref>
-=== वितरित बैकप्रेशर ===
+=== वितरित पश्चदाब ===
-ध्यान दें कि एक बार संचरण दर <math>(\mu_{ab}(t))</math> चयनित किया गया है, रूटिंग निर्णय चर
+ध्यान दें कि संचरण दर <math>(\mu_{ab}(t))</math> चयनित होने पर, परिसंचरण निर्णय चर <math>\mu_{ab}^{(c)}(t)</math> सामान्य वितरित प्रक्रिया से गणना की जा सकती है, जहां प्रत्येक बिंदु को केवल स्वयं और उनके प्रतिवेशियों के मध्य पंक्तिबद्ध संचित कार्य विभेदक के ज्ञान की आवश्यकता होती है। यद्यपि, संचरण दरों के चयन के लिए समीकरण (1)-(2) में अधिकतम-भार समस्या के समाधान की आवश्यकता होती है।विशेष स्थिति में जब चैनल लांबिक होते हैं, कलनविधि में एक प्राकृतिक वितरित कार्यान्वयन होता है और प्रत्येक बिंदु पर पृथक निर्णयों को न्यूनतम करता है। यद्यपि, अधिकतम-भार समस्या अंतर चैनल व्यतिकरण वाले नेटवर्क के लिए एक केंद्रीकृत नियंत्रण समस्या है। केंद्रीकृत प्रक्रिया से भी इसे हल करना अधिक कठिन हो सकता है।
-<math>\mu_{ab}^{(c)}(t)</math>
-सरल वितरित तरीके से गणना की जा सकती है, जहां प्रत्येक नोड को केवल ज्ञान की आवश्यकता होती है
-क्यू बैकलॉग अपने और अपने पड़ोसियों के बीच अंतर करता है। हालाँकि, संचरण दरों के चयन के लिए एक समाधान की आवश्यकता होती है
-Eq में अधिकतम वजन की समस्या। (1)-(2). विशेष मामले में जब चैनल ओर्थोगोनल होते हैं, एल्गोरिथ्म में एक प्राकृतिक वितरित कार्यान्वयन होता है और प्रत्येक नोड पर अलग-अलग निर्णयों को कम करता है। हालाँकि, अधिकतम-भार समस्या इंटर-चैनल हस्तक्षेप वाले नेटवर्क के लिए एक केंद्रीकृत नियंत्रण समस्या है। केंद्रीकृत तरीके से भी इसे हल करना बहुत मुश्किल हो सकता है।
-सिग्नल-टू-शोर-प्लस-हस्तक्षेप अनुपात (एसआईएनआर) द्वारा निर्धारित लिंक दरों के साथ हस्तक्षेप नेटवर्क के लिए एक वितरित दृष्टिकोण यादृच्छिककरण का उपयोग करके किया जा सकता है।<ref name=neely-power-network-jsac/>  प्रत्येक नोड बेतरतीब ढंग से प्रत्येक स्लॉट टी को प्रसारित करने का निर्णय लेता है (यदि यह वर्तमान में नहीं है तो एक अशक्त पैकेट को प्रेषित करता है
+सिग्नल-टू-नॉइज़-प्लस-इंटरफेरेंस अनुपात (एसआईएनआर) द्वारा निर्धारित लिंक दरों के साथ व्यतिकरण नेटवर्क के लिए एक वितरित दृष्टिकोण यादृच्छिककरण का उपयोग करके किया जा सकता है।<ref name=neely-power-network-jsac/> प्रत्येक बिंदु अव्यवस्थिततः प्रत्येक व्याकरणिक स्थान t को प्रसारित करने का निर्णय लेता है (यदि वर्तमान में प्रेषित करने के लिए पैकेट नहीं है तो "शून्य" पैकेट प्रेषण किया जाता है)। वास्तविक संचरण दर, और प्रेषित करने के लिए संबंधित वास्तविक पैकेट, 2-चरणीय हैंडशेक द्वारा निर्धारित किए जाते हैं: प्राथमिक चरण पर, अव्यवस्थिततः चयनित प्रेषक बिंदु वास्तविक संचरण के आनुपातिक संकेत सामर्थ्य के साथ एक पायलट संकेत प्रेषित करते हैं। द्वितीय चरण पर, सभी संभावित रिसीवर बिंदु परिणामी व्यतिकरण को मापते हैं और उस सूचना को पुनः प्रेषक को भेजते हैं। सभी आउटगोइंग लिंक (n, b) के लिए एसआईएनआर स्तर तब सभी बिंदु्स n के लिए ज्ञात होता है, और प्रत्येक बिंदु n इस सूचना के आधार पर अपने <math>\mu_{nb}(t)</math> और <math>(\mu_{nb}^{(c)}(t))</math> चरों के निर्णय ले सकते हैं।  परिणामी संदेश प्रवाह आवश्यक रूप से इष्टतम नहीं है। यद्यपि, अव्यवस्थित संचरण प्रक्रिया को चैनल स्थिति प्रक्रिया के एक भाग के रूप में देखा जा सकता है (किंतु अशक्त पैकेट अंडरफ़्लो के स्थितियों में भेजे जाते हैं, ताकि चैनल स्थिति प्रक्रिया पूर्व निर्णयों पर निर्भर न हो)। इसलिए, इस वितरित कार्यान्वयन का परिणामी संदेश प्रवाह सभी परिसंचरण और अनुसूचीयन कलनविधि के वर्ग पर इष्टतम है जो इस प्रकार के यादृच्छिक प्रसारण का उपयोग करते हैं।
-भेजने के लिए एक पैकेट है)। वास्तविक संचरण दर, और भेजने के लिए संबंधित वास्तविक पैकेट,
--स्टेप हैंडशेक द्वारा निर्धारित किया जाता है:
-पहले चरण में, बेतरतीब ढंग से चुने गए ट्रांसमीटर नोड सिग्नल की शक्ति के आनुपातिक के साथ एक पायलट सिग्नल भेजते हैं
-एक वास्तविक संचरण के लिए। दूसरे चरण पर,
-सभी संभावित रिसीवर नोड परिणामी हस्तक्षेप को मापते हैं और उस जानकारी को वापस भेजते हैं
-ट्रांसमीटर। सभी आउटगोइंग लिंक्स (एन, बी) के लिए एसआईएनआर स्तर तब सभी नोड्स एन के लिए जाना जाता है,
-और प्रत्येक नोड n तय कर सकता है
-इसका <math>\mu_{nb}(t)</math> और <math>(\mu_{nb}^{(c)}(t))</math> इस जानकारी के आधार पर चर।
-परिणामी थ्रूपुट आवश्यक रूप से इष्टतम नहीं है। हालाँकि, यादृच्छिक संचरण प्रक्रिया को चैनल राज्य प्रक्रिया के एक भाग के रूप में देखा जा सकता है (बशर्ते कि अशक्त पैकेट अंडरफ़्लो के मामलों में भेजे जाते हैं, ताकि चैनल राज्य प्रक्रिया पिछले निर्णयों पर निर्भर न हो)। इसलिए, इस वितरित कार्यान्वयन का परिणामी थ्रूपुट सभी रूटिंग और शेड्यूलिंग एल्गोरिदम के वर्ग पर इष्टतम है जो इस तरह के यादृच्छिक प्रसारण का उपयोग करते हैं।
-वैकल्पिक वितरित कार्यान्वयन को मोटे तौर पर दो वर्गों में बांटा जा सकता है:
+वैकल्पिक वितरित परिपालन को प्रायः दो वर्गों में विभाजित किया जा सकता है: कलनविधि की प्रथम श्रेणी अधिकतम-भार समस्या के निरंतर गुणक कारक अनुमानों पर विचार करती है, और निरंतर-कारक साद्यांत परिणाम उत्पन्न करती है। कलनविधि की द्वितीय श्रेणी समय के साथ अधिकतम-भार समस्या के समाधान को अद्यतन करने के आधार पर, अधिकतम-भार समस्या के योगात्मक अनुमानों पर विचार करती है।
-एल्गोरिद्म का प्रथम वर्ग अधिकतम-भार समस्या के लिए निरंतर गुणक कारक सन्निकटन पर विचार करता है,
-और निरंतर-कारक थ्रूपुट परिणाम प्राप्त करें। एल्गोरिदम की दूसरी श्रेणी अधिकतम वजन के लिए योगात्मक सन्निकटन पर विचार करती है
+इस द्वितीय श्रेणी में कलनविधि को स्थिर चैनल की स्थिति और दीर्घ (प्रायः गैर-बहुपद) अभिसरण समय की आवश्यकता हो सकती है, यद्यपि वे उपयुक्त धारणाओं के अंतर्गत अधिकतम साद्यांत प्राप्त कर सकते हैं।<ref name="modiano-distributed">
-समस्या, समय के साथ अधिकतम-वजन समस्या के समाधान को अद्यतन करने पर आधारित है। इस द्वितीय श्रेणी के एल्गोरिद्म को स्थैतिक चैनल की आवश्यकता प्रतीत होती है
-स्थितियां और लंबा (अक्सर गैर-बहुपद) अभिसरण समय, हालांकि वे अधिकतम थ्रूपुट प्राप्त कर सकते हैं
-उपयुक्त मान्यताओं के तहत।<ref name=modiano-distributed>
 E. Modiano, D. Shah, and G. Zussman, "Maximizing throughput in wireless networks via gossiping," Proc. ACM SIGMETRICS, 2006.
-</ref><ref name=jiang-walrand-book/><ref name=sno-text/>योगात्मक सन्निकटन अक्सर उपयोगी होते हैं
+</ref><ref name="jiang-walrand-book" /><ref name="sno-text" />अप्रचलित पंक्तिबद्ध संचित कार्य जानकारी के साथ परिपालित किए जाने पर पश्चदाब की इष्टतमता सिद्ध करने के लिए योगात्मक सन्निकटन प्रायः उपयोगी होते हैं (नीली पाठ का अभ्यास 4.10 देखें)।<ref name="sno-text" />
-आउट-ऑफ-डेट कतार बैकलॉग जानकारी के साथ कार्यान्वित किए जाने पर बैकप्रेशर की इष्टतमता साबित करने के लिए (नीली पाठ का अभ्यास 4.10 देखें)।<ref name=sno-text/>
 == लयपुनोव बहाव के माध्यम से गणितीय निर्माण ==
@@ Line 336: / Line 234: @@
 \text{(Eq. 6)} \qquad Q_n^{(c)}(t+1) \leq \max\left[Q_n^{(c)}(t) - \sum_{b=1}^N\mu_{nb}^{(c)}(t), 0\right] + \sum_{a=1}^N\mu_{an}^{(c)}(t) + A_n^{(c)}(t)
 </math>
-जहाँ <math>A_n^{(c)}(t)</math> नए पण्य c डेटा की यादृच्छिक मात्रा है जो वाह्य रूप से व्याकरणिक स्थान t पर बिंदु n पर आता है और <math>\mu_{nb}^{(c)}(t)</math> व्याकरणिक स्थान t से संबद्ध (एन, बी) पर पण्य c परिवहन के लिए आवंटित संचरण दर है। ध्यान दें कि <math>\mu_{nb}^{(c)}(t)</math> पण्य c डेटा की मात्रा से अधिक हो सकता है जो वस्तुतः व्याकरणिक स्थान t से संबद्ध (a,b) पर प्रसारित होता है। ऐसा इसलिए है क्योंकि बिंदु n में पर्याप्त संचित कार्य नहीं हो सकता है। इसी कारण से समीकरण (6) एक समानता की जगह एक असमानता है क्योंकि व्याकरणिक स्थान t पर बिंदु n के लिए पण्य c के वास्तविक अंतर्जात आगमन से <math>\sum_{a=1}^N\mu_{an}^{(c)}(t)</math> अधिक हो सकता है। समीकरण (6) की एक महत्वपूर्ण विशेषता यह है कि यद्यपि <math>\mu_{ab}^{(c)}(t)</math> निर्णय चर क्यू बैकलॉग से स्वतंत्र रूप से चुने गए हों।
+जहाँ <math>A_n^{(c)}(t)</math> नए पण्य c डेटा की यादृच्छिक मात्रा है जो वाह्य रूप से व्याकरणिक स्थान t पर बिंदु n पर आता है और <math>\mu_{nb}^{(c)}(t)</math> व्याकरणिक स्थान t से संबद्ध <math>(a,b)</math> पर पण्य c परिवहन के लिए आवंटित संचरण दर है। ध्यान दें कि <math>\mu_{nb}^{(c)}(t)</math> पण्य c डेटा की मात्रा से अधिक हो सकता है जो वस्तुतः व्याकरणिक स्थान t से संबद्ध <math>(a,b)</math> पर प्रसारित होता है। ऐसा इसलिए है क्योंकि बिंदु n में पर्याप्त संचित कार्य नहीं हो सकता है। इसी कारण से समीकरण (6) एक समानता की जगह एक असमानता है क्योंकि व्याकरणिक स्थान t पर बिंदु n के लिए पण्य c के वास्तविक अंतर्जात आगमन से <math>\sum_{a=1}^N\mu_{an}^{(c)}(t)</math> अधिक हो सकता है। समीकरण (6) की एक महत्वपूर्ण विशेषता यह है कि यद्यपि <math>\mu_{ab}^{(c)}(t)</math> निर्णय चर क्यू बैकलॉग से स्वतंत्र रूप से चुने गए हों।
 यह माना जाता है कि सभी व्याकरणिक स्थान t और सभी <math>c \in \{1, \ldots, N\}</math> के लिए <math>Q_c^{(c)}(t) =0</math> क्योंकि कोई क्रमित डेटा को स्वयं के लिए नियत नहीं करता है।
@@ Line 358: / Line 256: @@
 : <math>(\max[q - b, 0] + a)^2 \leq q^2 + b^2 + a^2 + 2q(a-b)</math>
-क्यू अद्यतन समीकरण (6) को अधिकोरन करके और उपरोक्त असमानता का उपयोग करके यह प्रदर्शित करना मुश्किल नहीं है कि सभी व्याकरणिक स्थान t के लिए तथा किसी भी एल्गोरिथ्म के अंतर्गत संचारण और परिसंचरण चर <math>(\mu_{ab}(t))</math>
+क्यू अद्यतन समीकरण (6) को अधिकोरन करके और उपरोक्त असमानता का उपयोग करके यह प्रदर्शित करना मुश्किल नहीं है कि सभी व्याकरणिक स्थान t के लिए तथा किसी भी कलनविधि के अंतर्गत संचारण और परिसंचरण चर <math>(\mu_{ab}(t))</math>
 और <math>(\mu_{ab}^{(c)}(t))</math> का चयन करने के लिए:<ref name="now" />
@@ Line 385: / Line 283: @@
 भार <math>Q_a^{(c)}(t) - Q_b^{(c)}(t)</math> को बिंदु a और b के मध्य पण्य c का वर्तमान अवकल बैकलॉग कहा जाता है। विचार यह है कि निर्णय चर <math>(\mu_{ab}^{(c)}(t))</math> का चयन किया जाए जिससे कि उपरोक्त भारित राशि को अधिकतम किया जा सके जहाँ भार अंतरात्मक बैकलॉग हैं। सहज रूप से इसका अर्थ है बड़े अंतर वाले बैकलॉग की दिशा में बड़ी दरों का आवंटन।
-जब कभी भी <math>Q_a^{(c)}(t) - Q_b^{(c)}(t) < 0</math> हो तो स्पष्ट रूप से <math>\mu_{ab}^{(c)}(t) = 0</math> का चयन करना चाहिए। इसके अतिरिक्त, किसी विशेष सम्बन्ध <math>(a,b)</math> के लिए दिए गए  <math>\mu_{ab}(t)</math> को यह प्रदर्शित करना मुश्किल नहीं है कि समीकरण (3) - (5) के अधीन इष्टतम <math>\mu_{ab}^{(c)}(t)</math> चयन निम्नानुसार निर्धारित किए गए हैं: सर्वप्रथम पण्य <math>c_{ab}^{opt}(t)\in\{1, \ldots, N\}</math> खोजें जो सम्बंध<math>(a,b)</math> के लिए अवकल बैकलॉग को अधिकतम करता है। यदि अधिकतमीकरण अवकल बैकलॉग सम्बंध <math>(a,b)</math> के लिए नकारात्मक है, तो सम्बंध <math>(a,b)</math> पर <math>c \in \{1, \ldots, N\}</math> सभी वस्तुओं के लिए <math>\mu_{ab}^{(c)}(t) =0</math> निर्दिष्ट करें। '''अन्यथा, पूरी लिंक दर आवंटित करें <math>\mu_{ab}(t)</math> कमोडिटी को <math>c_{ab}^{opt}(t)</math>, और इस लिंक पर अन्य सभी वस्तुओं के लिए शून्य दर।''' इस विकल्प के साथ यह इस प्रकार है:
+जब कभी भी <math>Q_a^{(c)}(t) - Q_b^{(c)}(t) < 0</math> हो तो स्पष्ट रूप से <math>\mu_{ab}^{(c)}(t) = 0</math> का चयन करना चाहिए। इसके अतिरिक्त, किसी विशेष सम्बन्ध <math>(a,b)</math> के लिए दिए गए  <math>\mu_{ab}(t)</math> को यह प्रदर्शित करना मुश्किल नहीं है कि समीकरण (3) - (5) के अधीन इष्टतम <math>\mu_{ab}^{(c)}(t)</math> चयन निम्नानुसार निर्धारित किए गए हैं: सर्वप्रथम पण्य <math>c_{ab}^{opt}(t)\in\{1, \ldots, N\}</math> खोजें जो सम्बंध<math>(a,b)</math> के लिए अवकल बैकलॉग को अधिकतम करता है। यदि अधिकतमीकरण अवकल बैकलॉग सम्बंध <math>(a,b)</math> के लिए नकारात्मक है, तो सम्बंध <math>(a,b)</math> पर <math>c \in \{1, \ldots, N\}</math> सभी वस्तुओं के लिए <math>\mu_{ab}^{(c)}(t) =0</math> निर्दिष्ट करें। अन्यथा, इस सम्बंध पर पण्य <math>c_{ab}^{opt}(t)</math> को पूर्ण लिंक दर <math>\mu_{ab}(t)</math> तथा अन्य सभी पण्य के लिए शून्य दर आवंटित करें। इस विकल्प के साथ यह इस प्रकार है:
 : <math>
@@ Line 403: / Line 301: @@
 \mathrm{Subject to: } (\mu_{ab}(t)) \in \Gamma_{S(t)}
 </math>
-उपरोक्त समस्या समीकरण (1)-(2) में अधिकतम भार समस्या के समान है। पश्चदाब एल्गोरिदम <math>(\mu_{ab}(t))</math> के लिए अधिकतम भार निर्णय का उपयोग करता है तथा तत्पश्चात उपरोक्त वर्णित अधिकतम अवकल बैकलॉग के माध्यम से संचरण चर <math>(\mu_{ab}^{(c)}(t))</math>का चयन करता है।
+उपरोक्त समस्या समीकरण (1)-(2) में अधिकतम भार समस्या के समान है। पश्चदाब एल्गोरिदम <math>(\mu_{ab}(t))</math> के लिए अधिकतम भार निर्णय का उपयोग करता है तथा तत्पश्चात उपरोक्त वर्णित अधिकतम अवकल बैकलॉग के माध्यम से संचरण चर <math>(\mu_{ab}^{(c)}(t))</math> का चयन करता है।
-'''बैकप्रेसर एल्गोरिथम की एक उल्लेखनीय संपत्ति यह है कि यह केवल देखी गई टोपोलॉजी स्थिति S(t) और क्यू बैकलॉग के आधार पर हर स्लॉट टी पर लालच से काम करता है। <math>\boldsymbol{Q}(t)</math> उस स्लॉट के लिए।''' इस प्रकार, इसे आगमन दर <math>(\lambda_n^{(c)})</math> या सांस्थिति अवस्था की संभावनाओं <math>\pi_S = Pr[S(t) = S]</math> के ज्ञान की आवश्यकता नहीं है।
+पश्चदाब कलनविधि का एक उल्लेखनीय गुण यह है कि यह केवल देखी गई सांस्थिति स्थिति S(t) के आधार पर व्याकरणिक स्थान टी पर लोलुपता से कार्य करता है और उस व्याकरणिक स्थान के लिए क्यू बैकलॉग <math>\boldsymbol{Q}(t)</math> पर कार्य करता है। इस प्रकार, इसे आगमन दर <math>(\lambda_n^{(c)})</math> या सांस्थिति अवस्था की संभावनाओं <math>\pi_S = Pr[S(t) = S]</math> के ज्ञान की आवश्यकता नहीं है।
-== प्रदर्शन विश्लेषण ==
+== निष्पादन विश्लेषण ==
-यह भाग पश्चदाब एल्गोरिथम की साद्यांत इष्टतमता को सिद्ध करता है।<ref name=now/><ref name = sno-text/>सरलता के लिए उस परिदृश्य पर विचार किया जाता है जहाँ घटनाएँ स्वतंत्र तथा व्याकरणिक स्थान पर समान रूप से वितरित (i.i.d.) होती हैं, हालाँकि समान एल्गोरिथ्म को गैर-i.i.d परिदृश्यों में कार्य करने के लिए प्रदर्शित किया जा सकता है (गैर-i.i.d. ऑपरेशन और सार्वभौमिक अनुसूचीकरण के अंतर्गत नीचे देखें)।
+यह भाग पश्चदाब एल्गोरिथम की साद्यांत इष्टतमता को सिद्ध करता है।<ref name=now/><ref name = sno-text/>सरलता के लिए उस परिदृश्य पर विचार किया जाता है जहाँ घटनाएँ स्वतंत्र तथा व्याकरणिक स्थान पर समान रूप से वितरित (i.i.d.) होती हैं, हालाँकि समान कलनविधि को गैर-i.i.d परिदृश्यों में कार्य करने के लिए प्रदर्शित किया जा सकता है (गैर-i.i.d. ऑपरेशन और सार्वभौमिक अनुसूचीकरण के अंतर्गत नीचे देखें)।
 === गतिक आगमन ===
@@ Line 422: / Line 320: @@
 === नेटवर्क क्षमता क्षेत्र ===
-मान लें कि टोपोलॉजी स्थिति S(t) i.i.d है। संभावनाओं के साथ स्लॉट्स पर <math>\pi_S = Pr[S(t)=S]</math>
+मान लें कि टोपोलॉजी स्थिति S(t) i.i.d है। संभावनाओं के साथ व्याकरणिक स्थान्स पर <math>\pi_S = Pr[S(t)=S]</math>
 (यदि एस (टी) वास्तविक मूल्यवान प्रविष्टियों वाले वैक्टरों के अनगिनत अनंत सेट में मान लेता है,
 तब <math>\pi_S</math> संभाव्यता वितरण है, संभाव्यता द्रव्यमान समारोह नहीं)।
-नेटवर्क के लिए एक सामान्य एल्गोरिद्म S(t) प्रत्येक स्लॉट t को देखता है और ट्रांसमिशन दरों को चुनता है <math>(\mu_{ab}(t))</math> और रूटिंग चर <math>(\mu_{ab}^{(c)}(t))</math> Eq में बाधाओं के अनुसार। (3) - (5)। नेटवर्क क्षमता क्षेत्र <math>\Lambda</math> सभी आगमन दर आव्यूहों के सेट का समापन है <math>(\lambda_n^{(c)})</math> जिसके लिए एक एल्गोरिथ्म मौजूद है जो नेटवर्क को स्थिर करता है। सभी कतारों की स्थिरता का अर्थ है कि नेटवर्क में ट्रैफ़िक की कुल इनपुट दर अपने गंतव्य तक पहुँचाए गए डेटा की कुल दर के समान है। यह दिखाया जा सकता है कि किसी भी आगमन दर मैट्रिक्स के लिए <math>(\lambda_n^{(c)})</math> क्षमता क्षेत्र में <math>\Lambda</math>, एक स्थिर और यादृच्छिक एल्गोरिदम है जो निर्णय चर चुनता है <math>(\mu_{ab}^*(t))</math> और <math>(\mu_{ab}^{*(c)}(t))</math>
+नेटवर्क के लिए एक सामान्य एल्गोरिद्म S(t) प्रत्येक व्याकरणिक स्थान t को देखता है और ट्रांसमिशन दरों को चुनता है <math>(\mu_{ab}(t))</math> और रूटिंग चर <math>(\mu_{ab}^{(c)}(t))</math> Eq में बाधाओं के अनुसार। (3) - (5)। नेटवर्क क्षमता क्षेत्र <math>\Lambda</math> सभी आगमन दर आव्यूहों के सेट का समापन है <math>(\lambda_n^{(c)})</math> जिसके लिए एक कलनविधि मौजूद है जो नेटवर्क को स्थिर करता है। सभी कतारों की स्थिरता का अर्थ है कि नेटवर्क में ट्रैफ़िक की कुल इनपुट दर अपने गंतव्य तक पहुँचाए गए डेटा की कुल दर के समान है। यह दिखाया जा सकता है कि किसी भी आगमन दर मैट्रिक्स के लिए <math>(\lambda_n^{(c)})</math> क्षमता क्षेत्र में <math>\Lambda</math>, एक स्थिर और यादृच्छिक एल्गोरिदम है जो निर्णय चर चुनता है <math>(\mu_{ab}^*(t))</math> और <math>(\mu_{ab}^{*(c)}(t))</math>
-प्रत्येक स्लॉट टी केवल एस (टी) पर आधारित है (और इसलिए क्यू बैकलॉग से स्वतंत्र)
+प्रत्येक व्याकरणिक स्थान टी केवल एस (टी) पर आधारित है (और इसलिए क्यू बैकलॉग से स्वतंत्र)
 जो सभी के लिए निम्नलिखित देता है <math>n \neq c</math>:<ref name=neely-power-network-jsac/><ref name=sno-text/>
@@ Line 441: / Line 339: @@
 === केवल-एस एल्गोरिदम की तुलना ===
-क्योंकि पश्चदाब एल्गोरिथ्म <math>\boldsymbol{Q}(t)</math> और S(t) प्रत्येक व्याकरणिक स्थान t को देखता है और बाध्य धारा समीकरण (7) के दाहिने हाथ की ओर कम करने के लिए <math>(\mu_{ab}(t))</math> और <math>(\mu_{ab}^{(c)}(t))</math> निर्णय का चयन करता है। हमें प्राप्त है:
+क्योंकि पश्चदाब कलनविधि <math>\boldsymbol{Q}(t)</math> और S(t) प्रत्येक व्याकरणिक स्थान t को देखता है और बाध्य धारा समीकरण (7) के दाहिने हाथ की ओर कम करने के लिए <math>(\mu_{ab}(t))</math> और <math>(\mu_{ab}^{(c)}(t))</math> निर्णय का चयन करता है। हमें प्राप्त है:
 : <math>
@@ Line 448: / Line 346: @@
 जहाँ <math>(\mu_{ab}^*(t))</math> और <math>(\mu_{ab}^{*(c)}(t))</math> कोई वैकल्पिक निर्णय हैं जो समीकरण (3) - (5) को संतुष्ट करते हैं जिसमें यादृच्छिक निर्णय सम्मिलित हैं।
-अब<math>(\lambda_n^{(c)}) \in \Lambda</math> मान लीजिए। तब एक केवल-S एल्गोरिथम उपस्थित होता है जो समीकरण (8) को संतुष्ट करता है। '''इसे समीकरण (10) के दाईं ओर यह देखते हुए प्लग करना कि इस केवल-S एल्गोरिथम के अंतर्गत <math>\boldsymbol{Q}(t)</math> अशर्त अपेक्षा (क्योंकि S(t) i.i.d. स्लॉट्स पर है और S-only एल्गोरिथम वर्तमान क्यू बैकलॉग से स्वतंत्र है) के समान है:'''
+अब<math>(\lambda_n^{(c)}) \in \Lambda</math> मान लीजिए। तब एक केवल-S एल्गोरिथम उपस्थित होता है जो समीकरण (8) को संतुष्ट करता है। इसे समीकरण (10) के दाईं ओर यह देखते हुए प्लग करना कि इस केवल-S एल्गोरिथम के अंतर्गत <math>\boldsymbol{Q}(t)</math> अशर्त अपेक्षा (क्योंकि S(t) आई.आई.डी. व्याकरणिक स्थान पर है और S-only एल्गोरिथम वर्तमान क्यू बैकलॉग से स्वतंत्र है) के समान है, प्राप्त:
 : <math>
@@ Line 457: / Line 355: @@
 \lim_{t\rightarrow\infty}  \frac{Q_n^{(c)}(t)}{t} = 0 \text{ with probability 1}
 </math>
-'''औसत कतार आकार की एक मजबूत समझ के लिए, आगमन दर मान सकते हैं <math>(\lambda_n^{(c)})</math> के आंतरिक हैं <math>\Lambda</math>, तो वहाँ एक है <math>\epsilon>0</math> ऐसा है कि Eq। (9) किसी विकल्प के लिए है
+सामान्य पंक्ति आकार की सुदृढ़ ज्ञान के लिए, आगमन दर <math>(\lambda_n^{(c)})</math>, <math>\Lambda</math> के आंतरिक माना जा सकता हैं इसलिए वहाँ एक <math>\epsilon>0</math> है जो समीकरण (9) कुछ वैकल्पिक S-ओनली कलनविधि के लिए है। समीकरण (9) को समीकरण (10) के दाएँ पक्ष में लगाने पर यह प्राप्त होता है:
-एस-केवल एल्गोरिदम।''' समीकरण (9) को समीकरण (10) के दाएँ पक्ष में लगाने पर यह प्राप्त होता है:
 : <math>
@@ Line 468: / Line 365: @@
   \limsup_{t\rightarrow\infty} \frac{1}{t}\sum_{\tau=0}^{t-1} \sum_{n=1}^N \sum_{c=1}^N E\left[ Q_n^{(c)}(\tau) \right] \leq \frac{B}{\epsilon}
 </math>
-'''जैसे-जैसे क्षमता क्षेत्र <math>\Lambda</math> की सीमा से दूरी <math>\epsilon</math> शून्य हो जाती है, यह औसत पंक्ति आकार सीमा बढ़ जाती है।''' यह आगमन दर <math>\lambda</math> और सेवा दर <math>\mu</math> के साथ एकल M/M/1 पंक्ति के समान गुणात्मक प्रदर्शन है जहां औसत पंक्ति का आकार <math>1/\epsilon</math> के समानुपाती होता है जहां <math>\epsilon = \mu-\lambda</math> होता है।
+जैसे-जैसे क्षमता क्षेत्र <math>\Lambda</math> की सीमा से दूरी <math>\epsilon</math> शून्य हो जाती है, यह औसत पंक्ति का आकार बढ़ता जाता है। यह आगमन दर <math>\lambda</math> और सेवा दर <math>\mu</math> के साथ एकल M/M/1 पंक्ति के समान गुणात्मक प्रदर्शन है जहां औसत पंक्ति का आकार <math>1/\epsilon</math> के समानुपाती होता है जहां <math>\epsilon = \mu-\lambda</math> होता है।
-== उपरोक्त फॉर्मूलेशन के एक्सटेंशन ==
+== उपरोक्त सूत्रीकरण का विस्तार ==
-=== गैर-आई.आई.डी. ऑपरेशन और यूनिवर्सल शेड्यूलिंग ===
+=== गैर-आई.आई.डी. संचालन और सार्वभौमिक अनुसूचीयन ===
-उपरोक्त विश्लेषण i.i.d. सादगी के लिए गुण। हालांकि, वही बैकप्रेशर एल्गोरिद्म गैर-आई.आई.डी. स्थितियों। जब आगमन प्रक्रियाएँ और टोपोलॉजी अवस्थाएँ एर्गोडिक होती हैं, लेकिन जरूरी नहीं कि i.i.d., बैकप्रेशर तब भी सिस्टम को स्थिर करता है जब भी <math>(\lambda_n^{(c)}) \in \Lambda</math>.<ref name=neely-power-network-jsac/>  अधिक आम तौर पर, एक सार्वभौमिक शेड्यूलिंग दृष्टिकोण का उपयोग करते हुए, यह यादृच्छिक (संभवतः गैर-एर्गोडिक) नमूना पथों के लिए स्थिरता और इष्टतम गुणों की पेशकश करने के लिए दिखाया गया है।<ref name=neely-universal-scheduling-cdc2010>
+उपरोक्त विश्लेषण सरलता के लिए आई.आई.डी. गुणों को मानता है। हालाँकि समान पश्चदाब कलनविधि को गैर-आईआईडी स्थितियों में मजबूती से संचालित होते प्रदर्शित किया जा सकता है। जब आगमन प्रक्रियाएँ और सांस्थिति स्थितियाँ अभ्यतिप्राय होती हैं किन्तु आवश्यक नहीं कि आई.आई.डी. हो, जब भी <math>(\lambda_n^{(c)}) \in \Lambda</math> होता है तो पश्चदाब प्रणाली को स्थिर कर देता है।<ref name=neely-power-network-jsac/> सामान्यतः सार्वभौमिक अनुसूचीयन दृष्टिकोण का उपयोग करके इसे यादृच्छिक (संभवतः गैर-एर्गोडिक) प्रतिदर्श पथ के लिए स्थिरता और इष्टतमता गुण प्रदान करने के लिए प्रदर्शित किया गया है।<ref name=neely-universal-scheduling-cdc2010>
 M. J. Neely, "Universal Scheduling for Networks with Arbitrary Traffic, Channels,
 and Mobility," ''Proc. IEEE Conf. on Decision and Control (CDC)'', Atlanta, GA, Dec. 2010.
 </ref>
-=== यूटिलिटी ऑप्टिमाइज़ेशन और पेनल्टी मिनिमाइज़ेशन के साथ बैकप्रेशर ===
+=== उपयोगिता इष्टतमीकरण और दंड न्यूनतमकरण के साथ पश्चदाब ===
-[[ड्रिफ्ट प्लस पेनल्टी]]|ड्रिफ्ट-प्लस-पेनल्टी तकनीक के माध्यम से बैकप्रेशर को प्रवाह नियंत्रण के संयोजन के साथ काम करने के लिए दिखाया गया है।<ref name=neely-thesis/><ref name=neely-fairness-infocom05/><ref name=now/>  यह तकनीक लालच से बहाव की मात्रा और भारित जुर्माना अभिव्यक्ति को अधिकतम करती है। जुर्माना एक पैरामीटर V द्वारा भारित होता है जो एक प्रदर्शन ट्रेडऑफ़ निर्धारित करता है।
+पश्चदाब को [[ड्रिफ्ट प्लस पेनल्टी]] तकनीक के माध्यम से प्रवाह नियंत्रण के साथ मिलकर काम करते दिखाया गया है।<ref name=neely-thesis/><ref name=neely-fairness-infocom05/><ref name=now/>  यह तकनीक लोलुपता से बहाव के योग और भारित दंड अभिव्यक्ति को अधिकतम कर देती है। दंड को एक पैरामीटर V द्वारा भारित किया जाता है जो एक निष्पादन ट्रेडऑफ़ निर्धारित करता है। यह तकनीक सुनिश्चित करती है कि प्रवाह क्षमता उपयोगिता इष्टतमता के O(1/V) के भीतर है जबकि औसत विलंब O(V) है। इस प्रकार, उपयोगिता को औसत विलंब में संबंधित ट्रेडऑफ़ के साथ स्वेच्छतः से इष्टतमता के समीप धकेला जा सकता है। समान गुण औसत बिजली न्यूनीकरण और <ref name=neely-energy-it>
-यह तकनीक सुनिश्चित करती है कि थ्रूपुट उपयोगिता इष्टतमता के O(1/V) के भीतर है जबकि औसत विलंब O(V) है। इस प्रकार, उपयोगिता को मनमाने ढंग से इष्टतमता के करीब धकेला जा सकता है, औसत देरी में एक समान व्यापार के साथ। औसत शक्ति न्यूनीकरण के लिए समान गुण दिखाए जा सकते हैं<ref name=neely-energy-it>
 M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks,"
 ''IEEE Transactions on Information Theory'', vol. 52, no. 7, pp. 2915-2934,
-July 2006</ref>
+July 2006</ref>अधिक सामान्य नेटवर्क विशेषताओं के अनुकूलन के लिए दिखाए जा सकते हैं।<ref name=sno-text/>
-और अधिक सामान्य नेटवर्क विशेषताओं के अनुकूलन के लिए।<ref name=sno-text/>
-नेटवर्क उपयोगिता को अधिकतम करते हुए कतारों को स्थिर करने के लिए वैकल्पिक एल्गोरिदम विकसित किए गए हैं
+नेटवर्क उपयोगिता को अधिकतम करते हुए पंक्तियों को स्थिर करने के लिए वैकल्पिक एल्गोरिदम को द्रव मॉडल विश्लेषण,<ref name=stolyar-greedy/>संयुक्त द्रव विश्लेषण और लैग्रेंज गुणक विश्लेषण,<ref name=atilla-fairness>
-द्रव मॉडल विश्लेषण का उपयोग करना,<ref name=stolyar-greedy/>संयुक्त द्रव विश्लेषण और लैग्रेंज गुणक विश्लेषण,<ref name=atilla-fairness>
 A. Eryilmaz and R. Srikant, "Fair Resource Allocation in Wireless Networks using Queue-Length-Based Scheduling
 and Congestion Control," Proc. IEEE INFOCOM, March 2005.
@@ Line 494: / Line 388: @@
 X. Lin and N. B. Shroff, "Joint Rate Control and Scheduling in Multihop Wireless Networks,"
 Proc. of 43rd IEEE Conf. on Decision and Control, Paradise Island, Bahamas, Dec. 2004.
-</ref> और स्टोकेस्टिक ग्रेडिएंट्स।<ref name=lee-stochastic-scheduling>
+</ref> और स्टोकेस्टिक ग्रेडिएंट्स का उपयोग करके विकसित किया गया है।<ref name=lee-stochastic-scheduling>
 J. W. Lee, R. R. Mazumdar,  and N. B. Shroff, "Opportunistic Power Scheduling for Dynamic Multiserver Wireless Systems,"
 ''IEEE Transactions on Wireless Communications'', vol. 5, no.6, pp. 1506–1515, June 2006.
@@ Line 500: / Line 394: @@
 == यह भी देखें ==
-* एड हॉक ऑन-डिमांड डिस्टेंस वेक्टर रूटिंग
+* एओडीवी
-* [[विविधता बैकप्रेशर रूटिंग]] (DIVBAR)<ref name=neely-divbar-journal/>* ड्रिफ्ट प्लस पेनल्टी
+* [[विविधता बैकप्रेशर रूटिंग]] (डीआईवीबीएआर)<ref name=neely-divbar-journal/>
-* ExOR (वायरलेस नेटवर्क प्रोटोकॉल)
+* ईएक्सओआर
-* भौगोलिक मार्ग
+* भौगोलिक परिसंचरण
-* एड [[तदर्थ रूटिंग प्रोटोकॉल की सूची]]
+* [[तदर्थ रूटिंग प्रोटोकॉल की सूची]]
-* लायपुनोव अनुकूलन
+* लायपुनोव इष्टतमीकरण
 == संदर्भ ==
@@ Line 521: / Line 415: @@
 श्रेणी:रूटिंग एल्गोरिथम
-[[Category: Machine Translated Page]]
 [[Category:Created On 01/06/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]

Anonymous

Search

बैकप्रेशर रूटिंग: Difference between revisions

Latest revision as of 11:41, 3 July 2023

परिचय

उत्पत्ति

यह कैसे काम करता है

बहुपद पंक्तियन नेटवर्क मॉडल

पश्चदाब नियंत्रण निर्णय

इष्टतम पण्य का चयन

μab(t) आव्यूह का चयन करना

रूटिंग वेरिएबल्स को अंतिम रूप देना

विलंब में सुधार

वितरित पश्चदाब

लयपुनोव बहाव के माध्यम से गणितीय निर्माण

नियंत्रण निर्णय बाध्यताएं और पंक्ति अद्यतन समीकरण

लायपुनोव बहाव

राशियों का स्विचन करके धारा को सीमित करना

निष्पादन विश्लेषण

गतिक आगमन

नेटवर्क क्षमता क्षेत्र

केवल-एस एल्गोरिदम की तुलना

उपरोक्त सूत्रीकरण का विस्तार

गैर-आई.आई.डी. संचालन और सार्वभौमिक अनुसूचीयन

उपयोगिता इष्टतमीकरण और दंड न्यूनतमकरण के साथ पश्चदाब

यह भी देखें

संदर्भ

प्राथमिक स्रोत

Navigation

Wiki tools

Page tools

Other projects

Hidden categories

μ_ab(t) आव्यूह का चयन करना