Performance of Low-Complexity Greedy Scheduling Policies in Multi-Channel Wireless Networks: Optimal Throughput and Near-Optimal Delay

Bo Ji, Gagan Raj Gupta, Xiaojun Lin, Ness B. Shroff

Abstract

In this paper, we focus on the scheduling problem in multi-channel 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^{2.5} \log n)$-complexity hybrid scheduling policies are 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^2+2n$, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, we show that the rate-function attained by D-SSG for any delay-violation threshold $b$, 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^{2.5} \log n)$ of the hybrid policies to $2n^2 + 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(\cdot)$ notation. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that D-SSG not only guarantees a near-optimal rate-function, but also empirically is virtually indistinguishable from delay-optimal policies.

Introduction

In modern wireless systems like 4G LTE or WiMax, a base station must decide every millisecond (the Transmission Time Interval, or TTI) which users get which frequency channels. This is a massive scheduling challenge: you might have hundreds of users and hundreds of channels. Ideally, a scheduling policy should be throughput-optimal, delay-optimal, and low complexity.

Previous "delay-optimal" policies, like Delay Weighted Matching (DWM), are computationally expensive ($O(n^5)$ complexity), making them impractical for real-world hardware. Even newer "hybrid" policies are complex ($O(n^{2.5} \log n)$). The gap addressed here is the need for a policy that is simple enough for actual implementation while maintaining rigorous performance guarantees.

System Model

The network is modeled as a system with $n$ queues (representing users) and $n$ servers (representing frequency channels). Each queue $Q_i$ stores packets for user $i$, and each server $S_j$ can serve one packet per time slot. The connectivity between queues and servers is dynamic, often modeled as ON-OFF channels.

Figure 1: Bipartite matching model between queues $Q_n$ and servers $S_n$ in a multi-channel wireless network.

The D-SSG Policy

The authors propose the Delay-based Server-Side-Greedy (D-SSG) policy. Instead of solving a complex global optimization (like a maximum weight matching), D-SSG works iteratively. In each time-slot, it looks at the available channels (servers) one by one. Each channel is assigned to the connected user whose "Head-of-Line" (HOL) packet has been waiting the longest. Crucially, the algorithm updates the state after each assignment so the next channel doesn't try to serve a packet that was just picked.

To prove this works, the authors use Large Deviations Theory, looking at the "rate-function" (the decay rate of the probability that delay exceeds a threshold). They introduce an analytical tool called G-FBS (Greedy Frame-Based Scheduling) to show that D-SSG is near-optimal and always performs at least as well as G-FBS on every possible sample path.

Performance and Results

D-SSG achieves a significant complexity reduction to $2n^2 + 2n$. In practical tests with 100 users/channels, D-SSG ran 7 to 10 times faster than previous hybrid policies. On a standard PC (3.4GHz CPU), D-SSG finished its 100-user scheduling task in ~0.3ms, well within the 1ms requirement for LTE systems.

Mathematically, D-SSG is proven to be throughput-optimal under general Markovian arrival processes. Regarding delay, the authors prove that D-SSG's performance for a threshold $b$ is at least as good as the best possible policy's performance for threshold $b-1$. In simulations, D-SSG’s delay curves were almost indistinguishable from the much more complex DWM and Hybrid policies, consistently outperforming other low-complexity alternatives like D-MWS or Q-SSG.

Conclusion and Future Work

D-SSG provides a practical solution for real-time 4G/5G hardware without sacrificing significant performance. However, current theoretical proofs assume "unit capacity" (one packet per channel). Real-world 5G channels have variable rates (Adaptive Modulation and Coding). Extending these proofs to multi-rate channels ($0-K$ packets) remains a significant challenge for future work. Future directions include exploring how to design "delay-optimal" policies that still maintain this low $O(n^2)$ complexity, especially in scenarios with heterogeneous QoS requirements.

Summary updated

Abstract

In this paper, we focus on the scheduling problem in multi-channel 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^{2.5} \log n)$-complexity hybrid scheduling policies are 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^2+2n$, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, we show that the rate-function attained by D-SSG for any delay-violation threshold $b$, 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^{2.5} \log n)$ of the hybrid policies to $2n^2 + 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(\cdot)$ notation. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that D-SSG not only guarantees a near-optimal rate-function, but also empirically is virtually indistinguishable from delay-optimal policies.
BibTeX
@article{ji2015performance,
  author = {Bo Ji and Gagan Raj Gupta and Xiaojun Lin and Ness B. Shroff},
  title = {{Performance of Low-Complexity Greedy Scheduling Policies in Multi-Channel Wireless Networks: Optimal Throughput and Near-Optimal Delay}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2015},
  url = {https://openreview.net/forum?id=Yeyb9drIcU},
}
Figure