Invariant states for fluid models of EDF networks : nonlinear lifting map

• Autorzy: Kruk Ł.
• Języki publikacji: EN

Abstrakty

EN

We study fluid models of an open, subcritical multiclass queueing network with the earliest-deadline-first (EDF) service discipline and we provide a characterization of the corresponding invariant manifold. We show that the invariant states exhibit nonlinear state space collapse. Consequences of these findings for diffusion limits for EDF queueing networks are also discussed.

Słowa kluczowe

EN

multiclass queueing networks; fluid model; deadlines; invariant states; state space collapse; lifting map

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2010
• Tom: Vol. 30, Fasc. 2
• Strony: 289--315
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Kruk Ł.

• Institute of Mathematics, Maria Curie-Skłodowska University, pl. Marii Curie-Skłodowskiej 1, 20-031 Lublin, Poland

Bibliografia

• [1] M. Bramson, Convergence to equilibria for fluid models of FIFO queueing networks, Queueing Syst. 22 (1996), pp. 5-45.
• [2] M. Bramson, Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks, Queueing Syst. 23 (1996), pp. 1-26.
• [3] M. Bramson, State space collapse with application to heavy traffic limits for multiclass queueing networks, Queueing Syst. 30 (1998), pp. 89-148.
• [4] M. Bramson, Stability of earliest-due-date, first-served queueing networks, Queueing Syst. 39 (2001), pp. 79-102.
• [5] M. Bramson and J. G. Dai, Heavy traffic limit theorems for some queueing networks, Ann. Appl. Probab. 11 (2001), pp. 49-90.
• [6] J. G. Dai, On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models, Ann. Appl. Probab. 5 (1995), pp. 49-77.
• [7] B. Doytchinov, J. P. Lehoczky and S. E. Shreve, Real-time queues in heavy traffic with earliest-deadline-first queue discipline, Ann. Appl. Probab. 11 (2001), pp. 332-379.
• [8] H. C. Gromoll, Diffusion approximation for a processor sharing queue in heavy traffic, Ann. Appl. Probab. 14 (2004), pp. 555-611.
• [9] H. C. Gromoll, A. L. Puha and R. J. Williams, The fluid limit of a heavily loaded processor sharing queue, Ann. Appl. Probab. 12 (2002), pp. 797-859.
• [10] J. M. Harrison, Balanced fluid models of multiclass queueing networks: a heavy traffic conjecture, in: Stochastic Networks, IMA Vol. Math. Appl. 71, Springer, New York 1995, pp. 1-20.
• [11] J. M. Harrison and R. J. Williams, A multiclass closed queueing network with unconventional heavy traffic behavior, Ann. Appl. Probab. 6 (1996), pp. 1-47.
• [12] W. Hopp and M. Spearman, Factory Physics: Foundations of Manufacturing Management, Irwin, Chicago 1996.
• [13] Ł. Kruk, Stability of two families of real-time queueing networks, Probab. Math. Statist. 28 (2008), pp. 179-202.
• [14] Ł. Kruk, An open queueing network with asymptotically stable fluid model and unconventional heavy traffic behavior, preprint.
• [15] Ł. Kruk, J. P. Lehoczky, K. Ramanan and S. E. Shreve, Heavy traffic analysis for EDF queues with reneging, Ann. Appl. Probab., to appear.
• [16] Ł. Kruk, J. P. Lehoczky, S. E. Shreve and S.-N. Yeung, Multiple-input heavy-traffic real-time queues, Ann. Appl. Probab. 13 (2003), pp. 54-99.
• [17] Ł. Kruk, J. P. Lehoczky, S. E. Shreve and S.-N. Yeung, Earliest-deadline-first service in heavy traffic acyclic networks, Ann. Appl. Probab. 14 (2004), pp. 1306-1352.
• [18] A. L. Puha and R. J. Williams, Invariant states and rates of convergence for a critical fluid model of a processor sharing queue, Ann. Appl. Probab. 14 (2004), pp. 517-554.
• [19] J. A. Stankovic, M. Spuri, K. Ramamritham and G. C. Buttazzo, Deadline Scheduling for Real-Time Systems, Springer, 1998.
• [20] R. J. Williams, An invariance principle for semimartingale reflecting Brownian motions in an orthant, Queueing Syst. 30 (1998), pp. 5-25.
• [21] R. J. Williams, Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse, Queueing Syst. 30 (1998), pp. 27-88.
• [22] S.-N. Yeung and J. P. Lehoczky, Real-time queueing networks in heavy traffic with EDF and FIFO queue discipline, working paper, 2001, Department of Statistics, Carnegie Mellon University.