Skip to main content
Erschienen in: Queueing Systems 4/2012

01.08.2012

The fluid limit of the multiclass processor sharing queue

verfasst von: Abdelghani Ben Tahar, Alain Jean-Marie

Erschienen in: Queueing Systems | Ausgabe 4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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 Gromoll et al. (Ann. Appl. Probab. 12:797–859, 2002) and Puha et al. (Math. Oper. Res. 31(2):316–350, 2006), 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat 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) 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)
2.
Zurück zum Zitat Altman, E., Avrachenkov, K., Ayesta, U.: A survey on discriminatory processor sharing. Queueing Syst. 53, 53–63 (2006) CrossRef Altman, E., Avrachenkov, K., Ayesta, U.: A survey on discriminatory processor sharing. Queueing Syst. 53, 53–63 (2006) CrossRef
3.
Zurück zum Zitat Athreya, K.B., Rama Murthy, K.: Feller’s renewal theorem for systems of renewal equations. J. Indian Inst. Sci. 58(10), 437–459 (1976) Athreya, K.B., Rama Murthy, K.: Feller’s renewal theorem for systems of renewal equations. J. Indian Inst. Sci. 58(10), 437–459 (1976)
4.
Zurück zum Zitat 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 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.
Zurück zum Zitat Ben Tahar, A., Jean-Marie, A.: The fluid limit of the multiclass processor sharing queue. INRIA research report RR 6867, version 2, April 2009 Ben Tahar, A., Jean-Marie, A.: The fluid limit of the multiclass processor sharing queue. INRIA research report RR 6867, version 2, April 2009
6.
Zurück zum Zitat Berman, A., Plemmons, A.J.: Nonnegative Matrices in the Mathematical Sciences. SIAM Classics in Applied Mathematics, vol. 9 (1994) CrossRef Berman, A., Plemmons, A.J.: Nonnegative Matrices in the Mathematical Sciences. SIAM Classics in Applied Mathematics, vol. 9 (1994) CrossRef
7.
Zurück zum Zitat Billingsley, P.: Convergence of Probability Measures. Wiley, New York (1968) Billingsley, P.: Convergence of Probability Measures. Wiley, New York (1968)
8.
Zurück zum Zitat Bramson, M.: Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Syst., Theory Appl. 22(1–2), 5–45 (1996) CrossRef Bramson, M.: Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Syst., Theory Appl. 22(1–2), 5–45 (1996) CrossRef
9.
Zurück zum Zitat 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) 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)
10.
Zurück zum Zitat 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) CrossRef 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) CrossRef
11.
Zurück zum Zitat Chen, H., Kella, O., Weiss, G.: Fluid approximations for a processor sharing queue. Queueing Syst., Theory Appl. 27, 99–125 (1997) CrossRef Chen, H., Kella, O., Weiss, G.: Fluid approximations for a processor sharing queue. Queueing Syst., Theory Appl. 27, 99–125 (1997) CrossRef
12.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Durrett, R.T.: Probability: Theory and Examples, 2nd edn.. Duxbury, Belmont (1996) Durrett, R.T.: Probability: Theory and Examples, 2nd edn.. Duxbury, Belmont (1996)
14.
Zurück zum Zitat Egorova, R., Borst, S., Zwart, B.: Bandwidth-sharing networks in overload. Perform. Eval. 64, 978–993 (2007) CrossRef Egorova, R., Borst, S., Zwart, B.: Bandwidth-sharing networks in overload. Perform. Eval. 64, 978–993 (2007) CrossRef
15.
Zurück zum Zitat Gromoll, H.C.: Diffusion approximation for a processor sharing queue in heavy traffic. Ann. Appl. Probab. 14, 555–611 (2004) CrossRef Gromoll, H.C.: Diffusion approximation for a processor sharing queue in heavy traffic. Ann. Appl. Probab. 14, 555–611 (2004) CrossRef
16.
Zurück zum Zitat Gromoll, H.C., Kruk, L.: Heavy traffic limit for a processor sharing queue with soft deadlines. Ann. Appl. Probab. 17(3), 1049–1101 (2007) CrossRef Gromoll, H.C., Kruk, L.: Heavy traffic limit for a processor sharing queue with soft deadlines. Ann. Appl. Probab. 17(3), 1049–1101 (2007) CrossRef
17.
Zurück zum Zitat 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) CrossRef 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) CrossRef
18.
Zurück zum Zitat 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) CrossRef 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) CrossRef
19.
Zurück zum Zitat Gromoll, H.C., Robert, Ph., Zwart, B.: Fluid Limits for Processor-Sharing Queues with Impatience. Math. Oper. Res. 33(2), 375–402 (2008) CrossRef Gromoll, H.C., Robert, Ph., Zwart, B.: Fluid Limits for Processor-Sharing Queues with Impatience. Math. Oper. Res. 33(2), 375–402 (2008) CrossRef
20.
Zurück zum Zitat Horn, R., Johnson, C.: Matrix Analysis. Cambridge University Press, Cambridge (1985) Horn, R., Johnson, C.: Matrix Analysis. Cambridge University Press, Cambridge (1985)
21.
Zurück zum Zitat Jean-Marie, A., Robert, P.: On the transient behavior of the processor sharing queue. Queueing Syst., Theory Appl. 17, 129–136 (1994) CrossRef Jean-Marie, A., Robert, P.: On the transient behavior of the processor sharing queue. Queueing Syst., Theory Appl. 17, 129–136 (1994) CrossRef
22.
Zurück zum Zitat 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) CrossRef 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) CrossRef
23.
Zurück zum Zitat 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) CrossRef 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) CrossRef
24.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Williams, R.J.: Diffusion approximation for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Syst., Theory Appl. 30, 27–88 (1998) CrossRef Williams, R.J.: Diffusion approximation for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Syst., Theory Appl. 30, 27–88 (1998) CrossRef
26.
Zurück zum Zitat Yashkov, S.F., Yashkova, A.S.: Processor sharing: a survey of the mathematical theory. Autom. Remote Control 68(9), 1662–1731 (2007) CrossRef Yashkov, S.F., Yashkova, A.S.: Processor sharing: a survey of the mathematical theory. Autom. Remote Control 68(9), 1662–1731 (2007) CrossRef
27.
Zurück zum Zitat 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) CrossRef 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) CrossRef
Metadaten
Titel
The fluid limit of the multiclass processor sharing queue
verfasst von
Abdelghani Ben Tahar
Alain Jean-Marie
Publikationsdatum
01.08.2012
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 4/2012
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-012-9287-9