Back-pressure-based packet-by-packet adaptive routing in communication networks

Eleftheria Athanasopoulou, Loc X. Bui, Tianxiong Ji, R. Srikant, Alexander Stolyar

Research output: Contribution to journalArticle

Abstract

Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing-coding tradeoff.

Original languageEnglish (US)
Article number6193399
Pages (from-to)244-257
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume21
Issue number1
DOIs
StatePublished - Feb 20 2013

Fingerprint

Telecommunication networks
Routing algorithms
Adaptive algorithms
Scheduling
Network coding
Wireless networks

Keywords

  • Back-pressure algorithm
  • network coding
  • routing
  • scheduling

ASJC Scopus subject areas

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

Cite this

Back-pressure-based packet-by-packet adaptive routing in communication networks. / Athanasopoulou, Eleftheria; Bui, Loc X.; Ji, Tianxiong; Srikant, R.; Stolyar, Alexander.

In: IEEE/ACM Transactions on Networking, Vol. 21, No. 1, 6193399, 20.02.2013, p. 244-257.

Research output: Contribution to journalArticle

Athanasopoulou, Eleftheria ; Bui, Loc X. ; Ji, Tianxiong ; Srikant, R. ; Stolyar, Alexander. / Back-pressure-based packet-by-packet adaptive routing in communication networks. In: IEEE/ACM Transactions on Networking. 2013 ; Vol. 21, No. 1. pp. 244-257.
@article{d6e6c256bdaf4971aa5a6f4290752ca9,
title = "Back-pressure-based packet-by-packet adaptive routing in communication networks",
abstract = "Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing-coding tradeoff.",
keywords = "Back-pressure algorithm, network coding, routing, scheduling",
author = "Eleftheria Athanasopoulou and Bui, {Loc X.} and Tianxiong Ji and R. Srikant and Alexander Stolyar",
year = "2013",
month = "2",
day = "20",
doi = "10.1109/TNET.2012.2195503",
language = "English (US)",
volume = "21",
pages = "244--257",
journal = "IEEE/ACM Transactions on Networking",
issn = "1063-6692",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Back-pressure-based packet-by-packet adaptive routing in communication networks

AU - Athanasopoulou, Eleftheria

AU - Bui, Loc X.

AU - Ji, Tianxiong

AU - Srikant, R.

AU - Stolyar, Alexander

PY - 2013/2/20

Y1 - 2013/2/20

N2 - Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing-coding tradeoff.

AB - Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing-coding tradeoff.

KW - Back-pressure algorithm

KW - network coding

KW - routing

KW - scheduling

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

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

U2 - 10.1109/TNET.2012.2195503

DO - 10.1109/TNET.2012.2195503

M3 - Article

AN - SCOPUS:84873886716

VL - 21

SP - 244

EP - 257

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 1

M1 - 6193399

ER -