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, and that the system is stable. We introduce the largest weighted delay first (LWDF) queueing discipline associated with any given weight vector α = (α₁, . . ., α_N). We show that under the LWDF discipline the sequence of scaled stationary distributions of the delay ŵ_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, ..., N} [α_i ^lim_n→∞ -1/n log P(ŵ_i > n)], within a large class of work conserving disciplines.