Exploring the inefficiency and instability of Back-Pressure algorithms

Bo Ji, Changhee Joo, Ness B. Shroff

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

13 Citations (Scopus)


In this paper, we focus on the issue of stability in multihop wireless networks under flow-level dynamics, and explore the inefficiency and instability of the celebrated Back-Pressure algorithms. It has been well-known that the Back-Pressure (or MaxWeight) algorithms achieve queue stability and throughput optimality in a wide variety of scenarios. Yet, these results all rely on the assumptions that the set of flows is fixed, and that all the flows are long-lived and keep injecting packets into the network. Recently, in the presence of flow-level dynamics, where flows arrive and request to transmit a finite amount of packets, it has been shown that the MaxWeight algorithms may not guarantee stability due to channel fading or inefficient spatial reuse. However, these observations are made only for single-hop traffic, and thus have resulted in partial solutions that are limited to the single-hop scenarios. An interesting question is whether straightforward extensions of the previous solutions to the known instability problems would achieve throughput optimality in multihop traffic setting. To answer the question, we explore potential inefficiency and instability of the Back-Pressure algorithms, and provide interesting examples that are useful to obtain insights into developing an optimal solution. We also conduct simulations to further illustrate the instability issue of the Back-Pressure algorithms in various scenarios. Our study reveals that new types of inefficiencies may arise in the settings with multihop traffic due to underutilization of the link capacity or inefficient routing, and the stability problem becomes more challenging than in the single-hop traffic counterpart.

Original languageEnglish
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Number of pages9
Publication statusPublished - 2013
Externally publishedYes
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: 2013 Apr 142013 Apr 19

Publication series

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


Other32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Exploring the inefficiency and instability of Back-Pressure algorithms'. Together they form a unique fingerprint.

Cite this