Real-time queues in heavy traffic with earliest-deadline-first queue discipline.

*(English)*Zbl 1015.60086From the authors’ summary: This paper studies systems that service customers with specific timing requirements (e.g., due dates or deadlines). Unlike standard queueing theory in which common performance measures are customer delay, queue length and server utilization, real-time queueing theory focuses on the ability of a queue discipline to meet customer timing requirements, for example, the fraction of customers who meet their requirements and the distribution of customer lateness.

To study these measures, we must keep track of the lead times (deadline minus current time) of each customer; hence, the system state is of unbounded dimension. A heavy traffic analysis is presented for the earliest-deadline-first scheduling policy. This analysis decomposes the behavior of the real-time queue into two parts: the number in the system (which converges weakly to a reflected Brownian motion with drift) and the set of lead times given the queue length. The lead-time profile has a limit that is a nonrandom function of the limit of the scaled queue length process. Hence, in heavy traffic, the system can be characterized as a diffusion evolving on a one-dimensional manifold of lead-time profiles. Simulation results are presented that indicate that this characterization is surprisingly accurate. A discussion of open research questions is also presented.

To study these measures, we must keep track of the lead times (deadline minus current time) of each customer; hence, the system state is of unbounded dimension. A heavy traffic analysis is presented for the earliest-deadline-first scheduling policy. This analysis decomposes the behavior of the real-time queue into two parts: the number in the system (which converges weakly to a reflected Brownian motion with drift) and the set of lead times given the queue length. The lead-time profile has a limit that is a nonrandom function of the limit of the scaled queue length process. Hence, in heavy traffic, the system can be characterized as a diffusion evolving on a one-dimensional manifold of lead-time profiles. Simulation results are presented that indicate that this characterization is surprisingly accurate. A discussion of open research questions is also presented.

Reviewer: E.A.van Doorn (Enschede)

##### MSC:

60K25 | Queueing theory (aspects of probability theory) |

60G57 | Random measures |

60J65 | Brownian motion |

90B22 | Queues and service in operations research |

PDF
BibTeX
XML
Cite

\textit{B. Doytchinov} et al., Ann. Appl. Probab. 11, No. 2, 332--378 (2001; Zbl 1015.60086)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York. · Zbl 0172.21201 |

[2] | Coffman, E. G., Jr., Puhalskii, A. A. and Reiman, M. I. (1995). Polling systems with zero switchover times: A heavy traffic-traffic averaging principle. Ann. Appl. Probab. 5 681-719. · Zbl 0842.60088 |

[3] | Doytchinov, B. (1997). Heavy traffic limits of queues with due dates. Ph.D. dissertation, Dept. Mathematical Sciences, Carnegie Mellon Univ. |

[4] | Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes. Characterization and Convergence. Wiley, New York. · Zbl 0592.60049 |

[5] | Harrison, J. M. (1973). A limit theorem for priority queues in heavy traffic. J. Appl. Probab. 10 907-912. JSTOR: · Zbl 0281.60109 |

[6] | Harrison, J. M. (1985). Brownian Motion and Stochastic Flow Systems. Wiley, New York. · Zbl 0659.60112 |

[7] | Harrison, J. M. (1988). Brownian models of queueing networks with heterogeneous customer populations. In Proceedings of the IMA Workshop on Stochastic Differential Systems 147-186. Springer, New York. · Zbl 0658.60123 |

[8] | Harrison, J. M. and Nguyen, V. (1993). Brownian models of multiclass queueing networks: Current status and open problems. Queueing Systems Theory Appl. 13 5-40. · Zbl 0781.60090 |

[9] | Harrison, J. M. and Wein, L. J. (1990). Scheduling networks of queues: Heavy traffic analysis of a two-station closed network. Oper. Res. 38 1052-1064. JSTOR: · Zbl 0723.90026 |

[10] | Hong, J., Tan, X. and Towsley, D. (1989). A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system. IEEE Trans. Comput. 38 1736-1744. · Zbl 1395.68070 |

