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

Bilal Sadiq, Gustavo de Veciana

Abstract

In wireless communication systems, schedulers must navigate a fundamental tradeoff between maximizing total system throughput (opportunism) and preventing individual buffer overflows (queue balancing). This paper introduces the p-Log rule, a novel scheduling algorithm belonging to the class of Radial Sum-rate Monotone (RSM) schedulers. Unlike traditional policies like MaxWeight, which maintain linear switching boundaries, the p-Log rule employs non-linear boundaries that prioritize total service rate as queues grow. We prove that for a two-user system, the p-Log rule is optimal for minimizing the probability of total buffer overflow (sum-queue) in the large deviations regime, while remaining robust to unknown arrival and channel statistics.

Introduction

Efficient resource allocation in time-varying wireless channels requires schedulers to be "opportunistic," serving users when their channel conditions are peak. However, purely opportunistic scheduling can lead to massive individual queue build-ups. Standard throughput-optimal schedulers, such as the MaxWeight (MW) or Exponential (Exp) rules, address this by balancing queues—serving the user with the longest queue to ensure stability.

While these rules are effective for stability, they may be suboptimal when the performance metric is the sum-queue overflow probability: the likelihood that the total number of packets across all buffers exceeds a large threshold. This paper investigates whether a different approach—one that de-emphasizes queue balancing in favor of maximizing the aggregate exit rate—can achieve better asymptotic performance.

Radial Sum-Rate Monotone (RSM) Schedulers

The authors propose a class of schedulers termed Radial Sum-rate Monotone (RSM). The defining characteristic of an RSM scheduler is its behavior as the total queue size increases. While traditional schedulers divide the queue-state space into fixed cones, RSM schedulers use curved boundaries. As the system moves further from the origin (i.e., as total packets increase), the scheduler spends more time in the "sum-rate optimal" region of the capacity polymatroid, prioritizing the maximization of the total service rate over the equalization of individual queue lengths.

The p-Log Rule and Geometric Analysis

A primary contribution of this work is the p-Log rule. Its switching boundaries are non-linear, creating a unique geometry in the queue-state space.

Figure 3: Comparison of the capacity region (a) with the switching regions of MaxWeight (b), the Exponential rule (c), and the proposed p-Log rule (d). Note the curved "French horn" boundaries in (d).

As shown in Figure 3, traditional rules like MaxWeight (b) and the Exp rule (c) use linear or near-linear boundaries that force the system toward the 45-degree line (queue balancing). In contrast, the p-Log rule (d) features curved boundaries that resemble a "French horn." This geometry allows the system to stay in the maximum-sum-rate region much longer, which is the key to minimizing the total number of packets in the system.

Large Deviations and Fluid Scaling

To prove the optimality of the p-Log rule, the authors employ the Large Deviations Principle (LDP). This framework characterizes the "most likely" path the system takes to reach a rare event, such as a massive buffer overflow. By using Fluid Scaling and Local Fluid Sample Paths (LFSP), the researchers analyze the dynamics of the queues at high occupancy levels.

They construct a novel Lyapunov function to demonstrate that the p-Log rule effectively forces the system's state toward a configuration that maximizes the asymptotic decay rate of the overflow probability. Essentially, the p-Log rule makes the "most likely" path to overflow as improbable as mathematically possible.

Key Results and Robustness

  • Sum-Queue Optimality: The p-Log rule is proven to maximize the asymptotic exponential decay rate of the sum-queue distribution, meeting the universal lower bound for any possible scheduler.
  • Throughput Stability: Despite its focus on sum-rate maximization, the p-Log rule is shown to be throughput-optimal, maintaining system stability for any arrival rate within the achievable capacity region.
  • Statistical Blindness: A significant practical advantage of the p-Log rule is that it does not require prior knowledge of arrival processes or channel statistics. This makes it highly robust for real-world wireless environments where these parameters are often unknown or non-stationary.

Conclusion

The p-Log rule represents a shift in scheduling philosophy for wireless networks. By prioritizing total system throughput over individual queue balancing in the large-buffer regime, it achieves superior performance for sum-queue metrics. While the current proof focuses on a two-user system, the underlying principle of radial sum-rate monotonicity provides a promising foundation for designing optimal schedulers in more complex, multi-user network architectures.

Summary updated

BibTeX
@article{sadiq2010large,
  author = {Bilal Sadiq and Gustavo de Veciana},
  title = {{Large deviation 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