Cluster-based back-pressure routing algorithm

Lei Ying, R. Srikant, Don Towsley, Shihuan Liu

Research output: Contribution to journalArticlepeer-review


The back-pressure algorithm introduced in 1992 by Tassiulas and Ephremides 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. 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 precludes its implementation in large-scale networks. In this paper, we propose a distributed cluster-based back-pressure routing algorithm that retains the adaptability of back-pressure routing while significantly reducing the number of queues that have to be maintained at each node.

Original languageEnglish (US)
Article number5759110
Pages (from-to)1773-1786
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2011


  • Back-pressure algorithm
  • clustering
  • distributed and adaptive routing
  • throughput-optimal

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


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

Cite this