Engset formula
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
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
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{{cite book|last1=Tijms|first1=Henk C.|year=2003|title=A first course in stochastic models|publisher=John Wiley and Sons|doi=10.1002/047001363X}}
:
By rearranging terms, one can rewrite the above formula as{{cite journal|last1=Azimzadeh|first1=Parsiad|last2=Carpenter|first2=Tommy|title=Fast Engset computation|journal=Operations Research Letters|volume=44|issue=3|year=2016|pages=313–318|issn=0167-6377|doi=10.1016/j.orl.2016.02.011|arxiv = 1511.00291}}
:
where is the Gaussian Hypergeometric function.
=Computation=
There are several recursions{{cite web|last=Zukerman|first=Moshe|title=An Introduction to Queueing Theory and Stochastic Teletraffic Models|date=2000|url=http://www.ee.cityu.edu.hk/~zukerman/classnotes.pdf|format=pdf|accessdate=2012-11-27}} 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.
from scipy.special import hyp2f1
P = 1.0 / hyp2f1(1, -c, N - c, -1.0 / (Lambda * h))
MATLAB with the [http://www.mathworks.com/products/symbolic/ Symbolic Math Toolbox]
P = 1 / hypergeom([1, -c], N - c, -1 / (Lambda * h))
Unknown source arrival rate
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=
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 . Alternatively, it is possible to use one of bisection or Newton's method, for which an [https://github.com/parsiad/fast-engset/releases open source implementation] is available.
References
{{reflist}}