Back-pressure routing for intermittently connected networks

Jung Ryu, Lei Ying, Sanjay Shakkottai

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

33 Scopus citations


We study a mobile wireless network where groups or clusters of nodes are intermittently connected via mobile "carriers" (the carriers provide connectivity over time among different clusters of nodes). Over such networks (an instantiation of a delay tolerant network), it is well-known that traditional routing algorithms perform very poorly. In this paper, we propose a two-level Back-Pressure with Source-Routing algorithm (BP+SR) for such networks. The proposed BP+SR algorithm separates routing and scheduling within clusters (fast time-scale) from the communications that occur across clusters (slow time-scale), without loss in network throughput (i.e., BP+SR is throughput-optimal). More importantly, for a source and destination node that lie in different clusters, the traditional back-pressure algorithm results in large queue lengths at each node along its path. This is because the queue dynamics are driven by the slowest time-scale (i.e., that of the carrier nodes) along the path between the source and destination, which results in very large end-to-end delays. On the other-hand, we show that the two-level BP+SR algorithm maintains large queues only at a very few nodes, and thus results in order-wise smaller end-to-end delays. We provide analytical as well as simulation results to confirm our claims.

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 'Back-pressure routing for intermittently connected networks'. Together they form a unique fingerprint.

Cite this