zbMATH — the first resource for mathematics

Sojourn time asymptotics in processor-sharing queues. (English) Zbl 1094.60059
This survey paper gives an overview of several methods used in investigating queues with processor-sharing (PS) discipline in case of heavy-tailed service requirements. In this case there exists a simple asymptotic equivalence between the sojourn time and the service requirement distribution, which is commonly referred to as a reduced service rate approximation. The paper considers Tauberian approach, sample-path large-deviations approach, and probabilistic approach using the conditional sojourn time. It also contains the generalization of the reduced service rate approximation to several extensions of the M/G/1 PS queue. In addition, it identifies a relationship between the reduced service rate approximation and a queue length distribution with a geometrically decaying tail, and extends it to so-called bandwidth-sharing networks. It also touches PS queues with light-tailed service requirements. The paper also proposes some possible avenues for further research.

60K25 Queueing theory (aspects of probability theory)
60F10 Large deviations
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B18 Communication networks in operations research
90B22 Queues and service in operations research
Full Text: DOI
[1] E. Altman, K. Avrachenkov, and U. Ayesta, A survey on Discriminatory Processor Sharing (2006). In this special issue.
[2] S. Asmussen, Applied Probability and Queues (Springer-Verlag, New York, 2003). · Zbl 1029.60001
[3] S. Asmussen, C. Klüppelberg, and K. Sigman, Sampling at subexponential times, with queueing applications, Stoch. Proc. Appl. 79 (1999) 265–286. · Zbl 0961.60080 · doi:10.1016/S0304-4149(98)00064-7
[4] R. Bekker, S.C. Borst, and R. Nú nez-Queija, Performance of TCP-friendly streaming sessions in the presence of heavy-tailed elastic flows, Perf. Evaluation 61 (2005) 143–162. · doi:10.1016/j.peva.2004.11.012
[5] J.L. van den Berg and O.J. Boxma, The M/G/1 queue with processor sharing and its relation to a feedback queue, Queueing Systems 9 (1991) 365–402. · Zbl 0743.60090 · doi:10.1007/BF01159223
[6] N.H. Bingham and R.A. Doney, Asymptotic properties of supercritical branching processes I: the Galton-Watson process, Adv. Appl. Prob. 6 (1974) 711–731. · Zbl 0297.60044 · doi:10.2307/1426188
[7] N.H. Bingham, C.M. Goldie, and J.L. Teugels, Regular Variation (Cambridge University Press, 1987). · Zbl 0617.26001
[8] T. Bonald and L. Massoulié, Impact of fairness on Internet performance, in: Proc. ACM Sigmetrics/Performance (2001).
[9] T. Bonald and A. Proutière, Insensitivity in processor sharing networks, Perf. Evaluation 49 (2002) 193–209. · Zbl 1043.68004 · doi:10.1016/S0166-5316(02)00110-4
[10] T. Bonald and A. Proutière, Insensitive bandwidth sharing in data networks, Queueing Systems 44 (2003) 69–100. · Zbl 1023.90003 · doi:10.1023/A:1024094807532
[11] T. Bonald and A. Proutière, On stochastic bounds for monotonic processor sharing networks, Queueing Systems 47 (2004) 81–106. · Zbl 1073.68018 · doi:10.1023/B:QUES.0000032802.41986.c6
[12] S.C. Borst, O.J. Boxma, J.A. Morrison, and R. Nú nez-Queija, The equivalence between processor sharing and service in random order, Oper. Res. Lett. 31 (2003) 254–262. · Zbl 1041.90009 · doi:10.1016/S0167-6377(03)00006-3
[13] S.C. Borst, O.J. Boxma, R. Nú nez-Queija, and A.P. Zwart, The impact of the service discipline on delay asymptotics, Perf. Evaluation 54 (2003) 177–206.
[14] S.C. Borst, R. Nú nez-Queija, and M.J.G. van Uitert, User-level performance of elastic traffic in a differentiated-services environment, Proc. Performance (2002) 507–519.
[15] S.C. Borst, R. Nú nez-Queija, and A.P. Zwart, Bandwidth sharing with heterogeneous service requirements, Ann. Telecommun. 59 (2004) 1297–1311.
[16] S.C. Borst, D.T.M.B. van Ooteghem, and A.P. Zwart, Tail asymptotics for discriminatory processor-sharing queues with heavy-tailed service requirements, Perf. Evaluation 61 (2005) 281–298. · doi:10.1016/j.peva.2004.11.010
[17] O.J. Boxma and V. Dumas, The busy period in the fluid queue, Perf. Eval. Rev. 26 (1998) 100–110. · doi:10.1145/277858.277881
[18] L. Breiman. On some limit theorems similar to the arc-sin law, Theory of Prob. Appl. 10 (1965) 351–360. · Zbl 0147.37004
[19] E.G. Coffman Jr., R.R. Muntz, and H. Trotter, Waiting time distribution for processor-sharing systems, J. ACM 17 (1970) 123–130. · Zbl 0197.15304 · doi:10.1145/321556.321568
[20] J.W. Cohen, The multiple phase service network with generalised processor sharing, Acta Informatica 12 (1979) 245–284. · Zbl 0415.68004 · doi:10.1007/BF00264581
[21] M. Crovella and A. Bestavros, Self-similarity in World Wide Web traffic: Evidence and possible causes, in: Proc. ACM Sigmetrics (1996) pp. 160–169.
[22] F. Delcoigne, A. Proutière, and G. Régnié, Modelling integration of streaming and data traffic, in: Proc. ITC Specialist Seminar (Würzburg, Germany, 2002).
[23] R. Egorova, A.P. Zwart, and O.J. Boxma, Sojourn time tails in the M/D/1 processor sharing queue. SPOR-Report 2005-05, Eindhoven University of Technology, Prob. Eng. Inf. Sciences (2006) to appear. · Zbl 1183.60035
[24] P. Embrechts, C. Klüppelberg, and T. Mikosch, Modeling Extremal Events (Springer, 1997).
[25] G. Fayolle, I. Mitrani, and R. Iasnogorodski, Sharing a processor among many job classes, J. ACM 27 (1980) 519–532. · Zbl 0475.68012 · doi:10.1145/322203.322212
[26] L. Flatto, The waiting time distribution for the random order service M/M/1 queue, Ann. Appl. Prob. 7 (1997) 382–409. · Zbl 0883.60086 · doi:10.1214/aoap/1034625337
[27] S. Foss and D.A. Korshunov, Sampling at random time with a heavy-tailed distribution, Markov Proc. Rel. Fields 6 (2000) 543–568. · Zbl 0977.60091
[28] F. Guillemin, Ph. Robert, and A.P. Zwart, Tail asymptotics for processor sharing queues, Adv. Appl. Prob. 36 (2004) 525–543. · Zbl 1054.60094 · doi:10.1239/aap/1086957584
[29] D.P. Heyman, T.V. Lakshman, and A.L. Neidhardt, A new method for analysing feedback-based protocols with applications to engineering Web traffic over the Internet, in: Proc. ACM Sigmetrics (1997) 24–38.
[30] D.L. Jagerman and B. Sengupta, The GI/M/1 processor-sharing queue and its heavy traffic analysis, Comm. Statist.–Stoch. Models 7 (1991) 379–395. · Zbl 0736.60092 · doi:10.1080/15326349108807197
[31] P.R. Jelenković, Network multiplexer with truncated heavy-tailed arrival streams, in: Proc. IEEE Infocom (New York, NY, USA, 1999) pp. 625–633.
[32] P.R. Jelenković and P. MomČilović, Large deviation analysis of subexponential waiting times in a processor sharing queue, Math. Oper. Res. 28 (2003) 587–608. · Zbl 1082.60083 · doi:10.1287/moor.28.3.587.16396
[33] P.R. Jelenković, P. MomČilović, and A.P. Zwart, Reduced load equivalence under subexponentiality, Queueing Systems 46 (2004) 97–112. · Zbl 1056.90032 · doi:10.1023/B:QUES.0000021143.87779.3f
[34] L. Kleinrock, Analysis of a time-shared processor, Nav. Res. Log. Quarterly 11 (1964) 59–73. · Zbl 0129.30902 · doi:10.1002/nav.3800110105
[35] L. Kleinrock, Time-shared systems: A theoretical treatment, J. ACM 14 (1967) 242–261. · Zbl 0173.20001 · doi:10.1145/321386.321388
[36] M.R.H. Mandjes and A.P. Zwart, Large deviations for sojourn times in processor sharing queues, Queueing Systems (to appear). · Zbl 1094.60062
[37] L. Massoulié and J.W. Roberts, Bandwidth sharing: Objectives and algorithms, in: Proc. IEEE Infocom (New York, NY, USA, 1999) 1395–1403.
[38] D. Mitra, Waiting time distributions from closed queueing network models of shared-processor systems, in: F.J. Kylstra (ed.), Proc. Performance, North-Holland, Amsterdam (1981) 113–131.
[39] D. Mitra and J.A. Morrison, Asymptotic expansions of moments of the waiting time in closed and open processor-sharing systems with multiple job classes, Adv. Appl. Prob. 15 (1983) 813–839. · Zbl 0526.60085 · doi:10.2307/1427326
[40] J.A. Morrison, Response-time distribution for a processor-sharing system, SIAM J. Appl. Math. 45 (1985) 152–167. · Zbl 0558.68031 · doi:10.1137/0145007
[41] J.A. Morrison and D. Mitra, Heavy-usage asymptotic expansions for the waiting time in closed processor-sharing systems with multiple classes, Adv. Appl. Prob. 17 (1985) 163–185. · Zbl 0556.60038 · doi:10.2307/1427058
[42] M. Nabe, M. Murata, and H. Miyahara, Analysis and modelling of World Wide Web traffic for capacity dimensioning of Internet access lines, Perf. Evaluation 34 (1998) 249–271. · doi:10.1016/S0166-5316(98)00040-6
[43] R. Nú nez-Queija, Processor-Sharing Models for Integrated-Services Networks, Ph.D. thesis, Eindhoven University of Technology (2000) ISBN 90-646-4667-8 (also available from the author upon request). · Zbl 0953.68016
[44] R. Nú nez-Queija, Queues with equally heavy sojourn time and service requirement distributions, Ann. Oper. Res. 113 (2002) 101–117. · Zbl 1013.90036 · doi:10.1023/A:1020905810996
[45] M. Nuyens, A. Wierman, and A.P. Zwart, Preventing large sojourn times with SMART scheduling, (SPOR Report 2005-13, Eindhoven University of Technology, 2005). Submitted for publication. · Zbl 1167.90457
[46] M. Nuyens and A.P. Zwart, A large deviations analysis of the GI/GI/1 SRPT queue (SPOR Report 2005–06, Eindhoven University of Technology, 2005). Submitted for publication. · Zbl 1107.60061
[47] D.T.M.B. van Ooteghem, A.P. Zwart, and S.C. Borst, A stochastic mean-value method for the derivation of delay asymptotics in heavy-tailed processor-sharing systems (SPOR Report 2004-11, Eindhoven University of Technology, 2004).
[48] T.J. Ott, The sojourn time distributions in the M/G/1 queue with processor sharing, J. Appl. Prob. 21 (1984) 360–378. · Zbl 0544.60087 · doi:10.2307/3213646
[49] Z. Palmowksi and T. Rolski, On busy period asymptotics in the GI/GI/1 queue, Available at http://www.math.uni.wroc.pl\(\sim\)zpalma/publication.html. Submitted for publication.
[50] F. Pollaczek, La loi d’attente des appels téléphoniques, Comptes Rendus Acad. Sci. Paris 222 (1946) 352–355. · Zbl 0063.06294
[51] V. Ramaswami, The sojourn time in the GI/M/1 queue with processor sharing, J. Appl. Prob. 21 (1984) 437–442. · Zbl 0543.60093 · doi:10.2307/3213654
[52] M. Sakata, S. Noguchi, and J. Oizumi, Analysis of a processor-shared queueing model for time-sharing systems, in: Proc. 2nd Hawaii Int. Conf. System Sciences (1969) pp. 625–628.
[53] M. Sakata, S. Noguchi, and J. Oizumi, An analysis of the M/G/1 queue under round-robin scheduling, Oper. Res. 19 (1971) 371–385. · Zbl 0247.60061 · doi:10.1287/opre.19.2.371
[54] B. Sengupta and D.L. Jagerman, A conditional response time of the M/M/1 processor-sharing queue, AT&T Techn. J. 64 (1985) 409–421. · Zbl 0587.68036
[55] S.F. Yashkov, Processor-sharing queues: Some progress in analysis, Queueing Systems 2 (1987) 1–17. · Zbl 0648.68050 · doi:10.1007/BF01182931
[56] S.F. Yashkov, Mathematical problems in the theory of processor-sharing queueing systems, J. Soviet Math. 58 (1992) 101–147. · Zbl 0735.68010 · doi:10.1007/BF01097426
[57] A.P. Zwart, Sojourn times in a multi-class processor sharing queue, in: P. Key and D. Smith (eds.), Teletraffic Engineering in a Competitive World, Proc. ITC-16, Edinburgh, UK, (North-Holland, Amsterdam) (1999) 335–344.
[58] A.P. Zwart, Tail asymptotics for the busy period in the GI/G/1 queue, Math. Oper. Res. 26 (2001) 475–483. · Zbl 1073.90510 · doi:10.1287/moor.26.3.485.10584
[59] 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 · doi:10.1023/A:1019142010994
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.