Delay-based Back-Pressure scheduling in multi-hop wireless networks

Bo Ji, Changhee Joo, Ness B. Shroff

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

25 Citations (Scopus)


Scheduling is a critical and challenging resource allocation mechanism for multi-hop wireless networks. It is well known that scheduling schemes that give a higher priority to the link with larger queue length can achieve high throughput performance. However, this queue-length-based approach could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets may get excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay for the packet has encountered. However, the throughput performance of delay-based schemes has largely been an open problem except in limited cases of single-hop networks. In this paper, we investigate delaybased scheduling schemes for multi-hop traffic scenarios. We view packet delays from a different perspective, and develop a scheduling scheme based on a new delay metric. Through rigorous analysis, we show that the proposed scheme achieves the optimal throughput performance. Finally, we conduct extensive simulations to support our analytical results, and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

Original languageEnglish
Title of host publication2011 Proceedings IEEE INFOCOM
Number of pages9
Publication statusPublished - 2011
Externally publishedYes
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: 2011 Apr 102011 Apr 15

Publication series

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



ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Delay-based Back-Pressure scheduling in multi-hop wireless networks'. Together they form a unique fingerprint.

Cite this