Deriving the Product Form for Open Jackson Networks

Why a Network Can Have a Product-Form Distribution

In a queueing network, the service rate available at a node depends on whether that node is empty, while customers arriving at one node may have been served at another. The stationary queue lengths are therefore not independent by assumption. For an open Jackson network, however, under specific arrival, service, and routing conditions, their joint stationary distribution factors into one geometric term per node. The derivation hinges on matching the traffic entering each node with its total arrival rate and then checking balance for every possible network state.

Consider a continuous-time Markov chain \((X_t)_{t\ge0}\) on a probability space \((\Omega,\mathcal F,\mathbb P)\), with state space \(S=\mathbb Z_{\ge0}^J\). Here \(J\) is a finite set of nodes, and \(X_t=(X_t(1),\ldots,X_t(J))\) records the number of customers at each node. External arrivals to node \(i\) form independent Poisson processes with rates \(\gamma_i\ge0\). At node \(i\), customers are served one at a time, with independent exponential service times of rate \(\mu_i>0\). After service, a customer goes to node \(j\ne i\) with probability \(r_{ij}\), or leaves the network with probability \(r_{i0}\). Routing choices are independent of the past, service times, and external arrivals. In particular, \(r_{ii}=0\), \(r_{ij}\ge0\), \(r_{i0}\ge0\), and each routing row satisfies \(r_{i0}+\sum_{j\ne i}r_{ij}=1\).

The strict inequalities \(\rho_i<1\) ensure that the proposed geometric factors can be normalized. They are the node-by-node stability conditions used in this derivation. We do not need to assume that every state can be reached from every other state to verify stationarity; irreducibility is relevant if one also wants a uniqueness conclusion.

The Balance Calculation

Write \(e_i\) for the vector with coordinate \(1\) at node \(i\) and \(0\) elsewhere. From state \(n=(n_1,\ldots,n_J)\), an external arrival to \(i\) changes the state to \(n+e_i\) at rate \(\gamma_i\). If \(n_i>0\), a service completion at node \(i\) changes the state to \(n-e_i\) at rate \(\mu_i r_{i0}\), or to \(n-e_i+e_j\) at rate \(\mu_i r_{ij}\). The total rate out of \(n\) is therefore \(\sum_i\gamma_i+\sum_i\mu_i\mathbf 1_{\{n_i>0\}}\).

Here stationarity means that if \(X_0\) has distribution \(\pi\), then \(X_t\) also has distribution \(\pi\) for every \(t\ge0\). The proof checks balance at an arbitrary state \(n\), including states with empty queues.

Proof. Fix \(n\in S\). An incoming transition from an external arrival at node \(i\) can come from \(n-e_i\), and exists only if \(n_i\ge1\). An incoming transition caused by a service completion that leaves the network at node \(i\) comes from \(n+e_i\). An incoming transition caused by routing from \(i\) to \(j\ne i\) comes from \(n+e_i-e_j\), and exists only if \(n_j\ge1\). Dividing each incoming rate-weighted probability by the positive number \(\pi(n)\), the total incoming rate relative to \(\pi(n)\) is \[ \sum_i\frac{\gamma_i}{\rho_i}\mathbf 1_{\{n_i>0\}} +\sum_i\mu_i r_{i0}\rho_i +\sum_i\sum_{j\ne i}\mu_i r_{ij}\frac{\rho_i}{\rho_j}\mathbf 1_{\{n_j>0\}}. \] Indeed, the product formula gives \(\pi(n-e_i)/\pi(n)=1/\rho_i\) when \(n_i>0\), \(\pi(n+e_i)/\pi(n)=\rho_i\), and \(\pi(n+e_i-e_j)/\pi(n)=\rho_i/\rho_j\) when \(n_j>0\).

For each fixed \(j\), the coefficient of \(\mathbf 1_{\{n_j>0\}}\) in this expression is \[ \frac{\gamma_j+\sum_{i\ne j}\lambda_i r_{ij}}{\rho_j} =\frac{\lambda_j}{\rho_j} =\mu_j. \] The first equality uses the traffic equation at node \(j\); the second uses \(\rho_j=\lambda_j/\mu_j\). Thus the terms depending on which queues are nonempty sum to \(\sum_j\mu_j\mathbf 1_{\{n_j>0\}}\).

The remaining constant term is \(\sum_i\mu_i r_{i0}\rho_i=\sum_i\lambda_i r_{i0}\). Summing the traffic equations over all nodes and using \(\sum_{j\ne i}r_{ij}=1-r_{i0}\) gives \[ \sum_i\lambda_i=\sum_i\gamma_i+\sum_i\lambda_i(1-r_{i0}), \] so \(\sum_i\lambda_i r_{i0}=\sum_i\gamma_i\). The incoming rate relative to \(\pi(n)\) is consequently \(\sum_i\gamma_i+\sum_i\mu_i\mathbf 1_{\{n_i>0\}}\), exactly the outgoing rate from \(n\). This proves the global balance equation at every state.

It remains to verify that this balanced measure is a probability distribution and is stationary. Since \(0<\rho_i<1\), the geometric series gives \(\sum_{m\ge0}(1-\rho_i)\rho_i^m=1\) at each node. The sum of the nonnegative product over the countable state space is the product of these \(J\) sums, hence \(\sum_{n\in S}\pi(n)=1\). The total transition rate out of every state is at most \(c=\sum_i\gamma_i+\sum_i\mu_i<\infty\). Uniformize the chain at rate \(c\): its transition matrix is \(R=I+Q/c\), where \(Q\) is the generator. The global balance equations give \(\pi Q=0\), and therefore \(\pi R=\pi\). The transition probabilities at time \(t\) are \(e^{-ct}\sum_{k\ge0}(ct)^kR^k/k!\); multiplying by \(\pi\) leaves \(\pi\) unchanged because \(\pi R^k=\pi\) for every \(k\ge0\). Thus \(\pi\) is stationary. \(\square\)

This proof uses global balance: all incoming probability flow to each state equals all outgoing flow from it. In general, it does not establish detailed balance, which would require each individual transition flow to match its reverse transition flow.

Worked Examples

Why Detailed Balance Is a Common Mistake

A tempting but generally incorrect shortcut is to demand that every transition have a reverse transition with exactly matching probability flow. For the tandem network in the first example, state \((1,0)\) can move to \((0,1)\) when the customer at node 1 completes service and is routed to node 2. The rate of that transition is \(4(1/2)=2\). There is no transition from \((0,1)\) to \((1,0)\): a service completion at node 2 exits the network, and no customer can move from node 2 to node 1. Thus detailed balance cannot hold for this pair of states, even though the product form is stationary.

The correct calculation is the global balance calculation: at each state, add the flows from all possible predecessor states and compare their total with the total outgoing flow. The traffic equations make those sums match. They do not require each incoming flow to pair with a reverse flow.

The strict load condition also matters. For a single node with \(\gamma_1=1\), exit probability one, and \(\mu_1=1\), the traffic equation gives \(\lambda_1=1\) and \(\rho_1=1\). The proposed geometric weights would be \((1-\rho_1)\rho_1^n=0\) for every \(n\), which sum to zero rather than one. The normalization argument fails at \(\rho_1=1\); the product-form probability distribution derived here therefore requires strict inequality, not \(\rho_i\le1\).