Towards optimal priority and deadline driven scheduling in dynamic wireless environments

We formulate the problem of point-to-point scheduling at a congested network node as a Markov decision process (MDP) that considers the deadlines and priorities of each packet as well as the dynamic packet arrivals and channel conditions. Within this framework, we formulate the problem with the objective of maximizing the node's long-run priority-weighted throughput subject to instantaneous transmission rate constraints. We then analyze the structural properties of the optimal scheduling policy with respect to the deadlines and priorities of the backlogged packets. Additionally, we compare our approach to existing heuristics such as Priority Queueing (PQ), Earliest Deadline First (EDF), and Weighted Fair Queueing (WFQ). Our MDP-based approach outperforms all three heuristics not only because it takes into account the packets' priorities and deadlines, but also because it takes into account the future channel and packet arrival dynamics. Lastly, we experimentally show that the optimal scheduling policy has a switch-over type structure in several key parameters including the relative priorities of different traffic classes, the discount factor, and the traffic load intensity.