Worked Jackson Network Analysis with Routing and Feedback

From Routing Probabilities to Network Performance

In an open queueing network, customers arrive from outside, receive service at one or more nodes, and eventually leave. Routing can send a customer back to a node already visited, so the external arrival rate to a node is generally not its total arrival rate. A complete analysis keeps these two rates distinct: first solve for the total traffic reaching each node, then check whether each server can handle that traffic, and only then compute stationary performance measures.

Consider a network with \(J\) single-server nodes. Let \(\lambda_i\) be the external Poisson arrival rate to node \(i\), and let \(r_{ij}\) be the probability that a customer completing service at node \(i\) next visits node \(j\). The remaining probability \(1-\sum_j r_{ij}\) is the probability of leaving the network. The total arrival rate \(\gamma_i\) must account for both external arrivals and routed arrivals.

Definition: The traffic equations are \(\gamma_j=\lambda_j+\sum_i\gamma_i r_{ij}\), for each node \(j\). Here \(\lambda_j\) is the external rate, while \(\gamma_j\) is the total rate of service completions and arrivals to node \(j\) in steady operation. For an M/M/1 node with service rate \(\mu_j\), its utilization is \(\rho_j=\gamma_j/\mu_j\). The Jackson product form applies when the routing network is open, the external streams are independent Poisson streams, service times are independent exponential variables, routing is independent with the stated probabilities, and \(\rho_j<1\) at every node.

For a finite set of nodes, the traffic equations can also be written \(\gamma=\lambda+\gamma R\), with row vectors \(\gamma,\lambda\) and routing matrix \(R=(r_{ij})\). When the network is open and the equations have a finite solution, this is the rate to use in the stability checks. The Jackson product-form theorem, established in the earlier material on open Jackson networks, then gives independent geometric stationary queue lengths at the nodes. The examples below show how to use those results without mistaking a formal traffic solution for a stable network.

A Three-Node Network with Feedback

Worked Example: Solve the Traffic Equations and Check Stability

External arrivals to nodes \(1,2,3\) have rates \(\lambda_1=\tfrac12\), \(\lambda_2=\tfrac14\), and \(\lambda_3=0\). After service, a customer routes from node 1 to nodes 2 and 3 with probabilities \(\tfrac12,\tfrac14\), respectively, and exits with probability \(\tfrac14\). From node 2, the probabilities to nodes 1 and 3 are \(\tfrac14,\tfrac12\), with exit probability \(\tfrac14\). From node 3, the probabilities to nodes 1 and 2 are \(\tfrac14,\tfrac14\), with exit probability \(\tfrac12\). The service rates are \(\mu_1=\tfrac32\), \(\mu_2=\tfrac43\), and \(\mu_3=1\).

Before using the routing data, check each row including its exit probability: node 1 gives \(\tfrac12+\tfrac14+\tfrac14=1\); node 2 gives \(\tfrac14+\tfrac12+\tfrac14=1\); node 3 gives \(\tfrac14+\tfrac14+\tfrac12=1\). The routing matrix among nodes is therefore

R= \begin{bmatrix} 0&\tfrac12&\tfrac14\\ \tfrac14&0&\tfrac12\\ \tfrac14&\tfrac14&0 \end{bmatrix}.

The traffic equations, one for each destination node, are

\gamma_1=\tfrac12+\tfrac14\gamma_2+\tfrac14\gamma_3,\qquad \gamma_2=\tfrac14+\tfrac12\gamma_1+\tfrac14\gamma_3,\qquad \gamma_3=\tfrac14\gamma_1+\tfrac12\gamma_2.

To solve, multiply each equation by \(4\): \(4\gamma_1-\gamma_2-\gamma_3=2\), \(-2\gamma_1+4\gamma_2-\gamma_3=1\), and \(-\gamma_1-2\gamma_2+4\gamma_3=0\). The third equation gives \(\gamma_3=(\gamma_1+2\gamma_2)/4\). Substituting this into the first gives \(15\gamma_1-6\gamma_2=8\), and substituting it into the second gives \(-9\gamma_1+14\gamma_2=4\). Multiply the first of these by \(14\) and the second by \(6\), then add: \(210\gamma_1-84\gamma_2-54\gamma_1+84\gamma_2=112+24\), so \(156\gamma_1=136\) and \(\gamma_1=\tfrac{34}{39}\). The equation \(15\gamma_1-6\gamma_2=8\) now gives \(6\gamma_2=\tfrac{510}{39}-8=\tfrac{66}{13}\), hence \(\gamma_2=\tfrac{11}{13}\). Finally, \(\gamma_3=(\tfrac{34}{39}+2\cdot\tfrac{11}{13})/4=\tfrac{25}{39}\).

Check the traffic solution by substitution. The right sides of the three original equations are, respectively, \(\tfrac12+\tfrac{11}{52}+\tfrac{25}{156}=\tfrac{34}{39}\), \(\tfrac14+\tfrac{17}{39}+\tfrac{25}{156}=\tfrac{11}{13}\), and \(\tfrac{17}{78}+\tfrac{11}{26}=\tfrac{25}{39}\). Each matches its proposed traffic rate.

