Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T14:24:29.615Z Has data issue: false hasContentIssue false
  • English
  • Français

Rare events of transitory queues

Part of: Computer system organization Operations research and management science Limit theorems Special processes

Published online by Cambridge University Press:  15 September 2017

Harsha Honnappa
Harsha Honnappa*
Affiliation:
Purdue University
*
* Postal address: School of Industrial Engineering, Purdue University, 315 N. Grant St., West Lafayette, IN 47906, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the rare-event behavior of the workload process in a transitory queue, where the arrival epochs (or 'points') of a finite number of jobs are assumed to be the ordered statistics of independent and identically distributed (i.i.d.) random variables. The service times (or 'marks') of the jobs are assumed to be i.i.d. random variables with a general distribution, that are jointly independent of the arrival epochs. Under the assumption that the service times are strictly positive, we derive the large deviations principle (LDP) satisfied by the workload process. The analysis leverages the connection between ordered statistics and self-normalized sums of exponential random variables to establish the LDP. In this paper we present the first analysis of rare events in transitory queueing models, supplementing prior work that has focused on fluid and diffusion approximations.

Keywords

Workloadempirical processexchangeable incrementslarge deviationpopulation accelerationtransitory queue

MSC classification

Primary: 60K25: Queueing theory 60F10: Large deviations
Secondary: 90B22: Queues and service 68M20: Performance evaluation; queueing; scheduling
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 3 , September 2017 , pp. 943 - 962
Copyright
Copyright © Applied Probability Trust 2017 

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] Aldous, D. J. (1985). Exchangeability and Related Topics. Springer, Berlin. Google Scholar
[2] Bet, G., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2015). Heavy-traffic analysis through uniform acceleration of queues with diminishing populations. Preprint. Available at https://arxiv.org/abs/1412.5329. Google Scholar
[3] Bet, G., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2016). Finite-pool queues with heavy-tailed services. Preprint. Available at https://arxiv.org/abs/1605.06264. Google Scholar
[4] Boistard, H. (2007). Large deviations for L-statistics. Statist. Decisions 25, 89–125. Google Scholar
[5] Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer, New York. Google Scholar
[6] David, H. A. and Nagaraja, H. N. (2003). Order Statistics, 3rd edn. John Wiley, Hoboken, NJ. Google Scholar
[7] Dembo, A. and Zeitouni, O. (2010). Large Deviations Techniques and Applications. Springer, Berlin. Google Scholar
[8] Dinwoodie, I. H. and Zabell, S. L. (1992). Large deviations for exchangeable random vectors. Ann. Prob. 20, 1147–1166. Google Scholar
[9] Duffy, K. R., Macci, C. and Torrisi, G. L. (2011). Sample path large deviations for order statistics. J. Appl. Prob. 48, 238–257. Google Scholar
[10] Durrett, R. (2010). Probability: Theory and Examples, 4th edn. Cambridge University Press. Google Scholar
[11] Ganesh, A., O'Connell, N. and Wischik, D. (2004). Big Queues. Springer, Berlin. Google Scholar
[12] Glynn, P. W. (2012). Perspectives on traffic modeling in networks. Stochastic Networks Conference, MIT. Google Scholar
[13] Glynn, P. W. (2014). Perspectives on traffic modeling. Markov Lecture, INFORMS Annual Meeting, San Francisco, CA. Google Scholar
[14] Glynn, P. W. and Honnappa, H. (2016). On Gaussian limits and large deviations for queues fed by high intensity randomly scattered traffic. Working paper. Google Scholar
[15] Honnappa, H., Jain, R. and Ward, A. R. (2016). On transitory queueing. Working paper. Available at https://arxiv.org/abs/1412.2321. Google Scholar
[16] Honnappa, H., Jain, R. and Ward, A. R. (2015). A queueing model with independent arrivals, and its fluid and diffusion limits. Queueing Systems 80, 71–103. Google Scholar
[17] Louchard, G. (1994). Large finite population queueing systems. The single-server model. Stoch. Process. Appl. 53, 117–145. Google Scholar
[18] Lynch, J. and Sethuraman, J. (1987). Large deviations for processes with independent increments. Ann. Prob. 15, 610–627. Google Scholar
[19] Puhalskii, A. (1995). Large deviation analysis of the single server queue. Queueing Systems Theory Appl. 21, 5–66. (Erratum: 23 (1996), 337.) Google Scholar
[20] Whitt, W. (2002). Stochastic-Process Limits. Springer, New York. Google Scholar