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

TL;DR

This paper introduces D-SSG (Delay-based Server-Side-Greedy), a scheduling policy for multi-channel wireless networks that achieves the "holy trinity" of network performance: optimal throughput, near-optimal delay, and low computational complexity. By replacing heavy matching algorithms with a simple iterative greedy approach, the authors provide a solution that is fast enough for real-time 4G/5G hardware without sacrificing significant performance.

What Problem Does This Paper Address?

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:

  1. Throughput-Optimal: It can handle any data load that is physically possible for the network to support.
  2. Delay-Optimal: It keeps packet waiting times as short as possible.
  3. Low Complexity: It must run fast enough to make a decision within that 1ms window.

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.

Methods

The authors propose the Delay-based Server-Side-Greedy (D-SSG) policy.

  • The Algorithm: 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.
  • Analytical Framework: To prove this works, the authors use Large Deviations Theory. They look at the "rate-function" (the decay rate of the probability that delay exceeds a threshold).
  • The "Proxy" Policy: To prove D-SSG’s delay performance, they introduce an analytical tool called G-FBS (Greedy Frame-Based Scheduling). They show that G-FBS is near-optimal and that D-SSG always performs at least as well as G-FBS on every possible sample path.

Datasets

The paper does not use real-world datasets. Instead, it relies on extensive numerical simulations implemented in Java to validate the theoretical results.

  • Traffic Models: They used i.i.d. Bernoulli arrivals and bursty traffic driven by two-state Markov chains.
  • Channel Models: They simulated i.i.d. ON-OFF channels and more realistic "near-user/far-user" heterogeneous scenarios with time-correlated fading.
  • Scale: Simulations were run for systems with up to $n=100$ users and $n=100$ channels.

Key Insights and Ideas

  • Iterative Greedy is "Good Enough": The biggest "aha moment" is that you don't need a perfect matching to get near-optimal delay. By simply being greedy in an iterative fashion, you capture most of the benefits of much more complex algorithms.
  • The "One-Step" Delay Shift: The authors prove that D-SSG's delay performance for a threshold $b$ is at least as good as the best possible policy's performance for threshold $b-1$. This "minimal drop" in performance is the small price paid for a massive leap in speed.
  • Server-Side vs. Queue-Side: The paper demonstrates a sample-path equivalence between picking the best user for a server (Server-Side) and picking the best server for a user (Queue-Side), which simplifies the mathematical proofs significantly.

Key Results

  • Complexity Reduction: D-SSG has a complexity of $2n^2 + 2n$. In practical tests with 100 users/channels, D-SSG ran 7 to 10 times faster than previous hybrid policies.
  • Throughput: Mathematically proven to be throughput-optimal under general Markovian arrival processes.
  • Delay Performance: 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.
  • Real-world Feasibility: 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.

Limitations and Future Work

  • Unit Capacity Assumption: The current theoretical proofs assume "unit capacity" (one packet per channel). Real-world 5G channels have variable rates (AMC - Adaptive Modulation and Coding). The authors note that extending these proofs to multi-rate channels ($0-K$ packets) is a significant challenge for future work.
  • Simple Channel Models: While simulations covered heterogeneous users, the core proofs rely on an i.i.d. ON-OFF channel model.
  • Future Directions: The authors suggest exploring how to design "delay-optimal" (not just near-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 efficient scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a recently developed scheduling policy, called Delay Weighted Matching (DWM), has been shown to be both rate-function delay-optimal (in the many-channel many-user asymptotic regime) and throughput-optimal (in general non-asymptotic setting), it has a high complexity O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sup> ), which makes it impractical for modern OFDM systems. To address this issue, we first develop a simple greedy policy called Delay-based Queue-Side-Greedy (D-QSG) with a lower complexity O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ), and rigorously prove that D-QSG not only achieves throughput optimality, but also guarantees near-optimal rate-function-based delay performance. Specifically, the rate-function attained by D-QSG for any fixed integer threshold b>0, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Further, we develop another simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with an even lower complexity O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), and show that D-SSG achieves the same performance as D-QSG. Thus, we are able to achieve a dramatic reduction in complexity (from O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sup> ) of DWM to O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> )) with a minimal drop in the delay performance. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that our proposed greedy policies not only guarantee a near-optimal rate-function, but also empirically are virtually indistinguishable from the delay-optimal policy DWM.
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},
}

Loading related content...

Figure