Low-complexity scheduling algorithms for multi-channel downlink wireless networks

Shreeshankar Bodas, Sanjay Shakkottai, Lei Ying, R. Srikant

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

29 Scopus citations


This paper considers the problem of designing scheduling algorithms for multi-channel (e.g., OFDM) wireless downlink networks with n users/OFDM sub-channels. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, we show it has zero rate function in our setting). To address this, we propose a class of algorithms called iHLQF (iterated Heaviest matching with Longest Queues First) that is shown to be throughput optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF however has higher complexity than MaxWeight (n4 vs. n2 respectively). To overcome this issue, we propose a new algorithm called SSG (Server-Side Greedy). We show that SSG is throughput optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n2) that is comparable to the MaxWeight algorithm. Thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
StatePublished - 2010
Externally publishedYes
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

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


Country/TerritoryUnited States
CitySan Diego, CA


  • Large deviations
  • Low complexity
  • Scheduling algorithms
  • Small buffer

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Low-complexity scheduling algorithms for multi-channel downlink wireless networks'. Together they form a unique fingerprint.

Cite this