जैक्सन नेटवर्क

{{more footnotes|date=June 2012}कतार सिद्धांत में, गणितीय संभाव्यता सिद्धांत के भीतर एक अनुशासन, एक जैक्सन नेटवर्क (कभी-कभी जैकसोनियन नेटवर्क) कतारबद्ध नेटवर्क का एक वर्ग है जहां संतुलन वितरण की गणना करना विशेष रूप से सरल है क्योंकि नेटवर्क में उत्पाद-रूप समाधान होता है। क्यूइंग सिद्धांत के सिद्धांत में यह पहला महत्वपूर्ण विकास था, और अन्य नेटवर्क में समान उत्पाद-रूप समाधानों की खोज के लिए प्रमेय के विचारों को सामान्य बनाना और लागू करना बहुत शोध का विषय रहा है, इंटरनेट के विकास में प्रयुक्त विचारों सहित। नेटवर्क की पहचान सबसे पहले जेम्स आर. जैक्सन ने की थी और उनका पेपर जर्नल मैनेजमेंट साइंस: ए जर्नल ऑफ द इंस्टीट्यूट फॉर ऑपरेशंस रिसर्च एंड द मैनेजमेंट साइंसेज के 'टेन मोस्ट इन्फ्लुएंशियल टाइटल्स ऑफ मैनेजमेंट साइंसेज फर्स्ट फिफ्टी इयर्स' में फिर से छपा था।

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

जैक्सन नेटवर्क जहां नौकरियों की एक सीमित आबादी एक बंद नेटवर्क के आसपास यात्रा करती है, उसके पास गॉर्डन-नेवेल प्रमेय द्वारा वर्णित एक उत्पाद-रूप समाधान भी है।

== एक जैक्सन नेटवर्क == के लिए आवश्यक शर्तें

m परस्पर जुड़ी कतारों के नेटवर्क को 'जैक्सन नेटवर्क' के रूप में जाना जाता है या जैकसोनियन नेटवर्क यदि यह निम्नलिखित शर्तों को पूरा करता है:

1. यदि नेटवर्क खुला है, नोड के लिए कोई भी बाहरी आगमन पॉसॉन प्रक्रिया बनाता है,
2. सभी सेवा समय घातीय रूप से वितरित किए जाते हैं और सभी कतारों में सेवा अनुशासन पहले आओ पहले पाओ वाला है,
3. कतार में सेवा पूरी करने वाला ग्राहक या तो संभावना के साथ किसी नई कतार j में चला जाएगा $P_{ij}$ या सिस्टम को संभाव्यता के साथ छोड़ दें $1-\sum _{j=1}^{m}P_{ij}$, जो एक खुले नेटवर्क के लिए क्यू के कुछ सबसेट के लिए गैर-शून्य है,
4. सभी कतारों का किराये का उपयोग एक से कम है।

प्रमेय

एम एम/एम/1 मॉडल | एम/एम/1 कतारों के खुले जैक्सन नेटवर्क में जहां किराये का उपयोग होता है $\rho _{i}$ प्रत्येक कतार में 1 से कम है, संतुलन राज्य संभाव्यता वितरण मौजूद है और राज्य के लिए $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ व्यक्तिगत कतार संतुलन वितरण के उत्पाद द्वारा दिया जाता है

$\pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].$

परिणाम $\pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})$ सी के साथ एम/एम/सी मॉडल स्टेशनों के लिए भी है_i सर्वर पर $i^{\text{th}}$ उपयोग की आवश्यकता के साथ स्टेशन $\rho _{i}<c_{i}$.

परिभाषा

एक खुले नेटवर्क में, दर के साथ पॉइसन प्रक्रिया के बाद नौकरियां बाहर से आती हैं $\alpha >0$. प्रत्येक आगमन को संभावना के साथ स्वतंत्र रूप से नोड j पर रूट किया जाता है $p_{0j}\geq 0$ और $\sum _{j=1}^{J}p_{0j}=1$. नोड I पर सेवा पूर्ण होने पर, एक कार्य संभाव्यता के साथ दूसरे नोड j पर जा सकता है $p_{ij}$ या संभाव्यता के साथ नेटवर्क छोड़ दें $p_{i0}=1-\sum _{j=1}^{J}p_{ij}$.

इसलिए हमारे पास नोड i के लिए समग्र आगमन दर है, $\lambda _{i}$, बाहरी आगमन और आंतरिक संक्रमण दोनों सहित:

$\lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)$

(चूंकि प्रत्येक नोड पर उपयोग 1 से कम है, और हम संतुलन वितरण यानी लंबे समय तक चलने वाले औसत व्यवहार को देख रहे हैं, j से i में संक्रमण की दर j पर आगमन दर के एक अंश से बंधी है और हम सेवा दर की उपेक्षा करते हैं $\mu _{j}$ ऊपरोक्त में।)

परिभाषित करना $a=(\alpha p_{0i})_{i=1}^{J}$, तो हम हल कर सकते हैं $\lambda =(I-P^{T})^{-1}a$.

पॉसों प्रक्रिया के बाद सभी कार्य प्रत्येक नोड को छोड़ देते हैं, और परिभाषित करते हैं $\mu _{i}(x_{i})$ जब वहाँ नोड मैं की सेवा दर के रूप में $x_{i}$ नोड i पर नौकरियां

होने देना $X_{i}(t)$ नोड i पर समय t पर नौकरियों की संख्या को निरूपित करें, और $\mathbf {X} =(X_{i})_{i=1}^{J}$. फिर का संतुलन वितरण $\mathbf {X}$, $\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$ संतुलन समीकरणों की निम्नलिखित प्रणाली द्वारा निर्धारित किया जाता है:

