Laxity-Based Opportunistic Scheduling with Flow-Level Dynamics and Deadlines

Huasen Wu, Youguang Zhang, Xin Liu

Introduction

In modern cellular networks, the primary metric of user experience has shifted from simple packet-level throughput to the successful completion of "flows"—entire files or video segments—before a strict deadline. For applications like video streaming or file pre-caching, partially downloaded data is often useless if the buffer empties before the flow completes. This creates a fundamental challenge known as the Urgency-Diversity Tradeoff. A base station must decide whether to serve users with the best current channel conditions to maximize total throughput (multi-user diversity) or prioritize users whose deadlines are imminent, even if their signal is currently weak (urgency).

Traditional scheduling policies like Proportional Fair ignore deadlines entirely, while classic real-time algorithms like Earliest Deadline First (EDF) ignore the volatile nature of wireless channels. This paper introduces the $L^2HPR$ (Less-Laxity-Higher-Possible-Rate) policy to bridge this gap, providing a framework that balances channel efficiency with flow-level dynamics.

The $L^2HPR$ Policy and Heuristics

The core innovation of this work is the use of Expected Laxity as a scheduling metric. Expected laxity is defined as the time remaining until a user's deadline minus the time required to finish their task, assuming they were granted the full channel capacity.

Theoretical Foundation

The $L^2HPR$ policy is designed for an idealized system where the capacity region is a polymatroid. It operates by sorting active users by their expected laxity and allocating higher data rates to those with lower laxity (higher urgency). The authors prove that $L^2HPR$ is asymptotically optimal for underloaded systems, meaning that as time slot lengths approach zero, it performs as well as an "offline" policy with perfect future knowledge.

Practical Implementation

To address real-world constraints like discrete time slots and varying channel states, the authors propose several heuristic variants:

  • L-MaxWeight, L-Exp, and L-Log: These map laxity to urgency weights using polynomial, exponential, and logarithmic functions, respectively.
  • Admission Control: The framework incorporates a threshold ($\delta$). If a user's laxity drops below this threshold, the system identifies them as likely to fail and stops allocating resources to them. This prevents "wasting" bandwidth on lost causes, ensuring other users can still meet their deadlines.

Performance Evaluation

The proposed policies were evaluated using numerical simulations of Rayleigh fading channels and an FTP traffic model (truncated lognormal distribution, mean 2MB). The study compared $L^2HPR$ and its heuristics against standard greedy policies like Max C/I and deadline-only policies like EDF and Least-Laxity-First (LLF).

Schedulability and Reliability

A key finding is the superior "schedulability" of laxity-based approaches. In scenarios with both identical deadlines and stationary Poisson arrivals, $L^2HPR$ consistently scheduled more sets of users than any other policy.

Figure 2: Comparison of schedulable realizations across different policies for identical-deadline (a) and stationary-arrival (b) systems.

As shown in Figure 2, $L^2HPR$ (red bars) significantly outperforms the greedy Max C/I policy, especially when deadlines are tight (low $D$ or low stretch factor $\xi$). In many cases, it was the only policy capable of finding a feasible schedule for the given realizations.

Deadline Violation Probability

The policies also demonstrated a marked reduction in the probability of deadline violations ($P_{viol}$). While channel-oblivious policies like LLF and EDF performed poorly due to their tendency to waste bandwidth on users with poor channel states, the laxity-based heuristics maintained high reliability.

Figure 5: Probability of deadline violation ($P_{viol}$) as a function of deadline (a) and stretch factor (b).

Figure 5 illustrates that $L^2HPR$ (dashed red line) achieves the lowest violation probability across all tested parameters. In stationary arrival systems, the proposed policies reduced $P_{viol}$ to approximately 25% of the levels seen with the standard Max C/I policy. The heuristics L-MaxWeight and L-Exp proved particularly robust, outperforming greedy approaches that require significantly more "slack" time to achieve comparable reliability.

Conclusion

$L^2HPR$ provides a theoretically grounded and practically effective solution for wireless scheduling with flow-level deadlines. By using expected laxity to navigate the urgency-diversity tradeoff, the policy maximizes both network efficiency and user satisfaction. Future work remains in optimizing performance for intentionally overloaded systems and exploring "soft deadlines" where partial utility can be derived from incomplete flows.

Summary updated

Abstract

Many data applications in the next generation cellular networks, such as content precaching and video progressive downloading, require flow-level quality of service (QoS) guarantees. One such requirement is deadline, where the transmission task needs to be completed before the application-specific time. To minimize the number of uncompleted transmission tasks, we study laxity-based scheduling policies in this paper. We propose a Less-Laxity-Higher-Possible-Rate (L$^2$HPR) policy and prove its asymptotic optimality in underloaded identical-deadline systems. The asymptotic optimality of L$^2$HPR can be applied to estimate the schedulability of a system and provide insights on the design of scheduling policies for general systems. Based on it, we propose a framework and three heuristic policies for practical systems. Simulation results demonstrate the asymptotic optimality of L$^2$HPR and performance improvement of proposed policies over greedy policies.
BibTeX
@inproceedings{wu2013laxity,
  author = {Huasen Wu and Youguang Zhang and Xin Liu},
  title = {{Laxity-Based Opportunistic Scheduling with Flow-Level Dynamics and Deadlines}},
  booktitle = {WCNC},
  year = {2013},
  url = {https://openreview.net/forum?id=2pbBRtPsjgZ},
}
Figure