Queueing networks and bottlenecks

A request may visit caches, application workers and a database, loop back, or fan out to several subrequests. Queueing networks translate external requests into the work each resource must perform.

Solve traffic before waiting

Let ${\gamma }_j$ be external arrival rate to node $j$, and $p_{ij}$ the probability of routing a completion at $i$ to $j$. Stationary flow conservation gives:

$${\lambda }_j={\gamma }_j+\sum _i{\lambda }_i{p}_{ij}.$$

These equations are routing accounting; they do not make each node M/M/1. An open Jackson network additionally assumes independent external Poisson arrivals, exponential service, suitable independent memoryless routing, unlimited waiting space and stable node loads. Internal processes must not be casually treated as independent request samples.

The key result is Jackson's stationary product form. For this chapter's single-server nodes:

$$P(N_1=n_1,\dots ,N_k=n_k)=\prod _{j=1}^k(1-{\rho }_j){\rho }_j^{n_j},{\rho }_j={\lambda }_j/{\mu }_j<1.$$

It makes node occupancies independent at a common stationary time, not successive delays along a path. With feedback, internal node arrivals need not even be Poisson. These marginals still give mean occupancy and hence network mean residence. See the MIT Jackson-network lecture for the distinction and assumptions.

The experiment visits nodes 1 and 2, then returns to node 1 with probability $p$ or exits. Each business request visits each node $V=1/(1-p)$ times on average. Both internal rates are ${\lambda }_{0}V$. Server rates are 100/s and 250/s; stability requires ${\lambda }_{0}V<100$.

$$E[T_{\mathrm{network}}]=V\left(\frac{1}{100-{\lambda }_{0}V}+\frac{1}{250-{\lambda }_{0}V}\right).$$

This follows by summing mean node occupancies and using network Little's law; it does not require independent delays along a request's path. At ${\lambda }_0=40$/s and $p=0.2$, $V=1.25$, each internal rate is 50/s and mean end-to-end time is 31.25 ms.

Increase return probability while keeping external traffic fixed. Internal demand increases. At or beyond the bottleneck, the stationary-condition indicator becomes false and mean delay shows —. A finite plotting window cannot supply a nonexistent stationary solution.

Service demand and bottleneck bounds

Mean service demand at resource $j$ per completed business request is $D_j=V_{j}E[S_j]$. A single-capacity resource has utilization $U_j=X{D}_j$, hence the necessary throughput bound:

$$X\le \frac{1}{{\max }_j{D}_j}.$$

$D_j$ includes resource service occupancy, not waiting. Substituting response time mistakes congestion for intrinsic work. For $c_j$ interchangeable parallel resources, the corresponding bound becomes $c_j/D_j$, assuming work can be assigned and no shared bottleneck intervenes. A bottleneck bound is not an achievable-throughput guarantee under an arbitrary latency target.

A closed system with $N$ circulating users and mean think time $Z$ satisfies $N=X(E[T]+Z)$. Users who submit again only after completion reduce new traffic as responses slow. An open system with externally scheduled arrivals does not self-throttle this way.

Fan-out amplifies tails

If a request waits for all $m$ children, its duration includes $\max (T_1,\dots ,T_m)$. Only for IID child times with CDF $F$ is the maximum's CDF $F(t{)}^m$. If one child finishes before a threshold with probability 0.99, 100 independent children all finish before it with probability only $0.99^{100}\approx 0.366$.

Shared databases, networks and failures create dependence, invalidating unconditional multiplication. Serial-stage means add, but adding stage p99 values generally does not produce end-to-end p99. Use joint measurements, appropriate probability bounds or an explicit dependence model.

Check your understanding

1. A business request visits a database three times, occupying it for 5 ms each. What is the single-resource throughput bound?

2. Ten users with $Z=0$ see mean response grow from 0.1 s to 1 s. What happens in a closed load test?

Further reading

The CMU performance syllabus covers operational laws, open and closed systems, and networks. Kafka architecture provides a concrete setting for partitions and routing.