Tutorials › Stochastic Processes › Computing Stationary Probabilities in Jackson Networks

Home  /  Tutorials  /  M/G/1 Queues and Networks

M/G/1 Queues and Networks · Tutorial 685 of 994

Computing Stationary Probabilities in Jackson Networks

You will turn Jackson network traffic rates into a normalized stationary distribution and use it to compute queue-length probabilities.

Advanced 10 min read

What You'll Learn

  • Set up routing probabilities and traffic equations for an open Jackson network.
  • Check the stability condition required for the stationary product form.
  • Normalize the product-form weights across the network state space.
  • Compute joint and marginal stationary queue-length probabilities.
  • Find probabilities of specified total-occupancy events.
  • Recognize why external arrival rates cannot replace total traffic rates.

From Traffic Rates to Queue-Length Probabilities

In an open Jackson network, customers may visit several service stations before leaving. The stationary probability of a network state depends on the total rate of traffic through each station, not just on the external arrivals to it. Once those rates are known, the product form reduces many network probability calculations to geometric probabilities and finite sums.

Consider \(J\) single-server stations. Customers arrive externally to station \(i\) at rate \(\alpha_i\), receive exponential service at rate \(\mu_i>0\), and after service at station \(i\) go to station \(j\) with probability \(r_{ij}\) or leave the network with probability \(r_{i0}\). Thus \(r_{ij}\ge0\), \(r_{i0}\ge0\), and \(r_{i0}+\sum_{j=1}^Jr_{ij}=1\) for every \(i\). The traffic rates \(\lambda_i\) solve \(\lambda_j=\alpha_j+\sum_{i=1}^J\lambda_i r_{ij}\). The state at time \(t\) is \(X_t=(X_t^{(1)},\ldots,X_t^{(J)})\), the queue lengths, on the state space \(S=\mathbb{N}_0^J\), where \(\mathbb{N}_0=\{0,1,2,\ldots\}\). This is a continuous-time Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\).

Definition: For each station set \(\rho_i=\lambda_i/\mu_i\). The network is in the stable regime considered here when \(0<\lambda_i<\mu_i\) for every station, so \(0<\rho_i<1\). The open Jackson product-form result states that the stationary probability of \(x=(x_1,\ldots,x_J)\in S\) is proportional to \(\prod_i\rho_i^{x_i}\). Its product-form assertion is the standard result established in the derivation of the product form; here we normalize it and use it for probability calculations.

Normalizing the Product Form

The product-form weights are not probabilities until their sum over all possible queue-length vectors is one. Since each \(\rho_i\) lies strictly between zero and one, each coordinate contributes a convergent geometric series.

Theorem: Under the stated stability conditions, the normalizing constant for the weights \(w(x)=\prod_{i=1}^J\rho_i^{x_i}\), \(x\in\mathbb{N}_0^J\), is \(Z=\prod_{i=1}^J(1-\rho_i)^{-1}\). The normalized stationary probability is \(\pi(x)=\prod_{i=1}^J(1-\rho_i)\rho_i^{x_i}\). Consequently, at a stationary time the queue lengths at the different stations are independent, and station \(i\) has geometric probabilities \(\pi_i(n)=(1-\rho_i)\rho_i^n\), \(n\in\mathbb{N}_0\).

Proof. For any integer \(m\ge0\), the finite geometric sum is \(\sum_{n=0}^m\rho_i^n=(1-\rho_i^{m+1})/(1-\rho_i)\). As \(m\) increases, this tends to \(1/(1-\rho_i)\), since \(0<\rho_i<1\). Sum the nonnegative weights first over the finite box \(0\le x_i\le m\) for every \(i\). Distributing this finite sum across coordinates gives \(\sum_{0\le x_1,\ldots,x_J\le m}\prod_i\rho_i^{x_i}=\prod_i\sum_{n=0}^m\rho_i^n\). Increasing \(m\) exhausts the countable state space, so the sum of all weights is the limit of these increasing finite-box sums, namely \(Z=\prod_i(1-\rho_i)^{-1}\). Dividing each weight by \(Z\) gives the displayed \(\pi(x)\), and summing it over \(S\) gives one. To obtain the marginal at station \(i\), sum \(\pi(x)\) over every coordinate other than \(i\). Each such coordinate contributes \(\sum_{n\ge0}(1-\rho_k)\rho_k^n=1\), leaving \((1-\rho_i)\rho_i^{x_i}\). Finally, the joint probability factors into the product of these marginals, which is precisely independence at a stationary time. \(\square\)

