ल्यपुनोव अनुकूलन: Difference between revisions

Latest revision as of 10:01, 22 August 2023

यह आलेख गतिशील प्रणालियों के लिए ल्यपुनोव अनुकूलन का वर्णन करता है। यह पंक्तिबद्ध नेटवर्क में इष्टतम नियंत्रण के लिए एक उदाहरण अनुप्रयोग देता है।

परिचय

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

कतारबद्ध नेटवर्क में इष्टतम नियंत्रण के अध्ययन के लिए ल्यपुनोव ड्रिफ्ट केंद्रीय है। एक विशिष्ट लक्ष्य कुछ प्रदर्शन उद्देश्यों को अनुकूलित करते हुए सभी नेटवर्क पंक्तियों को स्थिर करना है, जैसे औसत ऊर्जा को कम करना या औसत थ्रूपुट को अधिकतम करना। द्विघात ल्यपुनोव फलन के ड्रिफ्ट को कम करने से नेटवर्क स्थिरता के लिए बैकप्रेशर रूटिंग एल्गोरिदम बनता है, जिसे मैक्स-वेट एल्गोरिदम भी कहा जाता है।^[1]^[2] ल्यपुनोव ड्रिफ्ट में एक वेटेड पेनल्टी शब्द जोड़ने और राशि को कम करने से संयुक्त नेटवर्क स्थिरता और पेनल्टी न्यूनतमकरण के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम बनता है।^[3]^[4]^[5] ड्रिफ्ट-प्लस-पेनल्टी प्रक्रिया का उपयोग उत्तल अनुकूलन और रैखिक प्रोग्रामिंग के समाधान की गणना करने के लिए भी किया जा सकता है।^[6]

पंक्तिबद्ध नेटवर्क के लिए ल्यपुनोव ड्रिफ्ट

एक पंक्तिबद्ध नेटवर्क पर विचार करें जो सामान्यीकृत समय स्लॉट $t\in \{0,1,2,\ldots \}$ के साथ भिन्न-भिन्न समय में विकसित होता है। मान लीजिए कि नेटवर्क में $N$ पंक्तियां हैं, और समय $t$ पर पंक्ति बैकलॉग के सदिश को परिभाषित करें:

Q(t)=(Q_{1}(t),\ldots ,Q_{N}(t))

द्विघात ल्यपुनोव फलन

प्रत्येक स्लॉट $t$ के लिए, परिभाषित करें:

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

यह फलन नेटवर्क में कुल पंक्ति बैकलॉग का अदिश माप है। इसे पंक्ति स्थिति पर द्विघात ल्यपुनोव फलन कहा जाता है। ल्यपुनोव ड्रिफ्ट को इस फलन में स्लॉट से दूसरे स्लॉट में परिवर्तन के रूप में परिभाषित करें:

\Delta L(t)=L(t+1)-L(t)

लायपुनोव ड्रिफ्ट को बांधना

मान लीजिए कि पंक्ति बैकलॉग निम्नलिखित समीकरण के अनुसार समय के साथ बदलते हैं:

Q_{i}(t+1)=\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}

जहां स्लॉट $t$ पर पंक्ति $i$ में $a_{i}(t)$ और $b_{i}(t)$ क्रमशः आगमन और सेवा के अवसर हैं। इस समीकरण का उपयोग किसी भी स्लॉट t के लिए ल्यपुनोव ड्रिफ्ट पर सीमा की गणना करने के लिए किया जा सकता है:

Q_{i}(t+1)^{2}=\left(\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}\right)^{2}\leqslant \left(Q_{i}(t)+a_{i}(t)-b_{i}(t)\right)^{2}

इस असमानता को पुनर्व्यवस्थित करने, सभी $i,$ का योग करने और 2 से विभाजित करने पर यह प्राप्त होता है:

\Delta L(t)\leqslant B(t)+\sum _{i=1}^{N}Q_{i}(t)(a_{i}(t)-b_{i}(t))\qquad (Eq.1)

जहाँ:

B(t)={\frac {1}{2}}\sum _{i=1}^{N}\left(a_{i}(t)-b_{i}(t)\right)^{2}

मान लीजिए कि प्रत्येक पंक्ति में आगमन और सेवा के दूसरे क्षणों को सीमित कर दिया गया है, जिससे एक सीमित स्थिरांक $B>0$ हो जैसे कि सभी $t$ और सभी संभावित पंक्ति सदिश $Q(t)$ निम्नलिखित गुण रखती है:

\mathbb {E} [B(t)|Q(t)]\leqslant B

(समीकरण 1) की सशर्त अपेक्षाओं को लेने से सशर्त अपेक्षित ल्यपुनोव ड्रिफ्ट पर निम्नलिखित सीमाएँ उत्पन्न होती हैं:

\mathbb {E} [\Delta L(t)|Q(t)]\leqslant B+\sum _{i=1}^{N}Q_{i}(t)\mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\qquad (Eq.2)

मूलभूत लायपुनोव ड्रिफ्ट प्रमेय

अनेक स्थितियों में, नेटवर्क को नियंत्रित किया जा सकता है जिससे प्रत्येक पंक्ति में आगमन और सेवा के मध्य का अंतर कुछ वास्तविक संख्या $\varepsilon >0$ के लिए निम्नलिखित गुण को संतुष्ट कर सके:

\mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\leqslant -\varepsilon

यदि उपरोक्त सभी पंक्तियों $i,$ सभी स्लॉट $t,$ और सभी संभावित सदिश $Q(t)$ के लिए समान ईपीएसलॉन के लिए मान्य है, तब (समीकरण 2) निम्नलिखित ल्यपुनोव ड्रिफ्ट प्रमेय में प्रयुक्त ड्रिफ्ट की स्थिति को कम कर देता है। नीचे दिए गए प्रमेय को मार्कोव श्रृंखलाओं के लिए फोस्टर के प्रमेय पर भिन्नता के रूप में देखा जा सकता है। चूँकि, इसके लिए मार्कोव श्रृंखला संरचना की आवश्यकता नहीं है।

प्रमेय (ल्यपुनोव ड्रिफ्ट)-^[5]^[7] मान लीजिए कि स्थिरांक

B\geqslant 0,\varepsilon >0

हैं जैसे कि सभी

t

के लिए और सभी संभावित सदिश

Q(t)

सशर्त ल्यपुनोव ड्रिफ्ट संतुष्ट करता है:

