Real-Time Queues in Heavy Traffic with
Earliest-Deadline-First Queue Discipline



Bogdan Doytchinov1
John Lehoczky2
Steven Shreve3

September 1, 1999



ABSTRACT

This paper introduces a new aspect of queueing theory, the study of 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, e.g., the fraction of customers who meet their requirements and the distribution of customer lateness. It also focuses on queue control policies to reduce or minimize lateness, although these control aspects are not explicitly addressed in this paper.

To study these measures, one 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 (EDF) 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 which is a non-random function of the limit of the scaled queue length process. Hence, in heavy traffic, one can characterize the system as a diffusion evolving on a one-dimensional manifold of lead-time profiles. Simulation results are presented which indicate that this characterization is surprisingly accurate. A discussion of open research questions is also presented.


Get the paper in its entirety as