Useful consequences follow by summing the marginal geometric probabilities. For any integer \(a\ge0\), \(\mathbb{P}(X^{(i)}\ge a)=\rho_i^a\), since \(\sum_{n=a}^{\infty}(1-\rho_i)\rho_i^n=\rho_i^a\). In particular, \(\mathbb{P}(X^{(i)}=0)=1-\rho_i\). For several specified queue lengths, multiply their marginal probabilities; for an event involving a total queue length, enumerate or sum the corresponding joint probabilities.

Worked Example: A Two-Station Tandem Network

External arrivals enter station 1 at rate \(\alpha_1=1\), and \(\alpha_2=0\). After station 1, a customer goes to station 2 with probability \(r_{12}=\tfrac12\), or leaves with probability \(r_{10}=\tfrac12\). Station 2 sends every completed customer out, so \(r_{20}=1\). The routing rows sum to one: \(\tfrac12+\tfrac12=1\) for station 1 and \(1=1\) for station 2. Let \(\mu_1=4\) and \(\mu_2=3\). Find the stationary probability that the queue lengths are \((2,1)\), and the probability that station 1 has at least two customers.

The traffic equations give \(\lambda_1=1\) and \(\lambda_2=\lambda_1/2=1/2\). Thus \(\rho_1=1/4\) and \(\rho_2=(1/2)/3=1/6\), both strictly less than one. The stationary probability of \((2,1)\) is

$$ \pi(2,1)=\left(\frac34\right)\left(\frac14\right)^2 \left(\frac56\right)\left(\frac16\right) =\frac{3}{64}\cdot\frac{5}{36} =\frac{15}{2304} =\frac{5}{768}. $$

The marginal tail formula gives \(\mathbb{P}(X^{(1)}\ge2)=\rho_1^2=(1/4)^2=1/16\). As a normalization check, the two marginal geometric series have total masses \((3/4)\sum_{n\ge0}(1/4)^n=1\) and \((5/6)\sum_{n\ge0}(1/6)^n=1\). Their product therefore sums to one over all network states, as required.

Using the Joint and Marginal Laws

For a particular vector \(x\), the computation is direct: find each traffic rate, divide by the corresponding service rate, and substitute into the normalized product. A marginal probability requires summing over the other stations, but the theorem shows that those sums equal one. For an event about the total number of customers, independence still helps, although the event generally requires adding multiple joint probabilities.

Worked Example: Feedback Changes the Traffic Rates

Consider two stations with external rates \(\alpha_1=1/2\) and \(\alpha_2=1/4\). After service, station 1 sends a customer to station 2 with probability \(1/3\) and out with probability \(2/3\). Station 2 sends a customer to station 1 with probability \(1/4\) and out with probability \(3/4\). Both routing rows sum to one: \(1/3+2/3=1\) and \(1/4+3/4=1\). Let \(\mu_1=2\) and \(\mu_2=1\). Compute \(\pi(0,2)\) and the probability that both queues are empty.

The traffic equations are \(\lambda_1=1/2+\lambda_2/4\) and \(\lambda_2=1/4+\lambda_1/3\). Substitute the second equation into the first: \(\lambda_1=1/2+1/16+\lambda_1/12\). Hence \((11/12)\lambda_1=9/16\), so \(\lambda_1=(9/16)(12/11)=27/44\). Then \(\lambda_2=1/4+(27/44)/3=11/44+9/44=20/44=5/11\). The loads are \(\rho_1=(27/44)/2=27/88\) and \(\rho_2=5/11\); both are less than one.

For the state \((0,2)\), substitute these values into the product form:

$$ \pi(0,2)=\left(\frac{61}{88}\right) \left(\frac{6}{11}\right)\left(\frac{5}{11}\right)^2 =\frac{61\cdot6\cdot25}{88\cdot11\cdot121} =\frac{9150}{117128} =\frac{4575}{58564}. $$

