User:Ygh929/sandbox

In queueing theory, Jackson network is a kind of networks where Jackson's theorem or its extensions can be applied. A Jackson network consists of J nodes. Each node can be considered as a M/M/1 queue and the service rate at eac node i can be both node-dependent and state-dependent. Jobs travel among the nodes following a routing matrix $P$.

All jobs at each node belong to a single "class": All 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.

According to different specifications of the routing matrix, there are three different variations: the open, close and semi-open networks.

Open Jackson network

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

Define $a=(\alpha p_{0i})_{i=1}^{J}$, then we can solve $\lambda =(I-P')^{-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:

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

where $\mathbf {e} _{i}$ denote the $i^{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)=(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}})^{-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 on Jackson's Theorem page 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

A three-node open Jackson network

Suppose we have a three-node Jackson 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}}$ for all $x_{i}>0$

Then by the theorem, we can calculate:

$\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\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)=(1+\sum _{n=1}^{\infty }({\frac {2.5}{15}})^{n})^{-1}={\frac {5}{6}}$

$P(Y_{2}=0)=(1+\sum _{n=1}^{\infty }({\frac {3.75}{12}})^{n})^{-1}={\frac {11}{16}}$

$P(Y_{3}=0)=(1+\sum _{n=1}^{\infty }({\frac {1.25}{10}})^{n})^{-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 doesn't depend on state, the $Y_{i}'s$ simply follows geometric distribution.

Closed Jackson network

In some applications once a job leaves the network, a new job is immediately released into the network. This type of network can be viewed as having a fixed number of jobs in the network, with no job ever leaving the network and no external job entering the network. In this sense, the network is "closed". It is also referred to as Gordon-Newell network

In closed Jackson network, $p_{0i}$ and $p_{j0}$ are 0 for all i and j., and $\sum _{j=1}^{J}p_{ij}=1$ for each row. Let $(\nu _{i})_{i=1}^{J}$ be the solution to

$\nu _{i}=\sum _{j=1}^{J}\nu _{j}p_{ji}\qquad (5)$

The solution is not unique so we need to add another equation. For example $\sum _{i=1}^{J}\nu _{i}=\nu _{0}$ for some constant $\nu _{0}$ or $\nu _{j}=1$for some $j$.

The equilibrium balance equations are given by:

$\pi (\mathbf {x} )\sum _{i=1}^{J}\mu _{i}(x_{i})(1-p_{ii})=\sum _{i=1}^{J}\sum _{j\neq i}\pi )\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.$

for all $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ such that $|\mathbf {x} |:=\sum _{i=1}^{J}x_{i}=N$. Similarly, define $|\mathbf {X} |:=\sum _{i=1}^{J}X_{i}$ and $|\mathbf {Y} |:=\sum _{i=1}^{J}Y_{i}$ where $\mathbf {X}$ and $\mathbf {Y}$ are defined before.

Theorem

For all $\mathbf {x} \in {\mathcal {Z}}_{+}^{J},|\mathbf {x} |=N$, we have:

$\pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i})/P(|\mathbf {Y} |=N)$

Where $\mathbf {Y}$ follow the distribution in $(3)$ with $\lambda _{i}$ is replaced by $\nu _{i}$.⟩

Proof

It sufficed to verify $(4)$, with terms involving $\alpha ,p_{i}0$ being zero and $\lambda _{i}$ replaced by $\nu _{i}$:

$\sum _{i=1}^{J}\nu _{i}(x_{i})(1-p_{ii})=\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\nu _{i}}{\nu _{j}}}p_{ij}\mu _{j}(x_{j}).$

Both sides of it are equal by taking using $(5)$ and interchanging summation on right side.⟩

This is an extension of Gordon-Newell theorem, where service rate can differ between states.

Example

A three-node closed Jackson network

We can modify the previous example a little to be a closed network with coefficients:

$P={\begin{bmatrix}0&0.5&0.5\\0.5&0.5&0\\0.5&0.5&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}}$ for all $x_{i}>0$

Additionally, suppose there are totally 3 jobs in the network.

Set $\nu _{1}=1$ and solve $(I-P')\nu =0$, we get:

$\nu ={\begin{bmatrix}1\\1.5\\0.5\end{bmatrix}}$

Hence we can know the distribution of $\mathbf {Y}$:

$P(Y_{1}=0)=(1+\sum _{n=1}^{\infty }({\frac {1}{15}})^{n})^{-1}={\frac {14}{15}}$

$P(Y_{2}=0)=(1+\sum _{n=1}^{\infty }({\frac {1.5}{12}})^{n})^{-1}={\frac {7}{8}}$

$P(Y_{3}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.5}{10}})^{n})^{-1}={\frac {19}{20}}$

This time, the probability that there is one job at each node is:

$\pi (1,1,1)=(P(Y_{1}=1)\cdot P(Y_{2}=1)\cdot P(Y_{3}=1))/P(|\mathbf {Y} |=3)=\prod _{j=1}^{3}P(Y_{j}=1)/\sum _{|\mathbf {y} |=3}P(\mathbf {Y} =\mathbf {y} )\approx 0.07097$

Semi-open Jackson Network

Semi-open net work has features of both open and closed networks: it follows the descriptions of the open model with the exception that the total number in the network is limited to a maximum of K jobs at any time.

It turns out that the semiopen model can be reduced to a closed network with K jobs and J+1 nodes. The additional node, indexed as node 0, represents the external world. Its service rate is defined as $\mu _{0}(n)=\alpha$ if $n>0$ and $\mu _{0}(0)=0$. This captures the blocking of the external arrivals when the buffer is full.

Set $\nu _{0}=1$ and $\nu _{i}=\lambda _{i}/\alpha$, then they are solutions to the set of equations:

$\nu _{i}=\sum _{j=0}^{J}\nu _{j}p_{ji}\qquad$

It is same as the one described in $(5)$ for a J+1 closed work.

Theorem

The semiopen Jackson network with an overall buffer capacity of K, has the following distribution: For all $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ such that $|\mathbf {x} |\leq K$,

$\pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i})/P(|\mathbf {Y} |\leq K),$

where $Y_{i}$ follows distribution in $(3)$.⟩

Proof

In a J+1 closed network, the equilibrium distribution satisfies:

$P(X_{0}=x_{0},\ldots ,X_{J}=x_{J})=P(X_{1}=x_{1},\ldots ,X_{J}=x_{J}),$

with $x_{0}=K-|\mathbf {x} |$.

Hence with $\nu _{0}=1$ and $\nu _{i}=\lambda _{i}/\alpha$, we have:

$\pi (\mathbf {x} )=P(X_{1}=X_{1},\ldots ,X_{J}=x_{j})=P(X_{0}=X_{0},\ldots ,X_{J}=x_{j}$

$={\frac {1}{C}}\cdot {\frac {1^{x_{0}}\prod _{i=1}^{J}({\frac {\lambda _{i}}{\alpha }})^{x_{i}}}{\alpha ^{x_{0}}\prod _{i=1}^{J}M_{i}(x_{i})}}={\frac {1}{C\alpha ^{K}}}\cdot \prod _{i=1}^{J}{\frac {\lambda _{i}^{x_{i}}}{M_{i}(x_{i})}},$

where $C$ is a normalizing constant. Hence we can write $\pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i})/C'$, and $C'$ is decided by:

$C'=\sum _{|\mathbf {x} |\leq K}\prod _{i=1}^{J}P(Y_{i}=x_{i})=P(|\mathbf {Y} |\leq K)).$⟩

Example

A semiopen three-node network

Suppose we have a semi-open network (consisting of nodes 1,2 and 3)with coefficients:

$\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}}$ for all $x_{i}>0$

and the number of jobs in the system is smaller than 4.

When the systme is not full, the arrival rate is $\lambda ={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}.$

We can use node 0 to represent the out-side world, and its service rate is $\mu _{0}(x_{0})=\alpha =5$. Then we have a closed network with 4 jobs and coefficients:

$P_{close}={\begin{bmatrix}0&0.5&0.5&0\\0&0&0.5&0.5\\1&0&0&0\\1&0&0&0\end{bmatrix}},\quad \mu _{close}={\begin{bmatrix}\mu _{0}(x_{0})\\\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}5\\15\\12\\10\end{bmatrix}}$ for all $x_{i}>0$

By setting $\nu _{0}=1$ and dividing $\lambda$ by $\alpha$, we can calculate $\nu _{close}={\begin{bmatrix}1\\0.5\\0.75\\0.25\end{bmatrix}}$

Then we have

$P(Y_{0}=0)=(1+\sum _{n=1}^{\infty }({\frac {1}{5}})^{n})^{-1}={\frac {4}{5}}$

$P(Y_{1}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.5}{15}})^{n})^{-1}={\frac {29}{30}}$

$P(Y_{2}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.75}{12}})^{n})^{-1}={\frac {15}{16}}$

$P(Y_{3}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.25}{10}})^{n})^{-1}={\frac {39}{40}}$

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

$\pi (X_{1}=X_{2}=X_{3}=1)=\prod _{j=1}^{3}P(Y_{j}=1)/\sum _{|\mathbf {y} |\leq 4}P(\mathbf {Y} =\mathbf {y} )\approx 0.00329$

Generalized Jackson Network

In generalized Jackson network, arrival processes can be renewal process that is not Poisson, and i.i.d. service time that needs not follow exponential distribution. The stationary distribution of generalized Jackson network usually does not have an explicit analytical form.

Approximation

Under some mild conditions the queue-length process $Q(t)$ of a open generalized Jackson network can be approximated by a reflected Brownian motion defined as $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')\mu$

$\Gamma =(\Gamma _{kl})$ with $\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}$

$R=I-P'$

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^{th}$ node.
$c_{j}$	variation of service time at $j^{th}$ node.
$c_{0,j}$	variation of inter-arrival time at $j^{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\}$

See also

• Jackson's theorem
• Gordon–Newell network
• BCMP network
• G-network
• M/M/1 queue
• M/M/c queue
• reflected Brownian motion

References

• Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0.
• Jackson, James R. (Oct. 1963). "Jobshop-like Queueing Systems". Management Science 10 (1): 131–142. DOI:10.1287/mnsc.1040.0268. JSTOR 2627213
• William J. Gordon and Gordon F. Newell (1967) Closed queueing systems with exponential servers in Operations Research 15 (2), 254–65
• Jackson, R. R. P. (1995). "Book review: Queueing networks and product forms: a systems approach". IMA Journal of Management Mathematics 6 (4): 382–384.

Category:Stochastic processes Category:Probability theorems Category:Queueing theory