The Stability of Longest-Queue-First Scheduling With Variable Packet Sizes

It is well known that the MaxWeight scheduling algorithm is throughput-optimal in wireless networks. However, its complexity is exponential in the number of links in an ad hoc network. In this work, we consider a greedy variant of the MaxWeight algorithm, called Longest Queue First (LQF). A synchronous version of LQF is known to be throughput optimal under a topological condition called local pooling. Here we study an asynchronous version of LQF which is suitable for implementation in networks with variable packet sizes.We show that asynchronous LQF is also throughput-optimal under the local pooling condition.AFOSR Grant FA-9550-08-1-0432, ARO MURI W911NF-08-1-0233, ARO MURI W911NF-07-1-0287, and AFOSR MURI FA9550-10-1-0573.published or submitted for publicationis peer reviewe