How Traffic Moves Through an Open Network
A customer entering a network may visit several service stations before leaving. The external arrival rate at a station is therefore not, in general, the total rate that station must serve: customers routed from other stations contribute additional traffic, and feedback can send customers around more than once. Traffic equations account for these repeated visits using only the external rates and the routing probabilities.
Consider a probability space \((\Omega,\mathcal{F},\mathbb{P})\) and a network with \(d\) single-server stations, indexed by \(S=\{1,\ldots,d\}\), evolving in continuous time \(t\ge 0\). Let \(N_i(t)\) be the number of customers at station \(i\), including any customer in service. The network state is \((N_1(t),\ldots,N_d(t))\) in \(\mathbb{N}_0^d\). Station \(i\) has exponential service times with 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 randomness.
Write \(R=(r_{ij})\) for the \(d\times d\) matrix of probabilities of routing between stations. Its rows need not sum to one: the remaining probability in row \(i\) is \(r_{i0}\), the probability of exiting after service at \(i\). Thus \(R\) is substochastic. The external rates form the row vector \(\gamma=(\gamma_1,\ldots,\gamma_d)\). We seek the effective arrival-rate row vector \(\lambda=(\lambda_1,\ldots,\lambda_d)\), which includes both external arrivals and routed arrivals.
The indices in the traffic equation matter. The rate leaving station \(j\) for station \(i\) is \(\lambda_jr_{ji}\), so it is the \(ji\) entry of \(R\), not the \(ij\) entry. The balance equation adds this incoming flow to station \(i\)'s external rate. The equations describe the nominal flow through the network; whether the service capacity can handle that flow is a separate check.
Why the Traffic Equations Hold and Have a Unique Solution
First consider flow balance in a stationary operating regime in which each station has finite expected queue length. Let \(A_i(t)\) and \(D_i(t)\) count, respectively, arrivals to and service completions from station \(i\) during an interval of length \(t\). The queue-count identity is \(N_i(t)=N_i(0)+A_i(t)-D_i(t)\). Stationarity and finite means imply \(\mathbb{E}N_i(t)=\mathbb{E}N_i(0)\), so \(\mathbb{E}A_i(t)=\mathbb{E}D_i(t)\). If the common rate is \(\lambda_i\), external arrivals contribute \(\gamma_i\), and completions at station \(j\) are routed to \(i\) with probability \(r_{ji}\). This gives the traffic equations.
The next result solves those equations under the eventual-exit condition. It is an algebraic statement about the nominal rates; it does not assert that service capacities are sufficient.
Proof. The entries of \(R^n\) are nonnegative, and the sum of row \(i\) of \(R^n\) is the probability of remaining in the network after \(n\) routing decisions when starting at \(i\). In particular, all row sums of \(R^n\) are at most \(1\), and by assumption all row sums of \(R^L\) are at most \(1-\varepsilon\). For nonnegative matrices, if every row sum of \(A\) is at most \(a\) and every row sum of \(B\) is at most \(b\), then every row sum of \(AB\) is at most \(ab\), because \(\sum_j(AB)_{ij}=\sum_k A_{ik}\sum_jB_{kj}\le b\sum_kA_{ik}\le ab\). Consequently, every row sum of \(R^{kL}\) is at most \((1-\varepsilon)^k\). For \(n=kL+s\), where \(0\le s<L\), the row sums of \(R^n=R^{kL}R^s\) are also at most \((1-\varepsilon)^k\), since \(R^s\) has row sums at most \(1\). Thus the matrix series \(H=\sum_{n=0}^{\infty}R^n\) converges entrywise and has finite entries. Its partial sums satisfy \((I-R)\sum_{n=0}^{m}R^n=I-R^{m+1}\) and \((\sum_{n=0}^{m}R^n)(I-R)=I-R^{m+1}\). The row-sum bound implies \(R^{m+1}\) tends entrywise to zero, so \((I-R)H=H(I-R)=I\). Therefore \(H=(I-R)^{-1}\), and \(\lambda=\gamma H\) solves \(\lambda(I-R)=\gamma\), equivalently \(\lambda=\gamma+\lambda R\). It is finite and nonnegative because \(\gamma\) and every \(R^n\) are nonnegative. If \(\widetilde{\lambda}\) is another solution, then \((\widetilde{\lambda}-\lambda)(I-R)=0\); multiplying by \(H\) gives \(\widetilde{\lambda}-\lambda=0\). This proves existence and uniqueness. \(\square\)
The series has a useful interpretation: \(\gamma\) counts the external flow, \(\gamma R\) counts the flow after one routing step, \(\gamma R^2\) counts the flow after two steps, and so on. The eventual-exit condition ensures that the total contribution from repeated routing is finite.
Worked Traffic-Equation Calculations
Worked Example: A Two-Station Tandem Network
External arrivals enter station \(1\) at rate \(\gamma_1=\tfrac32\), and none enter station \(2\), so \(\gamma=(\tfrac32,0)\). After service at station \(1\), a customer goes to station \(2\) with probability \(\tfrac13\) and exits with probability \(\tfrac23\). After service at station \(2\), every customer exits. Take service rates \(\mu_1=2\) and \(\mu_2=1\).
In station order \(1,2\), the internal routing matrix is \(R=\begin{bmatrix}0&\tfrac13\\0&0\end{bmatrix}\). Its first row sums to \(0+\tfrac13=\tfrac13\), and its second row sums to \(0+0=0\); the exit probabilities are therefore \(\tfrac23\) and \(1\), respectively. The traffic equations are
Substitution gives \(\lambda_1=\tfrac32\) and \(\lambda_2=\tfrac13\cdot\tfrac32=\tfrac12\). Checking both equations, \(\tfrac32+\lambda_2r_{21}=\tfrac32+\tfrac12\cdot0=\tfrac32\), and \(\gamma_2+\lambda_1r_{12}+\lambda_2r_{22}=0+\tfrac32\cdot\tfrac13+\tfrac12\cdot0=\tfrac12\). The nominal loads are \(\lambda_1/\mu_1=(\tfrac32)/2=\tfrac34\) and \(\lambda_2/\mu_2=(\tfrac12)/1=\tfrac12\), both below \(1\).
Worked Example: Feedback Through Three Stations
Consider three stations with external rates \(\gamma=(1,0,\tfrac12)\). After service at station \(1\), a customer goes to station \(2\) with probability \(\tfrac12\) and exits with probability \(\tfrac12\). After station \(2\), the customer goes to station \(1\) with probability \(\tfrac14\), to station \(3\) with probability \(\tfrac14\), and exits with probability \(\tfrac12\). After station \(3\), the customer goes to station \(2\) with probability \(\tfrac13\) and exits with probability \(\tfrac23\). Let \((\mu_1,\mu_2,\mu_3)=(2,1,1)\).
The routing matrix is \(R=\begin{bmatrix}0&\tfrac12&0\\\tfrac14&0&\tfrac14\\0&\tfrac13&0\end{bmatrix}\). Its row sums are \(0+\tfrac12+0=\tfrac12\), \(\tfrac14+0+\tfrac14=\tfrac12\), and \(0+\tfrac13+0=\tfrac13\), so the exit probabilities are \(\tfrac12,\tfrac12,\tfrac23\). The traffic equations, with each incoming route written explicitly, are
Set \(x=\lambda_2\). The first and third equations give \(\lambda_1=1+\tfrac14x\) and \(\lambda_3=\tfrac12+\tfrac14x\). Substitute both into the second equation:
Thus \(\tfrac{19}{24}x=\tfrac23\), so \(x=\tfrac23\cdot\tfrac{24}{19}=\tfrac{16}{19}\). Then \(\lambda_1=1+\tfrac14\cdot\tfrac{16}{19}=\tfrac{23}{19}\), and \(\lambda_3=\tfrac12+\tfrac14\cdot\tfrac{16}{19}=\tfrac{27}{38}\). Substitution checks the equations: \(1+\tfrac14\cdot\tfrac{16}{19}=\tfrac{23}{19}\); \(\tfrac12\cdot\tfrac{23}{19}+\tfrac13\cdot\tfrac{27}{38}=\tfrac{23}{38}+\tfrac9{38}=\tfrac{16}{19}\); and \(\tfrac12+\tfrac14\cdot\tfrac{16}{19}=\tfrac{27}{38}\). The loads are \(\tfrac{23}{38}/2=\tfrac{23}{76}\), \(\tfrac{16}{19}/1=\tfrac{16}{19}\), and \(\tfrac{27}{38}/1=\tfrac{27}{38}\), each below \(1\).
Worked Example: Finite Traffic Does Not Guarantee Adequate Capacity
A single station receives external traffic at rate \(\gamma_1=1\). After each service, a customer returns to the station with probability \(\tfrac34\) and exits with probability \(\tfrac14\). Its service rate is \(\mu_1=3\).
The routing matrix is \(R=[\tfrac34]\), whose only row sums to \(\tfrac34\); the exit probability is \(\tfrac14\). The traffic equation is \(\lambda_1=1+\tfrac34\lambda_1\), so \(\tfrac14\lambda_1=1\) and \(\lambda_1=4\). Substitution gives \(1+\tfrac34\cdot4=4\), as required. But the load is \(\lambda_1/\mu_1=4/3>1\): the station's nominal incoming traffic exceeds its service capacity. The traffic equations still have a finite solution, but that calculation does not establish a stationary operating regime.
Capacity Checks and a Common Orientation Error
For station \(i\), the nominal load is \(\rho_i=\lambda_i/\mu_i\). A value below \(1\) means the calculated rate is below that station's service rate; a value at least \(1\) warns that the station cannot keep up with that nominal flow. In an open Jackson network, the usual stability condition is that every station has \(\rho_i<1\). The traffic equations calculate \(\lambda_i\); they do not replace the separate capacity check or the later stationary-distribution analysis.
Common mistake: multiplying in the wrong orientation. With the three-station example, mistakenly using the column-vector equation \(x=\gamma+Rx\) changes the routing contributions. If \(x=(x_1,x_2,x_3)^\mathsf{T}\), this incorrect equation gives \(x_1=1+\tfrac12x_2\), \(x_2=\tfrac14x_1+\tfrac13x_3\), and \(x_3=\tfrac12+\tfrac14x_2\). Substituting the first and third equations into the second gives \(x_2=\tfrac14(1+\tfrac12x_2)+\tfrac13(\tfrac12+\tfrac14x_2)=\tfrac5{12}+\tfrac5{24}x_2\), hence \(x_2=\tfrac{10}{19}\). That differs from the correct \(\lambda_2=\tfrac{16}{19}\). The correction is to keep rates as a row vector: \(\lambda=\gamma+\lambda R\), so incoming flow to \(i\) uses \(r_{ji}\).
When setting up a network calculation, first list every possible destination after service, including exit, and check that each routing row sums to \(1\) once exit is included. Then form the internal matrix \(R\), write one balance equation per station, solve the resulting system, and substitute the rates back into every equation. Only after that should you compare the rates with the service capacities.
Check Your Understanding
Use row-vector traffic rates and include exit probabilities when checking routing rows.
- A station receives external traffic at rate \(2\), and routes each completion back to itself with probability \(\tfrac12\). Find its traffic rate and verify the balance equation.
- In a two-station network, station \(1\) routes to station \(2\) with probability \(\tfrac14\), while station \(2\) routes to station \(1\) with probability \(\tfrac12\). Write both traffic equations for external rates \((1,0)\).
- Explain why the exit probability belongs in the row-sum check but not as an additional station in the traffic vector.
- For the feedback example with three stations, compute each exit probability and verify that each internal routing row sum is at most \(1\).
- Give a reason a finite solution to the traffic equations alone does not guarantee that a network can sustain a stationary operating regime.