Sojourn times in the \(M/ PH/1\) processor sharing queue. (English) Zbl 1080.90034
Summary: We give in this paper an algorithm to compute the sojourn time distribution in the processor sharing, single server queue with Poisson arrivals and phase type distributed service times. In a first step, we establish the differential system governing the conditional sojourn times probability distributions in this queue, given the number of customers in the different phases of the PH distribution at the arrival instant of a customer. This differential system is then solved by using a uniformization procedure and an exponential of matrix. The proposed algorithm precisely consists of computing this exponential with a controlled accuracy. This algorithm is then used in practical cases to investigate the impact of the variability of service times on sojourn times and the validity of the so-called reduced service rate (RSR) approximation, when service times in the different phases are highly dissymmetrical. For two-stage PH distributions, we give conjectures on the limiting behavior in terms of an \(M/M/1\) PS queue and provide numerical illustrative examples.
MSC:
| 90B22 | Queues and service in operations research |
| 60K25 | Queueing theory (aspects of probability theory) |
References:
| [1] | J. Abate and W. Whitt, Numerical inversion of Laplace transforms of probability distributions, ORSA J. Comput. 7(1) (1995) 36–43. · Zbl 0821.65085 |
| [2] | R. Agrawal, A.M. Makowski, and P. Nain, On a reduced load equivalence for fluid queues under subexponentiality, Queueing Systems. Theory and Applications 33(1–3) (1999) 5–41. · Zbl 0997.60114 · doi:10.1023/A:1019111809660 |
| [3] | S. Asmussen, Applied Probability and Queues (J. Wiley and Sons, 1987). · Zbl 0624.60098 |
| [4] | C. Barakat, P. Thiran, G. Iannaccone, C. Diot and P. Owezarski, Modeling internet backbone traffic at the flow level, IEEE Transactions on Signal Processing–Special Issue on Signal Processing in Networking 51(8) (2003) 2111–2124. |
| [5] | S. Ben Fredj, T. Bonald, A. Proutiére, G. Régnié and J.W. Roberts, Statistical bandwidth sharing: a study of congestion at flow level, in: Proc. SIGCOMM 2001, (San Diego, CA, USA, Aug. 2001). |
| [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, Oper. Res. Lett 31 (2003) 254–262. · Zbl 1041.90009 · doi:10.1016/S0167-6377(03)00006-3 |
| [7] | S.C. Borst, O.J. Boxma, J.A. Morrison and R. Núñez-Queija, The equivalence between processor sharing and service in random order, Oper. Res. Lett 31 (2003) 254–262. · Zbl 1041.90009 |
| [8] | E.G. Coffman, R.R. Muntz and H. Trotter, Waiting time distributions for processor-sharing systems, J. ACM 17 (1970) 123–130. · Zbl 0197.15304 · doi:10.1145/321556.321568 |
| [9] | 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 · doi:10.1214/aoap/1034625337 |
| [10] | F. Guillemin and J. Boyer, Analysis of the M/M/1 queue with processor sharing via spectral theory, Queueing Systems 39 (2001) 377–397. · Zbl 0995.60085 · doi:10.1023/A:1013913827667 |
| [11] | F. Guillemin, P. Robert and B. Zwart, Tail asymptotics for processor sharing queues, Annals of Applied Probability 36 (2004) 1–19. · Zbl 1054.60094 |
| [12] | P. Jelenković and P. Momçilović, Large deviation analysis of subexponential waiting time in an MG/1 PS queue (2001). http://comet.ctr.columbia.edu/petar/ps.pdf.Submitted. |
| [13] | M. Yu. Kitaev, The M/G/1 processor-sharing model: Transient behavior, Queueing Systems 14 (1993) 239–273. · Zbl 0802.68011 |
| [14] | M. Yu. Kitaev, The M/G/1 processor-sharing model: Transient behavior, Queueing Systems 14 (1993) 239–273. · Zbl 0802.68011 |
| [15] | J. Morrison, Response time for a processor-sharing system, SIAM J. Appl. Math. 45(1) (1985) 152–167. · Zbl 0558.68031 · doi:10.1137/0145007 |
| [16] | R. Núñez-Queija, Processor Sharing Models for Integrated Services Networks, PhD thesis, Eindhoven University of Technology (2000). |
| [17] | T. Ott, The sojourn-time distribution in the M/G/1 queue with processor sharing, J. Appl. Prob. 21 (1984) 360–378. · Zbl 0544.60087 · doi:10.2307/3213646 |
| [18] | F. Pollaczek, La loi d’attente des appels téléphoniques. C.R. Acad. Sci. 222 (1946) 353–355. · Zbl 0063.06294 |
| [19] | J. Riordan, Stochastic Service Systems (John Wiley and Sons, Inc., New York London, 1962). · Zbl 0106.33601 |
| [20] | J. Roberts and L. Massoulié, Bandwidth sharing and admission control for elastic traffic, in Proc. Infocom’99 (1998). · Zbl 1030.68774 |
| [21] | J. Roberts and L. Massoulié, Bandwidth sharing and admission control for elastic traffic, in Proc. Infocom’99 (1998). · Zbl 0383.60092 · doi:10.2307/3213122 |
| [22] | D. Starobinski and M. Sidi, Modeling and analysis of heavy-tailed distributions via classical teletraffic methods, Queueing Systems 36(1–3) (2000) 243–267. · Zbl 0966.90020 · doi:10.1023/A:1019195522806 |
| [23] | 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 |
| [24] | S.F. Yashkov, Processor sharing queues: some progress in analysis, Queueing System 2 (1987) 1–17. · Zbl 0648.68050 · doi:10.1007/BF01182931 |
| [25] | A.P. Zwart and O.J. Boxma, Sojourn time asymptotics in the M/G/1 processor sharing queue, Queueing Systems Theory Appl. 35(1–4) (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. 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.
