Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multichannel Wireless Networks With Low Complexity: A Practical Greedy Scheduling Policy

Bo Ji, Gagan Gupta, Manu Sharma, Xiaojun Lin, Ness B. Shroff

Abstract

In this paper, we focus on the scheduling problem in multichannel wireless networks, e.g., the downlink of a single cell in fourth-generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.5</sup> log n)-complexity hybrid scheduling policies is recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a lower complexity 2n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> +2n, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, the rate-function of the delay-violation probability attained by D-SSG for any fixed integer delay threshold b > 0 is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Thus, we are able to achieve a reduction in complexity (from O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.5</sup> logn) of the hybrid policies to 2n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> + 2n) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the O(·) notation. Finally, we conduct simulations to validate our theoretical results in various scenarios. The simulation results show that in all scenarios we consider, D-SSG not only guarantees a near-optimal rate-function, but also empirically has a similar delay performance to the rate-function delay-optimal policies.
BibTeX
@article{ji2015achieving,
  author = {Bo Ji and Gagan Gupta and Manu Sharma and Xiaojun Lin and Ness B. Shroff},
  title = {{Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multichannel Wireless Networks With Low Complexity: A Practical Greedy Scheduling Policy}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2015},
  url = {https://openreview.net/forum?id=Yeyb9drIcU},
}

Loading related content...

Figure