Queueing Theory for Software Capacity Planning

Capacity planning is not a search for one maximum requests-per-second number. A service can briefly complete 1,000 requests per second yet be unsafe at 700 when bursts grow queues, service varies, or a dependency saturates. The useful question is: under the expected arrivals and service distribution, how much work can the system admit while keeping delay and loss within explicit limits?

Queueing theory supplies conservation laws and models. Little’s Law relates concurrency, throughput, and latency. Utilization identifies the stability boundary, variability explains differing waits at the same mean service time, and bounded queues turn overload into controlled rejection.

The formulas produce hypotheses and reveal impossible targets; load experiments test them. This article applies that workflow to a hypothetical job service, so its numbers are planning calculations rather than observed benchmarks.

Draw the Queueing Boundary #

A queueing model needs a boundary. Requests arrive, possibly wait, receive service from one or more servers, then depart successfully or are rejected. A “server” is the resource that can make progress on one job at a time: a CPU core for CPU-bound work, an execution slot blocked on a dependency, a database connection, or a whole instance under a chosen abstraction.

Use consistent notation:

The boundary determines what counts as service. Database wait is service at a blocked handler station but may be queueing at the database station. Model a network of stations when one boundary hides the bottleneck; do not count the same resource wait as independent capacity.

Qualify every rate. Offered traffic arrives before admission, admitted traffic enters the queue, and completed traffic exits. Admitted and completed rates converge in a stable lossless interval but differ while backlog changes. Completed throughput alone can conceal rejection.

A model also states its discipline and workload classes. Mixing 2 ms lookups with 2 s reports into one average describes neither. Separate classes with different contention or objectives and account for their shared resource.

Use Little’s Law as a Conservation Check #

For a stable system observed over a sufficiently long interval, Little’s Law states

It requires consistent boundaries and units, but it does not require Poisson arrivals, exponential service, or first-come service. The same law applies to the queue alone:

Suppose a stable API admits and completes 120 requests per second, and mean time inside the chosen boundary is 180 ms. The implied mean in-flight population is

If mean service time is 40 ms, the mean population receiving service is $\lambda S=4.8$. The remaining 16.8 requests wait on average, which also follows from $120\times(0.180-0.040)$. Fractional population is normal because $L$ is a time average.

This is diagnostic. If telemetry reports mean in-flight 60 with throughput 120/s and latency 180 ms for the same interval, a boundary is inconsistent: perhaps in-flight includes rejected work, latency excludes queue wait, or throughput counts retries differently.

Little’s Law does not predict latency from throughput alone, and a growing queue is not in steady state. It also does not combine percentiles: p99 latency in $L=\lambda W$ does not yield p99 concurrency. Use means for conservation and distributions for service objectives.

For budgeting, a 100 ms mean-latency target at 500 admitted requests per second limits mean population to 50. This does not ensure a tail target, but rejects a design requiring 80 residents on average.

Respect Utilization’s Nonlinear Boundary #

For $m$ identical servers with mean service time $S$, nominal service capacity is $m/S$. Offered utilization is

A persistent workload with $\rho\ge1$ asks for at least as much service as the station can supply. Its expected queue cannot settle without rejection, cancellation, or another capacity change. More subtly, waiting rises sharply before 100% because random arrivals can cluster and service completions vary.

The elementary M/M/1 model assumes one server, Poisson arrivals, independent exponential service times, and first-come service. Under those assumptions,

Take a hypothetical server with mean service time 8 ms, so $\mu=125$ jobs/s. At $\lambda=100$ jobs/s, utilization is 0.8 and the model predicts mean system time of 40 ms, including 32 ms of waiting. At 112.5 jobs/s, utilization is 0.9 and predicted mean system time doubles to 80 ms even though arrival rate rose only 12.5%.

These are M/M/1 results, not universal forecasts. Real software has bounded concurrency, batching, caches, priorities, and multiple bottlenecks. The durable result is the shape: near saturation, small demand or service-time changes create large queues.

Target utilization is a risk decision based on bursts, scaling delay, failure reserve, variability, and rejection policy. Batch systems with generous completion windows can run hotter than interactive services that scale slowly.

Account for Service-Time and Arrival Variability #

Means determine offered load, but variance strongly affects waiting. For an M/G/1 queue with Poisson arrivals, general independent service times, and one server, the Pollaczek-Khinchine result can be written as

where $C_s^2=\operatorname{Var}(S)/\mathbb{E}[S]^2$ is squared coefficient of variation. At utilization 0.8 and mean service 10 ms, deterministic service with $C_s^2=0$ gives 20 ms mean wait under the model. Exponential service with $C_s^2=1$ gives 40 ms. A high-variance distribution with $C_s^2=9$ gives 200 ms. All three have the same mean service demand and nominal capacity.

Arrivals are more likely to encounter long service intervals, so a few expensive requests can dominate queueing without moving median service time much. Class isolation, input limits, or size-aware scheduling may outperform adding average capacity.

Arrivals vary too. A general approximation for a single-server G/G/1 queue is Kingman’s formula:

where $C_a^2$ describes interarrival-time variability. It is an approximation, especially away from its intended regime, but it exposes the levers: utilization, bursty arrivals, and variable service multiply each other. Averaging requests into one-minute rates erases bursts that a millisecond-scale queue must absorb.

Measure service time at the station, excluding its input queue wait, and retain class, payload, cache state, and dependency outcome when relevant. Compare any assumed distribution with controlled-experiment histograms or quantiles.

Turn Delay Budgets into Queue Bounds #

An unbounded queue turns overload into rising memory use and stale work. A bounded queue makes the policy explicit: admit, reject, shed a lower-priority class, or redirect. The bound should follow from how long queued work remains useful, not from available RAM.

