On scheduling for minimizing end-to-end buffer usage over multihop wireless networks

V. J. Venkataramanan, Xiaojun Lin, Lei Ying, Sanjay Shakkottai

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

32 Scopus citations


While there has been much progress in designing backpressure based stabilizing algorithms for multihop wireless networks, end-to-end performance (e.g., end-to-end buffer usage) results have not been as forthcoming. In this paper, we study the end-to-end buffer usage (sum of buffer utilization along a flow path) over a network with general topology and with fixed, loop-free routes using a large-deviations approach. We first derive bounds on the best performance that any scheduling algorithm can achieve. Based on the intuition from the bounds, we propose a class of (backpressure-like) scheduling algorithms called αβ-algorithms. We show that the parameters α and β can be chosen such that the system under the αβ-algorithm performs arbitrarily closely to the best possible scheduler (formally the decay rate function for end-to-end buffer overflow is shown to be arbitrarily close to optimal in the large-buffer regime). We also develop variants which have the same asymptotic optimality property, and also provide good performance in the small-buffer regime. Our results are substantiated using both analysis and simulation.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
StatePublished - 2010
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

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'On scheduling for minimizing end-to-end buffer usage over multihop wireless networks'. Together they form a unique fingerprint.

Cite this