Largest Weighted Delay First Scheduling Large Deviations and Optimality

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. We introduce the Largest Weighted Delay First (LWDF) queueing discipline associated with any given weight vector alpha = (alpha sub 1,...,alpha sub N). We show that under the LWDF discipline, the sequence of scaled stationary distributions of the delay W sub i of each flow satisfy a large deviation principle with the rate function given by a finite-dimensional variational problem. We also prove that the LWDF discipline is optimal in the sense that it maximizes the quantity min over i=1,...,N [alpha sub i lim over n->inf -1 over n log P (W sub i>n)], amongst a large class of work conserving disciplines.