In queueing theory, the Engset formula is used to determine the blocking probability of an M/M/c/c/N queue (in Kendall's notation).

The formula is named after its developer, T. O. Engset.

Example application

edit

Consider a fleet of   vehicles and   operators. Operators enter the system randomly to request the use of a vehicle. If no vehicles are available, a requesting operator is "blocked" (i.e., the operator leaves without a vehicle). The owner of the fleet would like to pick   small so as to minimize costs, but large enough to ensure that the blocking probability is tolerable.

Formula

edit

Let

  •   be the (integer) number of servers.
  •   be the (integer) number of sources of traffic;
  •   be the idle source arrival rate (i.e., the rate at which a free source initiates requests);
  •   be the average holding time (i.e., the average time it takes for a server to handle a request);

Then, the probability of blocking is given by[1]

 

By rearranging terms, one can rewrite the above formula as[2]

 

where   is the Gaussian Hypergeometric function.

Computation

edit

There are several recursions[3] that can be used to compute   in a numerically stable manner.

Alternatively, any numerical package that supports the hypergeometric function can be used. Some examples are given below.

Python with SciPy

from scipy.special import hyp2f1
P = 1.0 / hyp2f1(1, -c, N - c, -1.0 / (Lambda * h))

MATLAB with the Symbolic Math Toolbox

P = 1 / hypergeom([1, -c], N - c, -1 / (Lambda * h))

Unknown source arrival rate

edit

In practice, it is often the case that the source arrival rate   is unknown (or hard to estimate) while  , the offered traffic per-source, is known. In this case, one can substitute the relationship

 

between the source arrival rate and blocking probability into the Engset formula to arrive at the fixed point equation

 

where

 

Computation

edit

While the above removes the unknown   from the formula, it introduces an additional point of complexity: we can no longer compute the blocking probability directly, and must use an iterative method instead. While a fixed-point iteration is tempting, it has been shown that such an iteration is sometimes divergent when applied to  .[2] Alternatively, it is possible to use one of bisection or Newton's method, for which an open source implementation is available.

References

edit
  1. ^ Tijms, Henk C. (2003). A first course in stochastic models. John Wiley and Sons. doi:10.1002/047001363X.
  2. ^ a b Azimzadeh, Parsiad; Carpenter, Tommy (2016). "Fast Engset computation". Operations Research Letters. 44 (3): 313–318. arXiv:1511.00291. doi:10.1016/j.orl.2016.02.011. ISSN 0167-6377.
  3. ^ Zukerman, Moshe (2000). "An Introduction to Queueing Theory and Stochastic Teletraffic Models" (pdf). Retrieved 2012-11-27.