---
name: foundations-queueing-theory
description: Applies queueing theory (Little's Law, M/M/c, Erlang, Kingman, USL) to capacity and latency decisions. Use when load causes non-linear latency growth or queue overrun risk.
compatibility: Portable core only.
version: "1.2"
last_validated: 2026-08-14
---

# Queueing Theory Foundations

11 queueing-theory primitives for capacity planning, saturation prediction, and backpressure design. Each primitive addresses a specific failure mode that causes systems to degrade, saturate, or scale incorrectly. Primitives are domain-agnostic: the same M/M/c formula that sizes a call-center agent pool also sizes a database connection pool and a Kubernetes pod replica count.

## Contents

- [Quick Reference](#quick-reference)
- [Primitive Index](#primitive-index)
- [Formal Supporting Theory](#formal-supporting-theory)
- [Misuse Boundaries](#misuse-boundaries)
- [Expert Judgment](#expert-judgment)
- [Decision Checklist](#decision-checklist)
- [Anti-Patterns](#anti-patterns)
- [Composition Recipes](#composition-recipes)
- [Workflow](#workflow)
- [ASCII Flow](#ascii-flow)
- [Related Skills](#related-skills)
- [Navigation](#navigation)
- [Fact-Checking](#fact-checking)

---

## Quick Reference

| # | Primitive | Formula / Key Result | Use When |
|---|-----------|---------------------|----------|
| 1 | [Little's Law](assets/templates/queueing-theory/01-littles-law.md) | L = λW | Relating queue depth, rate, and latency at any stable system |
| 2 | [M/M/1](assets/templates/queueing-theory/02-mm1.md) | W = 1/(μ−λ) | Single-server baseline; understanding saturation curve |
| 3 | [M/M/c (Erlang-C)](assets/templates/queueing-theory/03-mmc.md) | C(c,a) Erlang-C formula | Multi-server pool sizing; wait-time SLO compliance |
| 4 | [M/G/1 / Pollaczek-Khinchine](assets/templates/queueing-theory/04-mg1-pollaczek-khinchine.md) | Wq = ρ·E[S]·(1+CV²)/2(1−ρ) | Service-time variability inflating queue latency |
| 5 | [Priority Queues](assets/templates/queueing-theory/05-priority-queues.md) | Wq_1 < Wq_2 via P-K residual | Protecting high-priority workloads from low-priority batch |
| 6 | [Jackson Networks](assets/templates/queueing-theory/06-jackson-networks.md) | Product-form: π = Πᵢ πᵢ | Multi-stage pipeline bottleneck identification |
| 7 | [Kingman's Formula](assets/templates/queueing-theory/07-kingman-formula.md) | Wq ≈ (ρ/(1−ρ))·(CV²_a+CV²_s)/2·E[S] | G/G/1 under real bursty+variable traffic |
| 8 | [Bufferbloat](assets/templates/queueing-theory/08-bufferbloat.md) | Buffer > BDP → standing queue | Diagnosing high latency despite good throughput |
| 9 | [USL](assets/templates/queueing-theory/09-usl-universal-scalability.md) | X(N) = λN/(1+σ(N−1)+κN(N−1)) | Predicting retrograde throughput when scaling out |
| 10 | [Erlang-B (Loss)](assets/templates/queueing-theory/10-loss-systems-erlang-b.md) | B(c,a) blocking formula | Sizing channels/connections for drop-on-busy systems |
| 11 | [Fork-Join](assets/templates/queueing-theory/11-fork-join-parallel.md) | E[max] = E[S]·H_K | Fan-out latency dominated by slowest worker |

---

## When to Apply

**Apply queueing-theory when:**
- Latency at p95/p99 grows non-linearly with load (sign of utilisation > 0.7)
- Queue or buffer can fill faster than it drains (request queue, message broker, thread pool)
- Capacity planning: "how many servers/replicas/workers do we need?"
- Rate-limiter or admission-control design (token bucket, leaky bucket, backpressure)
- Multi-stage pipeline where one stage's variance hurts downstream throughput

**Skip and use simpler alternatives when:**
- System is stateless and load is constant — basic capacity math (peak QPS × CPU/req) suffices
- Question is about *correctness* under partition/failure — use foundations-distributed-systems
- Question is about reliability/availability budgets — use foundations-reliability-theory
- Question is about feedback control of a moving target — use foundations-control-theory
- Single-user dev tool with no concurrency — queueing math adds overhead with no payoff
- ρ < 0.3 sustained — system is over-provisioned, not queue-limited

---

## Primitive Index

| # | Mechanism | Failure Mode It Addresses |
|---|-----------|--------------------------|
| 1 | [Little's Law](assets/templates/queueing-theory/01-littles-law.md) | Misaligned depth/rate/latency metrics; hidden measurement gaps |
| 2 | [M/M/1](assets/templates/queueing-theory/02-mm1.md) | Underestimated latency at moderate utilization; hyperbolic saturation |
| 3 | [M/M/c (Erlang-C)](assets/templates/queueing-theory/03-mmc.md) | Under/over-provisioned parallel server pools; incorrect wait SLO |
| 4 | [M/G/1 / P-K](assets/templates/queueing-theory/04-mg1-pollaczek-khinchine.md) | Variance-driven latency inflation invisible to M/M/1 |
| 5 | [Priority Queues](assets/templates/queueing-theory/05-priority-queues.md) | High-priority workload blocked by low-priority batch; head-of-line blocking |
| 6 | [Jackson Networks](assets/templates/queueing-theory/06-jackson-networks.md) | Pipeline bottleneck misidentified; scaling wrong stage |
| 7 | [Kingman's Formula](assets/templates/queueing-theory/07-kingman-formula.md) | M/M/1 underestimates real latency due to bursty arrivals and variable service |
| 8 | [Bufferbloat](assets/templates/queueing-theory/08-bufferbloat.md) | Oversized buffers accumulate standing queues; good throughput masks latency crisis |
| 9 | [USL](assets/templates/queueing-theory/09-usl-universal-scalability.md) | Retrograde scaling: adding servers reduces throughput past N_max |
| 10 | [Erlang-B](assets/templates/queueing-theory/10-loss-systems-erlang-b.md) | Blocking rate exceeds GoS target; call/connection loss uncontrolled |
| 11 | [Fork-Join](assets/templates/queueing-theory/11-fork-join-parallel.md) | Fan-out sized by mean worker time; completion dominated by slowest worker |

---

## Formal Supporting Theory

| Theory Area | Use When | Applied Primitives It Grounds |
|---|---|---|
| Conservation laws | Need universal consistency across rate, latency, and queue depth | #1 |
| Markovian queues | Need exact M/M/1, M/M/c, Erlang-B/C baselines | #2, #3, #10 |
| General service-time queues | Need variability effects beyond exponential assumptions | #4, #7 |
| Scheduling theory | Need priority lanes, preemption, or class-specific SLOs | #5. SOAP framework (Scully, Harchol-Balter & Scheller-Wolf 2018) unifies all M/G/1 age-based policies (SRPT, FCFS, FB, Gittins) under one response-time formula; use to compare policies for a given job-size distribution. SIGMETRICS 2025: Gittins policy with negative discount rate achieves strong tail optimality in light-tailed M/G/1 without known job sizes (Harlev, Yu, Scully 2025). Robust Gittins bounds degradation under distributional misspecification (Moseley et al. 2025). For multiserver, see the M/G/k caveats under [Fact-Checking](#fact-checking) — SRPT-k is no longer optimal for the mean, and tail-optimal policies are load-regime-dependent. |
| Memory-coupled service | Need stability where admitted work holds a growing, non-releasable resource until completion (KV cache, session state, long-lived connections with buffers) | #1, #8 — joint compute-and-memory stability conditions (Nie, Si & Zhou, ICML 2026); eviction limit cycles and the stabilizing role of service-time heterogeneity (Ao, Dong, Luo & Simchi-Levi 2026). Classical single-resource ρ is not sufficient for stability here. |
| Learning-augmented scheduling | Need to use ML-predicted job sizes to reduce mean response time while bounding degradation under prediction error | #4, #5 — SPRPT, Trail policy, consistency-robustness framework (Mitzenmacher & Shahout 2025); embedding-based output-length prediction for LLM scheduling (Shahout et al., arXiv 2410.01035). |
| Queueing networks | Need multi-stage pipeline flow balance | #6 |
| Active queue management | Need bounded latency under buffers and backpressure | #8 |
| Scalability laws | Need contention/coherency limits under scale-out | #9 |
| Parallel response time | Need fan-out, fork-join, or tail-latency analysis | #11 |

Use [`references/formal-theory-map.md`](references/formal-theory-map.md) when the task needs stationarity, arrival-process, or distribution assumptions.

---

## Misuse Boundaries

| Misuse | Why It Is Wrong | Required Correction |
|---|---|---|
| Applying Little's Law to a burst window | The law requires stable long-run averages | Use steady windows or separate transient analysis |
| Using M/M/1 for real bursty traffic | Poisson/exponential assumptions understate latency under high CV | Use Kingman or simulation |
| Confusing Erlang-B and Erlang-C | Blocking and waiting are different systems | Choose loss model vs queueing model explicitly |
| Treating higher utilization as efficiency | Waiting time explodes near saturation | Set target rho below the SLO breach point |
| Adding buffers to fix overload | Buffers hide overload as latency | Bound queues and apply backpressure |
| Scaling out without USL fit | Coherency and contention can make throughput retrograde | Fit USL from load-test data |
| Applying Jackson product-form to LLM inference networks | KV-cache memory coupling violates independence between stages; product-form assumption does not hold | Model single-engine throughput optimality via work-conservation criterion (Dai, Deng, Li & Peng 2026); use MaxWeight-style routing for multi-engine networks |
| Deriving ρ < 1 from compute alone on a KV-cached LLM engine | Stability is jointly constrained by compute *and* GPU memory: each in-flight request's KV cache grows with every token it emits, so admitted work consumes a second, non-releasable resource until completion. A compute-only ρ can read comfortably below 1 while the memory constraint is already the binding one | Apply the joint compute-plus-memory stability condition (Nie, Si & Zhou, ICML 2026); size the cluster from the derived stable service rate, not from GPU FLOPs utilization |
| Assuming an eviction-free operating point is a stable equilibrium | Under saturation with homogeneous request lengths, decode completions synchronize, memory demand peaks together, and the system falls into a limit cycle of evict-and-restart — up to ~50% throughput loss. The eviction-free point is an unstable equilibrium, not a target | Desynchronize completions (heterogeneous or coprime decode lengths, staggered admission); admission-control on projected peak KV occupancy rather than instantaneous (Ao, Dong, Luo & Simchi-Levi 2026) |

Check [`references/patterns-scenarios-traps.md`](references/patterns-scenarios-traps.md) before using formulas for capacity commitments.

---

## Expert Judgment

The formulas above are correct but mechanical. What separates an expert read of a capacity problem from a formula lookup is knowing *which number to distrust* and *why the textbook answer is usually optimistic*.

**Why "80% utilization" is a heuristic, not a law.** ρ ≤ 0.7–0.8 is a widely repeated rule of thumb, but it is not derived from M/M/1 — it is a scar tissue from postmortems. M/M/1's Wq = ρ/(μ(1−ρ)) is smooth and finite at ρ = 0.8 (only 5× service time); nothing in the pure math says 80% is special. What makes 80% the practical wall in real systems is that CV²_a and CV²_s are almost never 1 in production: Kingman's variability factor (CV²_a+CV²_s)/2 typically runs 1.5–5× for HTTP/LLM/DB workloads, and that factor multiplies the same ρ/(1−ρ) term. A system that "should" be fine at ρ=0.8 under M/M/1 is often already 2–4× over its real SLO because of variance the mean-based model doesn't see. Treat 70–80% as a starting guess to be replaced by a measured ρ* from Kingman (07) with real CV² inputs — never as a target that stands on its own.

**VUT decomposition — variance matters as much as utilization.** Kingman's formula factors cleanly into three independent levers: **V**ariability (CV²_a+CV²_s)/2, **U**tilization ρ/(1−ρ), **T**ime E[S]. When Wq blows up, an expert's first move is to ask *which factor moved*, not to assume it was utilization. The most common real-world regression is a variance shift with flat or even falling utilization: a new job class with a heavier tail, a noisy-neighbor GC pause, a cold-start penalty, a retry storm — all inflate CV²_s or CV²_a without moving ρ at all. Dashboards that show only "CPU 65%, looks fine" miss this entirely. If you have percentile telemetry, compare p99/p50 of service time over time — a widening ratio at flat utilization is the VUT variance term moving, and no amount of added capacity (which only fixes the U term) will help until the variance source is found and isolated (priority lane, timeout, or separate pool).

**Batch-size effects break the "μ is constant" assumption.** Every formula in this skill treats service rate μ as fixed. Batching (DB writes, Kafka consumer polls, LLM continuous batching, GPU inference) makes μ a function of the current queue state — larger batches raise throughput but also raise per-item latency and effective service-time variance (a request's completion now depends on what else is in its batch, not just its own size). This is closer to a batch-service queue (M[X]/M/1) or a vacation-queue model than to plain M/M/1/M/G/1, and naively plugging a batch system's mean service time into P-K or Kingman underestimates Wq because it ignores the correlation batching induces between co-scheduled jobs. Practical rule: if batch size is a tunable knob in the system, model it as a control variable feeding into E[S] and CV²_s, not as a constant absorbed into μ — and re-measure CV²_s at each candidate batch size rather than assuming it is batch-size-invariant.

**When Little's Law is the only tool you can still trust.** Every closed-form result above (M/M/1, Erlang-C, P-K, Kingman, USL) depends on distributional or stationarity assumptions — Poisson arrivals, exponential or known-moment service times, steady state, i.i.d. samples. Real production traffic routinely violates all of them at once: heavy-tailed service times where even the *variance* fails to converge (CV² is undefined, not just large), autocorrelated bursts from retries/cron/batch releases that a single CV²_a number cannot capture, and non-stationary regimes during incidents or autoscaling transitions. Little's Law (L = λW) is the one relationship in this skill that requires none of that — only that the system is stable and observed over a long-enough window. When you don't trust the distributional inputs a formula needs, don't force-fit Kingman or P-K anyway: fall back to measuring L, λ, and W directly and using L = λW purely as a **consistency check**, not as a way to derive the one unknown you can't measure. If L ≠ λW under direct measurement, the problem is measurement or population-mixing, not the formula.

**Two misapplications that produce confidently wrong capacity plans:**
- *M/M/1 (or P-K) applied to heavy-tailed service times.* Once CV²_s exceeds roughly 5, or the service-time distribution is Pareto-like with infinite or barely-finite variance, P-K's Wq — which is itself a function of the second moment E[S²] — becomes unreliable, not merely "a bit low." A handful of extreme requests can dominate E[S²] and make the formula's output swing wildly between similar-looking samples. This is a qualitatively different failure than "variance inflates wait" (primitive 04's normal case): the mean-based formula itself stops being a stable estimator. Escalate to percentile-based modeling or discrete-event simulation rather than trusting a P-K point estimate.
- *Ignoring arrival burstiness because "CV²_a looks close to 1."* CV²_a measures dispersion of inter-arrival times but says nothing about *correlation* between them. Self-similar / long-range-dependent traffic (see Leland, Taqqu, Willinger & Wilson, "On the Self-Similar Nature of Ethernet Traffic," SIGCOMM 1993 — a foundational, widely-replicated result on bursty network traffic) can have CV²_a near 1 while still producing much longer queueing episodes than an i.i.d. renewal process with the same CV²_a, because bursts cluster in time. Kingman's formula assumes renewal (uncorrelated) arrivals and will underestimate Wq under such traffic even after "correcting" for CV²_a. If arrival autocorrelation is suspected (batch releases, coordinated retries, diurnal micro-bursts), validate against a measured autocorrelation function or a trace-driven simulation, not just a single CV²_a plugged into Kingman.

---

## Decision Checklist

- [ ] **Is the system stable?** Compute ρ = λ/(c×μ). If ρ ≥ 1, no steady-state solution exists — scale capacity first.
- [ ] **Single-server baseline?** → M/M/1 (02). Establish the latency vs. ρ curve.
- [ ] **Multiple parallel servers?** → M/M/c / Erlang-C (03). Compute minimum c for wait-time SLO.
- [ ] **Service time non-exponential (CV² ≠ 1)?** → P-K (04) for Poisson arrivals; Kingman (07) for non-Poisson arrivals.
- [ ] **Bursty arrivals (CV²_a > 1)?** → Kingman (07). M/M/1 will underestimate latency.
- [ ] **Multi-stage pipeline?** → Jackson networks (06). Solve flow balance; find highest-ρ stage.
- [ ] **Scaling horizontally?** → USL (09). Fit σ and κ from load-test series; check N_max.
- [ ] **Mixed SLO classes in one pool?** → Priority queues (05). Separate classes; analyze each.
- [ ] **High latency but good throughput?** → Bufferbloat (08). Check queue depth; apply AQM or finite bounds.
- [ ] **Drop-on-busy (no queue)?** → Erlang-B (10). Compute blocking probability B(c, a).
- [ ] **Fan-out / parallel scatter-gather?** → Fork-join (11). Compute E[max] = E[S] × H_K.
- [ ] **Sanity-check any result?** → Little's Law (01). Verify L = λ × W is consistent with measurements.
- [ ] **Tail latency SLO on multi-stage pipeline with non-Poisson arrivals?** → Jackson networks (06) + Ciucu-Mehri tandem sojourn bounds (SIGMETRICS 2025). Mean Jackson analysis understates tail risk when CV²_a ≠ 1.
- [ ] **Does admitted work hold a growing resource until it completes (KV cache, session buffers)?** → Single-resource ρ is insufficient. Check the joint compute-and-memory stability condition and the eviction/limit-cycle risk before trusting any ρ < 1 result (see [Misuse Boundaries](#misuse-boundaries)).

---

## Anti-Patterns

| Anti-Pattern | Queueing Theory Diagnosis | Fix |
|-------------|--------------------------|-----|
| **Ignoring service-time variability (CV²) on G/G/1 systems** | M/M/1 assumes CV²=1; real CV²>1 inflates Wq by (1+CV²)/2 factor | Measure service-time distribution; apply P-K (04) or Kingman (07) |
| **M/M/1 used at ρ near 1 without USL retrograde check** | M/M/1 predicts infinite latency but doesn't account for coherency degradation when c is added | Fit USL (09) from multi-server load tests before committing to scaling decision |
| **Little's Law applied across non-stationary windows** | L = λW holds only at steady state; burst windows violate ergodicity assumption | Use a measurement window ≥ 10× mean service time; separate burst analysis |
| **Erlang-C confused with Erlang-B for queueing decisions** | Erlang-B models drop/loss (no queue); Erlang-C models queuing (wait, don't drop) | Determine whether the system queues or blocks; select model accordingly (03 vs 10) |
| **Fork-join sized by mean worker time rather than max** | Completion time = E[max(S₁,...,Sₖ)] = E[S]×H_K >> E[S] at moderate K | Apply H_K harmonic correction; model tail of maximum; use speculative execution for high-K |
| **Unbounded application queues (bufferbloat)** | Large buffers absorb spikes silently; latency accumulates without 503/backpressure signal | Set finite queue depth proportional to BDP; add AQM or backpressure |
| **Scaling pipeline stage without re-solving flow balance** | Jackson network bottleneck shifts to next highest-ρ stage after scaling | Re-run flow-balance equations after each scaling action; re-identify bottleneck |
| **Using FCFS when output-length predictions are available** | FCFS ignores size information; SPRPT with Trail degrade