Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-06T10:00:20.483Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite-pool queueing with heavy-tailed services

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

Published online by Cambridge University Press:  15 September 2017

Gianmarco Bet ,
Remco van der Hofstad  and
Johan S. H. van Leeuwaarden
Gianmarco Bet*
Affiliation:
Eindhoven University of Technology
Remco van der Hofstad*
Affiliation:
Eindhoven University of Technology
Johan S. H. van Leeuwaarden*
Affiliation:
Eindhoven University of Technology
*
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands.
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands.
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands.
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.

We consider the Δ(i)/G/1 queue, in which a total of n customers join a single-server queue for service. Customers join the queue independently after exponential times. We consider heavy-tailed service-time distributions with tails decaying as x-α, α ∈ (1, 2). We consider the asymptotic regime in which the population size grows to ∞ and establish that the scaled queue-length process converges to an α-stable process with a negative quadratic drift. We leverage this asymptotic result to characterize the head start that is needed to create a long period of uninterrupted activity (a busy period). The heavy-tailed service times should be contrasted with the case of light-tailed service times, for which a similar scaling limit arises (Bet et al. (2015)), but then with a Brownian motion instead of an α-stable process.

Keywords

Heavy-traffic approximationheavy-tailed distributionfunctional central limit theoremSkorokhod reflection map

MSC classification

