Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T04:22:05.867Z Has data issue: false hasContentIssue false
  • English
  • Français

Tail asymptotics for processor-sharing queues

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

Published online by Cambridge University Press:  01 July 2016

Fabrice Guillemin ,
Philippe Robert  and
Bert Zwart
Fabrice Guillemin*
Affiliation:
France Télécom
Philippe Robert*
Affiliation:
INRIA-Rocquencourt
Bert Zwart*
Affiliation:
Eindhoven University of Technology
*
∗ Postal address: France Télécom R&D, 2, Avenue Pierre Marzin, 22300 Lannion, France. Email address: fabrice.guillemin@rd.francetelecom.fr
∗∗ Postal address: INRIA-Rocquencourt, RAP project, Domaine de Voluceau, 78153 Le Chesnay, France. Email address: philippe.robert@inria.fr
∗∗∗ Postal address: Eindhoven University of Technology, Department of Mathematics and Computer Science, HG 9.35, PO Box 513, 5600 MB Eindhoven, The Netherlands. Email address: zwart@win.tue.nl
Get access Rights & Permissions [Opens in a new window]

Abstract

The basic queueing system considered in this paper is the M/G/1 processor-sharing queue with or without impatience and with finite or infinite capacity. Under some mild assumptions, a criterion for the validity of the reduced-service-rate approximation is established when service times are heavy tailed. This result is applied to various models based on M/G/1 processor-sharing queues.

Keywords

Heavy tailprocessor sharingreduced-load approximation

MSC classification

Primary: 60K25: Queueing theory 68M10: Network design and communication
Secondary: 90B22: Queues and service

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 36 , Issue 2 , June 2004 , pp. 525 - 543
Copyright
Copyright © Applied Probability Trust 2004 

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.)

Article purchase

Temporarily unavailable

References

[1] Asmussen, S. (1987). Applied Probability and Queues. John Wiley, Chichester.Google Scholar
[2] Asmussen, S., Klüppelberg, C. and Sigman, K. (1999). Sampling at subexponential times, with queueing applications. Stoch. Process. Appl. 79, 265–286.Google Scholar
[3] Bonald, T. and Proutière, A. (2002). Insensitivity in processor-sharing networks. Performance Evaluation 49, 193–209.CrossRefGoogle Scholar
[4] Boyer, J., Guillemin, F., Robert, P. and Zwart, B. (2003). Heavy tailed M/G/1-PS queues with impatience and admission control in packet networks. In Proc. IEEE Infocomm 2003 (San Francisco, CA, March–April 2003), pp. 186–195.Google Scholar
[5] Burman, D. Y. (1981). Insensitivity in queueing systems. Adv. Appl. Prob. 13, 846–859.Google Scholar
[6] Clark, D., Shenker, S. and Zhang, L. (1992). Supporting real time applications in an integrated services packet network: architecture and mechanism. In Proc. Sigcomm'92 (Baltimore, MD, August 1992), ACM, New York, pp. 14–26.Google Scholar
[7] Cline, D. B. H. (1994). Intermediate regular and Π variation. Proc. London Math. Soc. 68, 594–616.CrossRefGoogle Scholar
[8] Coffman, E., Puhalskii, A. A., Reiman, M. I. and Wright, P. E. (1994). Processor shared queues with reneging. Performance Evaluation 19, 25–46.Google Scholar
[9] Cohen, J. W. (1979). The multiple phase service network with generalized processor sharing. Acta Informatica 12, 245–284.Google Scholar
[10] Daley, D. J. (2001). The busy period of the M/GI/∞ queue. Queueing Systems 38, 195–204.Google Scholar
[11] Foss, S. and Korshunov, D. (2000). Sampling at a random time with a heavy-tailed distribution. Markov Process. Relat. Fields 6, 543–568.Google Scholar
[12] Jelenković, P. and Momcilović, P. (2003). Large deviation analysis of subexponential waiting time in a processor sharing queue. Math. Operat. Res. 28, 587–608.Google Scholar
[13] Jelenković, P., Momcilović, P. and Zwart, A. P. (2001). Reduced-load equivalence and subexponentiality. Submitted.Google Scholar
[14] Kelly, F. P. (1976). Networks of queues. Adv. Appl. Prob. 8, 416–432.Google Scholar
[15] Kleinrock, L. (1976). Queueing Systems. John Wiley, New York.Google Scholar
[16] Núñez-Queija, R. (2000). Processor sharing models for integrated services networks. Doctoral Thesis, Eindhoven University of Technology.Google Scholar
[17] Resnick, S. and Samorodnitsky, G. (1999). Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues. Queueing Systems 33, 43–71.Google Scholar
[18] Van den Berg, J. L. and Boxma, O. J. (1991). The M/G/1 queue with processor sharing and its relation to a feedback queue. Queueing Systems 9, 365–401.Google Scholar
[19] Zwart, A. P. (2001). Tail asymptotics for the busy period in the GI/G/1 queue. Math. Operat. Res. 26, 485–493.Google Scholar
[20] Zwart, A. P. and Boxma, O. J. (2000). Sojourn time asymptotics in the M/G/1 processor sharing queue. Queueing Systems 35, 141–166.Google Scholar