Abstract
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 stations,
and there are
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 acccording 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 dtails, and simulation results are
presented to illustrate the predictive value of the theory. This work
is a generalization of Doytchinov, Lehoczky and Shreve [5], which
developed these results for the single queue case.
Get the paper in its entirety as