Delay-optimal opportunistic scheduling and approximations: The log rule

Bilal Sadiq, Seung Jun Baek, Gustavo De Veciana

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Citations (Scopus)


This paper considers the design of opportunistic packet schedulers for users sharing a time-varying wireless channel from the performance and the robustness points of view. Firstly, for a simplified model falling in the classical Markov decision process framework where arrival and channel statistics are known, we numerically compute and evaluate the characteristics of mean-delay-optimal scheduling policies. The computed policies exhibit radial sum-rate monotonicity (RSM), i.e., when users' queues grow linearly (i.e. scaled up by a constant), the scheduler allocates service in a manner that de-emphasizes the balancing of unequal queues in favor of maximizing current system throughput (being opportunistic). This is in sharp contrast to previously proposed policies, e.g., MaxWeight and Exp rule. The latter, however, are throughput-optimal, in that without knowledge of arrival/channel statistics they achieve stability if at all feasible. To meet performance and robustness objectives, secondly, we propose a new class of policies, called the Log rule, that are radial sum-rate monotone and provably throughput optimal. Our simulations for realistic wireless channels confirm the superiority of the Log rule which achieves up to 80% reduction in mean packet delays. However, recent asymptotic analysis showed that Exp rule is optimal in terms of minimizing the asymptotic probability of max-queue overflow. In turn, in a companion paper we have shown that an RSM policy minimizes the asymptotic probability of sum-queue overflow. Finally, we use extensive simulations to explore the various possible design objectives for opportunistic schedulers. When users see heteroge-nous channels, we find that minimizing the worst asymptotic exponent across users may excessively compromise the overall delay. Our simulations show that only if perfectly tuned to the load will the Exp rule achieve low homogenous tails across users. Otherwise the Log rule achieves a 20-75% reduction in the 99 th percentile for most, if not all, the users. We conclude that for wireless environments, where precise resource allocation is virtually impossible, the Log rule may be more desirable for its robust and graceful degradation to unpredicted changes.

Original languageEnglish
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Number of pages9
Publication statusPublished - 2009
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: 2009 Apr 192009 Apr 25

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other28th Conference on Computer Communications, IEEE INFOCOM 2009
CityRio de Janeiro

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Delay-optimal opportunistic scheduling and approximations: The log rule'. Together they form a unique fingerprint.

Cite this