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

• 02-CNA-012.ps
• 02-CNA-012.pdf