Queueing Theory

M/M/1 queue intuition

Simple Fundamental Explanation

Imagine you manage a bank with 3 tellers. Customers arrive randomly. If you know exactly 10 customers arrive every hour, and a teller takes exactly 15 minutes per customer, 3 tellers can easily handle the load (3 tellers * 4 customers/hr = 12 capacity).

But in reality, arrivals are clumped. 5 people might walk in during the same minute. Suddenly, a line forms. If a line forms, how long will a customer have to wait? If you add a 4th teller, how much faster will the line move?

Queueing Theory is the mathematical study of waiting lines. It provides exact formulas to predict queue lengths, waiting times, and server utilization probabilities based on the randomness of arrivals and the randomness of service times. It is the absolute foundation of capacity planning in cloud computing.

---

Deep Dive: How It Works Under the Hood

Any system that processes tasks (a CPU scheduling threads, a web server processing HTTP requests, a load balancer routing packets) is a queue.

The Kendall Notation (A/B/C)

Queueing systems are classified using Kendall Notation.

• A (Arrival Process): How tasks arrive. Usually $M$ for Markovian (Poisson process/memoryless random arrivals).
• B (Service Process): How long tasks take to process. Usually $M$ (Exponential distribution) or $D$ (Deterministic/constant time).
• C (Number of Servers): How many workers process the queue simultaneously (e.g., 1, or $c$).

The Impact of Utilization ($\rho$)

Utilization ($\rho$) is the ratio of work arriving to the system’s total capacity. If a server can process 100 requests/sec, and 80 requests/sec are arriving, $\rho =0.8$ (80%).

The most counter-intuitive aspect of queueing theory is that waiting time is not linear with utilization. As utilization approaches 100%, the line doesn’t just get a little longer; it explodes to infinity asymptotically. A server running at 95% CPU will have a queue drastically longer than a server running at 85% CPU.

Visual Diagram: The Hockey Stick Curve

Queue Wait Time (W)
 |
 |                                     | (Approaches Infinity)
 |                                    /
 |                                  /
 |                                /
 |                              /
 |                           _/
 |                       __/
 |____________________/
 +--------------------------------------
   10%   30%   50%   70%   90%   100%
      Utilization (rho)

---

Practical Example: SRE Auto-scaling Triggers

Why do Site Reliability Engineers (SREs) set auto-scaling rules to trigger when CPU hits 70%? Why not 95% to save money?

Because of Queueing Theory. At 70% utilization, the mathematical wait time in the queue is extremely low. If a sudden burst of traffic pushes utilization to 85%, the wait time increases slightly, but the system survives while new servers boot up.

If they ran the system at 90% CPU to save money, a tiny 5% burst in traffic pushing it to 95% would push the system into the vertical part of the “Hockey Stick” curve. The queue length would exponentially explode, causing memory exhaustion (OOM), massive tail latency, and system collapse. SREs mathematically buy the 30% “wasted” CPU headroom specifically as a buffer against the exponential math of queues.

---

The Mathematics: Equations and In-Depth Analysis

1. Little’s Law

The most famous theorem in Queueing Theory.

$$L=\lambda \cdot W$$

• $L$: Average number of items in the system.
• $\lambda$: Average arrival rate.
• $W$: Average time spent in the system.

If a web server receives $\lambda =100$ requests/sec, and the total latency $W=0.5$ seconds, there are exactly $L=50$ requests sitting in memory at any given time. This holds true completely regardless of the statistical distribution of the traffic!

2. The M/M/1 Queue

The simplest model: Random arrivals, random service times, 1 server. Let $\mu$ be the service rate (capacity). Utilization $\rho =\frac{\lambda }{\mu }$.

The average number of items in the queue (waiting to be processed) is:

$$L_q=\frac{{\rho }^2}{1-\rho }$$

Look at the denominator: $1-\rho$. If $\rho =0.50$ (50% loaded), $L_q=0.25/0.5=0.5$ items waiting. If $\rho =0.90$ (90% loaded), $L_q=0.81/0.1=8.1$ items waiting. If $\rho =0.99$ (99% loaded), $L_q=0.98/0.01=98$ items waiting.

Moving from 90% to 99% utilization is only a 10% increase in load, but it causes the queue length to jump by over 1000%!

3. The Kingman Formula Approximation

Real-world systems are rarely perfect M/M/1 queues. The Kingman formula provides a heavy-traffic approximation for any G/G/1 queue (General arrivals, General service). Let $c_a$ be the coefficient of variation for arrival times, and $c_s$ be the coefficient of variation for service times.

$$\mathbb{E}[W_q]\approx \left(\frac{\rho }{1-\rho }\right)\left(\frac{c_a^2+c_s^2}{2}\right)\frac{1}{\mu }$$

This formula isolates the three mathematical causes of latency:

1. Capacity ($\frac{\rho }{1-\rho }$): Running too close to 100% utilization.
2. Variability ($c_a^2+c_s^2$): How “spiky” the traffic is, and how inconsistent the database processing times are. If you make the database response times perfectly consistent ($c_s=0$), latency drops massively even if capacity stays the same.
3. Speed ($\frac{1}{\mu }$): The raw hardware processing speed.

Lab

M/M/1 queue: Poisson arrivals (λ) and exponential service (μ) on one server. The chart is one discrete-event run; metrics average 8 runs against README formulas L_q = ρ²/(1−ρ) and W_q = ρ/(μ(1−ρ)).

Arrival rate λ4 arrivals per second

Service rate μ6 services per second

Stable ρ≈0.67Overloaded ρ>1Light traffic

Bar height = customers waiting. Near ρ→1 the hockey-stick curve steepens; at ρ≥1 the system is unstable.

With λ=4/sec and μ=6/sec (ρ=0.67), will the queue explode (unbounded growth)?

Yes — queue grows without boundNo — queue is stable

ρ = 0.67 · chart max queue 12. Avg wait (sim) 0.32s vs theory 0.33s.