Stability of preemptive EDF queueing networks

Łukasz Kruk

Abstract


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.

Keywords


Multiclass queueing networks; deadlines; preemption; stability; fluid models; fluid limits

Full Text:

PDF

References


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

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

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.

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

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

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.

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

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.

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.

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

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

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

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.

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

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

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

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.




DOI: http://dx.doi.org/10.17951/a.2019.73.2.105-134
Date of publication: 2020-01-16 07:29:35
Date of submission: 2019-12-29 16:34:29


Statistics


Total abstract view - 918
Downloads (from 2020-06-17) - PDF - 683

Indicators



Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Łukasz Kruk