\mathbb {E} [\Delta L(t)|Q(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}Q_{i}(t).

फिर सभी स्लॉट

t>0

के लिए नेटवर्क में समय का औसत पंक्ति आकार संतुष्ट करता है:

{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}.

प्रमाण- ड्रिफ्ट असमानता के दोनों पक्षों की अपेक्षाओं को ध्यान में रखते हुए और पुनरावृत्त अपेक्षाओं के नियम का उपयोग करने से परिणाम मिलता है:

\mathbb {E} [\Delta L(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]

$\tau \in \{0,1,\ldots ,t-1\}$ की उपरोक्त अभिव्यक्ति का योग करने और टेलीस्कोपिंग योग के नियम का उपयोग करने पर यह प्राप्त होता है:

\mathbb {E} [L(t)]-\mathbb {E} [L(0)]\leqslant Bt-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]

इस तथ्य का उपयोग करते हुए कि $L(t)$ गैर-ऋणात्मक है और उपरोक्त अभिव्यक्ति में शब्दों को पुनर्व्यवस्थित करने से परिणाम सिद्ध होता है।

पंक्तिबद्ध नेटवर्क के लिए ल्यपुनोव अनुकूलन

उपरोक्त अनुभाग के समान पंक्तिबद्ध नेटवर्क पर विचार करें। अब $p(t)$ को स्लॉट $t$ पर लगने वाले नेटवर्क पेनल्टी के रूप में परिभाषित करें। मान लीजिए कि लक्ष्य $p(t)$ के समय के औसत को कम करते हुए पंक्तिबद्ध नेटवर्क को स्थिर करना है। उदाहरण के लिए, समय की औसत शक्ति को कम करते हुए नेटवर्क को स्थिर करने के लिए, $p(t)$ को स्लॉट t पर नेटवर्क द्वारा खर्च की गई कुल विद्युत के रूप में परिभाषित किया जा सकता है।^[8] कुछ वांछनीय पुरस्कार $r(t),$ के औसत समय को अधिकतम करने की समस्याओं का समाधान करने के लिए, पेनल्टी को $p(t)=-r(t)$ परिभाषित किया जा सकता है। यह स्थिरता के अधीन संपूर्ण उपयोगिता में नेटवर्क को अधिकतम करने के लिए उपयोगी है।^[3]

पेनल्टी $p(t)$ के समय औसत को कम करते हुए नेटवर्क को स्थिर करने के लिए, नेटवर्क एल्गोरिदम को नियंत्रण क्रियाएं करने के लिए डिज़ाइन किया जा सकता है जो प्रत्येक स्लॉट $t$ पर निम्नलिखित ड्रिफ्ट-प्लस-पेनल्टी अभिव्यक्ति पर एक सीमा को कम कर देता है:^[5]

\Delta L(t)+Vp(t)

जहाँ $V$ गैर-ऋणात्मक भार है जिसे प्रदर्शन ट्रेडऑफ़ को प्रभावित करने के लिए इच्छानुसार चुना जाता है। इस दृष्टिकोण की प्रमुख विशेषता यह है कि इसमें सामान्यतः यादृच्छिक नेटवर्क घटनाओं (जैसे यादृच्छिक नौकरी आगमन या चैनल प्राप्ति) की संभावनाओं के ज्ञान की आवश्यकता नहीं होती है। $V=0$ चुनने से प्रत्येक स्लॉट में ड्रिफ्ट पर एक सीमा कम हो जाती है और, मल्टी-हॉप पंक्ति नेटवर्क में रूटिंग के लिए, टैसीयुलास और एफ़्रेमाइड्स द्वारा विकसित बैकप्रेशर रूटिंग एल्गोरिदम कम हो जाता है।^[1]^[2] $V>0$ का उपयोग करने और स्लॉट $t$ पर नेटवर्क पावर उपयोग के रूप में $p(t)$ को परिभाषित करने से नीली द्वारा विकसित नेटवर्क स्थिरता के अधीन औसत पावर को कम करने के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम प्राप्त होता है।^[8] $V>0$ का उपयोग करने और प्रवेश नियंत्रण उपयोगिता मीट्रिक के नकारात्मक के रूप में $p(t)$ का उपयोग करने से नीली, मोदियानो और ली द्वारा विकसित संयुक्त प्रवाह नियंत्रण और नेटवर्क रूटिंग के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम प्राप्त होता है।^[3]

इस संदर्भ में पिछले खंड के ल्यपुनोव ड्रिफ्ट प्रमेय का सामान्यीकरण महत्वपूर्ण है। व्याख्या की सरलता के लिए, मान लीजिए $p(t)$ नीचे से घिरा हुआ है:

p(t)\geqslant p_{\min }\quad \forall t\in \{0,1,2,...\}

उदाहरण के लिए, उपरोक्त उन स्थितियों में $p_{\min }=0$ से संतुष्ट है जब पेनल्टी $p(t)$ सदैव गैर-नकारात्मक होता है। मान लीजिए कि $p^{*}$ $p(t)$ के समय औसत के लिए वांछित लक्ष्य का प्रतिनिधित्व करता है। मान लीजिए $V$ एक पैरामीटर है जिसका उपयोग लक्ष्य को पूरा करने के महत्व को मापने के लिए किया जाता है। निम्नलिखित प्रमेय से पता चलता है कि यदि ड्रिफ्ट-प्लस-पेनल्टी की स्थिति पूरी हो जाती है, तब समय औसत पेनल्टी वांछित लक्ष्य से अधिकतम O(1/V) ऊपर होता है, जबकि औसत पंक्ति का आकार O(V) होता है। $V$ पैरामीटर को संबंधित पंक्ति आकार ट्रेडऑफ़ के साथ वांछित लक्ष्य के निकट (या नीचे) समय औसत पेनल्टी बनाने के लिए ट्यून किया जा सकता है।

प्रमेय (ल्यपुनोव अनुकूलन)- मान लीजिए कि स्थिरांक

\varepsilon >0,V,B\geqslant 0,

और

p^{*}

हैं, जैसे कि सभी

t

और सभी संभावित सदिश

Q(t)

के लिए निम्नलिखित ड्रिफ्ट-प्लस-पेनल्टी स्थिति प्रायुक्त होती है:

\mathbb {E} [\Delta L(t)+Vp(t)|Q(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}Q_{i}(t)

फिर सभी

t>0

के लिए समय औसत पेनल्टी और समय औसत पंक्ति आकार संतुष्ट करते हैं:

{\frac {1}{t}}\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]\leqslant p^{*}+{\frac {B}{V}}+{\frac {\mathbb {E} [L(0)]}{Vt}}

{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B+V(p^{*}-p_{\min })}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}