Primary: 60K25: Queueing theory
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. 921 - 942
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Aïdékon, E., van der Hofstad, R., Kliem, S. and van Leeuwaarden, J. S. H. (2016). Large deviations for power-law thinned Lévy processes. Stoch. Process. Appl. 126, 1353–1384. CrossRefGoogle Scholar
[2] Aldous, D. (1997). Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Prob. 25, 812–854. CrossRefGoogle Scholar
[3] Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York. Google Scholar
[4] 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.5329v2. Google Scholar
[5] Bet, G., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2017). Big jobs arrive early: from critical queues to random graphs. Preprint. Available at https://arxiv.org/abs/1704.03406. Google Scholar
[6] Bhamidi, S., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2012). Novel scaling limits for critical inhomogeneous random graphs. Ann. Prob. 40, 2299–2361. CrossRefGoogle Scholar
[7] Billingsley, P. (1999). Convergence of Probability Measures, 2nd edn. John Wiley, New York. CrossRefGoogle Scholar
[8] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Cambridge University Press. CrossRefGoogle Scholar
[9] Boxma, O. J. and Cohen, J. W. (1998). The M/G/1 queue with heavy-tailed service time distribution. IEEE J. Selected Areas Commun. 16, 749–763. CrossRefGoogle Scholar
[10] David, H. A. and Nagaraja, H. N. (2003). Order Statistics, 3rd edn. John Wiley, Hoboken, NJ. CrossRefGoogle Scholar
[11] Dhara, S., van der Hofstad, R., van Leeuwaarden, J. S. H. and Sen, S. (2016). Heavy-tailed configuration models at criticality. Preprint. Available at https://arxiv.org/abs/1612.00650. Google Scholar
[12] Dhara, S., van der Hofstad, R., van Leeuwaarden, J. S. H. and Sen, S. (2017). Critical window for the configuration model: finite third moment degrees. Electron. J. Prob. 22, 16. CrossRefGoogle Scholar
[13] Groeneboom, P. (1989). Brownian motion with a parabolic drift and Airy functions. Prob. Theory Relat. Fields 81, 79–109. CrossRefGoogle Scholar
[14] Groeneboom, P. (2010). The maximum of Brownian motion minus a parabola. Electron. J. Prob. 15, 1930–1937. CrossRefGoogle Scholar
[15] Honnappa, H., Jain, R. and Ward, A. R. (2014). On transitory queueing. Preprint. 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. CrossRefGoogle Scholar
[17] Iglehart, D. L. and Whitt, W. (1970). Multiple channel queues in heavy traffic. I. Adv. Appl. Prob. 2, 150–177. CrossRefGoogle Scholar
[18] 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
[19] Jacod, J. and Shiryaev, A. N. (2003). Limit Theorems for Stochastic Processes, 2nd edn. Springer, Berlin. CrossRefGoogle Scholar
[20] Janson, S., Louchard, G. and Martin-Löf, A. (2010). The maximum of Brownian motion with parabolic drift. Electron. J. Prob. 15, 1893–1929. CrossRefGoogle Scholar
[21] Joseph, A. (2014). The component sizes of a critical random graph with given degree sequence. Ann. Appl. Prob. 24, 2560–2594. CrossRefGoogle Scholar
[22] Klenke, A. (2008). Probability Theory: A Comprehensive Course. Springer, London. CrossRefGoogle Scholar
[23] Louchard, G. (1994). Large finite population queueing systems. The single-server model. Stoch. Process. Appl. 53, 117–145. CrossRefGoogle Scholar
[24] Mandelbaum, A. and Massey, W. A. (1995). Strong approximations for time-dependent queues. Math. Operat. Res. 20, 33–64. CrossRefGoogle Scholar
[25] Massey, W. A. (1981). Non-stationary queues. Doctoral thesis. Stanford University. Google Scholar
[26] Massey, W. A. (1985). Asymptotic analysis of the time dependent M/M/1 queue. Math. Operat. Res. 10, 305–327. CrossRefGoogle Scholar
[27] Newell, G. F. (1968). Queues with time-dependent arrival rates. III. A mild rush hour. J. Appl. Prob. 5, 591–606. CrossRefGoogle Scholar
[28] Pittel, B. (2001). On the largest component of the random graph at a nearcritical stage. J. Combinatorial Theory B 82, 237–269. CrossRefGoogle Scholar
[29] Roberts, M. I. (2016). The probability of unusually large components in the near-critical Erdős-Rényi graph. Preprint. Available at https://arxiv.org/abs/1610.05485. Google Scholar
[30] Roberts, M. I. and Sengul, B. (2017). Exceptional times of the critical dynamical Erdős-Rényi graph. Preprint. Available at https://arxiv.org/abs/1610.06000. Google Scholar
[31] Samorodnitsky, G. and Taqqu, M. S. (1994). Stable Non-Gaussian Random Processes. Chapman & Hall, New York. Google Scholar
[32] Sato, K.-I. (1999). Lévy Processes and Infinitely Divisible Distributions. Cambridge University Press. Google Scholar
[33] Simon, T. (2011). Hitting densities for spectrally positive stable processes. Stochastics 83, 203–214. CrossRefGoogle Scholar
[34] Skorokhod, A. V. (1956). Limit theorems for stochastic processes. Theory Prob. Appli. 1, 261–290. CrossRefGoogle Scholar
[35] Van der Hofstad, R., Janssen, A. J. E. M. and van Leeuwaarden, J. S. H. (2010). Critical epidemics, random graphs, and Brownian motion with a parabolic drift. Adv. Appl. Prob. 42, 1187–1206. CrossRefGoogle Scholar
[36] Van der Hofstad, R., Kliem, S. and van Leeuwaarden, J. S. H. (2014). Cluster tails for critical power-law inhomogeneous random graphs. Preprint. Available at https://arxiv.org/abs/1404.1727. Google Scholar
[37] Van der Hofstad, R., van Leeuwaarden, J. S. H. and Stegehuis, C. (2016). Mesoscopic scales in hierarchical configuration models. Preprint. Available at https://arxiv.org/abs/1612.02668. Google Scholar
[38] Whitt, W. (2002). Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, New York. CrossRefGoogle Scholar
[39] Whitt, W. (2016). Heavy-traffic limits for a single-server queue leading up to a critical point. Operat. Res. Lett. 44, 796–800. CrossRefGoogle Scholar
[40] Whitt, W. and You, W. (2017). Time-varying robust queueing. Submitted. Google Scholar