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.
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