Tandem Jackson Networks with Poisson Routing

From a Tandem Route to Node Loads

An open tandem network sends arriving jobs through an ordered sequence of service nodes. After service at a node, a job either moves to the next node or leaves the network. Even when the external input is a single Poisson stream, the nodes do not generally have the same arrival rate: each routing decision changes how many jobs reach the later stages. The first task is therefore to calculate the flow into each node before using single-server queue formulas.

Consider $m\ge1$ nodes in a line. External jobs arrive to node 1 according to a Poisson process of rate $\lambda>0$. Service times at node $i$ are independent exponential random variables with rate $\mu_i>0$. After service at node $i<m$, a job goes to node $i+1$ with probability $r_i$, and exits with probability $1-r_i$. After service at node $m$, it exits. Take $0\le r_i<1$, and set $r_m=0$ to represent the final exit. Routing choices, service times, and the external arrival process are independent.

Write $X_t=(X_t^{(1)},\ldots,X_t^{(m)})$ for the vector of numbers of jobs at the nodes at time $t$. On the probability space carrying the arrivals, services, and routing decisions, this is a continuous-time Markov chain with state space $S=\mathbb{Z}_{\ge0}^m$. Here $X_t^{(i)}$ counts all jobs at node $i$, including any job in service. The natural filtration is $\mathcal{F}_t=\sigma(X_s:0\le s\le t)$. Each service completion routes the job immediately, so a move from node $i$ to $i+1$ changes both coordinates at once.

Definition: The effective arrival rate, or throughput, at node $i$ is denoted by $\lambda_i$. It is the long-run rate of jobs reaching that node. For a tandem route, $$ \lambda_1=\lambda,\qquad \lambda_i=\lambda_{i-1}r_{i-1}\quad (2\le i\le m), $$ so $\lambda_i=\lambda\prod_{k=1}^{i-1}r_k$, with the empty product equal to $1$. Node $i$ is stable when $\lambda_i<\mu_i$; the network’s product-form stationary distribution requires this strict inequality at every node.

The recursion follows by counting flow across each link: only the fraction $r_{i-1}$ of completions at node $i-1$ proceeds to node $i$. In particular, a downstream rate is not usually the external rate $\lambda$. Define the utilization $\rho_i=\lambda_i/\mu_i$. Under the stability conditions, $0\le\rho_i<1$.

Product Form and Its Justification

The state process has external-arrival transitions $x\to x+e_1$ at rate $\lambda$. If $x_i>0$, a service completion at node $i<m$ produces $x\to x-e_i+e_{i+1}$ at rate $r_i\mu_i$, or $x\to x-e_i$ at rate $(1-r_i)\mu_i$. At node $m$, the completion transition $x\to x-e_m$ occurs at rate $\mu_m$. Here $e_i$ is the vector with a 1 in coordinate $i$ and zeros elsewhere.

Theorem (Tandem Jackson product form): Suppose $\lambda>0$, $\mu_i>0$, $0\le r_i<1$, and $\lambda_i<\mu_i$ for every node. A stationary distribution of the queue-length process is $$ \pi(x_1,\ldots,x_m)=\prod_{i=1}^{m}(1-\rho_i)\rho_i^{x_i}, \qquad x_i\in\mathbb{Z}_{\ge0}. $$ When $\rho_i=0$, the corresponding factor is interpreted as $1$ at $x_i=0$ and $0$ at $x_i>0$. Thus, in stationarity, the node queue lengths are independent geometric random variables.

Proof. First, each factor is normalized: for $0\le\rho_i<1$, $\sum_{k=0}^{\infty}(1-\rho_i)\rho_i^k=1$, including the degenerate case $\rho_i=0$. Hence $\sum_{x\in S}\pi(x)=1$. To verify stationarity, it is enough to check the global balance equations and then use bounded rates to pass from those equations to invariance.

Fix a state $x$. Its total outgoing rate is $\lambda+\sum_{i=1}^m\mu_i\mathbf{1}_{\{x_i>0\}}$. Incoming transitions from external arrivals contribute $\mu_1\pi(x)$ if $x_1>0$, and zero otherwise: when $x_1>0$, the predecessor is $x-e_1$, and $\lambda\pi(x-e_1)=\lambda\pi(x)/\rho_1=\mu_1\pi(x)$ if $\rho_1>0$. If $\rho_1=0$, then $\lambda_1=\lambda=0$ would be required, contrary to $\lambda>0$; thus this case does not arise at node 1.

For an internal transition from node $i-1$ to node $i$, where $2\le i\le m$, an incoming predecessor exists exactly when $x_i>0$; it is $x+e_{i-1}-e_i$. Its contribution is $$ r_{i-1}\mu_{i-1}\pi(x+e_{i-1}-e_i) =r_{i-1}\mu_{i-1}\frac{\rho_{i-1}}{\rho_i}\pi(x) =\mu_i\pi(x), $$ because $\rho_{i-1}\mu_{i-1}=\lambda_{i-1}$ and $\lambda_i=r_{i-1}\lambda_{i-1}$. If $\rho_i=0$, then $x_i>0$ has $\pi(x)=0$, and the incoming term is zero as well; thus the same balance holds on the support of $\pi$.

