Skip to main content
Erschienen in: Queueing Systems 3-4/2015

01.04.2015

Heavy-traffic asymptotics for networks of parallel queues with Markov-modulated service speeds

verfasst von: Jan-Pieter L. Dorsman, Maria Vlasiou, Bert Zwart

Erschienen in: Queueing Systems | Ausgabe 3-4/2015

Einloggen

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

search-config
loading …

Abstract

We study a network of parallel single-server queues, where the speeds of the servers are varying over time and governed by a single continuous-time Markov chain. We obtain heavy-traffic limits for the distributions of the joint workload, waiting-time and queue length processes. We do so by using a functional central limit theorem approach, which requires the interchange of steady-state and heavy-traffic limits. The marginals of these limiting distributions are shown to be exponential with rates that can be computed by matrix-analytic methods. Moreover, we show how to numerically compute the joint distributions, by viewing the limit processes as multi-dimensional semi-martingale reflected Brownian motions in the non-negative orthant.

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!

Literatur
1.
Zurück zum Zitat Asmussen, S.: Applied Probability and Queues. Springer, New York (2003) Asmussen, S.: Applied Probability and Queues. Springer, New York (2003)
2.
Zurück zum Zitat Ata, B., Shneorson, S.: Dynamic control of an M/M/1 service system with adjustable arrival and service rates. Manag. Sci. 52, 1778–1791 (2006)CrossRef Ata, B., Shneorson, S.: Dynamic control of an M/M/1 service system with adjustable arrival and service rates. Manag. Sci. 52, 1778–1791 (2006)CrossRef
3.
Zurück zum Zitat Bekker, R.: Queues with State-Dependent Rates. PhD thesis, Eindhoven University of Technology (2005) Bekker, R.: Queues with State-Dependent Rates. PhD thesis, Eindhoven University of Technology (2005)
4.
Zurück zum Zitat Bertoin, J.: Lévy Processes. Cambridge University Press, Cambridge (1996) Bertoin, J.: Lévy Processes. Cambridge University Press, Cambridge (1996)
5.
Zurück zum Zitat Budhiraja, A., Lee, C.: Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34, 45–56 (2009)CrossRef Budhiraja, A., Lee, C.: Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34, 45–56 (2009)CrossRef
6.
Zurück zum Zitat Chen, H., Whitt, W.: Diffusion approximations for open queueing networks with service interruptions. Queueing Syst. 13, 335–359 (1993)CrossRef Chen, H., Whitt, W.: Diffusion approximations for open queueing networks with service interruptions. Queueing Syst. 13, 335–359 (1993)CrossRef
7.
Zurück zum Zitat Chen, H., Yao, D.D.: Fundamentals of Queueing Networks. Springer, New York (2001)CrossRef Chen, H., Yao, D.D.: Fundamentals of Queueing Networks. Springer, New York (2001)CrossRef
8.
Zurück zum Zitat Choudhury, G.L., Mandelbaum, A., Reiman, M.I., Whitt, W.: Fluid and diffusion limits for queues in slowly changing environments. Commun. Stat. Stoch. Models 13, 121–146 (1997)CrossRef Choudhury, G.L., Mandelbaum, A., Reiman, M.I., Whitt, W.: Fluid and diffusion limits for queues in slowly changing environments. Commun. Stat. Stoch. Models 13, 121–146 (1997)CrossRef
9.
Zurück zum Zitat Dai, J.G., Harrison, J.M.: Reflected Brownian motion in an orthant: numerical methods for steady-state analysis. Ann. Appl. Probab. 2, 65–86 (1992)CrossRef Dai, J.G., Harrison, J.M.: Reflected Brownian motion in an orthant: numerical methods for steady-state analysis. Ann. Appl. Probab. 2, 65–86 (1992)CrossRef
10.
Zurück zum Zitat Debicki, K., Kosiński, K.M., Mandjes, M.: Gaussian queues in light and heavy traffic. Queueing Syst. 71, 137–149 (2012)CrossRef Debicki, K., Kosiński, K.M., Mandjes, M.: Gaussian queues in light and heavy traffic. Queueing Syst. 71, 137–149 (2012)CrossRef
11.
Zurück zum Zitat Dieker, A.B., Moriarty, J.: Reflected Brownian motion in a wedge: sum-of-exponential stationary densities. Electron. Commun. Probab. 14, 1–16 (2009)CrossRef Dieker, A.B., Moriarty, J.: Reflected Brownian motion in a wedge: sum-of-exponential stationary densities. Electron. Commun. Probab. 14, 1–16 (2009)CrossRef
13.
Zurück zum Zitat Dorsman, J.L., Boxma, O.J., Vlasiou, M.: Marginal queue length approximations for a two-layered network with correlated queues. Queueing Syst. 75, 29–63 (2013)CrossRef Dorsman, J.L., Boxma, O.J., Vlasiou, M.: Marginal queue length approximations for a two-layered network with correlated queues. Queueing Syst. 75, 29–63 (2013)CrossRef
14.
Zurück zum Zitat Dorsman, J.L., van der Mei, R.D., Vlasiou, M.: Analysis of a two-layered network by means of the power-series algorithm. Perform. Eval. 70, 1072–1089 (2013)CrossRef Dorsman, J.L., van der Mei, R.D., Vlasiou, M.: Analysis of a two-layered network by means of the power-series algorithm. Perform. Eval. 70, 1072–1089 (2013)CrossRef
15.
Zurück zum Zitat Gamarnik, D., Zeevi, A.: Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16, 56–90 (2006)CrossRef Gamarnik, D., Zeevi, A.: Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16, 56–90 (2006)CrossRef
16.
Zurück zum Zitat George, J.M., Harrison, J.M.: Dynamic control of a queue with adjustable service rate. Oper. Res. 49, 720–731 (2001)CrossRef George, J.M., Harrison, J.M.: Dynamic control of a queue with adjustable service rate. Oper. Res. 49, 720–731 (2001)CrossRef
17.
Zurück zum Zitat Halfin, S.: Steady-state distribution for the buffer content of an M/G/1 queue with varying service rate. SIAM J. Appl. Math. 23, 356–363 (1972)CrossRef Halfin, S.: Steady-state distribution for the buffer content of an M/G/1 queue with varying service rate. SIAM J. Appl. Math. 23, 356–363 (1972)CrossRef
18.
Zurück zum Zitat Harrison, J.M., Williams, R.J.: Brownian models of open queueing networks with homogeneous customer populations. Stochastics 22, 77–115 (1987)CrossRef Harrison, J.M., Williams, R.J.: Brownian models of open queueing networks with homogeneous customer populations. Stochastics 22, 77–115 (1987)CrossRef
19.
Zurück zum Zitat Harrison, J.M., Williams, R.J.: Multidimensional reflected Brownian motions having exponential stationary distributions. Ann. Probab. 15, 115–137 (1987)CrossRef Harrison, J.M., Williams, R.J.: Multidimensional reflected Brownian motions having exponential stationary distributions. Ann. Probab. 15, 115–137 (1987)CrossRef
20.
Zurück zum Zitat Hopp, W.J., Iravani, S.M.R., Yuen, G.J.: Operations systems with discretionary task completion. Manag. Sci. 53, 61–77 (2006)CrossRef Hopp, W.J., Iravani, S.M.R., Yuen, G.J.: Operations systems with discretionary task completion. Manag. Sci. 53, 61–77 (2006)CrossRef
21.
Zurück zum Zitat Ivanovs, J., Boxma, O.J., Mandjes, M.R.H.: Singularities of the matrix exponent of a Markov additive process with one-sided jumps. Stoch. Process. Their Appl. 120, 1776–1794 (2010)CrossRef Ivanovs, J., Boxma, O.J., Mandjes, M.R.H.: Singularities of the matrix exponent of a Markov additive process with one-sided jumps. Stoch. Process. Their Appl. 120, 1776–1794 (2010)CrossRef
22.
Zurück zum Zitat Jelenković, P.R., Momčilović, P., Zwart, B.: Reduced load equivalence under subexponentiality. Queueing Syst. 46, 97–112 (2004)CrossRef Jelenković, P.R., Momčilović, P., Zwart, B.: Reduced load equivalence under subexponentiality. Queueing Syst. 46, 97–112 (2004)CrossRef
23.
Zurück zum Zitat Kella, O., Whitt, W.: Diffusion approximations for queues with server vacations. Adv. Appl. Probab. 22, 706–729 (1990)CrossRef Kella, O., Whitt, W.: Diffusion approximations for queues with server vacations. Adv. Appl. Probab. 22, 706–729 (1990)CrossRef
24.
Zurück zum Zitat Kingman, J.F.C.: The single server queue in heavy traffic. Math. Proc. Camb. Philos. Soc. 57, 902–904 (1961)CrossRef Kingman, J.F.C.: The single server queue in heavy traffic. Math. Proc. Camb. Philos. Soc. 57, 902–904 (1961)CrossRef
25.
Zurück zum Zitat Kingman, J.F.C.: The heavy traffic approximation in the theory of queues. In: Smith, W.L., Wilkinson, W.E. (eds.) Proceedings of the Symposium on Congestion Theory, pp. 137–159. University of North Carolina Press, Chapel Hill (1965) Kingman, J.F.C.: The heavy traffic approximation in the theory of queues. In: Smith, W.L., Wilkinson, W.E. (eds.) Proceedings of the Symposium on Congestion Theory, pp. 137–159. University of North Carolina Press, Chapel Hill (1965)
26.
Zurück zum Zitat Kosiński, K.M., Boxma, O.J., Zwart, B.: Convergence of the all-time supremum of a Lévy process in the heavy-traffic regime. Queueing Syst. 67, 295–304 (2011)CrossRef Kosiński, K.M., Boxma, O.J., Zwart, B.: Convergence of the all-time supremum of a Lévy process in the heavy-traffic regime. Queueing Syst. 67, 295–304 (2011)CrossRef
27.
Zurück zum Zitat Mahabhashyam, S.R., Gautam, N.: On queues with Markov modulated service rates. Queueing Syst. 51, 89–113 (2005)CrossRef Mahabhashyam, S.R., Gautam, N.: On queues with Markov modulated service rates. Queueing Syst. 51, 89–113 (2005)CrossRef
28.
Zurück zum Zitat Mitra, D.: Stochastic theory of a fluid model of producers and consumers coupled by a buffer. Adv. Appl. Probab. 20, 646–676 (1988)CrossRef Mitra, D.: Stochastic theory of a fluid model of producers and consumers coupled by a buffer. Adv. Appl. Probab. 20, 646–676 (1988)CrossRef
29.
Zurück zum Zitat Núñez-Queija, R.: A queueing model with varying service rate for ABR. In: Puigjaner, R., Savino, N.N., Serra, B. (eds.) Proceedings of the 10th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, pp. 93–104. Springer, Berlin (1998)CrossRef Núñez-Queija, R.: A queueing model with varying service rate for ABR. In: Puigjaner, R., Savino, N.N., Serra, B. (eds.) Proceedings of the 10th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, pp. 93–104. Springer, Berlin (1998)CrossRef
30.
Zurück zum Zitat Purdue, P.: The M/M/1 queue in a Markovian environment. Oper. Res. 22, 562–569 (1974)CrossRef Purdue, P.: The M/M/1 queue in a Markovian environment. Oper. Res. 22, 562–569 (1974)CrossRef
31.
Zurück zum Zitat Revuz, D., Yor, M.: Continuous Martingales and Brownian Motion. Springer, New York (1999)CrossRef Revuz, D., Yor, M.: Continuous Martingales and Brownian Motion. Springer, New York (1999)CrossRef
32.
Zurück zum Zitat Shneer, S., Wachtel, V.: A unified approach to the heavy-traffic analysis of the maximum of random walks. Theory Probab. Appl. 55, 332–341 (2011)CrossRef Shneer, S., Wachtel, V.: A unified approach to the heavy-traffic analysis of the maximum of random walks. Theory Probab. Appl. 55, 332–341 (2011)CrossRef
33.
Zurück zum Zitat Siebert, F.: Real-time garbage collection in multi-threaded systems on a single processor. In: Proceedings of the 20th IEEE Real-Time Systems Symposium, pp. 277–278 (1999) Siebert, F.: Real-time garbage collection in multi-threaded systems on a single processor. In: Proceedings of the 20th IEEE Real-Time Systems Symposium, pp. 277–278 (1999)
34.
Zurück zum Zitat Steichen, J.L.: A functional central limit theorem for Markov additive processes with an application to the closed Lu-Kumar network. Stoch. Models 17, 459–489 (2001)CrossRef Steichen, J.L.: A functional central limit theorem for Markov additive processes with an application to the closed Lu-Kumar network. Stoch. Models 17, 459–489 (2001)CrossRef
35.
Zurück zum Zitat Stidham Jr, S., Weber, R.R.: Monotonic and insensitive optimal policies for control of queues with undiscounted costs. Oper. Res. 37, 611–625 (1989)CrossRef Stidham Jr, S., Weber, R.R.: Monotonic and insensitive optimal policies for control of queues with undiscounted costs. Oper. Res. 37, 611–625 (1989)CrossRef
36.
Zurück zum Zitat Takács, L.: Introduction to the Theory of Queues. Oxford University Press, New York (1962) Takács, L.: Introduction to the Theory of Queues. Oxford University Press, New York (1962)
37.
Zurück zum Zitat Takine, T.: Single-server queues with Markov-modulated arrivals and service speed. Queueing Syst. 49, 7–22 (2005)CrossRef Takine, T.: Single-server queues with Markov-modulated arrivals and service speed. Queueing Syst. 49, 7–22 (2005)CrossRef
38.
Zurück zum Zitat Tse, D., Viswanath, P.: Fundamentals of Wireless Communication. Cambridge University Press, Cambridge (2005)CrossRef Tse, D., Viswanath, P.: Fundamentals of Wireless Communication. Cambridge University Press, Cambridge (2005)CrossRef
39.
Zurück zum Zitat Tzenova, E.I., Adan, I.J.B.F., Kulkarni, V.G.: Fluid models with jumps. Stoch. Models 21, 37–55 (2005)CrossRef Tzenova, E.I., Adan, I.J.B.F., Kulkarni, V.G.: Fluid models with jumps. Stoch. Models 21, 37–55 (2005)CrossRef
40.
Zurück zum Zitat van der Mei, R.D., Hariharan, R., Reeser, P.K.: Web server performance modeling. Telecommun. Syst. 16, 361–378 (2001)CrossRef van der Mei, R.D., Hariharan, R., Reeser, P.K.: Web server performance modeling. Telecommun. Syst. 16, 361–378 (2001)CrossRef
41.
Zurück zum Zitat Weber, R.R., Stidham Jr, S.: Optimal control of service rates in networks of queues. Adv. Appl. Probab. 19, 202–218 (1987)CrossRef Weber, R.R., Stidham Jr, S.: Optimal control of service rates in networks of queues. Adv. Appl. Probab. 19, 202–218 (1987)CrossRef
42.
Zurück zum Zitat Whitt, W.: Asymptotic formulas for Markov processes with applications to simulation. Oper. Res. 40, 279–291 (1992)CrossRef Whitt, W.: Asymptotic formulas for Markov processes with applications to simulation. Oper. Res. 40, 279–291 (1992)CrossRef
43.
Zurück zum Zitat Whitt, W.: Stochastic-Process Limits. Springer, New York (2002) Whitt, W.: Stochastic-Process Limits. Springer, New York (2002)
44.
Zurück zum Zitat Zwart, B.: Heavy-traffic asymptotics for the single-server queue with random order of service. Oper. Res. Lett. 33, 511–518 (2004)CrossRef Zwart, B.: Heavy-traffic asymptotics for the single-server queue with random order of service. Oper. Res. Lett. 33, 511–518 (2004)CrossRef
Metadaten
Titel
Heavy-traffic asymptotics for networks of parallel queues with Markov-modulated service speeds
verfasst von
Jan-Pieter L. Dorsman
Maria Vlasiou
Bert Zwart
Publikationsdatum
01.04.2015
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 3-4/2015
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-014-9422-x

Weitere Artikel der Ausgabe 3-4/2015

Queueing Systems 3-4/2015 Zur Ausgabe