Throughput and Utilization in Jackson Networks

From Routing to Node Throughput

In a network, the external arrival rate at a service node is not generally the rate at which that node must work. Jobs may arrive from other nodes, and a job may visit more than one node before leaving the system. The traffic equations account for these internal arrivals. Once they are solved, each node’s effective arrival rate gives its throughput; comparing that rate with service capacity gives a direct capacity diagnostic.

Consider an open Jackson network with \(d\) single-server nodes, each having exponential service times. External arrivals to node \(i\) form a Poisson process of rate \(\gamma_i\). After service at node \(i\), a job goes to node \(j\) with probability \(r_{ij}\), or leaves the network with probability \(1-\sum_{j=1}^d r_{ij}\). Let \(R=(r_{ij})\) be the routing matrix. Its entries are nonnegative and each row sum is at most \(1\); the missing probability in a row is the probability of exiting from that node. Assume every node can reach an exit along routes of positive probability. Write \(\mu_i>0\) for node \(i\)’s service rate.

In this open network, the routing assumptions ensure that the traffic equations have a finite solution. The solution describes expected flow rates; using it as a stationary throughput requires the network to be stable. The distinction matters: traffic equations can have finite solutions even when one or more service nodes are overloaded.

Why the Traffic Equations Have a Unique Solution

Proof. Let \(\mathbf{1}\) denote the column vector of ones. Since each node can reach an exit, for each starting node \(i\) there is a finite route length \(n_i\) with positive probability of exiting within \(n_i\) routing steps. Choose \(N=\max_i n_i\). The probability of exiting within \(N\) steps is at least as large as the probability of exiting within \(n_i\) steps, so it is positive from every node. Because there are finitely many nodes, the minimum of these positive probabilities is some \(\delta>0\). The \(i\)th row sum of \(R^N\) is the probability of remaining in the network for the next \(N\) routing steps from node \(i\), and is therefore at most \(1-\delta\). Thus every row sum of \(R^N\) is at most \(1-\delta\). Multiplication by a substochastic matrix cannot increase the largest row-sum bound, so the row sums of \(R^{kN}\) are at most \((1-\delta)^k\). The intermediate powers also have row sums at most the corresponding preceding bound. Consequently \(\sum_{n=0}^{\infty}R^n\) converges entrywise. For each finite \(m\), \((I-R)\sum_{n=0}^{m}R^n=I-R^{m+1}\); the row sums of \(R^{m+1}\) tend to zero, so the limit gives \((I-R)\sum_{n=0}^{\infty}R^n=I\). The same finite-sum identity on the other side gives a two-sided inverse. The traffic equation \(\lambda=\gamma+\lambda R\) is equivalent to \(\lambda(I-R)=\gamma\), so its unique solution is \(\gamma(I-R)^{-1}\). Expanding the inverse gives the stated series, which is nonnegative. \(\square\)

The series \(\gamma+\gamma R+\gamma R^2+\cdots\) has a flow interpretation: \(\gamma\) is the external traffic, \(\gamma R\) is the traffic after one routing step, and \(\gamma R^n\) is the rate of traffic after \(n\) routing steps. Summing counts all node visits, including repeat visits if routes return to a node.

Stability and Capacity

Here the criterion is used as a standard result rather than reproved. Its capacity interpretation follows directly from the displayed marginal distribution. If \(\rho_i<1\), the probabilities sum to one because \(\sum_{n=0}^\infty(1-\rho_i)\rho_i^n=1\). The server is busy exactly when \(N_i>0\), whose probability is \(1-(1-\rho_i)=\rho_i\). Its stationary departure rate is therefore \(\mu_i\mathbb{P}(N_i>0)=\mu_i\rho_i=\lambda_i\). Thus, in a stable network, effective arrival rate equals departure throughput at each node. When any \(\rho_i\geq1\), there is no stationary probability distribution for the whole network; the traffic rate still flags that node as having insufficient capacity.

Common Pitfall: Using External Rates as Node Rates

A frequent error is to compute utilization using only \(\gamma_i\), ignoring traffic routed from other nodes. In the cross-routing example, this incorrect calculation gives node 1 utilization \(2/3\) and node 2 utilization \((1/2)/2=1/4\). The correct rates include routed arrivals: \(\lambda_1=2+\tfrac14\lambda_2=\tfrac{17}{7}\) and \(\lambda_2=\tfrac12+\tfrac12\lambda_1=\tfrac{12}{7}\). The correct utilizations are therefore \(\tfrac{17}{21}\) and \(\tfrac67\), not \(2/3\) and \(1/4\). Ignoring routing can conceal a nearly saturated node or, as in the overloaded example, a node whose arrival rate exceeds its service capacity.

For a capacity assessment, solve the traffic equations first, then compare each \(\lambda_i\) with its own \(\mu_i\). The largest utilization identifies the tightest relative capacity margin, while any utilization at least one violates the Jackson stability criterion. These are node-level diagnostics: the total rate of jobs leaving the network and the sum of all node throughputs are different quantities whenever a job can visit multiple nodes.