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, for example, 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, we must keep track of the lead times (dead-line 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 re flected
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.