Jackson network

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network (sometimes Jacksonian network^[1]) 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 networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research,^[2] including ideas used in the development of the Internet.^[3] The networks were first identified by James R. Jackson^[4]^[5] and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’^[6]

Jackson was inspired by the work of Burke and Reich,^[7] though Jean 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".^[8]

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).^[9]

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 (different nodes have different service rates) and state-dependent (service rates change depending on queue lengths). 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.^[10]

Necessary conditions for a Jackson network

A network of m interconnected queues is known as a Jackson network^[11] or Jacksonian network^[12] if it meets the following conditions:

if the network is open, any external arrivals to node i form a Poisson process,
All service times are exponentially distributed and the service discipline at all queues is first-come, first-served,
a customer completing service at queue i will either move to some new queue j with probability $P_{ij}$ or leave the system with probability $1-\sum _{j=1}^{m}P_{ij}$ , which, for an open network, is non-zero for some subset of the queues,
the utilization of all of the queues is less than one.

Theorem

In an open Jackson network of m M/M/1 queues where the utilization $\rho _{i}$ is less than 1 at every queue, the equilibrium state probability distribution exists and for state $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ is given by the product of the individual queue equilibrium distributions

\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})].

The result $\pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})$ also holds for M/M/c model stations with c_i servers at the $i^{\text{th}}$ station, with utilization requirement $\rho _{i}<c_{i}$ .

Definition

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

Hence we have the overall arrival rate to node i, $\lambda _{i}$ , including both external arrivals and internal transitions:

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

(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 j to i is bounded by a fraction of the arrival rate at j and we ignore the service rate $\mu _{j}$ in the above.)

Define $a=(\alpha p_{0i})_{i=1}^{J}$ , then we can solve $\lambda =(I-P^{T})^{-1}a$ .

All jobs leave each node also following Poisson process, and define $\mu _{i}(x_{i})$ as the service rate of node i when there are $x_{i}$ jobs at node i.

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

{\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}}

where $\mathbf {e} _{i}$ denote the $i^{\text{th}}$ unit vector.

Theorem

Suppose a vector of independent random variables $(Y_{1},\ldots ,Y_{J})$ with each $Y_{i}$ having a probability mass function as

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

where $M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)$ . If $\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty$ i.e. $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:

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

for all $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ .⟩

Proof

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

\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})]

Substituting these into the right side of $(2)$ we get:

\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)

Then use $(1)$ , we have:

\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}).

Substituting the above into $(4)$ , we have:

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

This can be verified by $\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}$ . Hence both side of $(2)$ are equal.⟨

This theorem extends the one shown above by allowing state-dependent service rate of each node. It relates the distribution of $\mathbf {X}$ by a vector of independent variable $\mathbf {Y}$ .

Example

Suppose we have a three-node Jackson network shown in the graph, the coefficients are:

\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

Then by the theorem, we can calculate:

\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}}

According to the definition of $\mathbf {Y}$ , we have:

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}}

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

\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

Since the service rate here does not depend on state, the $Y_{i}$ s simply follow a geometric distribution.

Generalized Jackson network

A generalized Jackson network allows 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 stationary distribution, so approximations are sought.^[13]

Brownian approximation

Under some mild conditions the queue-length process^{[clarification needed]} $Q(t)$ of an open generalized Jackson network can be approximated by a reflected Brownian motion defined as $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ , where $\theta$ is the drift of the process, $\Gamma$ is the covariance matrix, and $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.

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

\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}

where the symbols are defined as:

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\}$

References

^ 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.
^ Kelly, F. P. (June 1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.
^ 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.
^ 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
^ Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.
^ Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0.

[1] 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.

[2] Kelly, F. P. (June 1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.

[3] 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.

[jackson-4] 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

[5] Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.

[6] Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149.

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

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] 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.

[13] Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Queueing theory
Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue
Arrival processes	Poisson point process Markovian arrival process Rational arrival process
Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network
Service policies	FIFO LIFO Processor sharing Round-robin Shortest job next Shortest remaining time
Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method
Limit theorems	Fluid limit Mean-field theory Heavy traffic approximation Reflected Brownian motion
Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue
Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering
Category

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Langbahn Team – Weltmeisterschaft

Jackson network

Necessary conditions for a Jackson network

Theorem

Definition

Theorem

Example

Generalized Jackson network

Brownian approximation

See also

References