प्रमाण- प्रस्तुत ड्रिफ्ट-प्लस-पेनल्टी के दोनों पक्षों की अपेक्षाओं को लेते हुए और हमारे पास पुनरावृत्त अपेक्षाओं के कानून का उपयोग करते हुए:

\mathbb {E} [\Delta L(t)]+V\mathbb {E} [p(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]

उपरोक्त को पहले $t$ स्लॉट्स पर सारांशित करने और टेलीस्कोपिंग योगों के नियम का उपयोग करने से यह मिलता है:

{\begin{aligned}\mathbb {E} [L(t)]-\mathbb {E} [L(0)]+V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\\-\mathbb {E} [L(0)]+V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t&&{\text{Since }}L(t),Q_{i}(t)\geqslant 0\\V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant p^{*}Vt+Bt+\mathbb {E} [L(0)]\end{aligned}}

$Vt$ द्वारा विभाजित करने और पदों को पुनर्व्यवस्थित करने से समयबद्ध औसत पेनल्टी सिद्ध होता है। एक समान तर्क समय औसत पंक्ति आकार को बाध्य सिद्ध करता है।

संदर्भ

↑ ^1.0 ^1.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.
↑ ^2.0 ^2.1 L. Tassiulas and A. Ephremides, "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.
↑ ^3.0 ^3.1 ^3.2 M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005.
↑ 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.
↑ ^5.0 ^5.1 ^5.2 M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.
↑ M. J. Neely, "Distributed and Secure Computation of Convex Programs over a Network of Connected Processors," DCDIS Conf, Guelph, Ontario, July 2005
↑ E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan, "Bounds on Average Delays and Queue Size Averages and Variances in Input-Queued Cell-Based Switches", Proc. IEEE INFOCOM, 2001.
↑ ^8.0 ^8.1 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.

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

एम। जे. नीली. संचार और पंक्तिबद्ध प्रणालियों के अनुप्रयोग के साथ स्टोकेस्टिक नेटवर्क अनुकूलन, मॉर्गन और क्लेपूल, 2010।

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

[tass-radio-nets-1] 1.0 ^1.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.

[tass-server-allocation-2] 2.0 ^2.1 L. Tassiulas and A. Ephremides, "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.

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

[now-4] 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.

[sno-text-5] 5.0 ^5.1 ^5.2 M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.

[neely-dcdis-6] M. J. Neely, "Distributed and Secure Computation of Convex Programs over a Network of Connected Processors," DCDIS Conf, Guelph, Ontario, July 2005

[leonardi-7] E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan, "Bounds on Average Delays and Queue Size Averages and Variances in Input-Queued Cell-Based Switches", Proc. IEEE INFOCOM, 2001.

[neely-energy-it-8] 8.0 ^8.1 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 3: / Line 3: @@
 ==परिचय==
-ल्यपुनोव अनुकूलन एक गतिशील प्रणाली को उत्तम रूप से नियंत्रित करने के लिए [[ल्यपुनोव समारोह|ल्यपुनोव फलन]] के उपयोग को संदर्भित करता है। पद्धति स्थिरता के विभिन्न रूपों को सुनिश्चित करने के लिए ल्यपुनोव फलन का नियंत्रण सिद्धांत में बड़े स्तर पर उपयोग किया जाता है। किसी विशेष समय में किसी प्रणाली की स्थिति का वर्णन अधिकांश बहुआयामी सदिश द्वारा किया जाता है। ल्यपुनोव फलन इस बहु-आयामी स्थिति का एक गैर-ऋणात्मक अदिश माप है। सामान्यतः, जब पद्धति अवांछनीय स्थितियों की ओर बढ़ता है तो फलन को बड़े होने के लिए परिभाषित किया जाता है। नियंत्रण क्रियाएं करके पद्धति स्थिरता प्राप्त की जाती है जो ल्यपुनोव फलन को ऋणात्मक दिशा में शून्य की ओर ले जाती है।
+ल्यपुनोव अनुकूलन एक गतिशील प्रणाली को उत्तम रूप से नियंत्रित करने के लिए [[ल्यपुनोव समारोह|ल्यपुनोव फलन]] के उपयोग को संदर्भित करता है। पद्धति स्थिरता के विभिन्न रूपों को सुनिश्चित करने के लिए ल्यपुनोव फलन का नियंत्रण सिद्धांत में बड़े स्तर पर उपयोग किया जाता है। किसी विशेष समय में किसी प्रणाली की स्थिति का वर्णन अधिकांश बहुआयामी सदिश द्वारा किया जाता है। ल्यपुनोव फलन इस बहु-आयामी स्थिति का एक गैर-ऋणात्मक अदिश माप है। सामान्यतः, जब पद्धति अवांछनीय स्थितियों की ओर बढ़ता है तब फलन को बड़े होने के लिए परिभाषित किया जाता है। नियंत्रण क्रियाएं करके पद्धति स्थिरता प्राप्त की जाती है जो ल्यपुनोव फलन को ऋणात्मक दिशा में शून्य की ओर ले जाती है।
-कतारबद्ध नेटवर्क में इष्टतम नियंत्रण के अध्ययन के लिए ल्यपुनोव ड्रिफ्ट केंद्रीय है। एक विशिष्ट लक्ष्य कुछ प्रदर्शन उद्देश्यों को अनुकूलित करते हुए सभी नेटवर्क कतारों को स्थिर करना है, जैसे औसत ऊर्जा को कम करना या औसत थ्रूपुट को अधिकतम करना। द्विघात ल्यपुनोव फ़ंक्शन के ड्रिफ्ट को कम करने से नेटवर्क स्थिरता के लिए [[बैकप्रेशर रूटिंग]] एल्गोरिदम बनता है, जिसे मैक्स-वेट एल्गोरिदम भी कहा जाता है।<ref name="tass-radio-nets">L. Tassiulas and A. Ephremides,
+कतारबद्ध नेटवर्क में इष्टतम नियंत्रण के अध्ययन के लिए ल्यपुनोव ड्रिफ्ट केंद्रीय है। एक विशिष्ट लक्ष्य कुछ प्रदर्शन उद्देश्यों को अनुकूलित करते हुए सभी नेटवर्क पंक्तियों को स्थिर करना है, जैसे औसत ऊर्जा को कम करना या औसत थ्रूपुट को अधिकतम करना। द्विघात ल्यपुनोव फलन के ड्रिफ्ट को कम करने से नेटवर्क स्थिरता के लिए [[बैकप्रेशर रूटिंग]] एल्गोरिदम बनता है, जिसे मैक्स-वेट एल्गोरिदम भी कहा जाता है।<ref name="tass-radio-nets">L. Tassiulas and A. Ephremides,
-"[https://drum.lib.umd.edu/bitstream/handle/1903/5346/TR_92-129.pdf?sequence=1 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.</ref><ref name="tass-server-allocation"> L. Tassiulas and A. Ephremides, "[https://drum.lib.umd.edu/bitstream/handle/1903/5345/TR_92-128.pdf?sequence=1&isAllowed=y Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity]," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.</ref> ल्यपुनोव ड्रिफ्ट में एक वेटेड पेनल्टी शब्द जोड़ने और राशि को कम करने से संयुक्त नेटवर्क स्थिरता और पेनल्टी न्यूनतमकरण के लिए [[ बहाव प्लस जुर्माना | ड्रिफ्ट-प्लस-पेनल्टी]] एल्गोरिदम बनता है।<ref name="neely-fairness-infocom05"> M. J. Neely, E. Modiano, and C. Li, "[https://www.researchgate.net/profile/Chih_Ping_Li/publication/221242398_Fairness_and_Optimal_Stochastic_Control_for_Heterogeneous_Networks/links/0a85e532265750bfc3000000.pdf Fairness and Optimal Stochastic Control for Heterogeneous Networks]," Proc. IEEE INFOCOM, March 2005.</ref><ref name="now"> L. Georgiadis, M. J. Neely, and L. Tassiulas, "[https://www.nowpublishers.com/article/DownloadSummary/NET-001 Resource Allocation and Cross-Layer Control in Wireless Networks]," ''Foundations and Trends in Networking'', vol. 1, no. 1, pp. 1-149, 2006.</ref><ref name="sno-text">M. J. Neely. ''[https://www.morganclaypool.com/doi/abs/10.2200/s00271ed1v01y201006cnt007 Stochastic Network Optimization with Application to Communication and Queueing Systems],'' Morgan & Claypool, 2010.</ref> ड्रिफ्ट-प्लस-पेनल्टी प्रक्रिया का उपयोग [[उत्तल अनुकूलन]] और [[रैखिक प्रोग्रामिंग]] के समाधान की गणना करने के लिए भी किया जा सकता है।<ref name="neely-dcdis">M. J. Neely, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.422.2447&rep=rep1&type=pdf Distributed and Secure Computation of Convex Programs over a Network of Connected Processors]," DCDIS Conf, Guelph, Ontario, July 2005</ref>
+"[https://drum.lib.umd.edu/bitstream/handle/1903/5346/TR_92-129.pdf?sequence=1 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.</ref><ref name="tass-server-allocation"> L. Tassiulas and A. Ephremides, "[https://drum.lib.umd.edu/bitstream/handle/1903/5345/TR_92-128.pdf?sequence=1&isAllowed=y Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity]," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.</ref> ल्यपुनोव ड्रिफ्ट में एक वेटेड पेनल्टी शब्द जोड़ने और राशि को कम करने से संयुक्त नेटवर्क स्थिरता और पेनल्टी न्यूनतमकरण के लिए [[ बहाव प्लस जुर्माना |ड्रिफ्ट-प्लस-पेनल्टी]] एल्गोरिदम बनता है।<ref name="neely-fairness-infocom05"> M. J. Neely, E. Modiano, and C. Li, "[https://www.researchgate.net/profile/Chih_Ping_Li/publication/221242398_Fairness_and_Optimal_Stochastic_Control_for_Heterogeneous_Networks/links/0a85e532265750bfc3000000.pdf Fairness and Optimal Stochastic Control for Heterogeneous Networks]," Proc. IEEE INFOCOM, March 2005.</ref><ref name="now"> L. Georgiadis, M. J. Neely, and L. Tassiulas, "[https://www.nowpublishers.com/article/DownloadSummary/NET-001 Resource Allocation and Cross-Layer Control in Wireless Networks]," ''Foundations and Trends in Networking'', vol. 1, no. 1, pp. 1-149, 2006.</ref><ref name="sno-text">M. J. Neely. ''[https://www.morganclaypool.com/doi/abs/10.2200/s00271ed1v01y201006cnt007 Stochastic Network Optimization with Application to Communication and Queueing Systems],'' Morgan & Claypool, 2010.</ref> ड्रिफ्ट-प्लस-पेनल्टी प्रक्रिया का उपयोग [[उत्तल अनुकूलन]] और [[रैखिक प्रोग्रामिंग]] के समाधान की गणना करने के लिए भी किया जा सकता है।<ref name="neely-dcdis">M. J. Neely, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.422.2447&rep=rep1&type=pdf Distributed and Secure Computation of Convex Programs over a Network of Connected Processors]," DCDIS Conf, Guelph, Ontario, July 2005</ref>
 == पंक्तिबद्ध नेटवर्क के लिए ल्यपुनोव ड्रिफ्ट ==
-पंक्तिबद्ध नेटवर्क पर विचार करें जो सामान्यीकृत समय स्लॉट के साथ अलग-अलग समय में विकसित होता है <math>t \in \{0, 1, 2, \ldots\}.</math> मान लीजिए कि वहाँ हैं <math>N</math> नेटवर्क में कतारें, और समय पर कतार बैकलॉग के सदिश को परिभाषित करें <math>t</math> द्वारा:
+एक पंक्तिबद्ध नेटवर्क पर विचार करें जो सामान्यीकृत समय स्लॉट <math>t \in \{0, 1, 2, \ldots\}</math> के साथ भिन्न-भिन्न समय में विकसित होता है। मान लीजिए कि नेटवर्क में <math>N</math> पंक्तियां हैं, और समय <math>t</math> पर पंक्ति बैकलॉग के सदिश को परिभाषित करें:
 :<math> Q(t) = (Q_1(t), \ldots, Q_N(t))</math>
@@ Line 18: / Line 18: @@
 ===द्विघात ल्यपुनोव फलन===
-प्रत्येक स्लॉट के लिए <math>t,</math> परिभाषित करना:
+प्रत्येक स्लॉट <math>t</math> के लिए, परिभाषित करें:
 :<math>L(t) = \frac{1}{2}\sum_{i=1}^N Q_i(t)^2 </math>
-यह फलन नेटवर्क में कुल कतार बैकलॉग का अदिश माप है। इसे कतार स्थिति पर द्विघात ल्यपुनोव फलन कहा जाता है। ल्यपुनोव ड्रिफ्ट को इस फलन में स्लॉट से दूसरे स्लॉट में परिवर्तन के रूप में परिभाषित करें:
+यह फलन नेटवर्क में कुल पंक्ति बैकलॉग का अदिश माप है। इसे पंक्ति स्थिति पर द्विघात ल्यपुनोव फलन कहा जाता है। ल्यपुनोव ड्रिफ्ट को इस फलन में स्लॉट से दूसरे स्लॉट में परिवर्तन के रूप में परिभाषित करें:
 :<math>\Delta L(t) = L(t+1) - L(t)</math>
@@ Line 28: / Line 28: @@
 ===लायपुनोव ड्रिफ्ट को बांधना===
-मान लीजिए कि कतार बैकलॉग निम्नलिखित समीकरण के अनुसार समय के साथ बदलते हैं:
+मान लीजिए कि पंक्ति बैकलॉग निम्नलिखित समीकरण के अनुसार समय के साथ बदलते हैं:
 :<math>Q_i(t+1) = \max \left \{ Q_i(t) + a_i(t) - b_i(t), 0 \right \}</math>
-कहाँ <math>a_i(t)</math> और <math>b_i(t)</math> कतार में क्रमशः आगमन और सेवा के अवसर हैं <math>i</math> स्लॉट पर <math>t.</math> इस समीकरण का उपयोग किसी भी स्लॉट टी के लिए ल्यपुनोव ड्रिफ्ट पर सीमा की गणना करने के लिए किया जा सकता है:
+जहां स्लॉट <math>t</math> पर पंक्ति <math>i</math> में <math>a_i(t)</math> और <math>b_i(t)</math> क्रमशः आगमन और सेवा के अवसर हैं। इस समीकरण का उपयोग किसी भी स्लॉट t के लिए ल्यपुनोव ड्रिफ्ट पर सीमा की गणना करने के लिए किया जा सकता है:
 :<math>Q_i(t+1)^2 = \left ( \max \left \{ Q_i(t) + a_i(t) - b_i(t), 0 \right \} \right )^2 \leqslant  \left (Q_i(t) + a_i(t) - b_i(t) \right)^2</math>
-इस असमानता को पुनर्व्यवस्थित करते हुए, सभी को संक्षेप में प्रस्तुत करें <math>i,</math> और 2 से विभाजित करने पर प्राप्त होता है:
+इस असमानता को पुनर्व्यवस्थित करने, सभी <math>i,</math> का योग करने और 2 से विभाजित करने पर यह प्राप्त होता है:
 :<math>\Delta L(t) \leqslant B(t) + \sum_{i=1}^N Q_i(t) (a_i(t) - b_i(t)) \qquad (Eq. 1)</math>
-कहाँ:
+जहाँ:
 :<math>B(t) = \frac{1}{2}\sum_{i=1}^N \left (a_i(t) - b_i(t) \right )^2</math>
-मान लीजिए कि प्रत्येक कतार में आगमन और सेवा के दूसरे क्षण सीमित हैं, ताकि सीमित स्थिरांक हो <math>B>0</math> ऐसा कि सभी के लिए <math>t</math> और सभी संभावित कतार वैक्टर <math>Q(t)</math> निम्नलिखित संपत्ति रखती है:
+मान लीजिए कि प्रत्येक पंक्ति में आगमन और सेवा के दूसरे क्षणों को सीमित कर दिया गया है, जिससे एक सीमित स्थिरांक <math>B>0</math> हो जैसे कि सभी <math>t</math> और सभी संभावित पंक्ति सदिश <math>Q(t)</math> निम्नलिखित गुण रखती है:
 :<math>\mathbb{E}[B(t) | Q(t)] \leqslant B</math>
@@ Line 48: / Line 48: @@
-===बुनियादी लायपुनोव ड्रिफ्ट प्रमेय===
+===मूलभूत लायपुनोव ड्रिफ्ट प्रमेय===
-कई मामलों में, नेटवर्क को नियंत्रित किया जा सकता है ताकि प्रत्येक कतार में आगमन और सेवा के बीच का अंतर कुछ वास्तविक संख्या के लिए निम्नलिखित संपत्ति को संतुष्ट कर सके <math>\varepsilon>0</math>:
+अनेक स्थितियों में, नेटवर्क को नियंत्रित किया जा सकता है जिससे प्रत्येक पंक्ति में आगमन और सेवा के मध्य का अंतर कुछ वास्तविक संख्या <math>\varepsilon>0</math> के लिए निम्नलिखित गुण को संतुष्ट कर सके:
 :<math>\mathbb{E}[a_i(t) - b_i(t) | Q(t)] \leqslant -\varepsilon</math>
-यदि उपरोक्त सभी कतारों के लिए समान ईपीएसलॉन को लागू करता है <math>i,</math> सभी स्लॉट <math>t,</math> और सभी संभावित वैक्टर <math>Q(t),</math> तब (समीकरण 2) निम्नलिखित ल्यपुनोव ड्रिफ्ट प्रमेय में प्रयुक्त ड्रिफ्ट की स्थिति को कम कर देता है। नीचे दिए गए प्रमेय को मार्कोव श्रृंखलाओं के लिए फोस्टर के प्रमेय पर भिन्नता के रूप में देखा जा सकता है। हालाँकि, इसके लिए मार्कोव श्रृंखला संरचना की आवश्यकता नहीं है।
+यदि उपरोक्त सभी पंक्तियों <math>i,</math> सभी स्लॉट <math>t,</math> और सभी संभावित सदिश <math>Q(t)</math> के लिए समान ईपीएसलॉन के लिए मान्य है, तब (समीकरण 2) निम्नलिखित ल्यपुनोव ड्रिफ्ट प्रमेय में प्रयुक्त ड्रिफ्ट की स्थिति को कम कर देता है। नीचे दिए गए प्रमेय को मार्कोव श्रृंखलाओं के लिए फोस्टर के प्रमेय पर भिन्नता के रूप में देखा जा सकता है। चूँकि, इसके लिए मार्कोव श्रृंखला संरचना की आवश्यकता नहीं है।
-:प्रमेय (ल्यपुनोव ड्रिफ्ट)।<ref name=sno-text/><ref name=leonardi>E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan, "[https://www.researchgate.net/profile/Emilio_Leonardi/publication/221244643_Bounds_on_Average_Delays_and_Queue_Size_Averages_and_Variances_in_Input-Queued_Cell-Based_Switches/links/546c9c490cf21e510f63ec2d/Bounds-on-Average-Delays-and-Queue-Size-Averages-and-Variances-in-Input-Queued-Cell-Based-Switches.pdf Bounds on Average Delays and Queue Size Averages and Variances in Input-Queued Cell-Based Switches]", Proc. IEEE INFOCOM, 2001.</ref> मान लीजिए कि स्थिरांक हैं <math>B\geqslant 0, \varepsilon>0</math> ऐसा कि सभी के लिए <math>t</math> और सभी संभावित वैक्टर <math>Q(t)</math> सशर्त ल्यपुनोव ड्रिफ्ट संतुष्ट करता है:
+:'''प्रमेय (ल्यपुनोव ड्रिफ्ट)-'''<ref name=sno-text/><ref name=leonardi>E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan, "[https://www.researchgate.net/profile/Emilio_Leonardi/publication/221244643_Bounds_on_Average_Delays_and_Queue_Size_Averages_and_Variances_in_Input-Queued_Cell-Based_Switches/links/546c9c490cf21e510f63ec2d/Bounds-on-Average-Delays-and-Queue-Size-Averages-and-Variances-in-Input-Queued-Cell-Based-Switches.pdf Bounds on Average Delays and Queue Size Averages and Variances in Input-Queued Cell-Based Switches]", Proc. IEEE INFOCOM, 2001.</ref> मान लीजिए कि स्थिरांक <math>B\geqslant 0, \varepsilon>0</math> हैं जैसे कि सभी <math>t</math> के लिए और सभी संभावित सदिश <math>Q(t)</math> सशर्त ल्यपुनोव ड्रिफ्ट संतुष्ट करता है:
 ::<math>\mathbb{E}[\Delta L(t)|Q(t)] \leqslant B - \varepsilon  \sum_{i=1}^N Q_i(t).</math>
-:फिर सभी स्लॉट के लिए <math>t>0</math> नेटवर्क में समय का औसत कतार आकार संतुष्ट करता है:
+:फिर सभी स्लॉट <math>t>0</math> के लिए नेटवर्क में समय का औसत पंक्ति आकार संतुष्ट करता है:
 ::<math>\frac{1}{t}\sum_{\tau=0}^{t-1} \sum_{i=1}^N \mathbb{E}[Q_i(\tau)] \leqslant \frac{B}{\varepsilon } + \frac{\mathbb{E}[L(0)]}{\varepsilon  t}.</math>
-सबूत। ड्रिफ्ट असमानता के दोनों पक्षों की अपेक्षाओं को ध्यान में रखते हुए और पुनरावृत्त अपेक्षाओं के नियम का उपयोग करने से परिणाम मिलता है:
+'''प्रमाण-''' ड्रिफ्ट असमानता के दोनों पक्षों की अपेक्षाओं को ध्यान में रखते हुए और पुनरावृत्त अपेक्षाओं के नियम का उपयोग करने से परिणाम मिलता है:
 :<math>\mathbb{E}[\Delta L(t)] \leqslant B - \varepsilon  \sum_{i=1}^N \mathbb{E}[Q_i(t)]</math>
-उपरोक्त अभिव्यक्ति को संक्षेप में प्रस्तुत करें <math>\tau \in \{0, 1, \ldots, t-1\}</math> और टेलीस्कोपिंग योग के नियम का उपयोग करने से प्राप्त होता है:
+<math>\tau \in \{0, 1, \ldots, t-1\}</math> की उपरोक्त अभिव्यक्ति का योग करने और टेलीस्कोपिंग योग के नियम का उपयोग करने पर यह प्राप्त होता है:
 :<math>\mathbb{E}[L(t)] - \mathbb{E}[L(0)] \leqslant Bt - \varepsilon \sum_{\tau=0}^{t-1}\sum_{i=1}^N \mathbb{E}[Q_i(\tau)]</math>
-इस तथ्य का उपयोग करते हुए <math>L(t)</math> गैर-ऋणात्मक है और उपरोक्त अभिव्यक्ति में शब्दों को पुनर्व्यवस्थित करने से परिणाम सिद्ध होता है।
+इस तथ्य का उपयोग करते हुए कि <math>L(t)</math> गैर-ऋणात्मक है और उपरोक्त अभिव्यक्ति में शब्दों को पुनर्व्यवस्थित करने से परिणाम सिद्ध होता है।
 == पंक्तिबद्ध नेटवर्क के लिए ल्यपुनोव अनुकूलन ==
-उपरोक्त अनुभाग के समान पंक्तिबद्ध नेटवर्क पर विचार करें। अब परिभाषित करें <math>p(t)</math> स्लॉट पर लगने वाले नेटवर्क जुर्माने के रूप में <math>t.</math> मान लीजिए कि लक्ष्य समय के औसत को कम करते हुए पंक्तिबद्ध नेटवर्क को स्थिर करना है <math>p(t).</math> उदाहरण के लिए, समय की औसत शक्ति को कम करते हुए नेटवर्क को स्थिर करने के लिए, <math>p(t)</math> इसे स्लॉट टी पर नेटवर्क द्वारा खर्च की गई कुल बिजली के रूप में परिभाषित किया जा सकता है।<ref name = neely-energy-it>M. J. Neely, "[http://www-bcf.usc.edu/~mjneely/pdf_papers/neely-energy-it.pdf Energy Optimal Control for Time Varying Wireless Networks]," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006.</ref> कुछ वांछनीय पुरस्कार के समय औसत को अधिकतम करने की समस्याओं का इलाज करना <math>r(t),</math> पेनल्टी परिभाषित किया जा सकता है <math>p(t) = -r(t).</math> यह स्थिरता के अधीन संपूर्ण उपयोगिता में नेटवर्क को अधिकतम करने के लिए उपयोगी है।<ref name=neely-fairness-infocom05/>
+उपरोक्त अनुभाग के समान पंक्तिबद्ध नेटवर्क पर विचार करें। अब <math>p(t)</math> को स्लॉट <math>t</math> पर लगने वाले नेटवर्क पेनल्टी के रूप में परिभाषित करें। मान लीजिए कि लक्ष्य <math>p(t)</math> के समय के औसत को कम करते हुए पंक्तिबद्ध नेटवर्क को स्थिर करना है। उदाहरण के लिए, समय की औसत शक्ति को कम करते हुए नेटवर्क को स्थिर करने के लिए, <math>p(t)</math> को स्लॉट t पर नेटवर्क द्वारा खर्च की गई कुल विद्युत के रूप में परिभाषित किया जा सकता है।<ref name = neely-energy-it>M. J. Neely, "[http://www-bcf.usc.edu/~mjneely/pdf_papers/neely-energy-it.pdf Energy Optimal Control for Time Varying Wireless Networks]," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006.</ref> कुछ वांछनीय पुरस्कार <math>r(t),</math> के औसत समय को अधिकतम करने की समस्याओं का समाधान करने के लिए, पेनल्टी को <math>p(t) = -r(t)</math>परिभाषित किया जा सकता है। यह स्थिरता के अधीन संपूर्ण उपयोगिता में नेटवर्क को अधिकतम करने के लिए उपयोगी है।<ref name=neely-fairness-infocom05/>
-जुर्माने के औसत समय को कम करते हुए नेटवर्क को स्थिर करना <math>p(t),</math> नेटवर्क एल्गोरिदम को नियंत्रण क्रियाएं करने के लिए डिज़ाइन किया जा सकता है जो निम्नलिखित ड्रिफ्ट प्लस पेनल्टी | ड्रिफ्ट-प्लस-पेनल्टी अभिव्यक्ति पर प्रत्येक स्लॉट पर सीमा को लालच से कम कर देता है <math>t</math>:<ref name="sno-text"/>
+पेनल्टी <math>p(t)</math> के समय औसत को कम करते हुए नेटवर्क को स्थिर करने के लिए, नेटवर्क एल्गोरिदम को नियंत्रण क्रियाएं करने के लिए डिज़ाइन किया जा सकता है जो प्रत्येक स्लॉट <math>t</math> पर निम्नलिखित ड्रिफ्ट-प्लस-पेनल्टी अभिव्यक्ति पर एक सीमा को कम कर देता है:<ref name="sno-text"/>
 :<math> \Delta L(t) + Vp(t)</math>
-कहाँ <math>V</math> गैर-ऋणात्मक भार है जिसे प्रदर्शन ट्रेडऑफ़ को प्रभावित करने के लिए इच्छानुसार चुना जाता है। इस दृष्टिकोण की प्रमुख विशेषता यह है कि इसमें सामान्यतः यादृच्छिक नेटवर्क घटनाओं (जैसे यादृच्छिक नौकरी आगमन या चैनल प्राप्ति) की संभावनाओं के ज्ञान की आवश्यकता नहीं होती है। का चयन <math>V=0</math> प्रत्येक स्लॉट में ड्रिफ्ट पर बाउंड को कम करने के लिए और मल्टी-हॉप कतार नेटवर्क में रूटिंग के लिए, टैसीयुलास और एफ़्रेमाइड्स द्वारा विकसित बैकप्रेशर रूटिंग एल्गोरिदम को कम करने के लिए।<ref name=tass-radio-nets/><ref name=tass-server-allocation/>का उपयोग करते हुए <math>V>0</math> और परिभाषित करना <math>p(t)</math> स्लॉट पर नेटवर्क पावर का उपयोग के रूप में <math>t</math> नीली द्वारा विकसित नेटवर्क स्थिरता के अधीन औसत शक्ति को कम करने के लिए ड्रिफ्ट प्लस पेनल्टी | ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम की ओर जाता है।<ref name=neely-energy-it/>का उपयोग करते हुए <math>V>0</math> और उपयोग कर रहे हैं <math>p(t)</math> प्रवेश नियंत्रण उपयोगिता मीट्रिक के ऋणात्मक होने के कारण नीली, मोदियानो और ली द्वारा विकसित संयुक्त प्रवाह नियंत्रण और नेटवर्क रूटिंग के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम होता है।<ref name=neely-fairness-infocom05/>
+जहाँ <math>V</math> गैर-ऋणात्मक भार है जिसे प्रदर्शन ट्रेडऑफ़ को प्रभावित करने के लिए इच्छानुसार चुना जाता है। इस दृष्टिकोण की प्रमुख विशेषता यह है कि इसमें सामान्यतः यादृच्छिक नेटवर्क घटनाओं (जैसे यादृच्छिक नौकरी आगमन या चैनल प्राप्ति) की संभावनाओं के ज्ञान की आवश्यकता नहीं होती है। <math>V=0</math> चुनने से प्रत्येक स्लॉट में ड्रिफ्ट पर एक सीमा कम हो जाती है और, मल्टी-हॉप पंक्ति नेटवर्क में रूटिंग के लिए, टैसीयुलास और एफ़्रेमाइड्स द्वारा विकसित बैकप्रेशर रूटिंग एल्गोरिदम कम हो जाता है।<ref name=tass-radio-nets/><ref name=tass-server-allocation/> <math>V>0</math> का उपयोग करने और स्लॉट <math>t</math> पर नेटवर्क पावर उपयोग के रूप में <math>p(t)</math> को परिभाषित करने से नीली द्वारा विकसित नेटवर्क स्थिरता के अधीन औसत पावर को कम करने के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम प्राप्त होता है।<ref name=neely-energy-it/> <math>V>0</math> का उपयोग करने और प्रवेश नियंत्रण उपयोगिता मीट्रिक के नकारात्मक के रूप में <math>p(t)</math> का उपयोग करने से नीली, मोदियानो और ली द्वारा विकसित संयुक्त प्रवाह नियंत्रण और नेटवर्क रूटिंग के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम प्राप्त होता है।<ref name=neely-fairness-infocom05/>
 इस संदर्भ में पिछले खंड के ल्यपुनोव ड्रिफ्ट प्रमेय का सामान्यीकरण महत्वपूर्ण है। व्याख्या की सरलता के लिए, मान लीजिए <math>p(t)</math> नीचे से घिरा हुआ है:
 :<math>p(t) \geqslant p_{\min}  \quad \forall t \in \{0, 1, 2, ...\}</math>
-उदाहरण के लिए, उपरोक्त से संतुष्ट हैं <math>p_{\min} = 0</math> ऐसे मामलों में जब जुर्माना <math>p(t)</math> सदैव गैर-ऋणात्मक होता है। होने देना <math>p^*</math> के समय औसत के लिए वांछित लक्ष्य का प्रतिनिधित्व करें <math>p(t).</math> होने देना <math>V</math> लक्ष्य को पूरा करने के महत्व को महत्व देने के लिए उपयोग किया जाने वाला पैरामीटर बनें। निम्नलिखित प्रमेय से पता चलता है कि यदि ड्रिफ्ट-प्लस-पेनल्टी की स्थिति पूरी हो जाती है, तो समय औसत जुर्माना वांछित लक्ष्य से अधिकतम O(1/V) ऊपर होता है, जबकि औसत कतार का आकार O(V) होता है। <math>V</math> h> पैरामीटर को संबंधित कतार आकार ट्रेडऑफ़ के साथ वांछित लक्ष्य के करीब (या नीचे) समय औसत जुर्माना बनाने के लिए ट्यून किया जा सकता है।
+उदाहरण के लिए, उपरोक्त उन स्थितियों में <math>p_{\min} = 0</math> से संतुष्ट है जब पेनल्टी <math>p(t)</math> सदैव गैर-नकारात्मक होता है। मान लीजिए कि <math>p^*</math> <math>p(t)</math> के समय औसत के लिए वांछित लक्ष्य का प्रतिनिधित्व करता है। मान लीजिए <math>V</math> एक पैरामीटर है जिसका उपयोग लक्ष्य को पूरा करने के महत्व को मापने के लिए किया जाता है। निम्नलिखित प्रमेय से पता चलता है कि यदि ड्रिफ्ट-प्लस-पेनल्टी की स्थिति पूरी हो जाती है, तब समय औसत पेनल्टी वांछित लक्ष्य से अधिकतम O(1/V) ऊपर होता है, जबकि औसत पंक्ति का आकार O(V) होता है। <math>V</math> पैरामीटर को संबंधित पंक्ति आकार ट्रेडऑफ़ के साथ वांछित लक्ष्य के निकट (या नीचे) समय औसत पेनल्टी बनाने के लिए ट्यून किया जा सकता है।
-:प्रमेय (ल्यपुनोव अनुकूलन)। मान लीजिए कि स्थिरांक हैं <math>\varepsilon >0, V, B \geqslant 0,</math> और <math>p^*</math> ऐसा कि सभी के लिए <math>t</math> और सभी संभावित वैक्टर <math>Q(t)</math> निम्नलिखित ड्रिफ्ट-प्लस-पेनल्टी शर्त रखती है:
+:'''प्रमेय (ल्यपुनोव अनुकूलन)-''' मान लीजिए कि स्थिरांक <math>\varepsilon >0, V, B \geqslant 0,</math> और <math>p^*</math> हैं, जैसे कि सभी <math>t</math> और सभी संभावित सदिश <math>Q(t)</math> के लिए निम्नलिखित ड्रिफ्ट-प्लस-पेनल्टी स्थिति प्रायुक्त होती है:
 ::<math>\mathbb{E}[\Delta L(t) + Vp(t) | Q(t)] \leqslant B + Vp^* - \varepsilon \sum_{i=1}^NQ_i(t)</math>
-:फिर सबके लिए <math>t>0</math> समय औसत जुर्माना और समय औसत कतार आकार संतुष्ट करते हैं:
+:फिर सभी <math>t>0</math> के लिए समय औसत पेनल्टी और समय औसत पंक्ति आकार संतुष्ट करते हैं:
 ::<math>\frac{1}{t}\sum_{\tau=0}^{t-1} \mathbb{E}[p(\tau)] \leqslant p^* + \frac{B}{V} + \frac{\mathbb{E}[L(0)]}{Vt}</math>
 ::<math>\frac{1}{t}\sum_{\tau=0}^{t-1} \sum_{i=1}^N \mathbb{E}[Q_i(\tau)] \leqslant \frac{B + V(p^* - p_{\min})}{\varepsilon} + \frac{\mathbb{E}[L(0)]}{\varepsilon t} </math>
-सबूत। प्रस्तुत ड्रिफ्ट-प्लस-पेनल्टी के दोनों पक्षों की अपेक्षाओं को लेते हुए और हमारे पास पुनरावृत्त अपेक्षाओं के कानून का उपयोग करते हुए:
+'''प्रमाण-''' प्रस्तुत ड्रिफ्ट-प्लस-पेनल्टी के दोनों पक्षों की अपेक्षाओं को लेते हुए और हमारे पास पुनरावृत्त अपेक्षाओं के कानून का उपयोग करते हुए:
 :<math>\mathbb{E}[\Delta L(t)] + V \mathbb{E}[p(t)] \leqslant B + Vp^* - \varepsilon  \sum_{i=1}^N \mathbb{E}[Q_i(t)]</math>
-उपरोक्त को पहले के ऊपर सारांशित करें <math>t</math> स्लॉट और टेलीस्कोपिंग योग के नियम का उपयोग करने से मिलता है:
+उपरोक्त को पहले <math>t</math> स्लॉट्स पर सारांशित करने और टेलीस्कोपिंग योगों के नियम का उपयोग करने से यह मिलता है:
 :<math>\begin{align}
@@ Line 96: / Line 96: @@
 V\sum_{\tau=0}^{t-1}\mathbb{E}[p(\tau)] &\leqslant p^* Vt + Bt + \mathbb{E}[L(0)]
 \end{align}</math>
-द्वारा विभाजित करना <math>Vt</math> और शर्तों को पुनर्व्यवस्थित करने से समयबद्ध औसत पेनल्टी सिद्ध होता है। समान तर्क समय औसत कतार आकार को बाध्य साबित करता है।
+<math>Vt</math> द्वारा विभाजित करने और पदों को पुनर्व्यवस्थित करने से समयबद्ध औसत पेनल्टी सिद्ध होता है। एक समान तर्क समय औसत पंक्ति आकार को बाध्य सिद्ध करता है।
 ==संबंधित लिंक==
-* ड्रिफ्ट प्लस जुर्माना
+* ड्रिफ्ट प्लस पेनल्टी
 * बैकप्रेशर रूटिंग
-* ल्यपुनोव समारोह
+* ल्यपुनोव फलन
 * फोस्टर का प्रमेय
 * [[नियंत्रण-ल्यपुनोव फ़ंक्शन|नियंत्रण-ल्यपुनोव फलन]]
@@ Line 115: / Line 115: @@
 श्रेणी:पंक्तिबद्ध सिद्धांत
-[[Category: Machine Translated Page]]
 [[Category:Created On 10/08/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]

Anonymous

Search

ल्यपुनोव अनुकूलन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:01, 22 August 2023

Contents

परिचय