Engset formula explained

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

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.

Formula

Let

c > 0 be the (integer) number of servers.N > c be the (integer) number of sources of traffic;λ > 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^[1]

P = (\binom{N -1)/(c) \left( λ h\right) ^{c} }.By rearranging terms, one can rewrite the above formula as^[2] P = (1)/({) _{2} F _{1(1,-c;N-c;-1/(λ} h) ) } where {} _{2} F _{1} is the Gaussian Hypergeometric function.

Computation

There are several recursions^[3] 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 SciPyfrom scipy.special import hyp2f1P = 1.0 / hyp2f1(1, -c, N - c, -1.0 / (Lambda * h))

MATLAB with the Symbolic Math ToolboxP = 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 \alpha > 0 , the offered traffic per-source, is known.In this case, one can substitute the relationshipλ h = (\alpha)/(1- \alpha( 1- P)) between the source arrival rate and blocking probability into the Engset formula to arrive at the fixed point equationP = f(P) wheref(P) = (1)/({) _{2} F _{1(1,-c;N-c;1-P-1/\alpha)} }.

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 f . Alternatively, it is possible to use one of bisection or Newton's method, for which an open source implementation is available.

Notes and References

1. Book: Tijms. Henk C.. 2003. A first course in stochastic models. John Wiley and Sons. 10.1002/047001363X.
2. Azimzadeh. Parsiad. Carpenter. Tommy. Fast Engset computation. Operations Research Letters. 44. 3. 2016. 313–318. 0167-6377. 10.1016/j.orl.2016.02.011. 1511.00291.
3. Web site: Zukerman. Moshe. An Introduction to Queueing Theory and Stochastic Teletraffic Models. 2000. pdf. 2012-11-27.