1
Verify Little's Law on a trace and size with it
Compute L, λ and W from arrival and departure times, check L = λW exactly, and solve it for a connection pool, a thread count or the throughput cap they imply.
Course · System Design
Queues and Utilisation
Why a server at 80% is nearly full, in numbers. The course opens with the one law that needs no assumptions — L = λW, proved on a trace by counting — builds the exponential and Poisson distributions as limits of the geometric and binomial you already have, derives M/M/1 by flow balance, and ends with the four controls a designer actually has: fewer queues with more servers, less variance, a bounded buffer, and a token bucket.
ρ = λ/μ a ratio of rates; μ is not a latency
L = λW an identity; no distribution assumed
πₙ = (1 − ρ)ρⁿ L = ρ/(1 − ρ) M/M/1, by balance across a cut
W = S/(1 − ρ) S = 1/μ; the hyperbola and its asymptote
π_K = (1 − ρ)ρ^K/(1 − ρ^(K+1)) and the admitted rate is λ(1 − π_K)
What this course is about
- Subject
- System Design
- Lessons
- 13
- Format
- Interactive
Overview
What you will be able to do
By the end you can compute the three quantities of a queue from a trace, from a model and from a simulation, locate the knee, and price each of the four controls a designer has over waiting.
2
Compute M/M/1 at a rational utilisation and find the knee
πₙ, L, L_q, W and the tail P(N > k) as exact fractions, and the ρ at which the response time reaches k service times.
3
Say where the waiting comes from
Bunching rather than overload — shown on a seeded slotted simulation against deterministic arrivals at the same ρ — and the variability term that halves the wait when the variance halves.
4
Price the four controls
One pooled queue of s servers against s separate ones; a bounded buffer's loss, its latency cap and its admitted rate; a token bucket's admissions on a trace; and the backlog a transient spike leaves behind.
Lessons
13 lessons
The identity that needs no model comes first, then the two distributions built as limits, then the model they support, and last the four things a designer can change.
λ, μ and ρCompute ρ from an arrival rate and a service time, and give the growth rate when ρ reaches one.Not marked
Little's Law from a TraceCompute L, λ and W from arrival and departure times and verify L = λW exactly.Not marked
Sizing with Little's LawSize a connection pool from a rate and a latency, and state the throughput cap it implies.Not marked
Why Queues Form at ρ < 1Compare the mean queue of random and clockwork arrivals at the same utilisation and name the difference.Not marked
Memoryless Waiting: from Geometric to ExponentialCompute a waiting-time tail exactly in slots and as its continuous limit, and report the gap.Not marked
Poisson Arrivals and BurstsCompute the chance a window overflows a capacity, and the capacity a burst target needs.Not marked
The M/M/1 QueueCompute πₙ, L, L_q and a tail probability at a rational utilisation, exactly.Not marked
The Knee: Response Time vs UtilisationCompute the response time at a given utilisation, and the utilisation at which it reaches k service times.Not marked
Variability: the Kingman ApproximationCompute the waiting time for given coefficients of variation and compare it with the exact answer.Not marked
Many Servers: Pooling, and Erlang CCompute the waiting time of one pooled queue and of s separate queues at the same load, and compare.Not marked
Bounded Queues and LossCompute a buffer's loss, the K a loss target needs, its latency cap and its admitted rate.Not marked
Token Buckets and Rate LimitingRun a trace through a bucket and a fixed window, and count admissions, rejections and the largest burst each allows.Not marked
Transient Overload and Draining the BacklogCompute the peak backlog, the drain time and the worst consumer lag from a piecewise arrival rate.Not marked
Recommended background
Capacity Estimation and Latency and the Tail. Discrete Mathematics: the geometric and binomial distributions, expected value, and the seeded generator. Algebra: infinite geometric series, the number e, graphs and asymptotes, and literal equations.
Practice suggestions
Do the trace lesson with pencil and paper before touching the lab. L = λW is a statement about an area and a sum, and seeing the two agree by counting is what stops it being a formula.
Watch what the slot size does in the slotted lab. Every claim in this course about a continuous-time queue is the limit of a discrete one, and the slot control is where that limit is visible rather than asserted.
Read the knee as a hyperbola, not as a table of numbers. The asymptote at ρ = 1 is the whole content; the numbers at 0.5, 0.9 and 0.99 are three points on it.
What it does not cover
Queueing networks, and priority disciplines beyond a mention.
The Pollaczek–Khinchine derivation. Kingman's formula is stated as an approximation and the lab shows the simulation disagreeing with it.
The derivation of Erlang C. It is stated in “Many Servers: Pooling, and Erlang C” and used there; the state-dependent birth–death chain it comes from is Operations Research markov-chains-decisions-and-queues/multiple-servers-and-erlang-c.
Markov chains as a theory. M/M/1 here is a conservation argument across a cut, not a chapter on chains; Operations Research builds the chain.