Q1Computer Networks

Derivation of Mathematical Model for M/M/m/m Queue

The M/M/m/m queue (also known as the Erlang loss system or Erlang-B system) models a system with m servers and no waiting room at all (system capacity exactly equals the number of servers, m) - any arriving customer that finds all m servers already busy is immediately blocked (lost) rather than being made to wait, a model highly relevant to classical telephone trunk-line capacity engineering, where a blocked call is simply rejected (busy signal) rather than queued. The birth rate remains lambda_n = lambda for all states n from 0 up to m-1 (an arrival is always possible as long as fewer than m servers are busy), but becomes zero for n=m (no arrivals can be accepted once all m servers are occupied, since there is no waiting room to hold a blocked arrival). The death rate mu_n = n*mu for n from 0 to m (with n of the m servers currently busy, each independently completing service at rate mu).

Applying the general birth-death steady-state solution with these state-dependent rates (identical in form to the M/M/infinity case for states n from 0 to m, since the rates are the same in this range, differing only in that the M/M/m/m system's state space is truncated at n=m) gives Pn = P0*(lambda/mu)^n/n! for 0 <= n <= m, exactly as in the M/M/infinity case but restricted to this finite range of states.

Applying the normalization condition (summing only over the finite range n=0 to m, rather than to infinity as in the M/M/infinity case) determines P0, and the resulting formula for Pm (the probability that all m servers are simultaneously busy, and hence the probability that a newly arriving customer is blocked/lost) is precisely the famous Erlang-B blocking formula, one of the most historically important results in traffic engineering, originally derived by A.K. Erlang for sizing telephone exchange trunk-line capacity to achieve a target acceptable call-blocking probability, and still widely used today (extended to computer network and cellular system capacity planning) whenever a system with a hard capacity limit and no queuing (blocked requests simply rejected) must be sized to meet a specified blocking-probability service target.

Pure Birth and Pure Death Processes with Examples

A pure birth process is exemplified by the simple Poisson arrival process itself: packets arriving at a network router, with no packets ever departing in this idealized model (representing, for instance, only the arrival-counting aspect of traffic, ignoring service/departure entirely) - the number of arrivals observed by time t follows a Poisson distribution with mean lambda*t, growing monotonically over time with no possibility of decrease, exactly the defining characteristic of a pure birth process. A pure death process is exemplified by a finite population of n0 customers currently present in a system with no further arrivals permitted, being served and progressively leaving the system one at a time (for example, modeling the final phase of a batch job-processing system after all input jobs have been submitted and no more will arrive, with the system simply draining its existing backlog to completion) - the number remaining in the system decreases monotonically from n0 toward 0 over time, following state-dependent death rates that may depend on how many parallel servers are simultaneously processing the remaining backlog.

It is instructive to compare the M/M/m/m Erlang-B loss system derived here against the M/M/infinity system discussed in relation to another question in this examination: both share identical steady-state probability expressions Pn = P0*(lambda/mu)^n/n! for states up to n=m, since both systems have identical birth and death rate structure in this range (no queueing delay is possible in either model, since M/M/infinity has unlimited servers and M/M/m/m has no waiting room at all) - the two models differ only in their normalization (M/M/infinity sums over all n from 0 to infinity, while M/M/m/m sums only over n from 0 to m), and in their practical interpretation, with M/M/infinity representing an idealized always-available-capacity scenario and M/M/m/m representing a realistic, hard-capacity-limited scenario where exceeding capacity results in outright rejection (blocking) rather than unlimited additional service capacity.

The pure death process example given above, of a finite job backlog being progressively drained with no further arrivals, has a direct practical parallel in computer networking during a planned, graceful network maintenance shutdown procedure: once new connection requests are deliberately blocked (analogous to stopping further arrivals), the network monitoring system can model the remaining active connections as following a pure death process, with the death rate depending on how many of the existing connections are still active and how quickly each is completing (or being gracefully terminated), allowing network operators to estimate how long a full graceful shutdown of all active sessions will take before proceeding with planned maintenance work, based on the same birth-death mathematical machinery used to derive the queueing models throughout this examination.

A further important structural observation about the Erlang-B blocking formula derived above is that it depends only on the offered traffic load (expressed in Erlangs as A = lambda/mu) and the number of servers m, not on the arrival rate and service rate individually - meaning two systems with very different absolute arrival and service rates but the same ratio lambda/mu and the same number of servers m will experience exactly the same blocking probability, a property that greatly simplifies practical trunk-capacity engineering, since network planners can size a system purely based on this single normalized traffic-intensity figure rather than needing to separately account for the specific absolute magnitudes of arrival and service rates.

This traffic-intensity-based sizing approach remains directly applicable to modern computer network capacity planning problems well beyond its original telephone-trunk-engineering context, including sizing the number of parallel processing threads or virtual machine instances needed in a cloud computing service to meet a target request-blocking (or request-rejection) probability given an expected offered request arrival rate and per-request processing time, illustrating the enduring, cross-domain practical value of this nearly century-old traffic engineering result.

This closes out the full derivation of the M/M/m/m Erlang-B model and the accompanying discussion of pure birth and pure death processes with their respective networking-relevant examples.