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
• Primitive Index
• Formal Supporting Theory
• Misuse Boundaries
• Expert Judgment
• Decision Checklist
• Anti-Patterns
• Composition Recipes
• Workflow
• ASCII Flow
• Related Skills
• Navigation
• Fact-Checking

---

Quick Reference

#	Primitive	Formula / Key Result	Use When
1	Little's Law	L = λW	Relating queue depth, rate, and latency at any stable system
2	M/M/1	W = 1/(μ−λ)	Single-server baseline; understanding saturation curve
3	M/M/c (Erlang-C)	C(c,a) Erlang-C formula	Multi-server pool sizing; wait-time SLO compliance
4	M/G/1 / Pollaczek-Khinchine	Wq = ρ·E[S]·(1+CV²)/2(1−ρ)	Service-time variability inflating queue latency
5	Priority Queues	Wq_1 < Wq_2 via P-K residual	Protecting high-priority workloads from low-priority batch
6	Jackson Networks	Product-form: π = Πᵢ πᵢ	Multi-stage pipeline bottleneck identification
7	Kingman's Formula	Wq ≈ (ρ/(1−ρ))·(CV²_a+CV²_s)/2·E[S]	G/G/1 under real bursty+variable traffic
8	Bufferbloat	Buffer > BDP → standing queue	Diagnosing high latency despite good throughput
9	USL	X(N) = λN/(1+σ(N−1)+κN(N−1))	Predicting retrograde throughput when scaling out
10	Erlang-B (Loss)	B(c,a) blocking formula	Sizing channels/connections for drop-on-busy systems
11	Fork-Join	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	Misaligned depth/rate/latency metrics; hidden measurement gaps
2	M/M/1	Underestimated latency at moderate utilization; hyperbolic saturation
3	M/M/c (Erlang-C)	Under/over-provisioned parallel server pools; incorrect wait SLO
4	M/G/1 / P-K	Variance-driven latency inflation invisible to M/M/1
5	Priority Queues	High-priority workload blocked by low-priority batch; head-of-line blocking
6	Jackson Networks	Pipeline bottleneck misidentified; scaling wrong stage
7	Kingman's Formula	M/M/1 underestimates real latency due to bursty arrivals and variable service
8	Bufferbloat	Oversized buffers accumulate standing queues; good throughput masks latency crisis
9	USL	Retrograde scaling: adding servers reduces throughput past N_max
10	Erlang-B	Blocking rate exceeds GoS target; call/connection loss uncontrolled
11	Fork-Join	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 — 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 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 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: Variability (CV²_a+CV²_s)/2, Utilization ρ/(1−ρ), Time 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).

---

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 degrades gracefully under bounded prediction error and approaches SRPT performance when predictions are accurate	Add lightweight output-length predictor (embedding-based); apply Trail policy (Mitzenmacher & Shahout 2025) with preemption age threshold to avoid KV-cache re-compute cost

---

Composition Recipes

Recipe 1 — Capacity Plan for a New Service

Goal: Size server pool before launch.

1. Little's Law (01): derive initial L, λ, W relationship from design requirements.
2. M/M/c (03): find minimum c so that Erlang-C wait probability meets SLO.
3. P-K / Kingman (04, 07): inflate Wq by measured CV²_s and CV²_a; re-check c.
4. USL (09): validate that the c-server pool achieves near-linear scaling (κ ≈ 0).

Standout insight: Kingman's variability factor (CV²_a + CV²_s)/2 can easily be 2–5×; a service meeting its SLO at ρ = 0.7 with M/M/c can violate SLO at the same ρ if CV² is ignored.

---

Recipe 2 — Saturation SLO Alert Threshold

Goal: Determine the utilization ρ* at which latency will breach SLO, and set an alert before it happens.

1. M/M/1 (02): solve W(ρ) = SLO_target; find ρ* (first-pass, exponential baseline).
2. Kingman (07): recompute ρ* with real CV²_a and CV²_s — typically ρ* is 10–20% lower.
3. Bufferbloat (08): confirm that queue depth monitoring is in place; standing queues are the first signal.
4. Little's Law (01): set alert on Lq = λ × Wq_threshold; queue depth is a leading indicator of latency breach.

Standout insight: Setting the alert on latency p99 is reactive; setting it on queue depth (via Little's Law) is proactive — the queue builds before p99 breaches.

---

Recipe 3 — Multi-Stage Pipeline Bottleneck Hunt

Goal: Find and fix the throughput bottleneck in a microservice chain, then verify the fix didn't shift the bottleneck.

1. Jackson networks (06): instrument each stage; collect λᵢ, μᵢ, cᵢ; solve flow-balance equations; rank by ρᵢ.
2. M/M/c (03): compute servers needed at bottleneck station i to achieve target ρ ≤ 0.70.
3. USL (09): after scaling station i, verify new ρ distribution; check for retrograde at any stage.
4. Priority queues (05): if multiple SLO classes converge at the bottleneck, separate into priority lanes.

Standout insight: The Jackson product-form result means each stage can be analyzed independently — but only after solving the traffic equations. Teams that scale one stage without re-solving flow balance routinely move the bottleneck downstream without knowing it.

---

Recipe 4 — LLM Inference Capacity Sizing

Goal: Size GPU/CPU capacity and select a scheduling policy for an LLM serving endpoint.