Now compute utilization using \(\rho_i=\gamma_i/\mu_i\):

\rho_1=\frac{34/39}{3/2}=\frac{68}{117},\qquad \rho_2=\frac{11/13}{4/3}=\frac{33}{52},\qquad \rho_3=\frac{25/39}{1}=\frac{25}{39}.

Each fraction is positive and less than \(1\), so all three nodes are stable and the Jackson stationary product form applies. The traffic equations have no other solution: for the corresponding homogeneous equations, the same elimination gives \(15\gamma_1-6\gamma_2=0\) and \(-9\gamma_1+14\gamma_2=0\). Multiplying these by \(14\) and \(6\) and adding gives \(156\gamma_1=0\), so \(\gamma_1=0\), then \(\gamma_2=0\), and the third equation gives \(\gamma_3=0\). Thus the difference of any two solutions must be zero.

Stationary Queue Lengths and Mean Delay

Let \(N_i(t)\) be the number of customers at node \(i\), including any customer in service, at time \(t\). The continuous-time process \((N_1(t),N_2(t),N_3(t))_{t\ge0}\) takes values in \(S=\mathbb{Z}_{\ge0}^3\) on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). With the exponential service and independent routing assumptions above, the Jackson product form specifies its stationary distribution. At each node, the stationary queue length is geometric on \(\{0,1,2,\ldots\}\), and the three node counts are independent.

Result (product-form performance formulas): If every node is an M/M/1 queue with \(\rho_i=\gamma_i/\mu_i<1\), then \(\mathbb{P}(N_i=n)=(1-\rho_i)\rho_i^n\), and the joint stationary probability of \((n_1,\ldots,n_J)\) is \(\prod_i(1-\rho_i)\rho_i^{n_i}\). The mean number at node \(i\) is \(L_i=\rho_i/(1-\rho_i)\). If the total external arrival rate is \(\Lambda=\sum_i\lambda_i>0\), the mean time in the network per external customer is \(W_{\mathrm{net}}=(\sum_i L_i)/\Lambda\).

Proof. For \(0\le\rho_i<1\), the geometric series gives \(\sum_{n=0}^\infty(1-\rho_i)\rho_i^n=1\), so each node factor is a probability distribution. Independence makes the joint probabilities multiply, and summing over all \(J\) coordinates gives the product of the \(J\) unit sums, which is \(1\). For its mean, \(\sum_{n\ge0}n\rho_i^n=\rho_i/(1-\rho_i)^2\): multiplying the sum by \(1-\rho_i\) leaves \(\sum_{n\ge1}\rho_i^n=\rho_i/(1-\rho_i)\). Multiplication by \(1-\rho_i\) therefore gives \(L_i=\rho_i/(1-\rho_i)\). Finally, the network’s total mean population is \(\sum_i L_i\). Little’s law, applied to the stable network with external throughput \(\Lambda\), identifies this population as \(\Lambda W_{\mathrm{net}}\), giving the stated delay formula. \(\square\)

Worked Example: Product Form and End-to-End Delay

Continue the three-node calculation. The normalizing factors are \(1-\rho_1=\tfrac{49}{117}\), \(1-\rho_2=\tfrac{19}{52}\), and \(1-\rho_3=\tfrac{14}{39}\). Thus, for nonnegative integers \(n_1,n_2,n_3\),

\mathbb{P}(N_1=n_1,N_2=n_2,N_3=n_3) =\frac{49}{117}\left(\frac{68}{117}\right)^{n_1} \frac{19}{52}\left(\frac{33}{52}\right)^{n_2} \frac{14}{39}\left(\frac{25}{39}\right)^{n_3}.

The node mean populations are \(L_i=\rho_i/(1-\rho_i)\). Substitution gives \(L_1=(68/117)/(49/117)=\tfrac{68}{49}\), \(L_2=(33/52)/(19/52)=\tfrac{33}{19}\), and \(L_3=(25/39)/(14/39)=\tfrac{25}{14}\). The external rate is \(\Lambda=\tfrac12+\tfrac14+0=\tfrac34\). Therefore

W_{\mathrm{net}} =\frac{\tfrac{68}{49}+\tfrac{33}{19}+\tfrac{25}{14}}{\tfrac34} =\frac{64001}{13034}\cdot\frac43 =\frac{128002}{19551}.

Check using node sojourn times. At an M/M/1 node, the mean time per visit is \(1/(\mu_i-\gamma_i)\). Here the three values are \(1/(\tfrac32-\tfrac{34}{39})=\tfrac{78}{49}\), \(1/(\tfrac43-\tfrac{11}{13})=\tfrac{39}{19}\), and \(1/(1-\tfrac{25}{39})=\tfrac{39}{14}\). The mean delay can be recomputed as the total rate of time spent at nodes divided by the external rate: \[ \frac{\gamma_1(78/49)+\gamma_2(39/19)+\gamma_3(39/14)}{3/4} =\frac{\tfrac{68}{49}+\tfrac{33}{19}+\tfrac{25}{14}}{3/4} =\frac{128002}{19551}. \] This agrees with the population calculation. Feedback is included because a customer can contribute more than one visit to a node.

