बैकप्रेशर रूटिंग

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

परिचय

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

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

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

उत्पत्ति

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

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

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

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

चित्र संख्या 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 के संचरण दरों को चैनल स्थिति आव्यूह और विद्युत् आवंटन आव्यूह के सामान्य कार्यों द्वारा निर्धारित किया गया था। मॉडल का उपयोग तब भी किया जा सकता है जब दरें अन्य नियंत्रण निर्णयों जैसे सर्वर आवंटन, उप-बंध चयन, कोडिंग प्रकार और इत्यादि द्वारा निर्धारित की जाती हैं। यह अभिगृहीत करता है कि सहायक संचरण दर ज्ञात हैं और कोई संचरण त्रुटि नहीं है। बहु-रिसीवर विविधता के माध्यम से वायरलेस प्रसारण लाभ का समुपयोजन करने वाले नेटवर्क सहित संभाव्य चैनल त्रुटियों वाले नेटवर्क के लिए पश्चदाब परिसंचरण के विस्तारित सूत्रीकरण का उपयोग किया जा सकता है।

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

प्रत्येक व्याकरणिक स्थान 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)$

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

चित्र संख्या 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 वितरण दर प्राप्त करना)।

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

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

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

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

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

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

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

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

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

उपरोक्त खंड में वर्णित 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))$ का चयन करने के लिए:

${\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]$ के ज्ञान की आवश्यकता नहीं है।

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

यह भाग पश्चदाब एल्गोरिथम की साद्यांत इष्टतमता को सिद्ध करता है।सरलता के लिए उस परिदृश्य पर विचार किया जाता है जहाँ घटनाएँ स्वतंत्र तथा व्याकरणिक स्थान पर समान रूप से वितरित (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$:

${\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 से कम या उसके समान है। यह तथ्य इस धारणा के साथ है कि पंक्ति आगमन ने दूसरे क्षणों को सीमित कर दिया है, सभी नेटवर्क पंक्ति के लिए निम्नलिखित का अर्थ है:

$\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)$

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

$\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$ होता है तो पश्चदाब प्रणाली को स्थिर कर देता है। सामान्यतः सार्वभौमिक अनुसूचीयन दृष्टिकोण का उपयोग करके इसे यादृच्छिक (संभवतः गैर-एर्गोडिक) प्रतिदर्श पथ के लिए स्थिरता और इष्टतमता गुण प्रदान करने के लिए प्रदर्शित किया गया है।

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

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

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

यह भी देखें

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

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

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

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