Earliest-deadline-first service in heavy-traffic acyclic networks. (English) Zbl 1084.60056

Summary: This paper presents a heavy traffic analysis of the behavior of multi-class acyclic queueing networks in which the customers have deadlines. We assume the queueing system consists of \(J\) stations, and there are \(K\) different customer classes. Customers from each class arrive to the network according to independent renewal processes. The customers from each class are assigned a random deadline drawn from a deadline distribution associated with that class and they move from station to station according to a fixed acyclic route. The customers at a given node are processed according to the earliest-deadline-first (EDF) queue discipline. At any time, the customers of each type at each node have a lead time, the time until their deadline lapses. We model these lead times as a random counting measure on the real line. Under heavy traffic conditions and suitable scaling, it is proved that the measure-valued lead-time process converges to a deterministic function of the workload process. A two-station example is worked out in detail, and simulation results are presented to illustrate the predictive value of the theory. This work is a generalization of B. Doytchinov, J. Lehoczky and S. Shreve [Ann. Appl. Probab. 11, 332–378 (2001; Zbl 1015.60086)], which developed these results for the single queue case.


60K25 Queueing theory (aspects of probability theory)
60G57 Random measures
60J65 Brownian motion
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems


Zbl 1015.60086
Full Text: DOI arXiv


[1] Billingsley, P. (1986). Probability and Measure , 2nd ed. Wiley, New York. · Zbl 0649.60001
[2] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[3] Bourbaki, N. (1966). General Topology 1 . Addison–Wesley, Reading, MA. · Zbl 0145.19302
[4] Bramson, M. (2004). Stability of earliest-due-date, first-served queueing networks. Queueing Syst. Theory Appl. · Zbl 0995.60087
[5] Doytchinov, B., Lehoczky, J. P. and Shreve, S. E. (2001). Real-time queues in heavy traffic with earliest-deadline-first queue discipline. Ann. Appl. Probab. 11 332–379. · Zbl 1015.60086
[6] Ethier, S. N. and Kurtz, T. G. (1985). Markov Processes : Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[7] Harrison, J. M. (1995). Balanced fluid models of multiclass queueing networks: A heavy traffic conjecture. In Stochastic Networks (F. P. Kelly and R. Williams, eds.) 1–20. Springer, New York. · Zbl 0838.90045
[8] Kruk, Ł., Lehoczky, J. P., Shreve, S. E. and Yeung, S. N. (2003). Multiple-input heavy-traffic real-time queues. Ann. Appl. Probab. 13 54–99. · Zbl 1046.60082
[9] Lehoczky, J. P. (1997). Using real-time queueing theory to control lateness in real-time systems. Performance Evaluation Review 25 158–168.
[10] Lehoczky, J. P. (1998). Real-time queueing theory. In Proceedings of the IEEE Real-Time Systems Symposium 186–195.
[11] Lehoczky, J. P. (1998). Scheduling communication networks carrying real-time traffic. In Proceedings of the IEEE Real-Time Systems Symposium 470–479.
[12] Markowitz, D. M. and Wein, L. M. (2001). Heavy traffic analysis of dynamic cyclic policies: A unified treatment of the single machine scheduling problem. Oper. Res. 49 246–270. · Zbl 1163.90499
[13] Peterson, W. P. (1991). A heavy traffic limit theorem for networks of queues with different customer types. Math. Oper. Res. 16 90–118. · Zbl 0727.60114
[14] Prokhorov, Yu. (1956). Convergence of random processes and limit theorems in probability theory. Theory Probab. Appl. 1 157–214. · Zbl 0075.29001
[15] Van Mieghem, J. A. (1995). Dynamic scheduling with convex delay costs: The generalized \(c\mu\) rule. Ann. Appl. Probab. 5 809–833. JSTOR: · Zbl 0843.90047
[16] Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems Theory Appl. 30 27–88. · Zbl 0911.90171
[17] Yeung, S. N. and Lehoczky, J. P. (2002). Real-time queueing networks in heavy traffic with EDF and FIFO queue discipline. Working paper, Dept. Statistics, Carnegie Mellon Univ.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.