Diagnosing When Jackson Product Form Applies

What Must Be Checked Before Using Product Form?

A product-form expression can make a network's stationary distribution look deceptively easy to obtain. But the formula is a theorem with specific assumptions, not a general rule for queues connected by routes. Before calculating probabilities, check that customers arrive externally according to independent Poisson processes, service times are exponential, routing probabilities do not depend on the network state, and every station is stable. A failure can invalidate the standard result even when the traffic equations have a formal solution.

Consider a finite collection of stations $1,\dots,J$. On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $N_t=(N_1(t),\dots,N_J(t))$ be the continuous-time process of numbers of customers at the stations, with state space $\mathbb{Z}_{\ge0}^{J}$ and natural filtration $(\mathcal{F}_t)_{t\ge0}$. For the standard open Jackson model considered here, station $i$ is a single-server, infinite-capacity queue, with independent exponential service times of rate $\mu_i>0$. External arrivals to station $i$ form a Poisson process of rate $\gamma_i\ge0$, independent across stations and of service and routing. After service at station $i$, a customer goes to station $j$ with fixed probability $r_{ij}$, or leaves the network with probability $r_{i0}$. These routing choices are independent of the queue lengths and of other customers' choices.

Definition: The routing probabilities satisfy $r_{ij}\ge0$ and $r_{i0}\ge0$, with $\sum_{j=1}^J r_{ij}+r_{i0}=1$ for every $i$. The routing matrix is $R=(r_{ij})_{1\le i,j\le J}$. The nominal traffic rate $\lambda_i$ is the external-arrival rate to station $i$, together with the expected rate of visits to $i$ induced by external customers' full routes. It is not, by definition, the actual service-completion rate.

The word open means that customers can leave the network and that the route of an external customer ends after finitely many visits with probability one. For a finite routing matrix, a standard sufficient condition is $\rho(R)<1$, where $\rho(R)$ is the spectral radius. Under that condition, expected numbers of visits are finite. The traffic equations are

\lambda_i=\gamma_i+\sum_{j=1}^J\lambda_j r_{ji},\qquad i=1,\dots,J.

These equations account for visits generated by routes; they do not assert that an overloaded queue completes work at its nominal rate. When $\rho(R)<1$, they have the finite solution $\lambda=\sum_{k=0}^{\infty}(R^{\mathsf T})^k\gamma$, with $\lambda$ and $\gamma$ regarded as column vectors in this expression.

Proof. Pre-sample each external customer's complete route using the fixed routing probabilities, independently of the queueing process. Starting at a station $a$, the probability that the customer visits station $i$ after exactly $k$ routing steps is the $i$-coordinate of the row vector $e_aR^k$, where $e_a$ has a $1$ in coordinate $a$ and $0$ elsewhere. Thus the expected number of visits to each station from an external customer entering at $a$ is the vector $\sum_{k\ge0}e_aR^k$. Since $\rho(R)<1$, the matrix geometric series converges and equals $(I-R)^{-1}$. Summing the expected visit counts over external arrival streams gives $\lambda=\gamma+R^{\mathsf T}\lambda$, equivalently $\lambda=\sum_{k\ge0}(R^{\mathsf T})^k\gamma$. This counts expected visits in customers' routes; no step identifies nominal rates with completion rates. $\square$

Standard open Jackson product-form theorem: For a finite open network of single-server stations with independent Poisson external arrivals, independent exponential service times of rates $\mu_i$, and fixed state-independent routing probabilities, suppose $\rho(R)<1$ and the traffic equations have rates $\lambda_i$. If $\lambda_i<\mu_i$ for every station, the stationary distribution is $$ \mathbb{P}(N_1=n_1,\dots,N_J=n_J)=\prod_{i=1}^J(1-\rho_i)\rho_i^{n_i},\qquad n_i\ge0,\qquad \rho_i=\frac{\lambda_i}{\mu_i}. $$ This standard result is proved in the earlier material on deriving the product form. The strict inequalities are required for this expression to define a stationary probability distribution.

Two Checks: Traffic Equations and Stability

The traffic equations use external arrivals and fixed routing probabilities to calculate nominal visit rates. The stability check then compares those rates with service capacity. Both checks matter: solving the traffic equations does not by itself establish stability or a stationary distribution.

Proposition (normalization of the candidate product form). For a finite number of stations, the displayed product-form expression sums to $1$ over $\mathbb{Z}_{\ge0}^J$ if and only if $0\le\rho_i<1$ at every station.

