Cluster-based back-pressure routing algorithm

Lei Ying, R. Srikant, Don Towsley

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


We study scalable, distributed, and adaptive routing algorithms for communication networks. The back-pressure algorithm introduced in [21] is a well-known distributed and adaptive routing/scheduling algorithm where nodes only need the queue length information of neighboring nodes to make routing decisions, and packets are adaptively routed in the network according to congestion information, which makes the algorithm resilient to traffic and topology changes. However, the back-pressure algorithm requires routers to maintain a separate queue for each destination, which prevents its implementation in large-scale networks like the Internet. In this paper, we propose a cluster-based back-pressure routing algorithm, which retains the distributability and adaptability of back-pressure routing, while significantly reducing the number of queues that have to be maintained at each node. Since the cluster-based algorithm performs adaptive load-balancing in the network, it has the potential to eliminate the need for off-line traffic engineering in the Internet.

Original languageEnglish (US)
Title of host publicationINFOCOM 2008
Subtitle of host publication27th IEEE Communications Society Conference on Computer Communications
Number of pages9
StatePublished - 2008
EventINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States
Duration: Apr 13 2008Apr 18 2008

Publication series

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


OtherINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
Country/TerritoryUnited States
CityPhoenix, AZ

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Cluster-based back-pressure routing algorithm'. Together they form a unique fingerprint.

Cite this