Engset formula

Consider a fleet of $c$ vehicles and $N$ 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 $c$ small so as to minimize costs, but large enough to ensure that the blocking probability is tolerable.

Let

• $c\; >\; 0$ be the (integer) number of servers.
• $N\; >\; c$ be the (integer) number of sources of traffic;
• $\backslash lambda\; >\; 0$ be the idle source arrival rate (i.e., the rate at which a free source initiates requests);
• $h\; >\; 0$ 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}}

:$P=\backslash frac\{\backslash binom\{N-1\}\{c\}\backslash left(\backslash lambda\; h\backslash right)^\{c\}\}\{\backslash sum\_\{i=0\}^\{c\}\backslash binom\{N-1\}\{i\}\backslash left(\backslash lambda\; h\backslash right)^\{i\}\}.$

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}}

:$P\; =\; \backslash frac\{1\}\{\; \{\}\_2\; F\_1(1,-c;N-c;-1/(\backslash lambda\; h)\; )\; \}$

where $\{\}\_2\; F\_1$ is the Gaussian Hypergeometric function.

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 $P$ 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 [http://www.mathworks.com/products/symbolic/ Symbolic Math Toolbox]

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

In practice, it is often the case that the source arrival rate $\backslash lambda$ is unknown (or hard to estimate) while $\backslash alpha\; >\; 0$, the offered traffic per-source, is known.

In this case, one can substitute the relationship

:$\backslash lambda\; h=\backslash frac\{\backslash alpha\}\{1-\backslash alpha(1-P)\}$

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

:$P\; =\; f(P)$

where

:$f(P)\; =\; \backslash frac\{1\}\{\; \{\}\_2\; F\_1(1,-c;N-c;1-P-1/\backslash alpha)\; \}.$

While the above removes the unknown $\backslash lambda$ 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 $f$. 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.

{{reflist}}

Category:Queueing theory