Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-08T17:32:32.791Z Has data issue: false hasContentIssue false
  • English
  • Français

A new view of the heavy-traffic limit theorem for infinite-server queues

Published online by Cambridge University Press:  01 July 2016

Peter W. Glynn  and
Ward Whitt
Peter W. Glynn*
Affiliation:
Stanford University
Ward Whitt*
Affiliation:
AT & T Bell Laboratories
*
∗Postal address: Department of Operations Research, Stanford University, Stanford, CA 94305-4022, USA.
∗∗Postal address: AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974-2070, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a new approach for obtaining heavy-traffic limits for infinite-server queues and open networks of infinite-server queues. The key observation is that infinite-server queues having deterministic service times can easily be analyzed in terms of the arrival counting process. A variant of the same idea applies when the service times take values in a finite set, so this is the key assumption. In addition to new proofs of established results, the paper contains several new results, including limits for the work-in-system process, limits for steady-state distributions, limits for open networks with general customer routes, and rates of convergence. The relatively tractable Gaussian limits are promising approximations for many-server queues and open networks of such queues, possibly with finite waiting rooms.

Keywords

MANY-SERVER QUEUESHEAVY TRAFFICDIFFUSION APPROXIMATIONSQUEUEING NETWORKSGAUSSIAN DISTRIBUTIONSSTRONG APPROXIMATIONSG/G/∞QUEUES
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 1 , March 1991 , pp. 188 - 209
Copyright
Copyright © Applied Probability Trust 1991 

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.)

Footnotes

Research supported by the U.S. Army Research Office under Contract DAAL-03-88-K-0063 and by a Natural Sciences and Engineering Research Council of Canada grant.

References

Billingsley, P. (1968) Convergence of Probability Measures. Wiley, New York.Google Scholar
Borovkov, A. A. (1967) On limit laws for service processes in multi-channel systems. Siberian Math. J. 8, 746–763.CrossRefGoogle Scholar
Borovkov, A. A. (1984) Asymptotic Methods in Queuing Theory. Wiley, New York.Google Scholar
Csörgo, M. and Révész, P. (1981) Strong Approximations in Probability and Statistics. Academic Press, New York.Google Scholar
Csörgo, M., Deheuvels, P. and Horvath, L. (1987a) An approximation of stopped sums with applications in queueing theory. Adv. Appl. Prob. 19, 674–690.CrossRefGoogle Scholar
Csörgo, M., Horváth, L. and Steinebach, J. (1987b) Invariance principles for renewal processes. Ann. Prob. 15, 1441–1460.CrossRefGoogle Scholar
Einmahl, U. (1989) Extensions of results of Komlós, Major, and Tusnády to the multivariate case. J. Multivariate Anal. 28, 20–68.CrossRefGoogle Scholar
Ethier, S. N. and Kurtz, T. G. (1986) Markov Processes: Characterization and Convergence . Wiley, New York.CrossRefGoogle Scholar
Feller, W. (1971) An Introduction to Probability Theory and its Applications , Vol. II, 2nd edn. Wiley, New York.Google Scholar
Glynn, P. W. (1982) On the Markov property of the GI/G/∞ Gaussian limit. Adv. Appl. Prob. 14, 191–194.CrossRefGoogle Scholar
Glynn, P. W. and Whitt, W. (1988) Ordinary CLT and WLLN versions of L = ?W. Math. Operat. Res. 13, 674–692.CrossRefGoogle Scholar
Harrison, J. M. and Lemoine, A. J. (1981) A note on networks of infinite-server queues. J. Appl. Prob. 18, 561–567.CrossRefGoogle Scholar
Iglehart, D. L. (1965) Limit diffusion approximations for the many server queue and the repairman problem. J. Appl. Prob. 2, 429–441.CrossRefGoogle Scholar
Iglehart, D. L. and Whitt, W. (1971) The equivalence of functional central limit theorems for counting processes and associated partial sums. Ann. Math. Statist. 42, 1372–1378.CrossRefGoogle Scholar
Newell, G. F. (1973) Approximate Stochastic Behavior of n-Server Service Systems with Large n. Lecture Notes in Economics and Mathematical Systems 87, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Pomarede, J.-M. L. (1976) A Unified Approach Via Graphs to Skorohod's Topologies on the Function Space D. Ph.D. dissertation, Department of Statistics, Yale University.Google Scholar
Reiman, M. I. (1984) Open queueing networks in heavy traffic. Math. Operat. Res. 9, 441–458.CrossRefGoogle Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
Skorohod, A. V. (1956) Limit theorems for stochastic processes. Theor. Probability Appl. 1, 261–290.CrossRefGoogle Scholar
Vervaat, W. (1972) Functional central limit theorems for processes with positive drift and their inverses. Z. Wahrscheinlichkeitsth. 23, 245–253.CrossRefGoogle Scholar
Whitt, W. (1974) The continuity of queues. Adv. Appl. Prob. 6, 175–183.CrossRefGoogle Scholar
Whitt, W. (1980) Some useful functions for functional limit theorems. Math. Operat Res. 5, 67–85.CrossRefGoogle Scholar
Whitt, W. (1982) On the heavy-traffic limit theorem for GI/G/∞ queues. Adv. Appl. Prob. 14, 171–190.CrossRefGoogle Scholar
Whitt, W. (1984) Departures from a queue with many busy servers. Math. Operat. Res. 9, 534–544.CrossRefGoogle Scholar