Delay differentiation by optimal-balancing-of-queue-lengths scheduling

Scheduling policies adopted for statistical multiplexing should provide delay differentiation between different traffic classes, where each class represents an aggregate traffic of individual applications having the same target queueing delay requirement. We propose scheduling to optimally balance queue lengths as an approach to delay differentiation. in particular, we assume a discrete-time, two-class, single-server queueing model with unit service time per packet. We find a scheduling policy that we show to be discounted-cost optimal, for Bernoulli packet arrivals using dynamic programming analysis and for i.i.d. batch arrivals using a step-wise cost-dominance analytical approach. We then use cumulative queue length state variables in the one-step cost function of the optimization formulation and obtain the next-stage optimal policy. Simulations show that this policy achieves long-term mean queueing delays closer to the respective target delays than the first policy, and also achieves smaller errors in short-term mean queueing delays than the Coffman-Mitrani policy.