Large deviations sum-queue optimality of a radial sum-rate monotone opportunistic scheduler

Bilal Sadiq, Gustavo de Veciana

TL;DR

This paper introduces the "pseudo-Log" (p-Log) scheduling rule for wireless systems with time-varying channels and queues. The p-Log rule is proven to be optimal in minimizing the probability of the total queue length exceeding a threshold, a crucial metric for system stability and performance, especially under uncertain conditions.

What Problem Does This Paper Address?

In wireless systems, schedulers decide which user to serve at any given moment. This decision involves a fundamental trade-off: should the scheduler prioritize serving the user with the best current channel (maximizing immediate service rate) or the user with the longest queue (balancing load and ensuring fairness)? While many existing schedulers aim for "throughput-optimality" (ensuring queues don't grow indefinitely if possible), this paper focuses on a more stringent performance metric: minimizing the asymptotic exponential decay rate of the sum-queue distribution. This is equivalent to minimizing the probability of the total queue length exceeding a large threshold, which is critical for Quality of Service (QoS) guarantees. Existing work often assumes symmetry or specific channel models, leaving a gap in understanding optimal strategies for more general, heterogeneous wireless environments.

Methods

The paper introduces a novel scheduling policy called the "pseudo-Log" (p-Log) rule. This rule is characterized by a specific vector field that guides the scheduling decision based on queue lengths. The core of the analysis relies on large deviation theory, a mathematical framework for understanding rare events (like queue overflows) in stochastic systems. The authors leverage techniques from previous work on similar scheduling problems, particularly those involving "radial sum-rate monotonicity" (RSM) and "fluid-scaled processes" (FSPs) and "local fluid sample paths" (LFSPs). They establish a lower bound on the sum-queue overflow probability for any scheduler and then show that the p-Log rule achieves this bound, thus proving its optimality. The proofs involve constructing Lyapunov functions and analyzing the behavior of scaled queue processes under different conditions.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present experimental results or use specific datasets.

Key Insights and Ideas

  • The "p-Log" rule: A new scheduler that balances maximizing immediate service rate with queue balancing in a specific, mathematically elegant way.
  • Optimality for sum-queue overflow: The p-Log rule is shown to be optimal not just for throughput but for minimizing the probability of the total queue length exceeding a threshold, a more sensitive QoS metric.
  • Radial Sum-Rate Monotonicity (RSM): This property is key. Schedulers with this property tend to prioritize maximizing the system's service rate as queues grow large, which is beneficial for sum-queue overflow probabilities.
  • Trade-off in overflow modes: Minimizing max-queue overflow often leads to queues growing at similar rates, while minimizing sum-queue overflow allows queues to grow at different rates, as long as the total service rate is maximized.
  • Robustness: The p-Log rule's optimality holds without requiring knowledge of arrival or channel statistics, making it robust to uncertainty.

Key Results

  • Lower Bound: The paper establishes a fundamental lower bound on the asymptotic exponential decay rate of the weighted sum-queue overflow probability for any scheduler.
  • Upper Bound: For the p-Log scheduler, an upper bound on this decay rate is derived.
  • Optimality: The p-Log rule is proven to achieve the established lower bound, meaning it maximizes the asymptotic exponential decay rate of the sum-queue distribution. This implies it is optimal for minimizing sum-queue overflow probabilities.
  • Radial Sum-Rate Monotonicity: The p-Log rule is demonstrated to be a radial sum-rate monotone scheduler.

Limitations and Future Work

  • Two-Queue System: The primary theoretical results are presented for a two-queue system. While extensions to more queues are mentioned as possible, the detailed proofs are for the two-queue case.
  • Centralized Scheduler: The model assumes a centralized scheduler. Future work could explore decentralized or distributed scheduling mechanisms.
  • Extensions: The paper suggests several extensions:
  • Generalizing to an arbitrary number of queues.
  • Considering multiple parallel servers with asymmetric capacities.
  • Allowing more general convex polyhedral capacity regions instead of simple triangles.
  • Applying the framework to other scheduling policies and system models, potentially using gradient-based Lyapunov functions.

Summary updated

Abstract

A centralized wireless system is considered that is serving a fixed set of users with time varying channel capacities. An opportunistic scheduling rule in this context selects a user (or users) to serve based on the current channel state and user queues. Unless the user traffic is symmetric and/or the underlying capacity region a polymatroid, little is known concerning how performance optimal schedulers should tradeoff <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">maximizing current service rate</i> (being opportunistic) versus <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">balancing unequal queues</i> (enhancing user-diversity to enable future high service rate opportunities). By contrast, with currently proposed opportunistic schedulers, e.g., MaxWeight and Exp Rule, a radial sum-rate monotonic (RSM) scheduler de-emphasizes queue-balancing in favor of greedily maximizing the system service rate as the queue-lengths are scaled up linearly. In this paper, it is shown that an RSM opportunistic scheduler, p-Log Rule, is not only throughput-optimal, but also maximizes the asymptotic exponential decay rate of the sum-queue distribution for a two-queue system. The result complements existing optimality results for opportunistic scheduling and point to RSM schedulers as a good design choice given the need for robustness in wireless systems with both heterogeneity and high degree of uncertainty.
BibTeX
@article{sadiq2010large,
  author = {Bilal Sadiq and Gustavo de Veciana},
  title = {{Large deviations sum-queue optimality of a radial sum-rate monotone opportunistic scheduler}},
  journal = {IEEE Trans. Information Theory},
  year = {2010},
  url = {https://openreview.net/forum?id=5kYSobDVQ78},
}
Figure