Finite queues and admission control

A finite queue replaces unbounded accumulation with an admission-versus-rejection tradeoff. Bounded occupancy means storage is bounded; a system rejecting most requests can still fail its business objectives.

In M/M/1/K, K includes the job in service

Keep Poisson arrivals, independent exponential service and a single FCFS server, but allow at most $K$ jobs inside. Full arrivals are rejected immediately without retries or abandonment. For offered-load ratio $r=\lambda /\mu$, the finite-state stationary probabilities are:

$${\pi }_n=\frac{r^n}{{\sum }_{j=0}^K{r}^j},n=0,\dots ,K.$$

At $r=1$, every state has probability $1/(K+1)$; there is no singularity. With positive arrival and service rates the finite chain is positive recurrent even when offered traffic exceeds capacity. Here $r$ is not actual utilization and may exceed one.

Poisson arrivals give rejection probability ${\pi }_K$. Accepted throughput, busy fraction and mean residence of admitted jobs are:

$${\lambda }_{\mathrm{eff}}=\lambda (1-{\pi }_K)=\mu (1-{\pi }_0),U=1-{\pi }_0,E[T\mid \text{accepted}]=\frac{L}{{\lambda }_{\mathrm{eff}}}.$$

Here $L=\sum n{\pi }_n$. Using external $\lambda$ with internal occupancy incorrectly includes requests that never entered.

At the defaults $\lambda =120$/s, $\mu =100$/s and $K=5$, rejection is about 25.1%, accepted throughput 89.9/s and mean residence 33.6 ms. Larger K can reduce rejection and keep the server busier while increasing admitted-job waiting. The model has no timeout, service failure or retry: every admitted job eventually completes. Production successful throughput needs separate accounting.

Admission, backpressure and timeouts change different things

Admission rejects or defers work before consuming protected resources. Backpressure communicates downstream limits upstream, potentially moving the wait to a client or another queue. A timeout limits how long the caller waits. None substitutes for the others.

A client timeout need not stop server work. Retrying can create concurrent copies. Propagate deadlines, check remaining budgets while queued and at dispatch, and provide cancellation or deduplication that the operation can actually honor. These mechanisms are absent from M/M/1/K, so its mean does not predict deadline success.

A 20 ms waiting budget and mean throughput 1000/s do not imply K=20 guarantees a p99 target. Work ahead, residual service, parallelism and variability matter. Reliable bounds on individual job cost can support conservative waiting bounds; otherwise use distributions or measurements.

Effective successful work is the objective

Distinguish offered, admitted, completed and useful successful throughput, often called goodput. Fast rejections can make an aggregate latency percentile look better. Report rejection rate beside successful-request latency and state how timeouts, cancellations and unfinished requests enter the SLO.

Check your understanding

1. With $\lambda =\mu$ and $K=1$, what are rejection and admitted mean residence?

2. Does changing a timeout from 1 s to 100 ms necessarily reduce server work?

Further reading

See the MIT lecture for finite-capacity accounting, Google SRE for admission and rejection costs, and message semantics for duplicate delivery and business identity.