Jackson network

A network of m interconnected queues is known as a Jackson network{{cite journal|last1=Goodman|first1=Jonathan B.|last2=Massey|first2=William A.|title=The Non-Ergodic Jackson Network|journal=Journal of Applied Probability|date=December 1984|volume=21|issue=4 |pages=860–869|doi=10.2307/3213702}} or Jacksonian network{{cite journal |last1=Walrand|first1=J.|last2=Varaiya|first2=P.|title=Sojourn Times and the Overtaking Condition in Jacksonian Networks|journal=Advances in Applied Probability|date=December 1980 |volume=12|issue=4|pages=1000–1018|doi=10.2307/1426753}} if it meets the following conditions:

1. if the network is open, any external arrivals to node i form a Poisson process,
2. All service times are exponentially distributed and the service discipline at all queues is first-come, first-served,
3. 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-\backslash sum\_\{j=1\}^\{m\}P\_\{ij\}$, which, for an open network, is non-zero for some subset of the queues,
4. the utilization of all of the queues is less than one.

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

:$\backslash pi\; (k\_1,k\_2,\backslash ldots,k\_m)\; =\; \backslash prod\_\{i=1\}^\{m\}\; \backslash pi\_i(k\_i)\; =\; \backslash prod\_\{i=1\}^\{m\}\; [\backslash rho\_i^\{k\_i\}\; (1-\backslash rho\_i)].$

The result $\backslash pi\; (k\_1,k\_2,\backslash ldots,k\_m)\; =\; \backslash prod\_\{i=1\}^\{m\}\; \backslash pi\_i(k\_i)$ also holds for M/M/c model stations with c_i servers at the $i^\backslash text\{th\}$ station, with utilization requirement .

In an open network, jobs arrive from outside following a Poisson process with rate $\backslash alpha>0$. Each arrival is independently routed to node j with probability $p\_\{0j\}\backslash ge0$ and $\backslash 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-\backslash sum\_\{j=1\}^J\; p\_\{ij\}$.

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

:$\backslash lambda\_i\; =\backslash alpha\; p\_\{0i\}\; +\; \backslash sum\_\{j=1\}^J\; \backslash lambda\_j\; p\_\{ji\},\; i=1,\backslash ldots,J.\; \backslash 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 $\backslash mu\_j$ in the above.)

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

All jobs leave each node also following Poisson process, and define $\backslash 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 $\backslash mathbf\{X\}=(X\_i)\_\{i=1\}^J$. Then the equilibrium distribution of $\backslash mathbf\{X\}$, $\backslash pi(\backslash mathbf\{x\})=P(\backslash mathbf\{X\}=\backslash mathbf\{x\})$ is determined by the following system of balance equations:

:$$

\begin{align}

& \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\ne i}\pi(\mathbf{x}+\mathbf{e}_i-\mathbf{e}_j)\mu_i(x_i+1)p_{ij}.\qquad (2)

\end{align}

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

Suppose a vector of independent random variables $(Y\_1,\backslash ldots,Y\_J)$ with each $Y\_i$ having a probability mass function as

:$P(Y\_i=n)=p(Y\_i=0)\backslash cdot\; \backslash frac\{\backslash lambda\_i^n\}\{M\_i(n)\},\; \backslash quad\; (3)$

where $M\_i(n)=\backslash prod\_\{j=1\}^n\; \backslash mu\_i(j)$. If i.e. $P(Y\_i=0)=\backslash left(1+\backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\{\backslash lambda\_i^n\}\{M\_i(n)\}\backslash right)^\{-1\}$ is well defined, then the equilibrium distribution of the open Jackson network has the following product form:

:$\backslash pi(\backslash mathbf\{x\})=\backslash prod\; \_\{i=1\}^J\; P(Y\_i=x\_i).$

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

{{hidden begin

|toggle = left

|title = Proof

|titlestyle= font-size:12pt

}}

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

:$\backslash pi(\backslash mathbf\{x\})\; =\backslash pi\; (\backslash mathbf\{x\}+\backslash mathbf\{e\}\_i)\backslash mu\_i(x\_i+1)/\; \backslash 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:

:$\backslash sum\_\{i=1\}^J\; [\backslash alpha\; p\_\{0i\}+\backslash mu\_i(x\_i)(1-p\_\{ii\})]=\backslash sum\_\{i=1\}^J[\backslash frac\{\backslash alpha\; p\_\{0i\}\}\{\backslash lambda\_i\}\backslash mu\_i(x\_i)+\backslash lambda\_i\; p\_\{i0\}]+\backslash sum\_\{i=1\}^J\backslash sum\_\{j\backslash ne\; i\}\backslash frac\{\backslash lambda\_i\}\{\backslash lambda\_j\}p\_\{ij\}\backslash mu\_j(x\_j).\; \backslash qquad\; (4)$

