Hostname: page-component-6bf8c574d5-956mj Total loading time: 0 Render date: 2025-02-17T14:59:20.739Z Has data issue: false hasContentIssue false
  • English
  • Français

Logarithmic asymptotics for steady-state tail probabilities in a single-server queue

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Peter W. Glynn  and
Ward Whitt
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the standard single-server queue with unlimited waiting space and the first-in first-out service discipline, but without any explicit independence conditions on the interarrival and service times. We find conditions for the steady-state waiting-time distribution to have asymptotics of the form x–1 log P(W> x) → –θ ∗as x → ∞for θ ∗ > 0. We require only stationarity of the basic sequence of service times minus interarrival times and a Gärtner–Ellis condition for the cumulant generating function of the associated partial sums, i.e. n–1 log E exp (θSn) → ψ (θ) as n → ∞, plus regularity conditions on the decay rate function ψ. The asymptotic decay rate θ is the root of the equation ψ (θ) = 0. This result in turn implies a corresponding asymptotic result for the steady-state workload in a queue with general non-decreasing input. This asymptotic result covers the case of multiple independent sources, so that it provides additional theoretical support for a concept of effective bandwidths for admission control in multiclass queues based on asymptotic decay rates.

Keywords

WAITING TIMEWORKLOADTAIL PROBABILITIESASYMPTOTICSLARGE DEVIATIONSCUMULANT GENERATING FUNCTIONCOUNTING PROCESSEFFECTIVE BANDWIDTHSADMISSION CONTROLHIGH-SPEED NETWORKSASYNCHRONOUS TRANSFER MODE

MSC classification

Primary: 60K25: Queueing theory
Type
Part 3 Queueing Theory
Information
Journal of Applied Probability , Volume 31 , Issue A , 1994 , pp. 131 - 156
Copyright
Copyright © Applied Probability Trust 1994 

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

References

