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

Research output: Contribution to journalArticle

Abstract

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
Volume19
Issue number6
DOIs
StatePublished - Dec 1 2011

Fingerprint

Network routing
Data structures
Throughput

Keywords

  • Communication networks
  • queueing analysis
  • scheduling algorithm

ASJC Scopus subject areas

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

Cite this

A novel architecture for reduction of delay and queueing structure complexity in the back-pressure algorithm. / Bui, Loc X.; Srikant, R.; Stolyar, Alexander.

In: IEEE/ACM Transactions on Networking, Vol. 19, No. 6, 5739564, 01.12.2011, p. 1597-1609.

Research output: Contribution to journalArticle

@article{421c696506054337ab060a88eb2189ff,
title = "A novel architecture for reduction of delay and queueing structure complexity in the back-pressure algorithm",
abstract = "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.",
keywords = "Communication networks, queueing analysis, scheduling algorithm",
author = "Bui, {Loc X.} and R. Srikant and Alexander Stolyar",
year = "2011",
month = "12",
day = "1",
doi = "10.1109/TNET.2011.2126593",
language = "English (US)",
volume = "19",
pages = "1597--1609",
journal = "IEEE/ACM Transactions on Networking",
issn = "1063-6692",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

TY - JOUR

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

AU - Bui, Loc X.

AU - Srikant, R.

AU - Stolyar, Alexander

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

KW - Communication networks

KW - queueing analysis

KW - scheduling algorithm

UR - http://www.scopus.com/inward/record.url?scp=84655169975&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84655169975&partnerID=8YFLogxK

U2 - 10.1109/TNET.2011.2126593

DO - 10.1109/TNET.2011.2126593

M3 - Article

AN - SCOPUS:84655169975

VL - 19

SP - 1597

EP - 1609

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 6

M1 - 5739564

ER -