Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-28T04:11:08.028Z Has data issue: false hasContentIssue false
  • English
  • Français

Transient Asymptotics of Lévy-Driven Queues

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Krzysztof Dębicki ,
Abdelghafour Es-Saghouani  and
Michel Mandjes
Krzysztof Dębicki*
Affiliation:
University of Wrocław
Abdelghafour Es-Saghouani*
Affiliation:
University of Amsterdam
Michel Mandjes*
Affiliation:
University of Amsterdam, CWI, and EURANDOM
*
∗Postal address: Mathematical Institute, University of Wrocław, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland. Email address: [email protected]
∗∗Postal address: Korteweg-de Vries Institute for Mathematics, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands. Email address: [email protected]
∗∗∗Postal address: CWI, PO Box 94079, 1090 GB Amsterdam, The Netherlands. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

With (Qt)t denoting the stationary workload process in a queue fed by a Lévy input process (Xt)t, this paper focuses on the asymptotics of rare event probabilities of the type P(Q0 > pB, QTB > qB) for given positive numbers p and q, and a positive deterministic function TB. We first identify conditions under which the probability of interest is dominated by the ‘most demanding event’, in the sense that it is asymptotically equivalent to P(Q > max{p, q}B) for large B, where Q denotes the steady-state workload. These conditions essentially reduce to TB being sublinear (i.e. TB/B → 0 as B → ∞). A second condition is derived under which the probability of interest essentially ‘decouples’, in that it is asymptotically equivalent to P(Q > pB)P(Q > qB) for large B. For various models considered in the literature, this ‘decoupling condition’ reduces to requiring that TB is superlinear (i.e. TB / B → ∞ as B → ∞). This is not true for certain ‘heavy-tailed’ cases, for instance, the situations in which the Lévy input process corresponds to an α-stable process, or to a compound Poisson process with regularly varying job sizes, in which the ‘decoupling condition’ reduces to TB / B2 → ∞. For these input processes, we also establish the asymptotics of the probability under consideration for TB increasing superlinearly but subquadratically. We pay special attention to the case TB = RB for some R > 0; for light-tailed input, we derive intuitively appealing asymptotics, intensively relying on sample path large deviations results. The regimes obtained can be interpreted in terms of the most likely paths to overflow.

Keywords

Queuestransient analysisLévy processlarge deviations

MSC classification

Secondary: 60K25: Queueing theory
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 1 , March 2010 , pp. 109 - 129
Copyright
Copyright © Applied Probability Trust 2010 

Footnotes

Supported by MNiSW grant number N N2014079 33 (2007-2009) and by a Marie Curie Transfer of Knowledge Fellowship of the European Community-s Sixth Framework Programme under contract MTKD-CT-2004-013389.

Part of this work was done at Stanford University.

References

[1] Asmussen, S. (1998). Subexponential asymptotics for stochastic processes: extremal behavior, stationary distributions and first passage probabilities. Ann. Appl. Prob. 8, 354–374.CrossRefGoogle Scholar
[2] Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
[3] Bertoin, J. and Doney, R. A. (1994). Cramér's estimate for Lévy processes. Statist. Prob. Lett. 21, 363–365.CrossRefGoogle Scholar
[4] Bingham, N. H. (1975). Fluctuation theory in continuous time. Adv. Appl. Prob. 7, 705–766.CrossRefGoogle Scholar
[5] Borovkov, A. A. (1976). Stochastic Processes in Queueing Theory. Springer, New York.CrossRefGoogle Scholar
[6] Cohen, J. W. (1973). Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Prob. 10, 343–353.CrossRefGoogle Scholar
[7] De Acosta, A. (1994). Large deviations for vector-valued Lévy processes. Stoch. Process. Appl. 51, 75–115.CrossRefGoogle Scholar
[8] Debicki, K., Es-Saghouani, A. and Mandjes, M. (2009). Transient characteristics of Gaussian queues. Queueing Systems 62, 383–409.CrossRefGoogle Scholar
[9] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd edn. Springer, New York.CrossRefGoogle Scholar
[10] Es-Saghouani, A. and Mandjes, M. (2008). On the correlation structure of a Lévy-driven queue. J. Appl. Prob. 45, 940–952.CrossRefGoogle Scholar
[11] Glynn, P. and Whitt, W. (1994). Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. In Studies in Applied Probability (J. Appl. Prob. Spec. Vol. 31A), Applied Probability Trust, Sheffield, pp. 131–156.Google Scholar
[12] Kella, O., Boxma, O. and Mandjes, M. (2006). A Lévy process reflected at a Poisson age process. J. Appl. Prob. 43, 221–230.CrossRefGoogle Scholar
[13] Klüppelberg, C., Kyprianou, A. E. and Maller, R. A. (2004). Ruin probabilities and overshoots for general Lévy insurance risk processes. Ann. Appl. Prob. 14, 1766–1801.CrossRefGoogle Scholar
[14] Kyprianou, A. (2006). Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin.Google Scholar
[15] Mandjes, M. and Ridder, A. (2002). A large deviations analysis of the transient of a queue with many Markov fluid inputs: approximations and fast simulation. ACM Trans. Model Comput. Simul. 12, 1–26.CrossRefGoogle Scholar
[16] Mikosch, T., Resnick, S., Rootzén, H. and Stegeman, A. (2002). Is network traffic approximated by stable Lévy motion or fractional Brownian motion? Ann. Appl. Prob. 12, 23–68.CrossRefGoogle Scholar
[17] Port, S. C. (1989). Stable processes with drift on the line. Trans. Amer. Math. Soc. 313, 805–841.CrossRefGoogle Scholar
[18] Samorodnitsky, G. and Taqqu, M. (1994). Stable Non-Gaussian Random Processes. Chapman and Hall, London.Google Scholar
[19] Shwartz, A. and Weiss, A. (1995). Large Deviations for Performance Analysis. Chapman and Hall, London.Google Scholar
[20] Zolotarev, V. M. (1964). The first-passage time of a level and the behavior at infinity for a class of processes with independent increments. Theory Prob. Appl. 9, 653–662.CrossRefGoogle Scholar