Scheduling in multi-channel wireless networks: Rate function optimality in the small-buffer regime

The problem of designing scheduling algorithms for a multichannel (e.g., orthogonal frequency division multiplexing-based) wireless downlink network is considered. The classic MaxWeight algorithm, although throughput-optimal, results in a very poor per-user delay performance in such systems. Hence, an alternate class of algorithms called iterated longest queues first (iLQF) is proposed for overcoming this issue. The iLQF-class algorithms are analyzed in a number of different system configurations. A particular algorithm in this class, called iLQF with pullup, is shown to be rate function optimal for the problem in an appropriate large deviations setting, and is shown to result in a strictly positive value of the rate function for a number of modifications to the basic system model. Thus, the proposed algorithm yields provable performance guarantees. The analytic results are confirmed through simulations.