Paper Info
Title
Towards optimal priority and deadline driven scheduling in dynamic wireless environments
Abstract
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.
Year
DOI
Venue
2015
10.1109/WoWMoM.2015.7158128
2015 IEEE 16th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM)
Keywords
Field
DocType
Delay and priority driven scheduling,Markov decision process,wireless networks
Computer science,Deadline-monotonic scheduling,Computer network,Priority inversion,Rate-monotonic scheduling,Maximum throughput scheduling,Weighted fair queueing,Earliest deadline first scheduling,Dynamic priority scheduling,Round-robin scheduling,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
17
Authors
4
Name
Order
Citations
PageRank
Viral Patel110.70
Nicholas Mastronarde224026.93
Michael J. Medley333726.06
John D. Matyjas455443.69