End-to-End Response Times in Jackson Networks

From Node Delays to a Network Response Time

An external job in an open Jackson network may visit several service nodes before it leaves. It may also return to a node it has visited before. The network’s mean end-to-end response time must therefore account for both the delay at each node and how often a typical external job visits that node. The key is to use expected visit counts as weights: nodes visited more often contribute more to the total mean response time.

Consider a network with \(J\) single-server nodes, state space \(S=\mathbb{N}_0^J\), and continuous time \(t\geq0\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). External jobs arrive to node \(i\) as independent Poisson processes of rates \(\alpha_i\). Service times at node \(i\) are exponential with rate \(\mu_i\), and service is first-come, first-served. After service at node \(i\), a job goes to node \(j\) with probability \(r_{ij}\), or leaves the network with probability \(r_{i0}=1-\sum_{j=1}^J r_{ij}\). Write \(R=(r_{ij})\) for the routing matrix among the nodes, and let \(\gamma=\sum_{i=1}^J\alpha_i\) be the total external arrival rate.

We assume \(\gamma>0\), that the routing process eventually exits (equivalently, the spectral radius of \(R\) is less than \(1\)), and that the network is stable: each node’s total arrival rate \(\lambda_i\) satisfies \(\lambda_i<\mu_i\). These conditions ensure finite expected visit counts and the stationary node distributions used below. The traffic equations are \(\lambda_j=\alpha_j+\sum_i\lambda_i r_{ij}\). They account for external arrivals and jobs routed from other nodes.

Expected Visits and Mean Node Delay

Choose an external job at random from the combined external stream. Its entry node has probabilities \(a_i=\alpha_i/\gamma\). If \(v_i\) is its expected number of visits to node \(i\), then each visit either is its initial entry or follows a visit to another node. In row-vector notation this gives \(v=a+vR\), so \(v=a(I-R)^{-1}\). The inverse exists under the assumption that the spectral radius of \(R\) is less than \(1\).

The total rate of arrivals to node \(i\) is \(\lambda_i\), while external jobs enter the network at rate \(\gamma\). Thus the visit rate to node \(i\) per external job is \(v_i=\lambda_i/\gamma\). This relationship lets us use the traffic equations to find the weights without tracing every possible route.

At node \(i\), the arrivals are Poisson and the node behaves in steady state as an M/M/1 queue with arrival rate \(\lambda_i\) and service rate \(\mu_i\). Its mean sojourn time, including service, is

For example, this follows from the Pollaczek–Khinchine mean-waiting-time formula for an M/G/1 queue. With exponential service, \(\mathbb{E}[S_i]=1/\mu_i\) and \(\mathbb{E}[S_i^2]=2/\mu_i^2\); under \(\lambda_i<\mu_i\), the mean queueing wait is \(\lambda_i/(\mu_i(\mu_i-\lambda_i))\). Adding the mean service time \(1/\mu_i\) gives the displayed sojourn-time formula. In using this node formula, the Poisson arrivals and exponential service assumptions matter: a general network of M/G/1 nodes need not have the Jackson-network properties used here.

Proof. The routing process of an external job has initial entry distribution \(a\) and transition probabilities \(R\) among the nodes. The expected number of visits to each node is therefore \(v=a+vR\): the first term counts initial entries, and the second counts visits reached after a previous service. Because the spectral radius of \(R\) is less than \(1\), the series \(I+R+R^2+\cdots\) converges to \((I-R)^{-1}\); hence \(v=a(I-R)^{-1}\) is finite. Multiplying the traffic equations by \(1/\gamma\) shows that \(\lambda/\gamma=a+(\lambda/\gamma)R\). The solution is unique because \(I-R\) is invertible, so \(v=\lambda/\gamma\).

To combine the node means, apply Little’s law to each stable node and to the network as a whole. Write \(L_i\) for the mean number of jobs at node \(i\), and \(L=\sum_i L_i\) for the mean number in the network. Little’s law gives \(L_i=\lambda_iW_i\) and \(L=\gamma\mathbb{E}[T]\). These uses require steady state and finite means, which hold under the stated stability assumptions for this finite-node Jackson network. Therefore $$ \gamma\mathbb{E}[T]=L=\sum_{i=1}^J L_i =\sum_{i=1}^J\lambda_i W_i. $$ Dividing by \(\gamma>0\), then substituting \(W_i=1/(\mu_i-\lambda_i)\) and \(v_i=\lambda_i/\gamma\), proves the formula. \(\square\)

Little’s law is used here in its standard queueing form: mean number in a stable system equals throughput times mean time in the system. The proof above shows how its nodewise and network-wide forms produce the visit-weighted response-time identity. No independence between the delays at successive visits is required; the calculation uses steady-state averages and flow rates.

Worked Network Calculations

What the Weights Do—and a Common Mistake

The term \(v_iW_i\) is the contribution of node \(i\) to an external job’s mean total time. The weight is an expected number of visits, not the probability that the job ever visits the node. These differ when a job can return. In the feedback example, the probability of ever visiting the node is \(1\), but the expected number of visits is \(2\).

Common mistake. Counting the feedback node only once gives the incorrect calculation \(1\cdot(1/2)=1/2\). The correction is to include all visits in expectation: the visit count is \(1+1/2+(1/2)^2+\cdots=2\), so the response time is \(2\cdot(1/2)=1\). Another error is to weight by the external entry rates \(\alpha_i\) alone. The traffic rates \(\lambda_i\), which include routed arrivals, determine the visit weights. Before using the formula, check that routing rows including exits sum to \(1\), solve the traffic equations, and verify \(\lambda_i<\mu_i\) for every node.

The method applies to the stated open Jackson setting: Poisson external arrivals, Markovian routing, exponential service, and stable nodes. A nodewise M/G/1 delay formula by itself does not establish that a network of general-service nodes has Jackson product form. Changing the service assumptions may change the arrival processes seen by nodes and invalidate this combination.