Largest Weighted Delay First Scheduling: Large Deviations and Optimality

Abstract

We consider a single server system with N input flows. We assume that each flow has stationary increments and satisfies a sample path large deviation principle, and that the system is stable. We introduce the largest weighted delay first (LWDF) queueing discipline associated with any given weight vector α=(α1,...,αN). We show that under the LWDF discipline the sequence of scaled stationary distributions of the delay \(\hat{w}_{i}\) of each flow satisfies a large deviation principle with the rate function given by a finite- dimensional optimization problem. We also prove that the LWDF discipline is optimal in the sense that it maximizes the quantity $$\min_{i= 1,\space ...,\space N}\left[α_i \lim_{n\to\infty}\frac{−1}{n}\log P(\hat{w}_i>n)\right],$$ within a large class of work conserving disciplines.