zbMATH — the first resource for mathematics

Large deviations of sojourn times in processor sharing queues. (English) Zbl 1094.60062
The paper considers a GI/G/1 queue operating under the processor sharing (PS) service discipline. The GI/G/1 PS queue is positive recurrent when the load \(\rho < 1\), which is assumed throughout the paper. Some specific assumptions are imposed on the distribution of the service times. The paper considers a customer entering the system in steady state. Let \(V\) be the sojourn time of this tagged customer. The main focus is on the asymptotic behavior of \(P\{ V > x\} \) as \(x \to \infty \), under light-tailed service times. Proposition 1 says that \(\limsup_{x \to \infty } \frac{1} {x}\log P\{ V > x\} \leqslant - \gamma \), where \(\gamma \) is a constant given in terms of the main characteristics of the system. Under additional assumption, Theorem 3.1 shows that \(\lim_{x \to \infty } \frac{1} {x}\log P\{ V > x\} = - \gamma \). The results are compared to a number of other service disciplines.

60K25 Queueing theory (aspects of probability theory)
Full Text: DOI
[1] J. Abate and W. Whitt, A heavy-traffic expansion for the asymptotic decay rates of tail probabilities in multi-channel queues, Operations Research Letters 15 (1994) 223–230. · Zbl 0814.90029
[2] J.Abate and W. Whitt, Asymptotics for M/G/1 low-priority waiting-time tail probabilities, Queueing Systems 25 (1997) 173–233. · Zbl 0894.60088
[3] J. Abate and W. Whitt, Limits and approximations for the M/G/1 LIFO waiting-time distribution, Operations Research Letters 20 (1997) 199–206. · Zbl 0882.90046
[4] S. Asmussen, Applied Probability and Queues. Springer New York, (2003). · Zbl 1029.60001
[5] J. Bertoin and R. Doney, Some asymptotic results for transient random walks, Advances in Applied Probability 28 (1996) 207–226. · Zbl 0854.60069
[6] S.C. Borst, O.J. Boxma, J.A. Morrison and R. Núñez-Queija, The equivalence between processor sharing and service in random order, Operations Research Letters 31 (2003) 254–262. · Zbl 1041.90009
[7] S.C. Borst, O.J. Boxma, R. Nunez-Queija and A.P. Zwart, The impact of the service discipline on delay asymptotics, Performance Evaluation 54 (2003) 177–206.
[8] O.J. Boxma, S. Foss, J.-M. Lasgouttes and R. Núñez-Queija, Waiting time asymptotics in the single server queue with service in random order, Queueing Systems 46 (2004) 35–73. · Zbl 1056.90027
[9] E.G. Coffman, Jr., R.R. Muntz and H. Trotter, Waiting time distributions for processor-sharing systems, Journal of the ACM 17 (1970) 123–130. · Zbl 0197.15304
[10] P. Embrechts and N. Veraverbeke, Estimates for the probability of ruin with special emphasis on the possibility of large claims, Insurance: Mathematics and Economics 1 (1982) 55– 72. · Zbl 0518.62083
[11] L. Flatto, The waiting time distribution for the random order service M/M/1 queue. Annals of Applied Probability 7 (1997) 382– 409. · Zbl 0883.60086
[12] P. Glynn and W. Whitt, Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. Journal of Applied Probability 31A (1994) 131–156. · Zbl 0805.60093
[13] F. Guillemin and J. Boyer, Analysis of M/M/1 queue with processor sharing via spectral theory. Queueing Systems 39 (2002) 377–397. · Zbl 0995.60085
[14] F. Guillemin, P. Robert and A.P. Zwart, Asymptotic results for processor sharing queues. Advances in Applied Probability 36 (2004) 525–543. · Zbl 1054.60094
[15] C. Gromoll, Diffusion approximation for a processor sharing queue in heavy traffic. Annals of Applied Probability 14 (2004) 555–611. · Zbl 1050.60085
[16] A. Jean-Marie and P. Robert, On the transient behavior of the processor sharing queue. Queueing Systems 17 (1994) 129–136. · Zbl 0811.60083
[17] P. Jelenković and P. Momčilović, Large deviation analysis of subexponential waiting times in a processor-sharing queue. Mathematics of Operations Research 28 (2003) 587–608. · Zbl 1082.60083
[18] D.A. Korshunov, On distribution tail of the maximum of a random walk. Stochastic Processes and their Applications 72 (1997) 97–103. · Zbl 0942.60018
[19] M. Mandjes and M. Nuyens, Sojourn times in the M/G/1 FB queue with light-tailed service times. Probability in the Engineering and Informational Sciences 19 (2005) 351–361. · Zbl 1072.60079
[20] J.A. Morrison, Response-time distribution for a processor-sharing system. SIAM Journal of Applied Mathematics 45 (1985) 152–167. · Zbl 0558.68031
[21] R. Núñez-Queija, Queues with equally heavy sojourn time and service requirement distributions. Annals of Operations Research 113, 101–117. · Zbl 1013.90036
[22] M. Nuyens and B. Zwart, A large deviations analysis of the GI/GI/1 SRPT queue. Submitted for publication (2005). · Zbl 1107.60061
[23] T. Ott, The sojourn-time distribution in the M/G/1 queue with processor sharing. Journal of Applied Probability 21 (1984) 360–378. · Zbl 0544.60087
[24] Z. Palmowksi and T. Rolski, On the busy period asymptotics of GI/G/1 queues. (2004) Submitted for publication. Available at http://www.math.uni.wroc.pl/\(\sim\)zpalma/publication.html
[25] F. Pollaczek, La loi d’attente des appels téléphoniques. Comptes Rendus Acad. Sci. Paris 222 (1946) 353–355. · Zbl 0063.06294
[26] A. Puha, A. Stolyar and R. Williams, The fluid limit of an overloaded processor sharing queue. Mathematics of Operations Research, (2004) to appear. · Zbl 1278.90102
[27] K. Ramanan and A. Stolyar, Largest weighted delay first scheduling: large deviations and optimality. Annals of Applied Probability 11 (2001) 1–48. · Zbl 1024.60012
[28] P. Robert, Stochastic Networks and Queues–A probabilistic approach, Springer, New York, (2003).
[29] T. Rolski, H. Schmidli, V. Schmidt and J. Teugels, Stochastic Processes for Insurance and Finance. Wiley, New York, (1999). · Zbl 0940.60005
[30] S. Ross, Stochastic Processes. Wiley, New York, (1996).
[31] L.E. Schrage and L.W. Miller, The queue M/G/1 with the shortest remaining processing time discipline, Operations Research 14 (1966) 670–684. · Zbl 0147.16702
[32] W. Whitt, Tail probabilities with statistical multiplexing and effective bandwidths in multi-class queues, Telecommunication Systems 2 (1993) 71–107.
[33] A. Wierman and M. Harchol-Balter, Classifying scheduling policies with respect to unfairness in an M/GI/1. Proceedings of ACM Sigmetrics, San Diego, CA (2003). · Zbl 1043.68035
[34] A.P. Zwart and O.J. Boxma, Sojourn time asymptotics in the M/G/1 processor sharing queue, Queueing Systems 35 (2000) 141–166. · Zbl 0997.90024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.