${\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}$

कहाँ $\mathbf {e} _{i}$ निरूपित करें $i^{\text{th}}$ इकाई वेक्टर।

प्रमेय

मान लीजिए स्वतंत्र यादृच्छिक चर का एक वेक्टर $(Y_{1},\ldots ,Y_{J})$ प्रत्येक के साथ $Y_{i}$ संभाव्यता द्रव्यमान कार्य के रूप में

$P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)$

कहाँ $M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)$. अगर $\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty$ अर्थात। $P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}$ अच्छी तरह से परिभाषित है, तो खुले जैक्सन नेटवर्क के संतुलन वितरण में निम्नलिखित उत्पाद रूप हैं:

$\pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).$

सभी के लिए $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$.⟩

Proof

यह समीकरण को सत्यापित करने के लिए पर्याप्त है $(2)$ संतुष्ट है। उत्पाद रूप और सूत्र (3) द्वारा, हमारे पास:

$\pi (\mathbf {x} )=\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)/\lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)\lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]$

इन्हें के दाईं ओर प्रतिस्थापित करना $(2)$ हम पाते हैं:

$\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\sum _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i}p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j}).\qquad (4)$

फिर प्रयोग करें $(1)$, अपने पास:

$\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j})=\sum _{j=1}^{J}[\sum _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}]\mu _{j}(x_{j})=\sum _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j}}{\lambda _{j}}}]\mu _{j}(x_{j}).$

उपरोक्त को प्रतिस्थापित करना $(4)$, अपने पास:

$\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}p_{i0}$

द्वारा सत्यापित किया जा सकता है $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$. इसलिए दोनों तरफ $(2)$ बराबर हैं।⟨

यह प्रमेय प्रत्येक नोड की राज्य-निर्भर सेवा दर की अनुमति देकर ऊपर दिखाए गए को बढ़ाता है। के वितरण से संबंधित है $\mathbf {X}$ स्वतंत्र चर के एक वेक्टर द्वारा $\mathbf {Y}$.

उदाहरण

एक तीन-नोड खुला जैक्सन नेटवर्क

मान लीजिए कि हमारे पास ग्राफ में दिखाया गया तीन-नोड जैक्सन नेटवर्क है, गुणांक हैं:

$\alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad$

$P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}{\text{ for all }}x_{i}>0$

फिर प्रमेय द्वारा, हम गणना कर सकते हैं:

$\lambda =(I-P^{T})^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin{bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix}2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}$

की परिभाषा के अनुसार $\mathbf {Y}$, अपने पास:

$P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}$

$P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}$

$P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}$

इसलिए प्रायिकता है कि प्रत्येक नोड पर एक कार्य है:

$\pi (1,1,1)={\frac {5}{6}}\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\cdot {\frac {1.25}{10}}\approx 0.00326$

चूंकि यहां सेवा दर राज्य पर निर्भर नहीं करती है, इसलिए $Y_{i}$बस एक ज्यामितीय वितरण का पालन करें।

सामान्यीकृत जैक्सन नेटवर्क

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

ब्राउनियन सन्निकटन

कुछ हल्की परिस्थितियों में कतार-लंबाई की प्रक्रिया $Q(t)$ एक खुले सामान्यीकृत जैक्सन नेटवर्क के रूप में परिभाषित एक परिलक्षित ब्राउनियन गति द्वारा अनुमान लगाया जा सकता है $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$, कहाँ $\theta$ प्रक्रिया का बहाव है, $\Gamma$ सहप्रसरण मैट्रिक्स है, और $R$ प्रतिबिंब मैट्रिक्स है। यह सामान्य जैक्सन नेटवर्क के बीच सजातीय द्रव नेटवर्क और परिलक्षित ब्राउनियन गति के बीच संबंध द्वारा प्राप्त एक दो-क्रम सन्निकटन है।

परिलक्षित ब्राउनियन प्रक्रिया के पैरामीटर निम्नानुसार निर्दिष्ट हैं:

$\theta =\alpha -(I-P^{T})\mu$

$\Gamma =(\Gamma _{k\ell }){\text{ with }}\Gamma _{k\ell }=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{j\ell }-\delta _{j\ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }$

$R=I-P^{T}$

जहां प्रतीकों को इस प्रकार परिभाषित किया गया है:

Definitions of symbols in the approximation formula

symbol	Meaning
$\alpha =(\alpha _{j})_{j=1}^{J}$	a J-vector specifying the arrival rates to each node.
$\mu =(\mu )_{j=1}^{J}$	a J-vector specifying the service rates of each node.
$P$	routing matrix.
$\lambda _{j}$	effective arrival of $j^{\text{th}}$ node.
$c_{j}$	variation of service time at $j^{\text{th}}$ node.
$c_{0,j}$	variation of inter-arrival time at $j^{\text{th}}$ node.
$\delta _{ij}$	coefficients to specify correlation between nodes. They are defined in this way: Let $A(t)$ be the arrival process of the system, then $A(t)-\alpha t{}\approx {\hat {A}}(t)$ in distribution, where ${\hat {A}}(t)$ is a driftless Brownian process with covariate matrix $\Gamma ^{0}=(\Gamma _{ij}^{0})$, with $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$, for any $i,j\in \{1,\dots ,J\}$

यह भी देखें

• गॉर्डन-नेवेल नेटवर्क
• बीसीएमपी नेटवर्क
• जी नेटवर्क
• लघु नियम