Engset formula

From Wikipedia, the free encyclopedia
  (Redirected from Engset calculation)
Jump to: navigation, search

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. / hyp2f1(1, -c, N - c, -1. / (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, which converges unconditionally,[2] or
  • Newton's method, which is proven to converge for [2] (in practice, it also works for ).

An open source implementation is available for these methods.

References[edit]

  1. ^ Tijms, Henk C. (2003). A first course in stochastic models. John Wiley and Sons. doi:10.1002/047001363X. 
  2. ^ a b c d Azimzadeh, Parsiad; Carpenter, Tommy (2016). "Fast Engset computation". Operations Research Letters. 44 (3): 313–318. arXiv:1511.00291free to read. 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.