Finally, an incoming exit from node $i$ has predecessor $x+e_i$. Its contribution is $(1-r_i)\mu_i\pi(x+e_i)=(1-r_i)\lambda_i\pi(x)$, including $i=m$, where $r_m=0$. Summing the internal-arrival contributions, the external-arrival contribution, and the exit contributions gives total incoming rate times $\pi(x)$ equal to $$ \pi(x)\left(\sum_{i=1}^{m}\mu_i\mathbf{1}_{\{x_i>0\}}+ \sum_{i=1}^{m}(1-r_i)\lambda_i\right). $$ The flow recursion and $r_m=0$ give $\sum_{i=1}^{m}(1-r_i)\lambda_i=\lambda_1-\lambda_2+\lambda_2-\cdots-\lambda_m=\lambda$. This equals the outgoing rate times $\pi(x)$, proving global balance.

For completeness, the total transition rate is bounded above by $c=\lambda+\sum_i\mu_i$. Uniformize the chain using the transition matrix $R=I+Q/c$, where $Q$ is its rate matrix. Global balance says $\pi Q=0$, so $\pi R=\pi$. The continuous-time transition matrix is $e^{-ct}\sum_{n\ge0}(ct)^nR^n/n!$; consequently $\pi P(t)=\pi$ for every $t\ge0$. Thus $\pi$ is stationary. Its factorization gives independence of the node counts. $\square$

Nodewise and Network-Wide Performance

A geometric random variable $Y$ with probabilities $\mathbb{P}(Y=k)=(1-\rho)\rho^k$, $k\ge0$, has mean $\rho/(1-\rho)$. For $0<\rho<1$, this follows by differentiating $\sum_{k\ge0}\rho^k=(1-\rho)^{-1}$: $\sum_{k\ge0}k\rho^k=\rho/(1-\rho)^2$, and multiplication by $1-\rho$ gives the mean. For $\rho=0$, $Y=0$ with probability one, and the same mean formula gives zero.

Consequence: In the stationary tandem network, $$ \mathbb{E}[X_t^{(i)}]=\frac{\rho_i}{1-\rho_i} =\frac{\lambda_i}{\mu_i-\lambda_i}, \qquad \mathbb{P}(X_t^{(i)}=0)=1-\rho_i. $$ By Little’s law at node $i$, the mean time a job spends there, including waiting and service, is $$ W_i=\frac{\mathbb{E}[X_t^{(i)}]}{\lambda_i} =\frac{1}{\mu_i-\lambda_i}, $$ when $\lambda_i>0$. If $\lambda_i=0$, no jobs visit that node in stationarity, so this per-visit mean is not defined by the ratio.

Little’s law here relates the stationary mean number at a node to the rate of jobs visiting it and their mean time at that node. It does not say that each node sees the external rate. The total number in the network is $N_t=\sum_iX_t^{(i)}$; linearity of expectation gives $\mathbb{E}[N_t]=\sum_i\lambda_i/(\mu_i-\lambda_i)$. Independence also gives $\mathbb{P}(N_t=0)=\prod_i(1-\rho_i)$. These aggregate quantities summarize occupancy; they do not by themselves give the distribution of a job’s total time across its route.

Worked Example: Three Nodes with Partial Forward Routing

External arrivals have rate $\lambda=2$. At node 1, a completion goes to node 2 with probability $r_1=\tfrac12$; at node 2, it goes to node 3 with probability $r_2=\tfrac13$; node 3 always exits. Service rates are $(\mu_1,\mu_2,\mu_3)=(4,3,2)$. The routing rows, including exit, are $(\tfrac12,\tfrac12)$, $(\tfrac13,\tfrac23)$, and $(1)$; each sums to $1$.

The flow rates are $\lambda_1=2$, $\lambda_2=2\cdot\tfrac12=1$, and $\lambda_3=1\cdot\tfrac13=\tfrac13$. The utilizations are $\rho_1=2/4=\tfrac12$, $\rho_2=1/3=\tfrac13$, and $\rho_3=(\tfrac13)/2=\tfrac16$, all strictly below $1$. The node mean queue lengths are therefore $$ \mathbb{E}[X^{(1)}]=\frac{1/2}{1-1/2}=1,\qquad \mathbb{E}[X^{(2)}]=\frac{1/3}{1-1/3}=\frac12,\qquad \mathbb{E}[X^{(3)}]=\frac{1/6}{1-1/6}=\frac15. $$

The nodewise mean times are $W_1=1/(4-2)=\tfrac12$, $W_2=1/(3-1)=\tfrac12$, and $W_3=1/(2-\tfrac13)=\tfrac35$. The total mean number in the network is $1+\tfrac12+\tfrac15=\tfrac{17}{10}$, and the probability that all three nodes are empty is $(1-\tfrac12)(1-\tfrac13)(1-\tfrac16)=\tfrac12\cdot\tfrac23\cdot\tfrac56=\tfrac5{18}$.