Proof. Each factor is nonnegative when $0\le\rho_i<1$. In that case, summing the product over all vectors of nonnegative integers separates into a product of geometric series: $\prod_i (1-\rho_i)\sum_{n_i\ge0}\rho_i^{n_i}=\prod_i(1-\rho_i)/(1-\rho_i)=1$. If some $\rho_i=1$, the corresponding series has infinitely many terms equal to $1$, so the sum diverges. If some $\rho_i>1$, its terms do not tend to zero, so it also diverges. A negative $\rho_i$ is not possible here because $\lambda_i\ge0$ and $\mu_i>0$. Thus the product is a probability distribution exactly when each $\rho_i<1$. $\square$

This proposition checks normalization, not the whole Jackson theorem: the theorem's arrival, service, and routing assumptions are still needed for the candidate to be stationary. In particular, a normalized expression cannot repair a model with state-dependent routing or nonexponential service.

Worked Example: Fixed Routing with Feedback

Consider two stations with external rates $\gamma_1=\tfrac12$, $\gamma_2=\tfrac14$, service rates $\mu_1=\mu_2=1$, and routing probabilities $r_{12}=\tfrac12$, $r_{21}=\tfrac14$, $r_{11}=r_{22}=0$. The exit probabilities are $r_{10}=\tfrac12$ and $r_{20}=\tfrac34$. The routing-row checks are $0+\tfrac12+\tfrac12=1$ and $\tfrac14+0+\tfrac34=1$. Thus the routing probabilities, including exits, sum to $1$ in each row.

The traffic equations are $\lambda_1=\tfrac12+\tfrac14\lambda_2$ and $\lambda_2=\tfrac14+\tfrac12\lambda_1$. Substituting the second into the first gives $\lambda_1=\tfrac12+\tfrac14(\tfrac14+\tfrac12\lambda_1)=\tfrac9{16}+\tfrac18\lambda_1$. Hence $\tfrac78\lambda_1=\tfrac9{16}$, so $\lambda_1=\tfrac9{14}$. Then $\lambda_2=\tfrac14+\tfrac12\cdot\tfrac9{14}=\tfrac14+\tfrac9{28}=\tfrac47$.

Check: $\tfrac12+\tfrac14\cdot\tfrac47=\tfrac12+\tfrac17=\tfrac9{14}$, and $\tfrac14+\tfrac12\cdot\tfrac9{14}=\tfrac14+\tfrac9{28}=\tfrac47$. The utilizations are $\rho_1=\tfrac9{14}<1$ and $\rho_2=\tfrac47<1$. Under the stated Poisson, exponential-service, and fixed-routing assumptions, the theorem gives $\mathbb{P}(N_1=n_1,N_2=n_2)=(\tfrac5{14})(\tfrac37)(\tfrac9{14})^{n_1}(\tfrac47)^{n_2}$. At $(n_1,n_2)=(0,0)$, this is $\tfrac{15}{98}$; it is one value from the normalized product distribution.

Why Nominal Traffic Is Not Always Completion Flow

A common error is to use $\lambda_j r_{ji}$ as the actual completion flow from $j$ to $i$ without first establishing a stable stationary regime. The traffic equations define nominal visit rates from external customer routes. In a stable network, actual long-run flows can be related to these rates using flow conservation. Without stability, the equation still describes nominal route counts, but it does not say that an overloaded station completes customers at rate $\lambda_j$.

Worked Example: An Overloaded M/M/1 Queue

Take one station with external Poisson arrival rate $\gamma_1=\tfrac32$, service rate $\mu_1=1$, and routing probability $r_{11}=0$, $r_{10}=1$. The routing row checks: $0+1=1$. The traffic equation gives the nominal rate $\lambda_1=\gamma_1=\tfrac32$, and the utilization ratio is $\rho_1=\tfrac32>1$. The geometric factor $(1-\rho_1)\rho_1^n$ is not a probability distribution: its leading factor is negative, and its terms do not sum to $1$.

While the queue is nonempty, its instantaneous service-completion rate is $\mu_1=1$, not $\tfrac32$. Indeed, at state $N_1(t)=n$, the completion intensity is $1$ if $n\ge1$, and $0$ if $n=0$. The nominal traffic equation is still correct as an accounting of external customers' routes, but treating its solution as the completion rate would confuse offered workload with served workload. The stability condition fails, so the open Jackson stationary product formula cannot be used.

Diagnosing Routing and Service Violations

State-independent routing means the probability of a customer's next destination after service at $i$ is the same for every network state. This is stronger than saying that each customer's route is random: a destination rule that depends on another queue's length makes the probability conditional on the state. Similarly, exponential service is not just a convenient choice of mean. Its memoryless property allows the queue-length vector to be represented as a continuous-time Markov chain with the standard Jackson transition rates.

Worked Example: Routing Depends on Another Queue

