More Web Proxy on the site http://driver.im/

article

Sojourn time asymptotics in the M /G /1 processor sharing queue

Authors:

O. J. BoxmaAuthors Info & Claims

Queueing Systems: Theory and Applications, Volume 35, Issue 1/4

Pages 141 - 166

https://doi.org/10.1023/A:1019142010994

Published: 14 January 2000 Publication History

Abstract

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ý, ý non-integer, iff the sojourn time distribution is regularly varying of index -ý. This result is derived from a new expression for the Laplace-Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the k th moment of the sojourn time is finite iff the k th moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution.

References

[1]

{1} J. Abate, G.L. Choudhury and W. Whitt, Waiting-time tail probabilities in queues with longtail service-time distributions, Queueing Systems 16 (1994) 311-338.

[2]

{2} J. Abate, G.L. Choudhury and W. Whitt, Exponential approximations for tail probabilities in queues. I. Waiting times, Oper. Res. 43 (1995) 885-901.

Digital Library

[3]

{3} J. Abate and W. Whitt, Limits and approximations for the M/G/1 LIFO waiting-time distribution, Oper. Res. Lett. 20 (1997) 199-206.

Digital Library

[4]

{4} J. Abate and W. Whitt, Explicit M/G/1 waiting-time distributions for a class of long-tail service-time distributions, Oper. Res. Lett. 25 (1999) 25-31.

Digital Library

[5]

{5} M. Abramovitz and I.A. Stegun, Handbook of Mathematical Functions (Dover, New York, 1965).

Digital Library

[6]

{6} J. Beran, R. Sherman, M.S. Taqqu and W. Willinger, Long-range dependence in variable-bit-rate video, IEEE Trans. Commun. 43 (1995) 1566-1579.

[7]

{7} P. Billingsley, Probability and Measure , 3rd ed. (Wiley, New York, 1996).

[8]

{8} N.H. Bingham and R.A. Doney, Asymptotic properties of supercritical branching processes I: The Galton-Watson process, Adv. in Appl. Probab. 6 (1974) 711-731.

[9]

{9} N.H. Bingham and R.A. Doney, Asymptotic properties of supercritical branching processes II: Crump-Mode and Jirina processes, Adv. in Appl. Probab. 7 (1975) 66-82.

[10]

{10} N.H. Bingham, C.M. Goldie and J.L. Teugels, Regular Variation (Cambridge Univ. Press, Cambridge, 1987).

[11]

{11} O.J. Boxma and V. Dumas, The busy period in the fluid queue, Performance Evaluation Rev. 26 (1998) 100-110.

Digital Library

[12]

{12} O.J. Boxma and J.W. Cohen, The M/G/1 queue with heavy-tailed service time distribution, IEEE J. Selected Areas Commun. 16 (1998) 749-763.

Digital Library

[13]

{13} O.J. Boxma and J.W. Cohen, Heavy-traffic analysis for the GI/G/1 queue with heavy-tailed distributions, Queueing Systems 33 (1999) 177-204.

Digital Library

[14]

{14} L. Breiman, On some limit theorems similar to the arc-sin law, Theory Probab. Appl. 10 (1965) 323-331.

[15]

{15} E.G. Coffman, R.R. Muntz and H. Trotter, Waiting time distributions for processor-sharing systems, J. ACM 17 (1970) 123-130.

Digital Library

[16]

{16} J.W. Cohen, Some results on regular variation in queueing and fluctuation theory, J. Appl. Probab. 10 (1973) 343-353.

[17]

{17} J.W. Cohen, The multiple phase service network with generalized processor sharing, Acta Informatica 12 (1979) 245-284.

Digital Library

[18]

{18} J.W. Cohen, The Single Server Queue , 2nd ed. (North-Holland, Amsterdam, 1982).

[19]

{19} R.A. Davis and S.I. Resnick, Limit theory for bilinear processes with heavy-tailed noise, Ann. Appl. Probab. 6 (1996) 1191-1210.

[20]

{20} A. de Meyer, On a theorem of Bingham and Doney, J. Appl. Probab. 19 (1982) 217-220.

