Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing

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

Abstract

The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the backpressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Pages2936-2940
Number of pages5
DOIs
StatePublished - Oct 12 2009
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: Apr 19 2009Apr 25 2009

Publication series

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

Other

Other28th Conference on Computer Communications, IEEE INFOCOM 2009
CountryBrazil
CityRio de Janeiro
Period4/19/094/25/09

Fingerprint

Scheduling
Routing algorithms
Data structures
Throughput

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Bui, L., Srikant, R., & Stolyar, A. (2009). Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. In IEEE INFOCOM 2009 - The 28th Conference on Computer Communications (pp. 2936-2940). [5062262] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2009.5062262

Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. / Bui, Loc; Srikant, R.; Stolyar, Alexander.

IEEE INFOCOM 2009 - The 28th Conference on Computer Communications. 2009. p. 2936-2940 5062262 (Proceedings - IEEE INFOCOM).

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

Bui, L, Srikant, R & Stolyar, A 2009, Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. in IEEE INFOCOM 2009 - The 28th Conference on Computer Communications., 5062262, Proceedings - IEEE INFOCOM, pp. 2936-2940, 28th Conference on Computer Communications, IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 4/19/09. https://doi.org/10.1109/INFCOM.2009.5062262
Bui L, Srikant R, Stolyar A. Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. In IEEE INFOCOM 2009 - The 28th Conference on Computer Communications. 2009. p. 2936-2940. 5062262. (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2009.5062262
Bui, Loc ; Srikant, R. ; Stolyar, Alexander. / Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. IEEE INFOCOM 2009 - The 28th Conference on Computer Communications. 2009. pp. 2936-2940 (Proceedings - IEEE INFOCOM).
@inproceedings{1ad27a8fa33548ce83da86b16e3a988c,
title = "Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing",
abstract = "The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the backpressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.",
author = "Loc Bui and R. Srikant and Alexander Stolyar",
year = "2009",
month = "10",
day = "12",
doi = "10.1109/INFCOM.2009.5062262",
language = "English (US)",
isbn = "9781424435135",
series = "Proceedings - IEEE INFOCOM",
pages = "2936--2940",
booktitle = "IEEE INFOCOM 2009 - The 28th Conference on Computer Communications",

}

TY - GEN

T1 - Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing

AU - Bui, Loc

AU - Srikant, R.

AU - Stolyar, Alexander

PY - 2009/10/12

Y1 - 2009/10/12

N2 - The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the backpressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.

AB - The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the backpressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.

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

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

U2 - 10.1109/INFCOM.2009.5062262

DO - 10.1109/INFCOM.2009.5062262

M3 - Conference contribution

AN - SCOPUS:70349662383

SN - 9781424435135

T3 - Proceedings - IEEE INFOCOM

SP - 2936

EP - 2940

BT - IEEE INFOCOM 2009 - The 28th Conference on Computer Communications

ER -