Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-01-11T10:58:45.644Z Has data issue: false hasContentIssue false
  • English
  • Français

Large deviations and overflow probabilities for the general single-server queue, with applications

Published online by Cambridge University Press:  24 October 2008

N. G. Duffield  and
Neil O'connell
N. G. Duffield
Affiliation:
School of Mathematical Sciences, Dublin City University, Dublin 9, Ireland. e-mail: [email protected]
Neil O'connell
Affiliation:
Dublin Institute for Advanced Studies, 10 Burlington Road, Dublin 4, Ireland. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider queueing systems where the workload process is assumed to have an associated large deviation principle with arbitrary scaling: there exist increasing scaling functions (at, vt, t∈R+) and a rate function I such that if (Wt, t∈R+) denotes the workload process, then

on the continuity set of I. In the case that at = vt = t it has been argued heuristically, and recently proved in a fairly general context (for discrete time models) by Glynn and Whitt[8], that the queue-length distribution (that is, the distribution of supremum of the workload process Q = supt≥0Wt) decays exponentially:

and the decay rate δ is directly related to the rate function I. We establish conditions for a more general result to hold, where the scaling functions are not necessarily linear in t: we find that the queue-length distribution has an exponential tail only if limt→∞at/vt is finite and strictly positive; otherwise, provided our conditions are satisfied, the tail probabilities decay like

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 118 , Issue 2 , September 1995 , pp. 363 - 374
Copyright
Copyright © Cambridge Philosophical Society 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

REFERENCES

[1]Milton, Abramowitz and Stegun, Irene A. (eds.) Handbook of mathematical functions (Dover, 1965).Google Scholar
[2]David, Aldous. Probability approximations via the Poisson clumping heuristic (Springer-Verlag, 1989).Google Scholar
[3]Borovkov, A. A.. Asymptotic methods in queueing theory. (Wiley, 1984).Google Scholar
[4]Cheng-Shang, Chang. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Trans. on Automatic Control 39 (1994), 913–931.Google Scholar
[5]Kulkarni, V. and Rolski, T.. Fluid model driven by an Ornstein-Uhlenbeck process (preprint).Google Scholar
[6]Amir, Dembo and Ofer, Zeitoüni. Large deviation techniques and applications (Jones and Bartlett, 1993).Google Scholar
[7]Duffield, N. G.. Exponential bounds for queues with Markovian arrivals. Queueing Systems 17 (1994), 413–430CrossRefGoogle Scholar
[8]Glynn, Peter W. and Ward, Whitt. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. J. Appl. Prob. 31A (1994), 131–159CrossRefGoogle Scholar
[9]Kesidis, G., Walrand, J. and Chang, C. S.. Effective bandwidths for multiclass Markov fluids and other ATM Sources. IEEE/ACH Trans. Networking 1 (1993), 424–428.CrossRefGoogle Scholar
[10]Leland, Will E., Taqqu, Murad S., Walter, Willinger and Wilson, Daniel V.. On the self-similar nature of Ethernet traffic. ACM SIOCOMM Computer Communications Review 23 (1993), 183–193.CrossRefGoogle Scholar
[11]Lewis, J. T. and Pfister, C. E.. Thermodynamic probability theory: some aspects of large deviations. Theor. Prob. Appl, (to appear).Google Scholar
[12]Torgny, Lindvall. Lectures on the coupling method (Wiley, 1992).Google Scholar
[13]Mandelbrot, Benoit B. and Van Ness, John W.. Fractional Brownian motions, fractional noises and applications. SIAM Review 10 (1968), 422–437.Google Scholar
[14]Marcus, M. B. and Shepp, L. A.. Sample behaviour of Gaussian processes. Proceedings of the Sixth Berkeley Symposium (1972).Google Scholar
[15]Ilkka, Norros. Studies on a model for connectionless traffic, based on fractional Brownian motion. Conference on Applied Probability in Engineering, Computer and communication sciences INRIA/ORSA/TIMS/SMAI, Paris 1993.Google Scholar
[16]Ilkka, Norros. A storage model with self-similar input. Queueing Systems 16 (1994), 387–396.Google Scholar
[17]Norros, I., Roberts, J. W., Simonain, A. and Virtamo, J.. The superposition of variable bitrate sources in ATM multiplexers. IEEE J. Selected Areas in Commun. 9 (1991), 378–387.CrossRefGoogle Scholar
[18]Jim, Pitman and Marc, Yor. A decomposition of Bessel bridges. Z. Wahr. verw. Gebeit 59 (1982), 425–457.Google Scholar