×

The fluid limit of the multiclass processor sharing queue. (English) Zbl 1275.68040

Summary: Consider a single server queueing system with several classes of customers, each having its own renewal input process and its own general service times distribution. Upon completing service, customers may leave, or re-enter the queue, possibly as customers of a different class. The server is operating under the egalitarian processor sharing discipline. Building on prior work by H. C. Gromoll et al. [Ann. Appl. Probab. 12, No. 3, 797–859 (2002; Zbl 1017.60092)] and A. L. Puha et al. [Math. Oper. Res. 31, No. 2, 316–350 (2006; Zbl 1278.90102)], we establish the convergence of a properly normalized state process to a fluid limit characterized by a system of algebraic and integral equations. We show the existence of a unique solution to this system of equations, both for a stable and an overloaded queue. We also describe the asymptotic behavior of the trajectories of the fluid limit.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altman, E., Jiménez, T., Kofman, D.: DPS queues with stationary ergodic service times and the performance of TCP in overload. In: Proc. IEEE INFOCOM’04, Hong-Kong (2004) · Zbl 1208.68088
[2] Altman, E., Avrachenkov, K., Ayesta, U.: A survey on discriminatory processor sharing. Queueing Syst. 53, 53–63 (2006) · Zbl 1114.90014 · doi:10.1007/s11134-006-7586-8
[3] Athreya, K.B., Rama Murthy, K.: Feller’s renewal theorem for systems of renewal equations. J. Indian Inst. Sci. 58(10), 437–459 (1976) · Zbl 0356.60057
[4] Ben Tahar, A., Jean-Marie, A.: Population effects in multiclass processor sharing queues. In: Proc. Valuetools 2009, Fourth International Conference on Performance Evaluation Methodologies and Tools, Pisa, October 2009
[5] Ben Tahar, A., Jean-Marie, A.: The fluid limit of the multiclass processor sharing queue. INRIA research report RR 6867, version 2, April 2009 · Zbl 1275.68040
[6] Berman, A., Plemmons, A.J.: Nonnegative Matrices in the Mathematical Sciences. SIAM Classics in Applied Mathematics, vol. 9 (1994) · Zbl 0815.15016
[7] Billingsley, P.: Convergence of Probability Measures. Wiley, New York (1968) · Zbl 0172.21201
[8] Bramson, M.: Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Syst., Theory Appl. 22(1–2), 5–45 (1996) · Zbl 0851.90044 · doi:10.1007/BF01159391
[9] Bramson, M.: Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks. Queueing Syst., Theory Appl. 23(1–4), 1–26 (1997) · Zbl 0879.60087 · doi:10.1007/BF01206549
[10] Bramson, M.: State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst., Theory Appl. 30(1–2), 89–148 (1998) · Zbl 0911.90162 · doi:10.1023/A:1019160803783
[11] Chen, H., Kella, O., Weiss, G.: Fluid approximations for a processor sharing queue. Queueing Syst., Theory Appl. 27, 99–125 (1997) · Zbl 0892.90073 · doi:10.1023/A:1019105929766
[12] Dawson, D.A.: Measure-valued Markov processes, école d’été de probabilités de Saint Flour. Lecture Notes in Mathematics NO 1541, vol. XXI. Springer, Berlin (1993)
[13] Durrett, R.T.: Probability: Theory and Examples, 2nd edn.. Duxbury, Belmont (1996) · Zbl 1202.60001
[14] Egorova, R., Borst, S., Zwart, B.: Bandwidth-sharing networks in overload. Perform. Eval. 64, 978–993 (2007) · Zbl 1303.60081 · doi:10.1016/j.peva.2007.06.024
[15] Gromoll, H.C.: Diffusion approximation for a processor sharing queue in heavy traffic. Ann. Appl. Probab. 14, 555–611 (2004) · Zbl 1050.60085 · doi:10.1214/105051604000000035
[16] Gromoll, H.C., Kruk, L.: Heavy traffic limit for a processor sharing queue with soft deadlines. Ann. Appl. Probab. 17(3), 1049–1101 (2007) · Zbl 1130.60087 · doi:10.1214/105051607000000014
[17] Gromoll, H.C., Williams, R.: Fluid Limits for Networks with Bandwidth Sharing and General Document Size Distributions. Ann. Appl. Probab. 10(1), 243–280 (2009) · Zbl 1169.60025 · doi:10.1214/08-AAP541
[18] Gromoll, H.C., Puha, A.L., Williams, R.J.: The fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Probab. 12, 797–859 (2002) · Zbl 1017.60092 · doi:10.1214/aoap/1031863171
[19] Gromoll, H.C., Robert, Ph., Zwart, B.: Fluid Limits for Processor-Sharing Queues with Impatience. Math. Oper. Res. 33(2), 375–402 (2008) · Zbl 1213.60148 · doi:10.1287/moor.1070.0298
[20] Horn, R., Johnson, C.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
[21] Jean-Marie, A., Robert, P.: On the transient behavior of the processor sharing queue. Queueing Syst., Theory Appl. 17, 129–136 (1994) · Zbl 0811.60083 · doi:10.1007/BF01158692
[22] Puha, A.L., Williams, R.J.: Invariant states and rates of convergence for the fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Probab. 14, 517–554 (2004) · Zbl 1061.60098 · doi:10.1214/105051604000000017
[23] Puha, A.L., Stolyar, A.L., Williams, R.J.: The fluid limit of an overloaded processor sharing queue. Math. Oper. Res. 31(2), 316–350 (2006) · Zbl 1278.90102 · doi:10.1287/moor.1050.0181
[24] de Saporta, B.: Étude de la solution stationnaire de l’équation Y(n+1)=a(n)Y(n)+b(n) à coefficients aléatoires. PhD thesis, University of Rennes 1 (2004)
[25] Williams, R.J.: Diffusion approximation for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Syst., Theory Appl. 30, 27–88 (1998) · Zbl 0911.90171 · doi:10.1023/A:1019108819713
[26] Yashkov, S.F., Yashkova, A.S.: Processor sharing: a survey of the mathematical theory. Autom. Remote Control 68(9), 1662–1731 (2007) · Zbl 1147.93003 · doi:10.1134/S0005117907090202
[27] Zhang, J., Dai, J.G., Zwart, B.: Law of large number limits of limited processor-sharing queues. Math. Oper. Res. 34(4), 937–970 (2009) · Zbl 1213.60155 · doi:10.1287/moor.1090.0412
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.