en>NaBUru38: c

2009-08-14T06:41:50Z

New page

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]] a '''Jackson network''' (sometimes '''Jacksonian network'''<ref>{{cite jstor|1426753}}</ref>) is a class of queueing network where the [[equilibrium distribution]] is particularly simple to compute as the network has a [[product-form solution]]. It was the first significant development in the theory of [[queueing theory|networks of queues]], and generalising and applying the ideas of the theorem to search for similar [[product-form solution]]s in other networks has been the subject of much research,<ref>{{cite journal|title=Networks of Queues|authorlink=F. P. Kelly|first=F. P.|last=Kelly|journal=Advances in Applied Probability|volume=8|date=Jun 1976|pages=416–432|jstor=1425912|issue=2|doi=10.2307/1425912}}</ref> including ideas used in the development of the Internet.<ref>{{cite journal|title=Comments on "Jobshop-Like Queueing Systems": The Background|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=50|date=December 2004|pages=1796–1802|jstor=30046150|issue=12|doi=10.1287/mnsc.1040.0268}}</ref> The networks were first identified by [[James R. Jackson]]<ref name="jackson">{{cite journal|title=Jobshop-like Queueing Systems|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=10|date=Oct 1963|pages=131–142|doi=10.1287/mnsc.1040.0268|jstor=2627213|issue=1}}</ref><ref>{{cite doi|10.1287/opre.5.4.518}}</ref> and his paper was re-printed in the journal [[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’<ref>{{cite journal|title=Jobshop-Like Queueing Systems|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=50|date=December 2004|pages=1796–1802|jstor=30046149|issue=12|doi=10.1287/mnsc.1040.0268}}</ref>

Jackson was inspired by the work of [[Burke's theorem|Burke]] and Reich,<ref>{{cite journal|title=Waiting Times When Queues are in Tandem|journal=[[Annals of Mathematical Statistics]]|volume=28|date=September 1957|first=Edgar|last=Reich|doi=10.1214/aoms/1177706889|jstor=2237237|issue=3|pages=768}}</ref> though Walrand notes "product-form results … [are] a much less immediate result of the output theorem than Jackson himself appeared to believe in his fundamental paper".<ref>{{cite journal|title=A Probabilistic Look at Networks of Quasi-Reversible Queues|journal=[[IEEE Transactions on Information Theory]]|volume=29|date=November 1983|first=Jean|last=Walrand|doi=10.1109/TIT.1983.1056762|issue=6|pages=825}}</ref>

An earlier [[product-form solution]] was found by R. R. P. Jackson for tandem queues (a finite chain of queues where each customer must visit each queue in order) and cyclic networks (a loop of queues where each customer must visit each queue in order).<ref>{{cite journal|title=Book review: Queueing networks and product forms: a systems approach|first=R. R. P.|last=Jackson|doi=10.1093/imaman/6.4.382|year=1995|volume=6|pages=382–384|journal=IMA Journal of Management Mathematics|issue=4}}</ref>

A Jackson network consists of a number of nodes, where each node represents a queue in which the service rate can be both node-dependent and state-dependent. Jobs travel among the nodes following a fixed routing matrix. All jobs at each node belong to a single "class" and jobs follow the same service-time distribution and the same routing mechanism. Consequently, there is no notion of priority in serving the jobs: all jobs at each node are served on a [[first-come, first-served]] basis.

Jackson networks where a finite population of jobs travel around a closed network also have a product-form solution described by the [[Gordon–Newell theorem]].<ref>{{cite doi|10.1287/opre.15.2.254}}</ref>

==Definition==

In an open network, jobs arrive from outside following a [[Poisson process]] with rate <math>\alpha>0</math>. Each arrival is independently routed to node ''j'' with probability <math>p_{0j}\ge0</math> and <math>\sum_{j=1}^J p_{0j}=1</math>. Upon service completion at node ''i'', a job may go to another node ''j'' with probability <math>p_{ij}</math> or leave the network with probability <math>p_{i0}=1-\sum_{j=1}^J p_{ij}</math>.

Hence we have the overall arrival rate to node ''i'', <math>\lambda_i</math>, including both external arrivals and internal transitions:

:<math> \lambda_i =\alpha p_{0i} + \sum_{j=1}^J \lambda_j p_{ji}, i=1,\ldots,J. \qquad (1)</math>

Define <math> a=(\alpha p_{0i})_{i=1}^J</math>, then we can solve <math> \lambda=(I-P')^{-1}a</math>.

All jobs leave each node also following Poisson process, and define <math> \mu_i(x_i) </math> as the service rate of node ''i'' when there are <math> x_i </math> jobs at node ''i''.

Let <math>X_i(t)</math> denote the number of jobs at node ''i'' at time ''t'', and <math> \mathbf{X}=(X_i)_{i=1}^J</math>. Then the [[equilibrium distribution]] of <math>\mathbf{X}</math>, <math>\pi(\mathbf{x})=P(\mathbf{X}=\mathbf{x})</math> is determined by the following system of balance equations:

:<math> \pi(\mathbf{x}) \sum_{i=1}^J [\alpha p_{0i} +\mu_i (x_i) (1-p_{ii})] </math><math>=\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\ne i}\pi(\mathbf{x}+\mathbf{e}_i-\mathbf{e}_j)\mu_i(x_i+1)p_{ij}.\qquad (2)</math>

where <math>\mathbf{e}_i</math> denote the <math> i^{th}</math> [[unit vector]].

=== Theorem ===
Suppose a vector of independent random variables <math> (Y_1,\ldots,Y_J)</math> with each <math> Y_i</math> having a [[probability mass function]] as

:<math> P(Y_i=n)=p(Y_i=0)\cdot \frac{\lambda_i^n}{M_i(n)}, \quad (3)</math>

where <math> M_i(n)=\prod_{j=1}^n \mu_i(j) </math>. If <math> \sum_{n=1}^\infty \frac{\lambda_i^n}{M_i(n)} < \infty </math> i.e. <math>P(Y_i=0)=\left(1+\sum_{n=1}^\infty \frac{\lambda_i^n}{M_i(n)}\right)^{-1}</math> is well defined, then the equilibrium distribution of the open Jackson network has the following product form:

:<math> \pi(\mathbf{x})=\prod _{i=1}^J P(Y_i=x_i).</math>

for all <math>\mathbf{x}\in \mathcal{Z}_{+}^J </math>.⟩

{{hidden begin
|toggle = left
|title = Proof
|titlestyle= font-size:12pt
}}

It suffices to verify equation <math>(2)</math> is satisfied. By the product form and formula (3), we have:

:<math> \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)]</math>

Substituting these into the right side of <math>(2)</math> we get:

:<math> \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\ne i}\frac{\lambda_i}{\lambda_j}p_{ij}\mu_j(x_j). \qquad (4) </math>

Then use <math>(1)</math>, we have:

:<math> \sum_{i=1}^J\sum_{j\ne i}\frac{\lambda_i}{\lambda_j}p_{ij}\mu_j(x_j) = \sum_{j=1}^J [\sum_{i \ne 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). </math>

Substituting the above into <math>(4)</math>, we have:
:<math> \sum_{i=1}^J \alpha p_{0i}=\sum_{i=1}^J \lambda_i p_{i0}</math>

This can be verified by <math> \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_ip_{i0} </math>. Hence both side of <math> (2) </math> are equal.⟨
{{hidden end}}

This theorem extends the one shown on [[Jackson's theorem (queueing theory)|Jackson's Theorem]] page by allowing state-dependent service rate of each node. It relates the distribution of <math>\mathbf{X}</math> by a vector of ''independent'' variable <math> \mathbf{Y} </math>.

=== Example ===
[[File:Open jackson network (final).png|thumb|upright=1.5|A three-node open Jackson network]]
Suppose we have a three-node Jackson shown in the graph, the coefficients are:
:<math>\alpha=5, \quad
p_{01}=p_{02}=0.5, \quad p_{03}=0,\quad </math>

:<math>
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</math>

Then by the theorem, we can calculate:

: <math>\lambda=(I-P')^{-1}a=\begin{bmatrix}
1 & 0 & 0\\
-0.5 & 1 & 0 \\
-0.5 & 0 & 1\end{bmatrix}^{-1}\begin{bmatrix}
0.5\times5\\
0.5\times5\\
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}
</math>

According to the definition of <math> \mathbf{Y} </math>, we have:

:<math> P(Y_1=0)=\left(1+\sum_{n=1}^\infty \left(\frac{2.5}{15}\right)^n\right)^{-1}=\frac{5}{6} </math>
:<math> P(Y_2=0)=\left(1+\sum_{n=1}^\infty \left(\frac{3.75}{12}\right)^n\right)^{-1}=\frac{11}{16} </math>
:<math> P(Y_3=0)=\left(1+\sum_{n=1}^\infty \left(\frac{1.25}{10}\right)^n\right)^{-1}=\frac{7}{8} </math>

Hence the probability that there is one job at each node is:

:<math> \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</math>

Since the service rate here does not depend on state, the <math> Y_i</math>s simply follow a [[geometric distribution]].

==Generalized Jackson network==

A '''generalized Jackson network''' allows [[renewal process|renewal arrival processes]] that need not be Poisson processes, and independent, identically distributed non-exponential service times. In general, this network does not have a [[product-form solution|product-form stationary distribution]], so approximations are sought.<ref>{{cite book|title=Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization|first1=Hong|last1=Chen|first2=David D.|last2=Yao|publisher=Springer|year=2001|isbn=0-387-95166-0}}</ref>

===Brownian approximation===
Under some mild conditions the queue-length process{{clarify|date=January 2013}} <math>Q(t)</math> of an open generalized Jackson network can be approximated by a [[reflected Brownian motion]] defined as <math> RBM_{Q(0)}(\theta,\Gamma;R).</math>, where <math> \theta </math> is the drift of the process, <math> \Gamma </math> is the covariance matrix, and <math> R </math> 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.

The parameters of the reflected Brownian process is specified as follows:

:<math> \theta= \alpha -(I-P')\mu </math>
:<math> \Gamma=(\Gamma_{kl}) </math> with <math> \Gamma_{kl}=\sum_{j=1}^J (\lambda_j \wedge \mu_j)[p_{jk}(\delta_{kl}-p_{jl})+c_j^2(p_{jk}-\delta_{jk})(p_{jl}-\delta_{jl})]+\alpha_k c_{0,k}^2 \delta_{kl} </math>
:<math> R=I-P' </math>

where the symbols are defined as:
{|class="wikitable"
|+Definitions of symbols in the approximation formula
! symbol !! Meaning
|-
| <math> \alpha=(\alpha_j)_{j=1}^J </math>|| a J-vector specifying the arrival rates to each node.
|-
| <math> \mu=(\mu)_{j=1}^J </math> || a J-vector specifying the service rates of each node.
|-
| <math> P </math> || routing matrix.
|-
| <math> \lambda_j </math>|| effective arrival of <math> j^{th} </math> node.
|-
| <math> c_j </math> || variation of service time at <math> j^{th} </math> node.
|-
| <math> c_{0,j} </math> || variation of inter-arrival time at <math> j^{th}</math> node.
|-
| <math> \delta_{ij} </math> || coefficients to specify correlation between nodes.{{hidden begin
|toggle = left}}
They are defined in this way: Let <math>A(t)</math> be the arrival process of the system, then <math>A(t)-\alpha t {}\approx \hat{A}(t)</math> in distribution, where <math>\hat{A}(t)</math> is a driftless Brownian process with covariate matrix <math>\Gamma^0=(\Gamma^0_{ij})</math>, with <math>\Gamma^0_{ij}=\alpha_i c_{0,i}^2 \delta_{ij}</math>, for any <math>i,j\in \{1,\dots,J\}</math>
{{hidden end}}
|}

{{more footnotes|date=June 2012}}

==References==
{{Reflist}}

{{Queueing theory}}

[[Category:Stochastic processes]]
[[Category:Queueing theory]]

Classic Racing - Revision history

en>NaBUru38: c