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

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

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

अग्रानुक्रम पंक्तियां (पंक्तियां की परिमित श्रृंखला जहां प्रत्येक ग्राहक को प्रत्येक पंक्ति में क्रम से जाना चाहिए) और चक्रीय नेटवर्क (पंक्तियां का लूप जहां प्रत्येक ग्राहक को क्रम में प्रत्येक पंक्ति में जाना चाहिए) के लिए आर.आर.पी. जैक्सन द्वारा पूर्व उत्पाद-रूप समाधान पाया गया था।

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

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

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

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

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

प्रमेय

एम एम/एम/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})$ c_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})$ जब वहाँ नोड 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}$.⟩

प्रमाण

यह समीकरण को सत्यापित करने के लिए पर्याप्त है $(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}$

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

समीपता सूत्र में प्रतीकों की परिभाषाएँ

प्रतीक	अर्थ
$\alpha =(\alpha _{j})_{j=1}^{J}$	एक जे-वेक्टर प्रत्येक नोड के लिए आगमन दर निर्दिष्ट करता है।
$\mu =(\mu )_{j=1}^{J}$	एक जे-वेक्टर प्रत्येक नोड की सेवा दरों को निर्दिष्ट करता है।
$P$	रूटिंग मैट्रिक्स।
$\lambda _{j}$	प्रभावी आगमन का 𝑗वां नोड।
$c_{j}$	सेवा समय में परिवर्तन 𝑗वां नोड।
$c_{0,j}$	अंतर-आगमन समय की भिन्नता पर 𝑗वां नोड।
$\delta _{ij}$	नोड्स के बीच सहसंबंध निर्दिष्ट करने के लिए गुणांक। 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\}$

यह भी देखें

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