Blocking, throughput, and Little’s law
Section of Birth–death chains and queues, part of Stochastic processes
Blocking, throughput, and Little’s law
| Type | Section |
| Taught in | Birth–death chains and queues |
| Part | Stochastic processes |
For a finite room of size K, offered arrivals still occur at rate \lambda. An arrival that finds the system full does not enter. Under Poisson arrivals the long-run fraction blocked is \pi_K, and the accepted throughput is \lambda(1-\pi_K). In equilibrium the long-run departure rate equals the accepted throughput. It equals \lambda only when nothing is blocked.
Definition 1 (Little’s law) In a stable system, L=\lambda_{\mathrm{eff}} W, where L is the mean number in the system, \lambda_{\mathrm{eff}} is the mean arrival rate of the customers counted in L, and W is their mean time in the system.
The relation is an accounting identity between those three averages. It does not require exponential service. The arrival rate has to be the rate of the population being counted. For a blocking queue, use the accepted throughput, not the offered rate. For the queue excluding service, use the mean number waiting L_q together with the mean waiting time W_q. Mixing L_q with the total time in system pairs two different populations.
A service operation can have a rate that changes with the hour, several customer classes, balking, priorities, service laws other than exponential, and servers who are not independent. Each of those changes the generator. The first check is whether the state and the constant rates are credible for the decision at hand. Near a stability boundary, \rho close to 1, the mean L=\rho/(1-\rho) moves sharply when \lambda or \mu moves a little, so that boundary deserves a direct look.
Local balance gives \pi_n as a product of birth rates over death rates. The product is a probability when its sum converges. For M/M/1 that happens exactly when \lambda<\mu, and then the number present is geometric with mean \rho/(1-\rho). Finite capacity restores a stationary law at every load by refusing arrivals, and the throughput falls below the offered rate.
Used in
See also
Little’s law · Birth–death balance · M/M/1 queue · M/M/∞ queue · Multi-server and finite-capacity queues · Machine-repair model · Three capacity rules · Local balance