Little’s Law can translate a mean waiting budget into a mean queue budget. At admitted rate $\lambda=300$/s and target mean queue wait $W_q=20$ ms,

This says the mean queue population must be around six or lower to meet that mean target in steady state. It does not prove that a queue capacity of six meets every request’s 20 ms deadline. Queue capacity is a maximum; $L_q$ is an average.

A deterministic waiting bound needs stronger assumptions. If at most $Q$ jobs are ahead, $m$ servers are work-conserving, and service time is at most $S_{max}$, a coarse first-come bound is

plus any unmodeled scheduling or preemption delay. Without a true service-time maximum, there is no deterministic wait bound from queue length alone. Use request deadlines and cancellation so obsolete work leaves both the queue and the service station.

Bound queues at every relevant layer; an application limit cannot help if a proxy, broker, retry buffer, or database pool queues without limit. Record enqueue time and propagate deadlines across the chain.

Admission also affects fairness. Per-class limits, weighted scheduling, or reserved capacity can prevent one tenant filling a global FIFO, but change the model. Rejections should discourage synchronized retries that return shed work as a larger burst.

Work a Capacity Plan from Demand to Backlog #

Consider a hypothetical image-metadata service with these planning inputs:

• Sustained admitted demand: 300 jobs/s.
• Two-second offered burst: 600 jobs/s.
• Mean service time at one worker: 12 ms.
• Initial worker count: 6.
• Maximum useful queue depth: 100 jobs before work becomes too stale.

The sustained offered load is

server-seconds of work per second. Six workers therefore have nominal utilization $3.6/6=0.60$ and mean-rate capacity $6/0.012=500$ jobs/s. This is a lower-bound capacity calculation, not a latency prediction; service variance and shared dependencies still need measurement.

During the 600/s burst, offered work exceeds nominal completion capacity by 100 jobs/s. A fluid approximation predicts backlog growth of 200 jobs over two seconds. A 100-job queue would begin rejecting around one second into the burst if all assumptions held. When demand returns to 300/s, spare nominal capacity is 200 jobs/s, so a 200-job backlog would take about one second to drain.

Several design choices follow. Increasing to eight workers raises nominal capacity to about 667/s and sustained utilization to 45%, enough to avoid mean-rate backlog during that particular burst if no downstream station saturates. Keeping six workers requires accepting rejection, increasing the queue beyond the staleness budget, reducing service demand, or pre-scaling before the burst. Autoscaling triggered only after the queue grows cannot erase work already waiting during its startup delay.

Now apply a mean latency budget. If the target mean system time is 50 ms at 300/s, Little’s Law permits mean population $L=15$. Mean service occupancy is 3.6, leaving a mean queue budget of 11.4. That budget is compatible with a maximum queue of 100 only if the queue is usually far below its limit. A queue-size alert at 100 is therefore an overload signal, not a normal operating target.

Before approval, replace mean service capacity with a model fitted to the measured distribution, include dependency limits, and test both six- and eight-worker configurations. The calculation has done its job if it predicts where backlog should begin and makes every tradeoff visible.

Run an Open-Loop Saturation Experiment #

A saturation experiment tests the capacity hypothesis by controlling offered arrivals. Use an open-loop generator that schedules requests at the intended rate independently of response completion. A closed-loop generator with a fixed number of virtual users slows its own arrivals when the service slows, hiding queue growth and producing a self-throttled workload.

Increase offered rate in steps long enough to observe queue behavior and reach a meaningful state. At each step record:

• Offered, admitted, rejected, cancelled, and completed rates.
• Queue depth and age, active servers, and utilization at each station.
• Queue wait, service time, and end-to-end time as separate distributions.
• Service-time variance and workload-class mix.
• Dependency utilization, errors, and retry attempts.

Saturation appears when throughput flattens, queue age grows, or rejection rises as offered load increases. CPU need not be high; a database, connection limit, lock, or quota may cap completion first. Hold payload and class mix constant, then vary them in separate scenarios.

Validate the model with identities. In stable intervals, check that $L\approx\lambda W$ and $L_q\approx\lambda W_q$ using admitted rate. Check flow conservation:

Compare the predicted utilization $\lambda S/m$ with measured busy fraction. Material disagreement identifies a boundary error, hidden work, batching, or non-work-conserving behavior that the model omitted.

Test steady plateaus, steps, spikes, expected ramps, one unavailable worker, and a slowed dependency. Label results by configuration and workload; they are evidence for a declared demand envelope, not a universal benchmark.

Operate with Assumptions Visible #

Capacity models fail when their assumptions drift silently. Track arrival rate by class, service demand, squared variation, queue age, utilization, rejection, cancellations, and retry amplification. Forecast from the offered workload, not only admitted traffic, because successful load shedding can otherwise make demand appear to vanish.

Common failures are treating average rate as a burst description, ignoring service tails, assuming shared dependencies are independent, and adding queue space to “improve throughput.” A queue creates no capacity; larger buffers trade short-burst rejection for staler work, memory pressure, and longer recovery.

Headroom should cover named scenarios such as forecast error, one unavailable instance, scaling delay, cache misses, or dependency slowdown. Calculate each contingency instead of adding an unexplained factor, and combine only scenarios that can plausibly coincide.

Queueing theory is most useful as a system of cross-checks. Little’s Law connects mean population, throughput, and time. Utilization rejects unstable plans. Variance explains why identical means produce different waits. Queue bounds make overload behavior deliberate. Saturation experiments reveal where the simplified model stops matching the software.

The resulting capacity decision should state the demand envelope, worker or instance count, utilization range, queue and admission policy, deadline behavior, scaling lead time, dependency assumptions, and evidence from the load curve. That is far more durable than a peak throughput number. It explains not only how much the system can process, but what happens when reality asks for more.