Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T18:20:45.724Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximum Values in Queueing Processes

Published online by Cambridge University Press:  27 July 2009

Arthur W. Berger  and
Ward Whitt
Arthur W. Berger
Affiliation:
AT&T Bell Laboratories, Holmdel, New Jersey 07733-3030
Ward Whitt
Affiliation:
AT&T Bell Laboratories, Murray Hill, New Jersey 07974-0636
Get access Rights & Permissions [Opens in a new window]

Abstract

Motivated by extreme-value engineering in service systems, we develop and evaluate simple approximations for the distributions of maximum values of queueing processes over large time intervals. We provide approximations for several different processes, such as the waiting times of successive customers, the remaining workload at an arbitrary time, and the queue length at an arbitrary time, in a variety of models. All our approximations are based on extreme-value limit theorems. Our first approach is to approximate the queueing process by one-dimensional reflected Brownian motion (RBM). We then apply the extremevalue limit for RBM, which we derive here. Our second approach starts from exponential asymptotics for the tail of the steady-state distribution. We obtain an approximation by relating the given process to an associated sequence of i.i.d. random variables with the same asymptotic exponential tail. We use estimates of the asymptotic variance of the queueing process to determine an approximate number of variables in this associated i.i.d. sequence. Our third approach is to simplify GI/G/1 extreme-value limiting formulas in Iglehart [25] by approximating the distribution of an idle period by the stationary-excess distribution of an interarrival time. We use simulation to evaluate the quality of these approximations for the maximum workload. From the simulations we obtain a rough estimate of the time when the extreme-value limit theorems begin to yield good approximations.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 9 , Issue 3 , July 1995 , pp. 375 - 409
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Abate, J., Choudhury, G.L., & Whitt, W. (1993). Calculation of the GI/G/I waiting-time distribution and its cumulants from Pollaczek's formulas. Archiv für Eleklronik und Übertragungslechnik 47: 311–321.Google Scholar
2.Abate, J., Choudhury, G.L., & Whitt, W. (1994). Asymptotics for steady-state tail probabilities in structured Markov queueing models. Stochastic Models 10: 99–143.Google Scholar
3.Abate, J., Choudhury, G.L., & Whitt, W. (1994). Waiting-time tail probabilities in queues with long-tail service-time distributions. Queueing Systems 16: 311–338.CrossRefGoogle Scholar
4.Abate, J., Choudhury, G.L., & Whitt, W. (to appear). Exponential approximations for tail probabilities in queues, I: Waiting times. Operations Research.Google Scholar
5.Abate, J., Choudhury, G.L., & Whitt, W. (to appear). Exponential approximations for tail probabilities in queues, II: Sojourn time and workload. Operations Research.Google Scholar
6.Abate, J. & Whitt, W. (1987). Transient behavior of regulated Brownian motion, I: Starting at the origin. Advances in Applied Probability 19: 560–598.Google Scholar
7.Abate, J. & Whitt, W. (1988). Transient behavior of the M/M/l queue via Laplace transforms. Advances in Applied Probability 20: 145–178.Google Scholar
8.Asmussen, S. (1992). Queueing simulations in heavy traffic. Mathematics of Operations Research 17: 84–111.Google Scholar
9.Asmussen, S. & Perry, D. (1992). On cycle maxima, first passage problems and extreme value theory of queues. Stochastic Models 8: 421–458.Google Scholar
10.Bailey, N.T.J. (1957). Some further results in the non-equilibrium theory of a simple queue. Journal of the Royal Statistical Society B 19: 326–333.Google Scholar
11.Berger, A.W. & Whitt, W. (1992). The Brownian approximation for rate-control throttles and the G/G/I/C queue. Discrete Event Dynamic Systems 2: 7–60.Google Scholar
12.Berger, A.W. & Whitt, W. (1994). Asymptotics for open-loop window flow control. Journal of Applied Mathematics and Stochastic Analysis 7: 337–356.CrossRefGoogle Scholar
13.Berger, A.W. & Whitt, W. (to appear). Comparison of the sliding window and the leaky bucket. Queueing Systems.Google Scholar
14.Berman, S. (1962). Limiting distributions of the maximum term in sequences of dependent random variables. Annals of Mathematical Statistics 33: 894–908.Google Scholar
15.Billingsley, P. (1968). Convergence of probability measures. New York: Wiley.Google Scholar
16.Castillo, E. (1988). Extreme value theory in engineering. Boston: Academic Press.Google Scholar
17.Choudhury, G.L. & Lucantoni, D.M. (to appear). Numerical computation of the moments of a probability distribution from its transforms. Operations Research.Google Scholar
18.Choudhury, G.L., Lucantoni, D.M., & Whitt, W. (to appear). Squeezing the most out of ATM. IEEE Transactions on Communications.Google Scholar
19.Choudhury, G.L. & Whitt, W.(1994). Heavy-traffic asymptotic expansions for the asymptotic decay rates in the BMAP/G/I queue. Stochastic Models 10: 453–498.Google Scholar
20.Cohen, J.W.(1968). Extreme value distributions for the M/G/I and GI/M/I queueing systems. Annales de I'Institut Henri Poincaré Sect. B 4: 83–98.Google Scholar
21.Darling, D.A. & Siegert, A.J.F. (1953). The first passage problem for a continuous Markov process. Annals of Mathematical Statistics 24: 624–639.Google Scholar
22.Glynn, P.W. & Whitt, W. (to appear). Heavy-traffic extreme-value limits for queues. Operations Research Letters.Google Scholar
23.Halfin, S. (1985). Delays in queues, properties and approximations. In Akiyama, M. (ed.), Teletraffic issues in an advanced information society, ITC 11. Amsterdam: Elsevier, pp. 47–52.Google Scholar
24.Harrison, J.M. & Nguyen, V. (1993). Brownian models of multiclass queueing networks: Current status and open problems. Queueing Systems 13: 5–40.Google Scholar
25.Iglehart, D.L. (1972). Extreme values in the GI/G/I queue. Annals of Mathematical Statistics 43: 627–635.CrossRefGoogle Scholar
26.Johnson, N.L. & Kotz, S. (1970). Distributions in statistics: Continuous univariate distribulions-I. New York: Wiley.Google Scholar
27.Kemeny, J.G. & Snell, J.L. (1960) Finite Markov chains. New York: Van Nostrand.Google Scholar
28.Kraemer, W. & Langenbach-Belz, M. (1976). Approximate formulae for the delay in the queueing system GI/G/I. Proceedings of the Eighth International Teletraffic Congress, Melbourne, 235–1/8.Google Scholar
29.Leadbetter, M.R., Lindgren, G., & Rootzen, H. (1983). Extremes and related properties of random sequences and processes. New York: Springer-Verlag.CrossRefGoogle Scholar
30.McCormick, W.P. & Park, Y.S. (1992). Approximating the distribution of the maximum queue length for M/M/s queues. In Bhat, U.N. & Basawa, I.V. (eds.), Queueing and related models. Oxford: Oxford University Press, pp. 240–261.Google Scholar
31.Neuts, M.F. (1989). Structured stochastic matrices of M/G/I type and their applications. New York: Marcel Dekker.Google Scholar
32.Pakes, A.G. (1975). On the tails of waiting-time distributions. Journal of Applied Probability 12: 555–564.Google Scholar
33.Sadowsky, J.S. (1995). The probability of large queue lengths and waiting times in a heterogeneous multiserver queue, Pt. II: Positive recurrence and logarithmic limits. Advances in Applied Probability 27: 567–583.Google Scholar
34.Sadowsky, J.S. & Szpankowski, W. (1992). Maximum queue length and waiting time revisited: G/G/c queue. Probability in the Engineering and Informational Sciences 6: 157–170.Google Scholar
35.Sadowsky, J.S. & Szpankowski, W. (1995). The probability of large queue lengths and waiting times in a heterogeneous multiserver queue, Pt. 1: Tight limits. Advances in Applied Probability 27: 532–566.Google Scholar
36.Serfozo, R.F. (1988). Extreme values of birth and death processes and queues. Stochastic Processes and Their Applications 27: 291–306.Google Scholar
37.Serfozo, R.F. (1988). Extreme values of queue lengths in M/G/I and GI/M/I systems. Mathematics of Operations Research 13: 349–357.Google Scholar
38.Whitt, W. (1989). Planning queueing simulations. Management Science 35: 1341–1366.Google Scholar
39.Whitt, W. (1992). Asymptotic formulas for Markov processes with applications to simulations. Operations Research 40: 279–291.Google Scholar
40.Whitt, W. (1993). Approximations for the GI/G/m queue. Production and Operations Management 2: 114–161.Google Scholar