Queueing theory and performance

Level AdvancedDifficulty ★★★★★Application⌖ Open in the map

What is it?

Models of requests waiting for servers. With exponential (memoryless) arrivals and services, the M/M/1 queue gives closed formulas: as utilization $\rho \to 1$ , waiting time explodes like $1/(1 - \rho)$ — why systems are run well below full capacity.

Formulas

\rho = \frac{\lambda}{\mu}, \qquad W = \frac{1}{\mu - \lambda}, \qquad L = \lambda W

The mathematics behind it

Continuous distributions★★★★★fundamental
Poisson arrivals have exponential inter-arrival times — the basis of M/M/1 models of servers.
Expectation★★★★★frequent
Little's law $L = \lambda W$ relates expected queue length and expected waiting time.
Geometric series★★★★★frequent
In an M/M/1 queue the number of customers is geometric: $P(N = n) = (1 - \rho)\rho^n$ .
Cumulative distribution function★★★★★frequent
Latency percentiles (p99) are quantiles of the response-time distribution.

Exercises

1Computing

A service handles $\mu = 100$ req/s. Compare the mean response time at $\lambda = 50$ , $90$ and $99$ req/s (M/M/1).

Solution

$W = 1/(\mu - \lambda)$ : 20 ms, 100 ms and 1 s. Going from 90% to 99% utilization multiplies latency by 10.

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.