Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Jackson network
open-in-new
<h2 id="necessary-conditions-for-a-jackson-network">Necessary conditions for a Jackson network</h2> <p>A network of <i>m</i> interconnected queues is known as a Jackson network<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> or Jacksonian network<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> if it meets the following conditions: </p> <ol><li>if the network is open, any external arrivals to node <i>i</i> form a <a href="/facts/Poisson_process/8uphjAUc">Poisson process</a>,</li> <li>All service times are exponentially distributed and the service discipline at all queues is <a href="/facts/First-come,_first-served/8NDl56EM">first-come, first-served</a>,</li> <li>a customer completing service at queue <i>i</i> will either move to some new queue <i>j</i> with probability P i j {\displaystyle P_{ij}} or leave the system with probability 1 − ∑ j = 1 m P i j {\displaystyle 1-\sum _{j=1}^{m}P_{ij}} , which, for an open network, is non-zero for some subset of the queues,</li> <li>the <a href="/facts/Rental_utilization/dlXCALQu">utilization</a> of all of the queues is less than one.</li></ol> <h2 id="theorem">Theorem</h2> <p>In an open Jackson network of <i>m</i> <a href="/facts/M/M/1_model/eTkKX6Ro">M/M/1 queues</a> where the <a href="/facts/Rental_utilization/dlXCALQu">utilization</a> ρ i {\displaystyle \rho _{i}} is less than 1 at every queue, the equilibrium state <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a> exists and for state ( k 1 , k 2 , … , k m ) {\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}} is given by the product of the individual queue equilibrium distributions </p> π ( k 1 , k 2 , … , k m ) = ∏ i = 1 m π i ( k i ) = ∏ i = 1 m [ ρ i k i ( 1 − ρ i ) ] . {\displaystyle \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})].} <p>The result π ( k 1 , k 2 , … , k m ) = ∏ i = 1 m π i ( k i ) {\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})} also holds for <a href="/facts/M/M/c_model/MXB6lmQ1">M/M/c model</a> stations with <i>c</i><i>i</i> servers at the i th {\displaystyle i^{\text{th}}} station, with utilization requirement ρ i < c i {\displaystyle \rho _{i}<c_{i}} . </p> <h2 id="definition">Definition</h2> <p>In an open network, jobs arrive from outside following a <a href="/facts/Poisson_process/8uphjAUc">Poisson process</a> with rate α > 0 {\displaystyle \alpha >0} . Each arrival is independently routed to node <i>j</i> with probability p 0 j ≥ 0 {\displaystyle p_{0j}\geq 0} and ∑ j = 1 J p 0 j = 1 {\displaystyle \sum _{j=1}^{J}p_{0j}=1} . Upon service completion at node <i>i</i>, a job may go to another node <i>j</i> with probability p i j {\displaystyle p_{ij}} or leave the network with probability p i 0 = 1 − ∑ j = 1 J p i j {\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}} . </p><p>Hence we have the overall arrival rate to node <i>i</i>, λ i {\displaystyle \lambda _{i}} , including both external arrivals and internal transitions: </p> λ i = α p 0 i + ∑ j = 1 J λ j p j i , i = 1 , … , J . ( 1 ) {\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)} <p>(Since the utilisation at each node is less than 1, and we are looking at the equilibrium distribution i.e. the long-run-average behaviour, the rate of jobs transitioning from <i>j</i> to <i>i</i> is bounded by a fraction of the <i>arrival</i> rate at <i>j</i> and we ignore the service rate μ j {\displaystyle \mu _{j}} in the above.) </p><p>Define a = ( α p 0 i ) i = 1 J {\displaystyle a=(\alpha p_{0i})_{i=1}^{J}} , then we can solve λ = ( I − P T ) − 1 a {\displaystyle \lambda =(I-P^{T})^{-1}a} . </p><p>All jobs leave each node also following Poisson process, and define μ i ( x i ) {\displaystyle \mu _{i}(x_{i})} as the service rate of node <i>i</i> when there are x i {\displaystyle x_{i}} jobs at node <i>i</i>. </p><p>Let X i ( t ) {\displaystyle X_{i}(t)} denote the number of jobs at node <i>i</i> at time <i>t</i>, and X = ( X i ) i = 1 J {\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}} . Then the <a href="/facts/Equilibrium_distribution/5oP5hntk">equilibrium distribution</a> of X {\displaystyle \mathbf {X} } , π ( x ) = P ( X = x ) {\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )} is determined by the following system of balance equations: </p> π ( x ) ∑ i = 1 J [ α p 0 i + μ i ( x i ) ( 1 − p i i ) ] = ∑ i = 1 J [ π ( x − e i ) α p 0 i + π ( x + e i ) μ i ( x i + 1 ) p i 0 ] + ∑ i = 1 J ∑ j ≠ i π ( x + e i − e j ) μ i ( x i + 1 ) p i j . ( 2 ) {\displaystyle {\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}}} <p>where e i {\displaystyle \mathbf {e} _{i}} denote the i th {\displaystyle i^{\text{th}}} <a href="/facts/Unit_vector/GyaXneDn">unit vector</a>. </p> <h3>Theorem</h3> <p>Suppose a vector of independent random variables ( Y 1 , … , Y J ) {\displaystyle (Y_{1},\ldots ,Y_{J})} with each Y i {\displaystyle Y_{i}} having a <a href="/facts/Probability_mass_function/LhurokRt">probability mass function</a> as </p> P ( Y i = n ) = p ( Y i = 0 ) ⋅ λ i n M i ( n ) , ( 3 ) {\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)} <p>where M i ( n ) = ∏ j = 1 n μ i ( j ) {\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)} . If ∑ n = 1 ∞ λ i n M i ( n ) < ∞ {\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty } i.e. P ( Y i = 0 ) = ( 1 + ∑ n = 1 ∞ λ i n M i ( n ) ) − 1 {\displaystyle P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}} is well defined, then the equilibrium distribution of the open Jackson network has the following product form: </p> π ( x ) = ∏ i = 1 J P ( Y i = x i ) . {\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).} <p>for all x ∈ Z + J {\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}} .⟩ </p> <p>This theorem extends the one shown above by allowing state-dependent service rate of each node. It relates the distribution of X {\displaystyle \mathbf {X} } by a vector of <i>independent</i> variable Y {\displaystyle \mathbf {Y} } . </p> <h3>Example</h3> <p>Suppose we have a three-node Jackson network shown in the graph, the coefficients are: </p> α = 5 , p 01 = p 02 = 0.5 , p 03 = 0 , {\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad } P = [ 0 0.5 0.5 0 0 0 0 0 0 ] , μ = [ μ 1 ( x 1 ) μ 2 ( x 2 ) μ 3 ( x 3 ) ] = [ 15 12 10 ] for all x i > 0 {\displaystyle 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} <p>Then by the theorem, we can calculate: </p> λ = ( I − P T ) − 1 a = [ 1 0 0 − 0.5 1 0 − 0.5 0 1 ] − 1 [ 0.5 × 5 0.5 × 5 0 ] = [ 1 0 0 0.5 1 0 0.5 0 1 ] [ 2.5 2.5 0 ] = [ 2.5 3.75 1.25 ] {\displaystyle \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}}} <p>According to the definition of Y {\displaystyle \mathbf {Y} } , we have: </p> P ( Y 1 = 0 ) = ( ∑ n = 0 ∞ ( 2.5 15 ) n ) − 1 = 5 6 {\displaystyle 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 ) = ( ∑ n = 0 ∞ ( 3.75 12 ) n ) − 1 = 11 16 {\displaystyle 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 ) = ( ∑ n = 0 ∞ ( 1.25 10 ) n ) − 1 = 7 8 {\displaystyle P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}} <p>Hence the probability that there is one job at each node is: </p> π ( 1 , 1 , 1 ) = 5 6 ⋅ 2.5 15 ⋅ 11 16 ⋅ 3.75 12 ⋅ 7 8 ⋅ 1.25 10 ≈ 0.00326 {\displaystyle \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} <p>Since the service rate here does not depend on state, the Y i {\displaystyle Y_{i}} s simply follow a <a href="/facts/Geometric_distribution/c8wjfaoV">geometric distribution</a>. </p> <h2 id="generalized-jackson-network">Generalized Jackson network</h2> <p>A generalized Jackson network allows <a href="/facts/Renewal_process/1rDc2czB">renewal arrival processes</a> that need not be Poisson processes, and independent, identically distributed non-exponential service times. In general, this network does not have a <a href="/facts/Product-form_solution/NC3xSFck">product-form stationary distribution</a>, so approximations are sought.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> <h3>Brownian approximation</h3> <p>Under some mild conditions the queue-length process Q ( t ) {\displaystyle Q(t)} of an open generalized Jackson network can be approximated by a <a href="/facts/Reflected_Brownian_motion/Wb4Knnzv">reflected Brownian motion</a> defined as RBM Q ( 0 ) ( θ , Γ ; R ) . {\displaystyle \operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).} , where θ {\displaystyle \theta } is the drift of the process, Γ {\displaystyle \Gamma } is the <a href="/facts/Covariance_matrix/kLhgjHC6">covariance matrix</a>, and R {\displaystyle R} is the reflection matrix. This is a two-order approximation obtained by relation between general Jackson network with homogeneous fluid network and reflected Brownian motion. </p><p>The parameters of the reflected Brownian process is specified as follows: </p> θ = α − ( I − P T ) μ {\displaystyle \theta =\alpha -(I-P^{T})\mu } Γ = ( Γ k ℓ ) with Γ k ℓ = ∑ j = 1 J ( λ j ∧ μ j ) [ p j k ( δ k ℓ − p j ℓ ) + c j 2 ( p j k − δ j k ) ( p j ℓ − δ j ℓ ) ] + α k c 0 , k 2 δ k ℓ {\displaystyle \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 {\displaystyle R=I-P^{T}} <p>where the symbols are defined as: </p> Definitions of symbols in the approximation formula<table><tbody><tr><th>symbol</th><th>Meaning</th></tr><tr><td> α = ( α j ) j = 1 J {\displaystyle \alpha =(\alpha _{j})_{j=1}^{J}} </td><td>a <i>J</i>-vector specifying the arrival rates to each node.</td></tr><tr><td> μ = ( μ ) j = 1 J {\displaystyle \mu =(\mu )_{j=1}^{J}} </td><td>a <i>J</i>-vector specifying the service rates of each node.</td></tr><tr><td> P {\displaystyle P} </td><td>routing matrix.</td></tr><tr><td> λ j {\displaystyle \lambda _{j}} </td><td>effective arrival of j th {\displaystyle j^{\text{th}}} node.</td></tr><tr><td> c j {\displaystyle c_{j}} </td><td>variation of service time at j th {\displaystyle j^{\text{th}}} node.</td></tr><tr><td> c 0 , j {\displaystyle c_{0,j}} </td><td>variation of inter-arrival time at j th {\displaystyle j^{\text{th}}} node.</td></tr><tr><td> δ i j {\displaystyle \delta _{ij}} </td><td>coefficients to specify correlation between nodes.</td></tr></tbody></table> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Gordon%E2%80%93Newell_network/rkbWqHcY">Gordon–Newell network</a></li> <li><a href="/facts/BCMP_network/CR7xPqFP">BCMP network</a></li> <li><a href="/facts/G-network/pXGuAIBK">G-network</a></li> <li><a href="/facts/Little%27s_law/lVGmPs6U">Little's law</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Walrand, J.; Varaiya, P. (1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. JSTOR 1426753. <a href="/wiki/Jean_Walrand" target="_blank">/wiki/Jean_Walrand</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Kelly, F. P. (June 1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912. <a href="/wiki/F._P._Kelly" target="_blank">/wiki/F._P._Kelly</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Jackson, James R. (December 2004). "Comments on "Jobshop-Like Queueing Systems": The Background". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046150. <a href="/wiki/Management_Science:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences" target="_blank">/wiki/Management_Science:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Jackson, James R. (Oct 1963). "Jobshop-like Queueing Systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.1040.0268. JSTOR 2627213. A version from January 1963 is available at http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf Archived 2018-04-12 at the Wayback Machine <a href="/wiki/Management_Science:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences" target="_blank">/wiki/Management_Science:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249. <a href="/wiki/James_R._Jackson" target="_blank">/wiki/James_R._Jackson</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149. <a href="/wiki/Management_Science:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences" target="_blank">/wiki/Management_Science:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Reich, Edgar (September 1957). "Waiting Times When Queues are in Tandem". Annals of Mathematical Statistics. 28 (3): 768. doi:10.1214/aoms/1177706889. JSTOR 2237237. <a href="https://doi.org/10.1214%2Faoms%2F1177706889" target="_blank">https://doi.org/10.1214%2Faoms%2F1177706889</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Walrand, Jean (November 1983). "A Probabilistic Look at Networks of Quasi-Reversible Queues". IEEE Transactions on Information Theory. 29 (6): 825. doi:10.1109/TIT.1983.1056762. <a href="/wiki/IEEE_Transactions_on_Information_Theory" target="_blank">/wiki/IEEE_Transactions_on_Information_Theory</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Jackson, R. R. P. (1995). "Book review: Queueing networks and product forms: a systems approach". IMA Journal of Management Mathematics. 6 (4): 382–384. doi:10.1093/imaman/6.4.382. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557. <a href="/wiki/Gordon_F._Newell" target="_blank">/wiki/Gordon_F._Newell</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Goodman, Jonathan B.; Massey, William A. (December 1984). "The Non-Ergodic Jackson Network". Journal of Applied Probability. 21 (4): 860–869. doi:10.2307/3213702. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Walrand, J.; Varaiya, P. (December 1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0. <a href="0-387-95166-0" target="_blank">0-387-95166-0</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> </ol>