Then use $(1)$, we have:

:$\backslash sum\_\{i=1\}^J\backslash sum\_\{j\backslash ne\; i\}\backslash frac\{\backslash lambda\_i\}\{\backslash lambda\_j\}p\_\{ij\}\backslash mu\_j(x\_j)\; =\; \backslash sum\_\{j=1\}^J\; [\backslash sum\_\{i\; \backslash ne\; j\}\backslash frac\{\backslash lambda\_i\}\{\backslash lambda\_j\}p\_\{ij\}]\backslash mu\_j(x\_j)=\backslash sum\_\{j=1\}^J[1-p\_\{jj\}-\backslash frac\{\backslash alpha\; p\_\{0j\}\}\{\backslash lambda\_j\}]\backslash mu\_j(x\_j).$

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

:$\backslash sum\_\{i=1\}^J\; \backslash alpha\; p\_\{0i\}=\backslash sum\_\{i=1\}^J\; \backslash lambda\_i\; p\_\{i0\}$

This can be verified by $\backslash sum\_\{i=1\}^J\; \backslash alpha\; p\_\{0i\}=\; \backslash sum\_\{i=1\}^J\backslash lambda\_i-\backslash sum\; \_\{i=1\}^J\backslash sum\_\{j=1\}^J\backslash lambda\_j\; p\_\{ji\}=\backslash sum\_\{i=1\}^J\backslash lambda\_i-\backslash sum\_\{j=1\}^J\backslash lambda\_j(1-p\_\{j0\})=\backslash sum\_\{i=1\}^J\backslash lambda\_ip\_\{i0\}$. Hence both side of $(2)$ are equal.⟨

{{hidden end}}

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

File:Open jackson network (final).png

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

:$\backslash alpha=5,\; \backslash 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:

: $\backslash lambda=(I-P^T)^\{-1\}a=\backslash 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}

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

:$P(Y\_1=0)=\backslash left(\backslash sum\_\{n=0\}^\backslash infty\; \backslash left(\backslash frac\{2.5\}\{15\}\backslash right)^n\backslash right)^\{-1\}=\backslash frac\{5\}\{6\}$

:$P(Y\_2=0)=\backslash left(\backslash sum\_\{n=0\}^\backslash infty\; \backslash left(\backslash frac\{3.75\}\{12\}\backslash right)^n\backslash right)^\{-1\}=\backslash frac\{11\}\{16\}$

:$P(Y\_3=0)=\backslash left(\backslash sum\_\{n=0\}^\backslash infty\; \backslash left(\backslash frac\{1.25\}\{10\}\backslash right)^n\backslash right)^\{-1\}=\backslash frac\{7\}\{8\}$

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

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

Since the service rate here does not depend on state, the $Y\_i$s simply follow a geometric distribution.

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

Under some mild conditions the queue-length process{{clarify|date=January 2013}} $Q(t)$ of an open generalized Jackson network can be approximated by a reflected Brownian motion defined as $\backslash operatorname\{RBM\}\_\{Q(0)\}(\backslash theta,\backslash Gamma;R).$, where $\backslash theta$ is the drift of the process, $\backslash 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:

:$\backslash theta=\; \backslash alpha\; -(I-P^T)\backslash mu$

:$\backslash Gamma=(\backslash Gamma\_\{k\backslash ell\})\; \backslash text\{\; with\; \}\; \backslash Gamma\_\{k\backslash ell\}=\backslash sum\_\{j=1\}^J\; (\backslash lambda\_j\; \backslash wedge\; \backslash mu\_j)[p\_\{jk\}(\backslash delta\_\{k\backslash ell\}-p\_\{j\backslash ell\})+c\_j^2(p\_\{jk\}-\backslash delta\_\{jk\})(p\_\{j\backslash ell\}-\backslash delta\_\{j\backslash ell\})]+\backslash alpha\_k\; c\_\{0,k\}^2\; \backslash delta\_\{k\backslash ell\}$

:$R=I-P^T$

where the symbols are defined as:

• Gordon–Newell network
• BCMP network
• G-network
• Little's law

{{Reflist}}

{{Queueing theory}}

Category:Queueing theory