A novel architecture for reduction of delay and queueing structure complexity in the back-pressure algorithm

Research output: Contribution to journalArticle


The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its implementation requires that each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. This fact may lead to a poor delay performance even when the traffic load is not close to network capacity. Also, since the number of commodities in the network is usually very large, the queueing data structure that has to be maintained at each node is respectively complex. In this paper, we present a solution to address both of these issues in the case of a fixed-routing network scenario where the route of each flow is chosen upon arrival. Our proposed architecture allows each node to maintain only per-neighbor queues and, moreover, improves the delay performance of the back-pressure algorithm.

Original languageEnglish (US)
Article number5739564
Pages (from-to)1597-1609
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 1 2011



  • Communication networks
  • queueing analysis
  • scheduling algorithm

ASJC Scopus subject areas

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

Cite this