Stability of two families of real-time queueing networks

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

Abstrakty

EN

We study open multiclass queueing networks with renewal arrival streams and general service time distributions. Upon arrival to the network, customers from each class are assigned a random deadline drawn from a distribution associated with this class.We show that preemptive subcritical EDF networks with fixed customer routes are stable. We also prove that a broad class of (not necessarily subcritical) networks with reneging and Markovian routing, including EDF, FIFO, LIFO, SRPT, fixed priorities and processor sharing, is stable.

Słowa kluczowe

EN

multiclass queueing networks; deadlines; reneging; stability; fluid model; fluid limits

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2008
• Tom: Vol. 28, Fasc. 2
• Strony: 179--202
• Opis fizyczny: Bibliogr. 23 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] F. Bacelli, P. Boyer and G. Hebuterne, Single server queues with impatient customers, Adv. in Appl. Probab. 16 (1984), pp. 887-905.
• [2] P. Billingsley, Probability and Measure, 2nd edition, Wiley, New York 1986.
• [3] M. Bramson, Instability of FIFO queueing networks, Ann. Appl. Probab. 4 (1994), pp. 414-431.
• [4] M. Bramson, Instability of FIFO queueing networks with quick service times, Ann. Appl. Probab. 4 (1994), pp. 693-718.
• [5] M. Bramson, Convergence to equilibria for fluid models of FIFO queueing networks, Queueing Syst. 22 (1996), pp. 5-45.
• [6] 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.
• [7] M. Bramson, Stability of earliest-due-date, first-served queueing networks, Queueing Syst. 39 (2001), pp. 79-102.
• [8] 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.
• [9] J. G. Dai and G. Weiss, Stability and instability for fluid models of reentrant lines, Math. Oper. Res. 21 (1996), pp. 115-134.
• [10] M. H. A. Davis, Piecewise-deterministic Markov processes: a general class of non-diffusion stochastic models, J. Roy. Statist. Soc. Ser. B 46 (1984), pp. 353-388.
• [11] 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.
• [12] R. K. Getoor, Transience and recurrence of Markov processes, in: Séminaire de Probabilités XIV, Lecture Notes in Math. No. 784, Springer, New York 1980, pp. 397-409.
• [13] W. Hopp and M. Spearman, Factory Physics: Foundations of Manufacturing Management, Irwin, Chicago 1996.
• [14] Ł. 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.
• [15] R. Lillo and M. Mar tin, Stability in queues with impatient customers, Stoch. Models 17 (2001), pp. 375-389.
• [16] S. P. Meyn and D. Down, Stability of generalized Jackson networks, Ann. Appl. Probab. 4 (1994), pp. 124-148.
• [17] S. P. Meyn and R. J. Tweedie, Stability of Markovian processes III: Foster-Lyapunov criteria for continuous-time processes, Adv. in Appl. Probab. 25 (1993), pp. 518-548.
• [18] S. P. Meyn and R. J. Tweedie, State-dependent criteria for convergence of Markov chains, Ann. Appl. Probab. 4 (1994), pp. 149-168.
• [19] A. N. Rybko and A. L. Stolyar, Ergodicity of stochastic processes describing the operations of open queueing networks, Probl. Inf. Transm. 28 (1992), pp. 199-220.
• [20] R. E. Stanford, Reneging phenomena in single channel queues, Math. Oper. Res. 4 (1979), pp. 162-178.
• [21] J. A. Stankovic, M. Spuri, K. Ramamritham and G. C. Buttazzo, Deadline Scheduling for Real-Time Systems, Springer, 1998.
• [22] A. R. Ward and N. Bambos, On stability of queueing networks with job deadlines, J. Appl. Probab. 40 (2003), pp. 293-304.
• [23] 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.