Check: At each node, $\lambda_iW_i$ reproduces its mean queue length: $2\cdot\tfrac12=1$, $1\cdot\tfrac12=\tfrac12$, and $\tfrac13\cdot\tfrac35=\tfrac15$. The routing flow also gives total exit rate $2\cdot\tfrac12+1\cdot\tfrac23+\tfrac13=1+\tfrac23+\tfrac13=2$, equal to the external rate.

Worked Example: Two Nodes and the Total Occupancy Distribution

Let $\lambda=\tfrac32$, let $r_1=\tfrac23$, and let the service rates be $\mu_1=3$, $\mu_2=2$. The routing probabilities are $(\tfrac23,\tfrac13)$ at node 1 and $1$ to exit at node 2; both routing rows sum to $1$.

The node rates are $\lambda_1=\tfrac32$ and $\lambda_2=\tfrac32\cdot\tfrac23=1$. Thus $\rho_1=(\tfrac32)/3=\tfrac12$ and $\rho_2=1/2=\tfrac12$, so both nodes are stable. The stationary probability of state $(x_1,x_2)$ is $$ \pi(x_1,x_2)=\left(\frac12\right)^2\left(\frac12\right)^{x_1+x_2} =\frac14\left(\frac12\right)^{x_1+x_2}. $$ The mean at each node is $(1/2)/(1-1/2)=1$, hence the total mean occupancy is $2$. The empty-network probability is $\pi(0,0)=\tfrac14$. Exactly one job is present in states $(1,0)$ and $(0,1)$, each having probability $\tfrac14\cdot\tfrac12=\tfrac18$; therefore $\mathbb{P}(N_t=1)=\tfrac18+\tfrac18=\tfrac14$.

Check: The product-form probabilities sum to $1$, since $\sum_{x_1,x_2\ge0}\tfrac14(1/2)^{x_1+x_2}=\tfrac14\cdot2\cdot2=1$. The nodewise times are $1/(3-\tfrac32)=\tfrac23$ and $1/(2-1)=1$; multiplying by their respective rates gives $(\tfrac32)(\tfrac23)=1$ and $1\cdot1=1$, as required.

Worked Example: A Later Node Can Dominate Occupancy

Let $\lambda=1$, $r_1=\tfrac34$, and $(\mu_1,\mu_2)=(2,1)$. At node 1 the routing probabilities are $(\tfrac34,\tfrac14)$, and node 2 exits with probability $1$; each row sums to $1$. The node rates are $\lambda_1=1$ and $\lambda_2=1\cdot\tfrac34=\tfrac34$. The utilizations are $\rho_1=\tfrac12$ and $\rho_2=\tfrac34$, so the strict stability conditions hold.

The means are $\mathbb{E}[X^{(1)}]=(\tfrac12)/(\tfrac12)=1$ and $\mathbb{E}[X^{(2)}]=(\tfrac34)/(\tfrac14)=3$, giving total mean occupancy $4$. The nodewise times are $W_1=1/(2-1)=1$ and $W_2=1/(1-\tfrac34)=4$.

Check: $\lambda_1W_1=1\cdot1=1$ and $\lambda_2W_2=\tfrac34\cdot4=3$. The larger mean at node 2 results from its higher utilization, even though only three quarters of external jobs reach it.

Stability and a Common Routing Error

The strict condition $\lambda_i<\mu_i$ is required at every node, not just at the first one. For example, with external rate $1$, routing probability $r_1=\tfrac12$, and service rates $\mu_1=2$, $\mu_2=\tfrac12$, the second-node rate is $\lambda_2=\tfrac12$. It equals $\mu_2$, so $\rho_2=1$; the proposed geometric factor at that node cannot be normalized, and there is no stationary product-form distribution of the stated kind.

Common mistake: assigning the external rate to every node. In the first worked example, the rate into node 3 is $\tfrac13$, not $2$, because a job must first take the node-1-to-node-2 route and then the node-2-to-node-3 route. Using $2$ at node 3 would give the incorrect utilization $2/2=1$ and incorrectly declare the network unstable. The correct calculation is $\lambda_3=2\cdot\tfrac12\cdot\tfrac13=\tfrac13$, giving $\rho_3=(\tfrac13)/2=\tfrac16$. The routing probabilities determine the node loads before any queue formula is applied.

Check Your Understanding

Use the routing recursion and the strict stability test before computing stationary quantities.

A two-node tandem has external rate $2$, routing probability $r_1=\tfrac14$, and service rates $\mu_1=4$, $\mu_2=1$. Find both effective arrival rates and utilizations, then determine whether the product form applies.
For a stable node with arrival rate $\tfrac23$ and service rate $2$, calculate its utilization, stationary mean queue length, and mean time in the node.
In a two-node network with $\rho_1=\tfrac13$ and $\rho_2=\tfrac12$, find the probability that both nodes are empty.
Explain why the nodewise mean time formula $W_i=\mathbb{E}[X^{(i)}]/\lambda_i$ is not defined for a node with $\lambda_i=0$.
Give the flow-rate formula for node $i$ in a tandem and identify the condition needed at every node for a normalizable product-form distribution.

Tandem Jackson Networks with Poisson Routing

What You'll Learn