[11] | Hooke, J. (1970). On some limit theorems for the GI/G/1 queue. J. Appl. Probab. 7 634-640. JSTOR: · Zbl 0206.22403 |

[12] | Iglehart, D. and Whitt, W. (1970). Multiple channel queues in heavy traffic I. Adv. in Appl. Probab. 2 150-177. JSTOR: · Zbl 0218.60098 |

[13] | Iglehart, D. and Whitt, W. (1970). Multiple channel queues in heavy traffic II. Adv. in Appl. Probab. 2 355-364. JSTOR: · Zbl 0218.60098 |

[14] | Kingman, J. F. C. (1961). The single server queue in heavy traffic. Proceedings of the Cambridge Philosophical Society 48 277-289. · Zbl 0114.11703 |

[15] | Klein, M., Ralya, T., Pollak, B., Obenza, R. and Gonzalez-Harbour, M. (1993). A Practitioner’s Handbook for Real-Time Analysis. Kluwer, Dordrecht. |

[16] | Kyprianou, E. (1971). The virtual waiting time of the GI/G/1 queue in heavy traffic. Adv. in Appl. Probab. 3 249-268. JSTOR: · Zbl 0235.60091 |

[17] | Lehoczky, J. P. (1996). Real-time queueing theory. In Proceedings of the IEEE Real-Time Systems Symposium 186-195. IEEE, New York. |

[18] | Lehoczky, J. P. (1997). Using real-time queueing theory to control lateness in real-time systems. Performance Evaluation Review 25 158-168. |

[19] | Lehoczky, J. P. (1997). Real-time queueing network theory. In Proceedings of the IEEE Real-Time Systems Symposium 58-67. IEEE, New York. |

[20] | Liu, C. L. and Layland, J. W. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment. J. Assoc. Comput. Mach. 20(1) 40-61. · Zbl 0265.68013 |

[21] | Markowitz, D. M. and Wein, L. M. (1996). Heavy traffic analysis of dynamic cyclic policies: A unified treatment of the single machine scheduling problem. Preprint, Sloan School of Management, MIT. JSTOR: · Zbl 1163.90499 |

[22] | Panwar, S. and Towsley, D. (1988). On the optimality of the STE rule for multiple server queues that serve customers with deadlines. Technical Report 88-81, Dept. Computer and Information Science, Univ. Massachusetts, Amherst. |

[23] | Parthasarathy, K. R. (1967). Probability Measures on Metric Spaces, Academic Press, New York. · Zbl 0153.19101 |

[24] | Peterson, W. P. (1991). A heavy traffic limit theorem for networks of queues with multiple customer types. Math. Oper. Res. 16 90-118. JSTOR: · Zbl 0727.60114 |

[25] | Prokhorov, Yu. (1956). Convergence of randomprocesses and limit theorems in probability theory. Theory Probab. Appl. 1 157-214. · Zbl 0075.29001 |

[26] | Reiman, M. (1983). Some diffusion approximations with state space collapse. In Proceedings of the International Seminar on Modeling and Performance Evaluation Methodology. Springer, Berlin. · Zbl 0545.60089 |

[27] | Reiman, M. (1988). A multiclass feedback queue in heavy traffic. Adv. in Appl. Probab. 20 179-207. JSTOR: · Zbl 0647.60100 |

[28] | Van Mieghem, J. A. (1995). Dynamic scheduling with convex delay costs: The generalized c\mu rule. Ann. Appl. Probab. 5 809-833. · Zbl 0843.90047 |

[29] | Wein, L. J. (1990). Scheduling networks of queues: Heavy traffic analysis of a two-station network with controllable inputs. Oper. Res. 38 1065-1078. JSTOR: · Zbl 0724.90025 |

[30] | Whitt, W. (1971). Weak convergence theorems for priority queues: Preemptive-resume discipline. J. Appl. Probab. 8 74-94. JSTOR: · Zbl 0215.53801 |

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.