Stability of preemptive EDF queueing networks

Kruk, Łukasz

Annales Universitatis Mariae Curie-Skłodowska. Mathematica , Tome 73 (2019) no. 2.

Résumé

We show stability of preemptive, strictly subcritical EDF networks with Markovian routing. To this end, we prove that the associated fluid limits satisfy the first-in-system, first-out (FISFO) fluid model equations and thus, by an extension of a result of Bramson (2001), the corresponding fluid models are stable. We also demonstrate that in a preemptive multiclass EDF network, after a time large enough to process all the initial customers to completion, the maximal number of partially served customers in the system over a finite time horizon converges to zero in L^1 under fluid scaling.

Détail

Keywords: Multiclass queueing networks, deadlines, preemption, stability, fluid models, fluid limits

Bibliographie

[1] Billingsley, P., Probability and Measure, 2nd Edition, Wiley, New York, 1986.

[2] Bramson, M., Convergence to equilibria for fluid models of FIFO queueing networks, Queueing Syst. Theory Appl. 22 (1996), 5–45.

[3] Bramson, M., Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks, Queueing Syst. Theory Appl. 23 (1996), 1–26.

[4] Bramson, M., State space collapse with application to heavy traffic limits for multiclass queueing networks, Queueing Syst. Theory Appl. 30 (1998), 89–148.

[5] Bramson, M., Stability of earliest-due-date, first-served queueing networks, Queueing Syst. Theory Appl. 39 (2001), 79–102.

[6] Dai, J. G., On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models, Ann. Appl. Probab. 5 (1995), 49–77.

[7] Dai, J. G., Weiss, G., Stability and instability for fluid models of reentrant lines, Math. Oper. Res. 21 (1996), 115–134.

[8] Davis, M. H. A., Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models, Journal of the Royal Statistical Society. Series B 46 (1984), 353–388.

[9] Doytchinov, B., Lehoczky, J. P., Shreve, S. E., Real-time queues in heavy traffic with earliest-deadline-first queue discipline, Ann. Appl. Probab. 11 (2001), 332–379.

[10] Getoor, R. K., Transience and recurrence of Markov processes, Seminaire de Probabilites XIV 284, 397–409, Springer, New York, 1979.

[11] Kruk, Ł, Stability of two families of real-time queueing networks, Probab. Math. Stat. 28 (2008), 179–202.

[12] Kruk, Ł, Invariant states for fluid models of EDF networks: nonlinear lifting map, Probab. Math. Stat. 30 (2010), 289–315.

[13] Kruk, Ł, Lehoczky, J. P., Shreve, S. E., Yeung, S.-N., Earliest-deadline-first service in heavy traffic acyclic networks, Ann. Appl. Probab. 14 (2004), 1306–1352.

[14] Meyn, S. P., Down, D., Stability of generalized Jackson networks, Ann. Appl. Probab. 4 (1994), 124–148.

[15] Rybko, A. N., Stolyar, A. L., Ergodicity of stochastic processes describing the operations of open queueing networks, Probl. Inf. Transm. 28 (1992), 199–220.

[16] Williams, R. J., Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse, Queueing Syst. Theory Appl. 30 (1998), 27–88.

[17] Yeung, S.-N., Lehoczky, J. P., Real-time queueing networks in heavy traffic with EDF and FIFO queue discipline, working paper, Department of Statistics, Carnegie Mellon University.