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 [math]\displaystyle{ c }[/math] vehicles and [math]\displaystyle{ N }[/math] 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 [math]\displaystyle{ c }[/math] small so as to minimize costs, but large enough to ensure that the blocking probability is tolerable.
Formula
Let
- [math]\displaystyle{ c \gt 0 }[/math] be the (integer) number of servers.
- [math]\displaystyle{ N \gt c }[/math] be the (integer) number of sources of traffic;
- [math]\displaystyle{ \lambda \gt 0 }[/math] be the idle source arrival rate (i.e., the rate at which a free source initiates requests);
- [math]\displaystyle{ h \gt 0 }[/math] 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]
- [math]\displaystyle{ P=\frac{\binom{N-1}{c}\left(\lambda h\right)^{c}}{\sum_{i=0}^{c}\binom{N-1}{i}\left(\lambda h\right)^{i}}. }[/math]
By rearranging terms, one can rewrite the above formula as[2]
- [math]\displaystyle{ P = \frac{1}{ {}_2 F_1(1,-c;N-c;-1/(\lambda h) ) } }[/math]
where [math]\displaystyle{ {}_2 F_1 }[/math] is the Gaussian Hypergeometric function.
Computation
There are several recursions[3] that can be used to compute [math]\displaystyle{ P }[/math] 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 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 [math]\displaystyle{ \lambda }[/math] is unknown (or hard to estimate) while [math]\displaystyle{ \alpha \gt 0 }[/math], the offered traffic per-source, is known. In this case, one can substitute the relationship
- [math]\displaystyle{ \lambda h=\frac{\alpha}{1-\alpha(1-P)} }[/math]
between the source arrival rate and blocking probability into the Engset formula to arrive at the fixed point equation
- [math]\displaystyle{ P = f(P) }[/math]
where
- [math]\displaystyle{ f(P) = \frac{1}{ {}_2 F_1(1,-c;N-c;1-P-1/\alpha) }. }[/math]
Computation
While the above removes the unknown [math]\displaystyle{ \lambda }[/math] 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 [math]\displaystyle{ f }[/math].[2] Alternatively, it is possible to use one of bisection or Newton's method, for which an open source implementation is available.
References
- ↑ Tijms, Henk C. (2003). A first course in stochastic models. John Wiley and Sons. doi:10.1002/047001363X.
- ↑ 2.0 2.1 Azimzadeh, Parsiad; Carpenter, Tommy (2016). "Fast Engset computation". Operations Research Letters 44 (3): 313–318. doi:10.1016/j.orl.2016.02.011. ISSN 0167-6377.
- ↑ Zukerman, Moshe (2000). "An Introduction to Queueing Theory and Stochastic Teletraffic Models" (pdf). http://www.ee.cityu.edu.hk/~zukerman/classnotes.pdf. Retrieved 2012-11-27.
![]() | Original source: https://en.wikipedia.org/wiki/Engset formula.
Read more |