The last reduction divides numerator and denominator by two: \(9150/2=4575\) and \(117128/2=58564\). For the empty state, \(\pi(0,0)=(61/88)(6/11)=366/968=183/484\), again reducing numerator and denominator by two. The marginal check for station 1 is \(\mathbb{P}(X^{(1)}\ge1)=27/88\), so \(\mathbb{P}(X^{(1)}=0)=1-27/88=61/88\), the factor used in both joint calculations.

Worked Example: Probability of Exactly Two Customers

Consider three stations arranged in a cycle. External arrivals enter station 1 at rate \(1/2\), with no external arrivals to stations 2 and 3. Each station sends a customer to the next station in the cycle with probability \(1/2\), and sends the customer out with probability \(1/2\). Thus each routing row sums to \(1/2+1/2=1\). Let all three service rates equal one. Find the probability that the network contains exactly two customers at a stationary time.

The traffic equations are \(\lambda_1=1/2+\lambda_3/2\), \(\lambda_2=\lambda_1/2\), and \(\lambda_3=\lambda_2/2\). The last two give \(\lambda_3=\lambda_1/4\), so \(\lambda_1=1/2+\lambda_1/8\), and therefore \((7/8)\lambda_1=1/2\). It follows that \(\lambda_1=4/7\), \(\lambda_2=2/7\), and \(\lambda_3=1/7\). With service rates one, the loads are \(4/7,2/7,1/7\), all less than one.

The probability of the empty state is \((3/7)(5/7)(6/7)=90/343\). Exactly two customers can be distributed among three queues in six ways: \((2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)\). Relative to the empty-state probability, their product-form weights are respectively \(16/49,4/49,1/49,8/49,4/49,2/49\). Adding these gives \((16+4+1+8+4+2)/49=35/49=5/7\). Thus

$$ \mathbb{P}\!\left(X^{(1)}+X^{(2)}+X^{(3)}=2\right) =\frac{90}{343}\cdot\frac57 =\frac{450}{2401}. $$

As a check, the six probabilities are \(90/343\) times the six listed weights, and their sum is \(90/343\cdot35/49=450/2401\), the same value. The calculation also illustrates why a total-occupancy probability is not generally just one joint-state probability: all six states must be included.

Common Mistake: Using External Rates as Queue Loads

A frequent error is to use \(\alpha_i/\mu_i\) in the stationary probabilities. Those are the external arrival rates, whereas \(\lambda_i\) includes customers routed in from other stations. In the feedback example, using external rates alone would give the incorrect loads \((1/2)/2=1/4\) and \((1/4)/1=1/4\), and hence would incorrectly calculate \(\pi(0,2)\) as \((3/4)(3/4)(1/4)^2=9/256\). The traffic equations instead give loads \(27/88\) and \(5/11\), and the correct probability is \(4575/58564\). Routing must be accounted for before normalizing or evaluating any state probability.

The stability condition is also essential to this calculation: if any \(\rho_i\ge1\), the geometric series for that station does not have a finite sum, so these normalized stationary probabilities do not result. Under the stated Jackson assumptions and strict inequalities \(0<\rho_i<1\), the product form provides a stationary distribution; it does not say that every initial distribution is already stationary. The probabilities calculated here describe the queue-length vector when its distribution is stationary.

Check Your Understanding

For each question, write the traffic equations before substituting loads into the product form.

  1. A station receives external arrivals at rate \(\alpha\), sends a fraction \(r\) of its completed customers to a second station, and otherwise exits. What equation gives the second station's total traffic rate?
  2. For two stations with loads \(\rho_1=1/3\) and \(\rho_2=1/4\), write the normalized probability of state \((1,2)\).
  3. Why does summing the joint product-form probability over the second queue leave the first queue's geometric marginal unchanged?
  4. With three independent stationary queue-length marginals, how many states must be included when computing the probability that the total queue length is exactly two?
  5. What goes wrong with geometric normalization if one station has \(\rho_i=1\)?

Previous

Next

Back to Tutorials