A large-deviations analysis of the GI/GI/1 SRPT queue. (English) Zbl 1107.60061
For the GI/GI/1 queue with light-tailed service times, the authors obtain expressions for the logarithmic decay rate of the tail of the workload, the busy period, the waiting time and sojourn time of low-priority customers in a priority queue, and the sojourn time under the (preemptive and non-preemptive) SRPT discipline. For the sojourn time under SRPT, it turns out that there are three different regimes, namely for service times with no mass, with some mass and with all mass in the endpoint of the service time distribution. In the first case the decay rate is minimal among all work-conserving disciplines, in the last case it is maximal, but if there is some mass in the endpoint, then the decay rate lies strictly in between these two. The large-deviations results for the unconditional sojourn times suggest that a switch from FIFO to SRPT is not advisable.
Reviewer: Oleg K. Zakusilo (Kyïv)
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 60F10 | Large deviations |
| 90B22 | Queues and service in operations research |
Keywords:
Busy period; large deviations; light-tailed service times; priority queue; shortest remaining processing time; sojourn timeReferences:
| [1] | 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 · doi:10.1023/A:1019104402024 |
| [2] | S. Asmussen, Applied Probability and Queues, 2nd edition (Springer, 2003). · Zbl 1029.60001 |
| [3] | F. Baccelli and P. Brémaud, Elements of Queueing Theory 3rd edition (Springer, 2003). · Zbl 1021.60001 |
| [4] | N. Bansal and M. Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness. In Proceedings of ACM Sigmetrics (2001) pp. 279–290. |
| [5] | N. Bansal, On the average sojourn time under M/M/1 SRPT. Operations Research Letters 33 (2004) 195–200. · Zbl 1099.90014 |
| [6] | N. Bansal and D. Gamarnik, Handling load with less stress (Submitted for publication, 2005). · Zbl 1101.90016 |
| [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. · doi:10.1016/S0166-5316(03)00071-3 |
| [8] | D. Cox and W. Smith, Queues. Methuen (1961). |
| [9] | A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications (Springer, 1998). · Zbl 0896.60013 |
| [10] | R. Egorova, B. Zwart, and O.J. Boxma, Sojourn time tails in the M/D/1 Processor Sharing queue. Probability in the Engineering and Informational Sciences 20 (2006) 429–446. · Zbl 1183.60035 |
| [11] | A. Ganesh, N. O’Connell, and D. Wischik, Big Queues (Springer, 2003). · Zbl 1044.60001 |
| [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 · doi:10.2307/3214953 |
| [13] | M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal, Sizebased scheduling to improve web performance. ACM Transactions on Computer Systems 21 (2003) 207–233. · doi:10.1145/762483.762486 |
| [14] | J.F.C. Kingman, A martingale inequality in the theory of queues. In Proceedings of the Cambridge Philosophical Society, vol. 59 (1964) pp. 359–361. · Zbl 0127.10004 |
| [15] | 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 · doi:10.1017/S0269964805050205 |
| [16] | M. Mandjes and M. Van Uitert, Sample path large deviations for tandem and priority queues with Gaussian input. Annals of Applied Probability 15 (2005) 1193–1226. · Zbl 1069.60079 · doi:10.1214/105051605000000133 |
| [17] | M. Mandjes and B. Zwart, Large deviations for sojourn times in processor sharing queues. Queueing Systems 52 (2006) 237–250. · Zbl 1094.60062 · doi:10.1007/s11134-006-5567-6 |
| [18] | R. Núñez-Queija, Processor-Sharing Models for Integrated-Service Networks. PhD thesis, Eindhoven University of Technology (2000). · Zbl 0953.68016 |
| [19] | Z. Palmowski and T. Rolski, On busy period asymptotics in the GI/GI/1 queue. To appear in Advances in Applied Probability (2006), available at http://www.math.uni.wroc.pl/\(\sim\)zpalma/publication.html · Zbl 1107.60062 |
| [20] | 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 |
| [21] | W. Rosenkrantz, Calculation of the Laplace transform of the length of the busy period for the M/G/1 queue via martingales. Annals of Probability 11 (1983) 817–818. · Zbl 0513.60093 · doi:10.1214/aop/1176993531 |
| [22] | L. Schrage, A proof of the optimality of the shortest remaining service time discipline. Operations Research 16 (1968) 670–690. · Zbl 0237.60039 · doi:10.1287/opre.16.3.687 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
