Jackson network

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

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

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

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

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

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

A three-node open Jackson network

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

${\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }$

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

Then by the theorem, we can calculate:

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

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

${\displaystyle P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}$

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

${\displaystyle 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:

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

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

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

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

${\displaystyle \theta =\alpha -(I-P^{T})\mu }$

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

${\displaystyle R=I-P^{T}}$

where the symbols are defined as:

Definitions of symbols in the approximation formula

symbol	Meaning
${\displaystyle \alpha =(\alpha _{j})_{j=1}^{J}}$	a J-vector specifying the arrival rates to each node.
${\displaystyle \mu =(\mu )_{j=1}^{J}}$	a J-vector specifying the service rates of each node.
${\displaystyle P}$	routing matrix.
${\displaystyle \lambda _{j}}$	effective arrival of ${\displaystyle j^{\text{th}}}$ node.
${\displaystyle c_{j}}$	variation of service time at ${\displaystyle j^{\text{th}}}$ node.
${\displaystyle c_{0,j}}$	variation of inter-arrival time at ${\displaystyle j^{\text{th}}}$ node.
${\displaystyle \delta _{ij}}$	coefficients to specify correlation between nodes. They are defined in this way: Let ${\displaystyle A(t)}$ be the arrival process of the system, then ${\displaystyle A(t)-\alpha t{}\approx {\hat {A}}(t)}$ in distribution, where ${\displaystyle {\hat {A}}(t)}$ is a driftless Brownian process with covariate matrix ${\displaystyle \Gamma ^{0}=(\Gamma _{ij}^{0})}$, with ${\displaystyle \Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}}$, for any ${\displaystyle i,j\in \{1,\dots ,J\}}$