[21]

{21} A. de Meyer and J.L. Teugels, On the asymptotic behaviour of the distributions of the busy period and service time in M/G/1, J. Appl. Probab. 17 (1980) 802-813.

[22]

{22} P. Embrechts and C. Goldie, On closure and factorization properties of subexponential and related distributions, J. Austral. Math. Soc. A 29 (1980) 243-256.

[23]

{23} P. Embrechts, C. Klüppelberg and T. Mikosch, Modelling Extremal Events (Springer, Berlin, 1997).

Digital Library

[24]

{24} W. Feller, An Introduction to Probability Theory and its Applications , Vol. II, 2nd ed. (Wiley, New York, 1971).

[25]

{25} S. Grishechkin, On a relationship between processor-sharing queues and Crump-Mode-Jagers branching processes, Adv. in Appl. Probab. 24 (1992) 653-698.

[26]

{26} S. Grishechkin, GI/G/1 processor sharing queue in heavy traffic, Adv. in Appl. Probab. 26 (1994) 539-555.

[27]

{27} F.P. Kelly, Reversibility and Stochastic Networks (Wiley, New York, 1979).

[28]

{28} L. Kleinrock, Queueing Systems, Vol. II: Computer Applications (Wiley, New York, 1976).

[29]

{29} M. Loève, Probability Theory , 2nd ed. (New York, 1960).

[30]

{30} J.A. Morrison, Response-time distribution for a processor sharing system, SIAM J. Appl. Math. 45 (1985) 152-167.

[31]

{31} T.J. Ott, The sojourn-time distribution in the M/G/1 queue with processor sharing, J. Appl. Probab. 21 (1984) 360-378.

[32]

{32} V. Paxson and S. Floyd, Wide area traffic: The failure of Poisson modeling, IEEE/ACM Trans. Networking 3 (1995) 226-244.

Digital Library

[33]

{33} S. Resnick, Point processes, regular variation and weak convergence, Adv. in Appl. Probab. 18 (1986) 66-138.

[34]

{34} M. Sakata, S. Noguchi and J. Oizumi, Analysis of a processor shared queueing model for time sharing systems, in: Proc. of the 2nd Hawaii Internat. Conf. on System Sciences (1969) pp. 625- 628.

[35]

{35} R. Schassberger, A new approach to the M/G/1 processor sharing queue, Adv. in Appl. Probab. 16 (1984) 802-813.

[36]

{36} B. Sengupta, An approximation for the sojourn-time distribution for the GI/G/1 processor-sharing queue, Comm. Statist. Stochastic Models 8 (1992) 35-57.

[37]

{37} H.C. Tijms, Stochastic Models (Wiley, Chichester, 1994).

[38]

{38} J.L. van den Berg, Sojourn times in feedback and processor sharing queues, Ph.D. thesis, Utrecht (1990).

[39]

{39} W. Willinger, M.S. Taqqu, W.E. Leland and D.V. Wilson, Self-similarity in high-speed packet traffic: Analysis and modeling of ethernet traffic measurements, Statist. Sci. 10 (1995) 67-85.

[40]

{40} S.F. Yashkov, A derivation of response time distribution for a M/G/1 processor sharing queue, Problems Control Inform. Theory 12 (1983) 133-148.

[41]

{41} S.F. Yashkov, Processor-sharing queues: Some progress in analysis, Queueing Systems 2 (1987) 1-17.

Digital Library

[42]

{42} S.F. Yashkov, Mathematical problems in the theory of shared-processor systems, J. Soviet Math. 58 (1992) 101-147.

[43]

{43} S.F. Yashkov, On a heavy traffic limit theorem for the M/G/1 processor-sharing queue, Comm. Statist. Stochastic Models 9 (1993) 467-471.

[44]

{44} A.P. Zwart, Sojourn times in a multiclass processor sharing queue, in: Teletraffic Engineering in a Competitive World, Proc. of ITC 16 , Edinburgh, UK, eds. P. Key and D. Smith (North-Holland, Amsterdam, 1999) pp. 335-344.