A Smaller Feedback Network

Worked Example: Two Nodes with a Return Route

Suppose the external rate to node 1 is \(\tfrac13\), and node 2 has no external arrivals. A customer at node 1 routes to node 2 with probability \(\tfrac12\), otherwise exiting. A customer at node 2 routes to node 1 with probability \(\tfrac13\), otherwise exiting. The service rates are \(\mu_1=1\) and \(\mu_2=\tfrac12\). The routing rows including exit probabilities sum to \(1\): \(\tfrac12+\tfrac12=1\) at node 1 and \(\tfrac13+\tfrac23=1\) at node 2.

The traffic equations are \(\gamma_1=\tfrac13+\tfrac13\gamma_2\) and \(\gamma_2=\tfrac12\gamma_1\). Substitution gives \(\gamma_1=\tfrac13+\tfrac16\gamma_1\), so \(\tfrac56\gamma_1=\tfrac13\), \(\gamma_1=\tfrac25\), and \(\gamma_2=\tfrac15\). Substitution checks the first equation: \(\tfrac13+\tfrac1{15}=\tfrac25\); the second gives \(\tfrac12\cdot\tfrac25=\tfrac15\). Utilizations are \(\rho_1=(\tfrac25)/1=\tfrac25\) and \(\rho_2=(\tfrac15)/(\tfrac12)=\tfrac25\), both below \(1\).

The stationary node factors are \(\mathbb{P}(N_i=n)=\tfrac35(\tfrac25)^n\), and each mean population is \((\tfrac25)/(\tfrac35)=\tfrac23\). Hence total mean population is \(\tfrac43\), while the external rate is \(\tfrac13\), giving mean network delay \(W_{\mathrm{net}}=(\tfrac43)/(\tfrac13)=4\). Independently, the mean times per visit are \(1/(1-\tfrac25)=\tfrac53\) and \(1/(\tfrac12-\tfrac15)=\tfrac{10}{3}\). The corresponding rate-weighted total is \((\tfrac25)(\tfrac53)+(\tfrac15)(\tfrac{10}{3})=\tfrac23+\tfrac23=\tfrac43\); dividing by \(\tfrac13\) again gives \(4\).

When Stability Fails—and a Common Mistake

Worked Example: A Service Rate That Is Too Small

Keep the three-node routing and external arrival rates from the first example, but change node 3’s service rate to \(\mu_3=\tfrac35\). The routing rows still sum to \(1\), and the traffic equations are unchanged, so \(\gamma_3=\tfrac{25}{39}\). Its utilization is \(\rho_3=(\tfrac{25}{39})/(\tfrac35)=\tfrac{125}{117}\), which exceeds \(1\) because \(125>117\). Thus the product-form geometric factor at node 3 cannot be normalized: its proposed sum contains \(\sum_{n\ge0}(\tfrac{125}{117})^n\), whose terms do not tend to zero. The stationary product form and the finite-mean delay calculation do not apply to this network.

Common mistake: omitting feedback in the traffic rates. Setting \(\gamma_1=\lambda_1=\tfrac12\) ignores arrivals routed back from nodes 2 and 3. In the stable three-node example, those incoming rates are \(\tfrac14\gamma_2=\tfrac{11}{52}\) and \(\tfrac14\gamma_3=\tfrac{25}{156}\). Their sum is \(\tfrac{33}{156}+\tfrac{25}{156}=\tfrac{29}{78}\), so the correct rate is \(\gamma_1=\tfrac12+\tfrac{29}{78}=\tfrac{34}{39}\), not \(\tfrac12\). Using the external rate alone would also give the wrong utilization and queue-length distribution.

A reliable calculation therefore has an order: check that each routing row, including exit, sums to one; solve and substitute into every traffic equation; compare each total traffic rate with its service rate; and only for a stable network compute product-form probabilities and delay. The total external rate belongs in the final network Little’s law calculation, while the node traffic rates belong in the node utilizations and visit-level calculations.

Check Your Understanding

Use exact fractions and verify numerical answers by substitution.

In the two-node example, what would the traffic rate at node 1 be if the return route from node 2 were incorrectly omitted? Compare it with the correct rate.
For the three-node network, compute the probability that all three nodes are empty under the stationary product form.
Explain why the external rate \(\Lambda\), rather than \(\gamma_1+\gamma_2+\gamma_3\), is used to convert total mean population into mean end-to-end delay.
If node 2’s service rate in the two-node example were changed to \(\tfrac16\), compute its utilization and decide whether the stationary product form applies.
For the first three-node example, verify the value of \(L_2\) by substituting \(\rho_2=\tfrac{33}{52}\) into \(L_2=\rho_2/(1-\rho_2)\).