Laxity-based opportunistic scheduling with flow-level dynamics and deadlines

Huasen Wu, Youguang Zhang, Xin Liu

TL;DR

This paper introduces laxity-based scheduling policies for wireless networks to minimize missed deadlines for data transmission tasks, crucial for applications like video streaming. They propose a novel "Less-Laxity-Higher-Possible-Rate" (L²HPR) policy, proving its asymptotic optimality in ideal scenarios, and then develop practical heuristic policies that outperform traditional greedy approaches.

What Problem Does This Paper Address?

Modern cellular networks are increasingly supporting applications like video streaming and content precaching. These applications have specific Quality of Service (QoS) requirements, particularly deadlines. For instance, a video segment must be downloaded before the playback buffer empties to maintain a smooth viewing experience. Traditional scheduling algorithms often focus on maximizing throughput or minimizing average delay without explicitly considering these deadlines. This paper addresses the challenge of minimizing the number of transmission tasks that miss their deadlines in a wireless network setting, where channel conditions fluctuate and users arrive and depart dynamically (flow-level dynamics). The core problem is how to intelligently allocate limited wireless resources to ensure that time-sensitive data transmissions are completed on time.

Methods

The paper's core contribution is the development and analysis of laxity-based scheduling policies.

  • Laxity: They define "laxity" as the remaining time a transmission task has before its deadline, adjusted by the estimated time to complete the remaining data. A lower laxity indicates higher urgency.
  • L²HPR Policy: For ideal, underloaded systems with identical deadlines, they propose the "Less-Laxity-Higher-Possible-Rate" (L²HPR) policy. This policy prioritizes users with lower laxity by allocating them higher data rates, while still aiming to maximize overall system throughput by leveraging multi-user diversity. They mathematically prove the asymptotic optimality of L²HPR, meaning it approaches optimal performance as the time slot duration approaches zero.
  • Heuristic Policies: Recognizing that the L²HPR policy relies on idealized assumptions (like a polymatroid capacity region), they propose a framework for practical systems. This framework balances serving urgent users with maximizing system throughput. From this framework, they derive three heuristic policies: L-MaxWeight, L-Exp, and L-Log, which use different functions to quantify user urgency based on laxity.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation-based evaluation using synthetic traffic and channel models.

Key Insights and Ideas

  • Laxity as a Key Metric: The paper highlights that "laxity" is a more appropriate metric than just channel quality or arrival time for scheduling tasks with deadlines. It directly quantifies urgency.
  • Trade-off Between Urgency and Throughput: The core challenge is balancing the need to serve urgent tasks (low laxity) with the desire to maximize overall data transmission (multi-user diversity). L²HPR and the heuristic policies are designed to navigate this trade-off.
  • Asymptotic Optimality: Proving asymptotic optimality for L²HPR in idealized scenarios provides a strong theoretical foundation and a benchmark for evaluating practical policies. It suggests that laxity-based approaches are fundamentally sound for deadline-aware scheduling.
  • Channel Awareness is Crucial: Simulations show that channel-oblivious policies (like EDF and LLF) perform poorly compared to channel-aware policies (like Max C/I and the proposed laxity-based ones), underscoring the importance of adapting to varying wireless conditions.
  • Heuristic Policies Outperform Greedy: The proposed laxity-based heuristic policies consistently outperform the traditional greedy Max C/I policy in terms of schedulability and delay violation probability, especially in more dynamic (stationary-arrival) systems.

Key Results

  • L²HPR Asymptotic Optimality: The L²HPR policy is proven to be asymptotically optimal in underloaded identical-deadline systems.
  • Schedulability: Simulations show that L²HPR achieves the largest number of schedulable realizations (tasks completed before deadlines) across various scenarios. The proposed laxity-based heuristics (L-MaxWeight, L-Exp, L-Log) significantly outperform the greedy Max C/I policy.
  • Delay Violation Probability: While L²HPR can sometimes lead to higher delay violation probabilities in specific scenarios (due to its strict prioritization of the least lax user), the heuristic policies generally show much lower delay violation probabilities than Max C/I, particularly in stationary-arrival systems. For instance, L-LLF achieved only 25% of the delay violation probability of Max C/I in stationary-arrival systems.

Limitations and Future Work

  • Idealized Assumptions: The theoretical results for L²HPR rely on idealized assumptions like the polymatroid capacity region and identical deadlines. Practical systems are often more complex.
  • Overloaded Systems: The paper primarily focuses on underloaded systems. The behavior and optimality of the proposed policies in overloaded scenarios (where not all tasks can possibly be completed) are not fully addressed.
  • Task Values: The current model assumes all completed tasks have equal value. In reality, tasks might have different priorities or values, which could influence scheduling decisions.

The authors suggest future work in several areas:

  • Developing algorithms to estimate the schedulability of incoming task sequences.
  • Designing policies that can intelligently drop users to avoid wasting resources when the system is overloaded.
  • Maximizing the obtained utility when the system is possibly overloaded, considering that different tasks might have different values.

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> HPR) policy and prove its asymptotic optimality in underloaded identical-deadline systems. The asymptotic optimality of L <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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