Cited By

Yu GScully Z(2024)Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1Proceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560118:2(1-33)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656011
Raaijmakers YBorst SBoxma O(2022)Fork–join and redundancy systems with heavy-tailed job sizesQueueing Systems: Theory and Applications10.1007/s11134-022-09856-6103:1-2(131-159)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11134-022-09856-6
Scully Zvan Kreveld LBoxma ODorsman JWierman A(2020)Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job SizesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33921484:2(1-33)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3392148
Show More Cited By

Sojourn time asymptotics in the M /G /1 processor sharing queue
1. Theory of computation

Recommendations

Tail asymptotics for the queue length in an M/G/1 retrial queue

In this paper, we study the tail behavior of the stationary queue length of an M/G/1 retrial queue. We show that the subexponential tail of the stationary queue length of an M/G/1 retrial queue is determined by that of the corresponding M/G/1 queue, and ...
Sojourn time distribution in polling systems with processor-sharing policy

We consider a polling system with a single server and multiple queues where customers arrive at the queues according to independent Poisson processes. The server visits and serves the queues in a cyclic order. The service discipline at all queues is ...
Sojourn time distribution in a MAP/M/1 processor-sharing queue

This paper considers the sojourn time distribution in a processor-sharing queue with a Markovian arrival process and exponential service times. We show a recursive formula to compute the complementary distribution of the sojourn time in steady state. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Queueing Systems: Theory and Applications

Queueing Systems: Theory and Applications Volume 35, Issue 1/4

2000

388 pages

ISSN:0257-0130

Issue’s Table of Contents

Copyright © Copyright © 2000 Kluwer Academic Publishers.

Publisher

J. C. Baltzer AG, Science Publishers

United States

Publication History

Published: 14 January 2000

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yu GScully Z(2024)Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1Proceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560118:2(1-33)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656011
Raaijmakers YBorst SBoxma O(2022)Fork–join and redundancy systems with heavy-tailed job sizesQueueing Systems: Theory and Applications10.1007/s11134-022-09856-6103:1-2(131-159)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11134-022-09856-6
Scully Zvan Kreveld LBoxma ODorsman JWierman A(2020)Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job SizesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33921484:2(1-33)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3392148
Markakis MModiano ETsitsiklis J(2018)Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid ApproximationsMathematics of Operations Research10.1287/moor.2017.086743:2(460-493)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1287/moor.2017.0867
Al-Abbasi AAggarwal V(2018)Video Streaming in Distributed Erasure-Coded Storage SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2018.285137926:4(1921-1932)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2851379
(2014)Cost-per-Click Pricing for Display AdvertisingManufacturing & Service Operations Management10.1287/msom.2014.049116:4(482-497)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1287/msom.2014.0491
Liu BWang JZhao Y(2014)Tail asymptotics of the waiting time and the busy period for the $${{\varvec{M/G/1/K}}}$$ queues with subexponential service timesQueueing Systems: Theory and Applications10.1007/s11134-013-9348-876:1(1-19)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1007/s11134-013-9348-8
Gupta VHarchol-Balter M(2009)Self-adaptive admission control policies for resource-sharing systemsACM SIGMETRICS Performance Evaluation Review10.1145/2492101.155538537:1(311-322)Online publication date: 15-Jun-2009
https://dl.acm.org/doi/10.1145/2492101.1555385
Gupta VHarchol-Balter MDouceur JGreenberg ABonald TNieh J(2009)Self-adaptive admission control policies for resource-sharing systemsProceedings of the eleventh international joint conference on Measurement and modeling of computer systems10.1145/1555349.1555385(311-322)Online publication date: 15-Jun-2009
https://dl.acm.org/doi/10.1145/1555349.1555385
Jelenković PKang X(2008)Is fair resource sharing responsible for spreading long delays?ACM SIGMETRICS Performance Evaluation Review10.1145/1453175.145319736:2(101-103)Online publication date: 31-Aug-2008
https://dl.acm.org/doi/10.1145/1453175.1453197
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents