Jeffrey P. Kharoufeh
Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania

Abstract

This article describes the M/G/s/s queueing system, also known as the Erlang loss model. Customers arrive to this stochastic service system according to a homogeneous Poisson process and request service from one of s parallel servers The service times are assumed to be independent and identically distributed with a finite mean. Because there is no waiting space in the system, arriving customers who find all s servers busy are lost. Summarized herein are the primary operating characteristics of the M/G/s/ssystem, namely, the steady-state probability distribution of the number of occupied servers and the steady-state blocking probability (the Erlang B formula). Also summarized is the closely related delay probability (the Erlang C formula) for systems with exponential service times and unlimited waiting space. Some computational issues related to the Erlang B and C formulae are also discussed.

Keywords: Erlang loss system; loss formula; delay formula

INTRODUCTION

The M/G/s/s queueing system is perhaps the most important and popular model for analyzing service systems characterized by random arrival patterns, random processing times, and a limited number of resources. It has been especially useful for telephone network design, the performance evaluation of telecommunications systems, and the design and analysis of large-scale service systems (e.g., customer contact centers). Most of the main results for the model were developed within the first three decades of the twentieth century, and the model’s utility and importance have grown since that time.

In the parlance of Kendall’s notation (1), the abbreviation M/G/s/s means that the customer arrival process is Markovian or memoryless (M), the service times follow a general distribution (G), there are s identical servers and the total system capacity is limited to s (i.e., there is no waiting space in the system). The absence of a waiting space implies that customers who arrive to find all s servers busy leave and do not retry their service later. These customers are said to be lost. The M/G/s/s queue is often called the Erlang loss system since its development can be traced primarily to the Danish mathematician, Agner Krarup Erlang (1878–1929).

The popularity of the M/G/s/s model stems from the simplicity of the steady-state probability distribution of the number of busy servers, which makes it easy to estimate the proportion of customers that are lost by the system in the long run. This performance parameter is an important measure of service quality in many practical contexts. For example, the lost customers might represent vehicles arriving at a parking garage to find no vacant parking spaces. The garage owner forfeits a fraction of the revenue he or she would have obtained if another parking space were available. In telecommunications applications, the lost customers may represent lost data packets that contain critical information. For either case, the service provider is concerned with minimizing the proportion of lost customers to ensure a high quality of service. The steady-state distribution of the number of busy servers also provides an estimate of the utilization of the system’s resources in the long run.

The next section provides a mathematical description of the M/G/s/s system and presents the main results for its steady-state behavior, namely, the steady-state distribution of the number of occupied servers and the steady-state blocking probability.

MODEL DESCRIPTION AND THE ERLANG B FORMULA

In an M/G/s/s queue, customers arrive to the system according to a homogeneous Poisson process with rate parameter and the service times form an independent and identically distributed (i.i.d.) sequence of nonnegative random variables with finite mean The offered load to the system is the dimensionless quantity

(1)

The offered load per server, often termed the traffic intensity, is given by

(2)

Denote by Q(t) the number of occupied servers (or equivalently, the number of customers in the system) at time t. Note that is a stochastic process on the state space Let Q denote the steady-state number of busy servers and define the probability mass function (p.m.f.) of Q by

(3)

Owing to the fact that, at most, a finite number of customers can be present in the system, the existence of the steady-state distribution is ensured. Using a reversibility argument, as outlined by Gross and Harris (2) and detailed in Ross (3), it can be shown that

(4)

Equation 4 indicates that Q has a truncated Poisson distribution with parameter a, the offered load. The attractive feature of the steady-state distribution is that it depends on the service time distribution only through its mean (since ) and is otherwise insensitive to the form of the distribution. This insensitivity property is extremely useful for real applications when service times may be distinctly nonexponential. Because Poisson arrivals see time averages (PASTA, see Wolff (4, 5)), the long-run proportion of arriving customers who see s servers busy (and are blocked from receiving service) is precisely The formula for this blocking probability, termed the Erlang B formula, is

(5)

The Erlang B formula is a fundamental result for telephone traffic engineering problems and can be used to select the appropriate number of trunks (servers) needed to ensure a small proportion of lost calls (customers).

Several important properties of the function B(s,a) can easily be derived. For example, for a fixed, the blocking probability B(s,a) monotonically decreases to zero as s increases, and for s fixed, B(s,a) monotonically increases to unity as a increases. Other properties, such as convexity of the loss formula, have been discussed in Refs 6–8 among others. The Erlang B formula can also provide valuable insights into the behavior of large systems. For instance, Equation 5 can be used to show that it is more efficient to use a single large system with pooled servers than it is to use multiple smaller systems.

The next section examines the case when service times follow an exponential distribution. We discuss loss systems as well as systems with additional waiting space.

EXPONENTIAL SERVICE AND THE ERLANG C FORMULA

If the service times are i.i.d. exponential random variables with mean the system is an M/M/s/s queue and is a Markov process, namely, a birth-and-death process with birth rates

(6)

and death rates

(7)

In this case, so the Erlang B formula is (2)

(8)

Related to the Erlang B formula is the Erlang C formula (or Erlang delay formula) for the M/M/s system (or Erlang delay system), which includes an infinite-capacity queue to accommodate arriving customers who find all s servers busy. For this model, is interpreted as the long-run proportion of customers who experience a delay before their service begins. The model assumes that the customers are willing to wait as long as needed to receive service. The Erlang C formula is given by (9)

(9)

where Note that Equation 9 does not hold for arbitrary service time distributions, and it requires that the traffic intensity does not exceed unity.

As one might expect, a simple relationship exists between the Erlang B formula of Equation 5 and the Erlang C formula of Equation 9. It can be shown [cf. Cooper (9)] that

(10)

COMPUTATIONAL ISSUES

When a and s are large, it can be difficult to compute the right-hand side of Equation 5 due to the presence of factorials and potentially very large powers. However, the blocking probability can be much more easily computed by using a recursive scheme. As before, let

(11)

denote the blocking probability when an s-server system is offered a units of Poisson traffic. By analyzing the reciprocal of B(s,a), it is not difficult to derive the recursion,

(12)

where This recursion can be easily implemented in a spreadsheet or a computer program to obtain the blocking probability for systems with very large numbers of servers that are heavily loaded. To illustrate, consider a system with servers that is offered units of Poisson traffic. Computing by Equation 12, the steady-state blocking probability is

(13)

This means that about 0.8% of customers will be blocked from service.

When designing a new system, an important consideration is whether to use multiple small systems or to pool servers in one larger system. Suppose the first option is to operate two different loss systems, one with servers handling units of traffic and a second with servers handling units of traffic. The alternative is to operate a single larger system with servers and a combined offered load of Is it more efficient to operate the single larger system or the two smaller systems? This question can be answered using the Erlang B formula. Suppose and The proportion of blocked customers in the first system is

(14)

The proportion of blocked customers in the second system is

(15)

Therefore, the combined total proportion of lost customers between the two small systems is approximately 59%. If, on the other hand, all of the servers are pooled in a single system with servers, and the two traffic streams are combined so that the offered load is then the blocking probability is

(16)

That is, the larger service system reduces the (overall) proportion of lost customers by more than 50%. In general, it can be shown that

FURTHER READING

Classical textbooks that provide further details on the standard M/G/s/s model include Cooper (9), Gross and Harris (2), Ross (3), and Wolff (5). Important properties of the loss and delay formulae have been studied by many researchers. Jagerman (8) provided convexity results for the Erlang loss function. Harel and Zipkin (10) proved strong convexity results for the average sojourn time in an M/M/c system. Harel (7) showed that the proportion of lost customers in an M/G/s/s system is convex in the arrival rate, provided that the traffic intensity is below a threshold. Jagers and van Doorn (11) proved the convexity of functions that generalize the Erlang loss and delay functions. Some simple inequalities for the performance parameters of multiserver queues, including loss systems, were provided by Sobel (12). Harel (6) provided sharp bounds and simple approximations for the loss and delay formulae. Recently, Adelman (13) contributed simple algebraic approximations to the blocking formula using Palm calculus (14), which equates long-run event averages to long-run time averages. Ross and Seshadri (15) provided methods for estimating the expected time until the first customer is lost by the system.

Other authors have extended the basic model to include more complex and realistic dynamics. For instance, Brumelle (16) considered state-dependent systems with arrival and service rates that depend on the number of busy servers. The transient analysis of the Erlang loss system was considered by Abate and Whitt (17) and Grier et al. (18). Systems with time-varying arrival and/or service rates have been studied by Davis et al. (19), and more recently by Knessl and Yang (20). Lin and Ross (21) considered optimal admission control policies for a single-server Erlang loss model. Ziya et al. (22) analyzed the optimal pricing of customers in a loss model.

REFERENCES

1. Kendall DG. “Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains”. Ann Math Stat 1953; 24:338–354.
2. Gross D, Harris C. Fundamentals of queueing theory. New York, NY: John Wiley & Sons, Inc.; 1998.
3. Ross SM. Stochastic processes. New York, NY: John Wiley & Sons, Inc.; 1996.
4. Wolff RW. “Poisson arrivals see time averages”. Oper Res 1982 ;30:223–231.
5. Wolff RW. Stochastic modeling and the theory of queues. New York, NY: John Wiley & Sons, Inc.; 1989.
6. Harel A. “Sharp bounds and simple approximations for the Erlang delay and loss formulas”. Manage Sci 1988; 34:959–972.
7. Harel A. “Convexity properties of the Erlang loss formula”. Oper Res 1990 ;38:499–505.
8. Jagerman DL. “Some properties of the Erlang loss function”. Bell Syst Tech J 1974 ;53:525–551.
9. Cooper RB. Introduction to queueing theory. 2nd ed. New York, NY: North-Holland; 1981.
10. Harel A, Zipkin PH. “Strong convexity results for queueing systems”. Oper Res 1987; 35:405–418.
11. Jagers AA, van Doorn EA. “Convexity of functions which are generalizations of the Erlang loss function and the Erlang delay function”. SIAM Rev 1991; 33:281–282.
12. Sobel MJ. “Some inequalities for multiserver queues”. Manage Sci 1980; 26:951–956.
13. Adelman D. “A simple algebraic approximation to the Erlang loss model”. Oper Res Lett 2008; 36:484–491.
14. Baccelli F, Brémaud P. Elements of queueing theory: Palm Martingale calculus and stochastic recurrences. Berlin: Springer-Verlag; 2003.
15. Ross SM, Seshadri S. “Hitting time in an Erlang loss system”. Probab Eng Inform Sci 2002; 16:167–184.
16. Brumelle SL. “A generalization of Erlang’s loss system to state dependent arrival and service rates”. Math Oper Res 1978; 3:10–16.
17. Abate J, Whitt W. “Calculating transient characteristics of the Erlang loss model by numerical transform inversion”. Commun Stat Stoch Models 1998; 14:663–680.
18. Grier N, Massey WA, McKoy T, Whitt W. “The time-dependent Erlang loss model with retrials”. Telecommun Syst 1997;7:253–265.
19. Davis JL, Massey WA, Whitt W. “Sensitivity to the service-time distribution in the nonstationary Erlang loss model”. Manage Sci 1995; 41:1107–1116.
20. Knessl C, Yang Y. “On the Erlang loss model with time dependent input”. Queueing Syst 2006; 52:49–104.
21. Lin KY, Ross SM. “Optimal admission control for a single-server loss queue”. J Appl Probab 2004; 41:535–546.
22. Ziya S, Ayhan H, Foley RD. “Optimal prices for finite capacity queueing systems”. Oper Res Lett 2006; 34:214–218.