Abate, J. and Whitt, W. (1994) A heavy-traffic expansion for asymptotic decay rates of tail probabilities in multi-channel queues. Operat. Res. Lett. To appear.CrossRefGoogle Scholar
Abate, J., Choudhury, G. L. and Whitt, W. (1994a) Exponential approximations for tail probabilities of queues, I: waiting times. Operat. Res. To appear.CrossRefGoogle Scholar
Abate, J., Choudhury, G. L. and Whitt, W. (1994b) Exponential approximations for tail probabilities of queues, II: sojourn time and workload. Operat. Res. To appear.Google Scholar
Abate, J., Choudhury, G. L. and Whitt, W. (1994C) Asymptotics for steady-state tail probabilities in structured Markov queueing models. Stoch. Models 10. To appear.Google Scholar
Abate, J., Choudhury, G. L. and Whitt, W. (1993) Calculation of the GI/G/1 waiting-time distribution and its cumulants from Pollaczek's formulas. AEü 47, 311–321.Google Scholar
Addie, R. G. and Zuckerman, M. (1993) An approximation for performance evaluation of stationary single server queues. IEEE Trans. Commun. , to appear.Google Scholar
Asmussen, S. (1987) Applied Probability and Queues . Wiley, New York.Google Scholar
Asmussen, S. (1989) Risk theory in a Markovian environment. Scand. Actuarial J. 69–100.Google Scholar
Asmussen, S. (1993) Fundamentals of Ruin Probability Theory. Preliminary draft, Aalborg University, Denmark.Google Scholar
Asmussen, S. and Perry, D. (1992) On cycle maxima, first passage problems and extreme value theory for queues. Stoch. Models 8, 421–458.Google Scholar
Borovkov, A. A. (1976) Stochastic Processes in Queueing Theory. Springer-Verlag, New York.CrossRefGoogle Scholar
Bucklew, J. A. (1990) Large Deviations Techniques in Decision, Simulation and Estimation. Wiley, New York.Google Scholar
Chang, C.-S. (1992) Stability, queue length and delay, part II: stochastic queueing networks. Proc. 31st IEEE Conf. Decision and Control , Tucson, AZ, 1005–1010.Google Scholar
Chang, C.-S. (1993) Stability, queue length and delay of deterministic and stochastic queueing networks. IBM T. J. Watson Research Center, Yorktown Heights, NY.Google Scholar
Chang, C.-S., Heidelberger, P., Juneja, S. and Shahabuddin, P. (1992) Effective bandwidth and fast simulation of ATM intree networks. IBM T. J. Watson Research Center, Yorktown Heights, NY.Google Scholar
Choudhury, G. L. and Whitt, W. (1994) Heavy-traffic asymptotic expansions for the asymptotic decay rates in the BMAP/G/1 queue. Stoch. Models. To appear.CrossRefGoogle Scholar
Choudhury, G. L., Lucantoni, D. M. and Whitt, W. (1993) Squeezing the most out of ATM. Submitted.Google Scholar
Choudhury, G. L., Lucantoni, D. M. and Whitt, W. (1994) On the effectiveness of effective bandwidths for admission control in ATM networks. Proc. 14th Internat. Teletraffic Congr. , Antibes, France. To appear.CrossRefGoogle Scholar
Chung, K. L. (1974) A Course in Probability Theory , 2nd edn. Academic Press, New York.Google Scholar
Dembo, A. and Zeitouni, O. (1992) Large Deviations Techniques and Applications. A. K. Peters, Wellesley, MA.Google Scholar
Ellis, R. (1984) Large deviations for a general class of random vectors. Ann. Prob. 12, 1–12.CrossRefGoogle Scholar
Elwalid, A. I. and Mitra, D. (1993) Effective bandwidth of general Markovian traffic sources and admission control of high speed networks. IEEE/ACM Trans. Networking 1, 329–343.CrossRefGoogle Scholar
Elwalid, A. I. and Mitra, D. (1994) Markovian arrival and service communication systems: spectral expansions, separability and Kronecker-product forms. AT&T Bell Laboratories, Murray Hill, NJ.Google Scholar
Feller, W. (1971) An Introduction to Probability Theory and its Applications , Vol. II, 2nd edn. Wiley, New York.Google Scholar
Franken, P., König, D., Arndt, U. and Schmidt, V. (1981) Queues and Point Processes. Akademie-Verlag, Berlin.Google Scholar
Gärtner, J. (1977) On large deviations from the invariant measure. Theory Prob. Appl. 22, 24–39.Google Scholar
Gibbens, R. J. and Hunt, P. J. (1991) Effective bandwidths for the multi-type UAS channel. QUESTA 9, 17–28.Google Scholar
Glynn, P. W. and Whitt, W. (1988a) Ordinary CLT and WLLN versions of L = λW. Math. Operat. Res. 13, 674–692.CrossRefGoogle Scholar
Glynn, P. W. and Whitt, W. (1988b) An LIL version of L = λW. Math. Operat. Res. 13, 693–710.Google Scholar
Glynn, P. W. and Whitt, W. (1994) Large deviations behavior of counting processes and their inverses. QUESTA. To appear.Google Scholar
Guerin, R., Ahmadi, H. and Naghshineh, M. (1991) Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE J. Sel. Areas Commun. 9, 968–981.CrossRefGoogle Scholar
Iglehart, D. L. and Whitt, W. (1970) Multiple channel queues in heavy-traffic, II: sequences, networks and batches. Adv. Appl. Prob. 2, 355–369.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.Google Scholar
Keilson, J. (1965) Greens' Function Methods in Probability Theory. Griffin, London.Google Scholar
Kelly, F. P. (1991) Effective bandwidths at multi-class queues. QUESTA 9, 5–16.Google Scholar
Kingman, J. F. C. (1962) On queues in heavy traffic. J. R. Statist. Soc. B24, 383–392.Google Scholar
Neuts, M. F. (1986) The caudal characteristic curve of queues. Adv. Appl. Prob. 18, 221–254.CrossRefGoogle Scholar
Shwartz, A. and Weiss, A. (1993) Large Deviations for Performance Analysis: Queues, Communication and Computing. In preparation.Google Scholar
Smith, W. L. (1953) On the distribution of queueing times. Proc. Camb. Phil. Soc. 49, 449–461.CrossRefGoogle Scholar
Sohraby, K. (1993) On the theory of general on-off sources with applications in high speed networks. Proc. INFOCOM '93 , San Francisco. pp. 401–410.Google Scholar
Stern, T. E. and Elwalid, A. I. (1991) Analysis of a separable Markov-modulated rate model for information-handling systems. Adv. Appl. Prob. 23, 105–139.CrossRefGoogle Scholar
Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
Takács, L. (1963) The limiting distribution of the virtual waiting time and the queue size for a single server queue with recurrent input and general service times. Sankhya A25, 91–100.Google Scholar
Takács, L. (1967) Combinatorial Methods in the Theory of Stochastic Processes. Wiley, New York.Google Scholar
Tijms, H. C. (1986) Stochastic Modeling and Analysis: A Computational Approach. Wiley, New York.Google Scholar
Van Ommeren, J. C. W. (1988) Exponential expansion for the tail of the waiting-time probability in the single-server queue with batch arrivals. Adv. Appl. Prob. 20, 880–895.Google Scholar
Whitt, W. (1980) Some useful functions for functional limit theorems. Math. Operat. Res. 5, 67–85.Google Scholar
Whitt, W. (1981) Comparing counting processes and queues. Adv. Appl. Prob. 13, 207–220.Google Scholar
Whitt, W. (1994) Tail probabilities with statistical multiplexing and effective bandwidths for multi-class queues. Telecommunication Systems , to appear.CrossRefGoogle Scholar

References added in proof

Sadowsky, J. S. (1995) The probability of large queue lengths and waiting times in a heterogeneous multiserver queue, part II: positive recurrence and logarithmic limits. Adv. Appl. Prob. 27(2). To appear.Google Scholar
Sadowsky, J. S. and Szpankowski, W. (1995) The probability of large queue lengths and waiting times in a heterogeneous multiserver queue, part I: tight limits. Adv. Appl. Prob. 27(2). To appear.Google Scholar