Suppose an external Poisson stream enters station $1$, and both stations have exponential service rate $1$. After service at station $1$, a customer goes to station $2$ if $N_2(t)=0$, and leaves if $N_2(t)>0$. In state $n=(n_1,n_2)$, the routing probability from station $1$ to station $2$ is $1$ when $n_2=0$, but $0$ when $n_2>0$. The exit probability is the complementary value, so for either state the routing probabilities plus exit probability sum to $1$.

There is no fixed number $r_{12}$ that describes this rule across all states. Therefore the state-independent routing assumption fails, and the standard open Jackson product-form theorem does not apply. One must not substitute an average routing probability into the fixed-routing traffic equations and infer a Jackson product form: the routing decision is tied to the network state, which is precisely what those equations' fixed probabilities exclude.

Worked Example: Deterministic Service Is Not Jackson Service

Consider a single M/G/1 queue with Poisson arrival rate $\lambda=\tfrac12$, deterministic service time $1$, and routing probability $r_{10}=1$. The routing check is $0+1=1$. The mean service time is $1$, so the service capacity based on the mean is $\mu=1$ and the traffic intensity is $\rho=\lambda\mathbb{E}[S]=\tfrac12<1$. Stability alone does not make this an M/M/1 queue: deterministic service is not exponential.

For this M/G/1 queue, the standard Pollaczek–Khinchine queue-length transform gives the stationary probability generating function of the number $N$ in the system: $G_N(z)=(1-\rho)(1-z)B^*(\lambda(1-z))/(B^*(\lambda(1-z))-z)$, where $B^*(s)=\mathbb{E}[e^{-sS}]$ is the service-time transform. Here $B^*(s)=e^{-s}$, so $G_N(z)=\tfrac12(1-z)e^{-(1-z)/2}/(e^{-(1-z)/2}-z)$.

At $z=0$, this gives $\mathbb{P}(N=0)=G_N(0)=\tfrac12$. To calculate the coefficient of $z$, write $B(z)=e^{-(1-z)/2}$, so $B(0)=e^{-1/2}$, $B'(0)=\tfrac12 e^{-1/2}$, and $G_N(z)=\tfrac12(1-z)B(z)/(B(z)-z)$. Differentiating at $0$ gives $G_N'(0)=\tfrac12(e^{1/2}-1)$. Thus $\mathbb{P}(N=1)=\tfrac12(e^{1/2}-1)$, which is not the geometric M/M/1 value $(1-\rho)\rho=\tfrac14$: equality would require $e^{1/2}=\tfrac32$, whereas $e^{1/2}>1+\tfrac12=\tfrac32$. The queue is stable, but its stationary queue-length distribution is not the Jackson geometric factor. This calculation uses the standard M/G/1 transform from the earlier material on the Pollaczek–Khinchine formula.

A Practical Diagnostic Checklist

Before applying the open Jackson product form, check the model in this order:

Open routing: Each routing row, including its exit probability, sums to $1$, and routes end with probability $1$. Check that expected visit counts are finite, for example by verifying $\rho(R)<1$.
External arrivals: Each station's external input is Poisson, with independent streams under the standard model.
Service: Each station has independent exponential service times and the specified service capacity. A general service-time distribution is not covered by this standard product form.
Routing: Probabilities are fixed by the station and do not depend on queue lengths, elapsed service, or other network state.
Traffic and stability: Solve the nominal traffic equations, then check $\lambda_i<\mu_i$ at every station. Do not use nominal rates as actual completion rates in an overloaded system.

Common mistake. A tempting but incorrect calculation is to write “station $j$ sends customers to $i$ at rate $\lambda_j r_{ji}$” immediately after solving the traffic equations. For the overloaded example, that would give an asserted flow of $\tfrac32$ departures per unit time even though the service-completion intensity is at most $1$ at every instant. The correction is to treat $\lambda_j$ first as a nominal rate obtained from expected visits along routes. Interpret it as a stationary flow only after the model's stability and stationarity conditions have been established.

Check Your Understanding

For each question, identify which assumptions or calculations are relevant before deciding whether the standard product form applies.

A two-station network has fixed routing probabilities and exponential service, but its traffic equations give $\lambda_2=\mu_2$. Can the normalized geometric product form be used? Explain.
Why do the traffic equations describe nominal route visits even if a station is overloaded?
At a station with service rate $2$, what is the instantaneous completion intensity when its queue is empty? What is it when the queue is nonempty?
A customer is routed from station $1$ to station $2$ with probability $1$ when station $2$ is empty and probability $0$ otherwise. Which Jackson assumption fails?
A stable single-station queue has Poisson arrivals and deterministic service. Why is stability not enough to justify the M/M/1 geometric stationary distribution?