Efficient bufferless routing on leveled networks

Costas Busch; Shailesh Kelkar; Malik Magdon-Ismail

doi:10.1007/11549468_102

Efficient bufferless routing on leveled networks

Costas Busch, Shailesh Kelkar, Malik Magdon-Ismail

Research output: Contribution to journal › Conference article › peer-review

2 Scopus citations

Abstract

We give near optimal bufferless routing algorithms for leveled networks. N packets with preselected paths are given, and once injected, the packets may not be buffered while in transit to their destination. For the preselected paths, the dilation D is the maximum path length, and the congestion C is the maximum number of times an edge is used. We give two bufferless routing algorithms for leveled networks: (i) a centralized algorithm with routing time O((C + D) log(DN)); (ii) a distributed algorithm with routing time O((C + D) log²(DN)). The distributed algorithm uses a new technique, reverse-simulation, which is used to obtain a distributed emulation of the centralized algorithm. Since a well known lower bound on the routing time is Ω(C + D), our results are at most one or two logarithmic factors from optimal.

Original language	English (US)
Pages (from-to)	931-940
Number of pages	10
Journal	Lecture Notes in Computer Science
Volume	3648
DOIs	https://doi.org/10.1007/11549468_102
State	Published - 2005
Externally published	Yes
Event	11th International Euro-Par Conference, Euro-Par 2005 - Lisbon, Portugal Duration: Aug 30 2005 → Sep 2 2005

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11549468_102

Cite this

@article{5f9f01ba774341fcbd4284e21ad9e6fc,

title = "Efficient bufferless routing on leveled networks",

abstract = "We give near optimal bufferless routing algorithms for leveled networks. N packets with preselected paths are given, and once injected, the packets may not be buffered while in transit to their destination. For the preselected paths, the dilation D is the maximum path length, and the congestion C is the maximum number of times an edge is used. We give two bufferless routing algorithms for leveled networks: (i) a centralized algorithm with routing time O((C + D) log(DN)); (ii) a distributed algorithm with routing time O((C + D) log2(DN)). The distributed algorithm uses a new technique, reverse-simulation, which is used to obtain a distributed emulation of the centralized algorithm. Since a well known lower bound on the routing time is Ω(C + D), our results are at most one or two logarithmic factors from optimal.",

author = "Costas Busch and Shailesh Kelkar and Malik Magdon-Ismail",

year = "2005",

doi = "10.1007/11549468_102",

language = "English (US)",

volume = "3648",

pages = "931--940",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "11th International Euro-Par Conference, Euro-Par 2005 ; Conference date: 30-08-2005 Through 02-09-2005",

}

TY - JOUR

T1 - Efficient bufferless routing on leveled networks

AU - Busch, Costas

AU - Kelkar, Shailesh

AU - Magdon-Ismail, Malik

PY - 2005

Y1 - 2005

N2 - We give near optimal bufferless routing algorithms for leveled networks. N packets with preselected paths are given, and once injected, the packets may not be buffered while in transit to their destination. For the preselected paths, the dilation D is the maximum path length, and the congestion C is the maximum number of times an edge is used. We give two bufferless routing algorithms for leveled networks: (i) a centralized algorithm with routing time O((C + D) log(DN)); (ii) a distributed algorithm with routing time O((C + D) log2(DN)). The distributed algorithm uses a new technique, reverse-simulation, which is used to obtain a distributed emulation of the centralized algorithm. Since a well known lower bound on the routing time is Ω(C + D), our results are at most one or two logarithmic factors from optimal.

AB - We give near optimal bufferless routing algorithms for leveled networks. N packets with preselected paths are given, and once injected, the packets may not be buffered while in transit to their destination. For the preselected paths, the dilation D is the maximum path length, and the congestion C is the maximum number of times an edge is used. We give two bufferless routing algorithms for leveled networks: (i) a centralized algorithm with routing time O((C + D) log(DN)); (ii) a distributed algorithm with routing time O((C + D) log2(DN)). The distributed algorithm uses a new technique, reverse-simulation, which is used to obtain a distributed emulation of the centralized algorithm. Since a well known lower bound on the routing time is Ω(C + D), our results are at most one or two logarithmic factors from optimal.

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

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

U2 - 10.1007/11549468_102

DO - 10.1007/11549468_102

M3 - Conference article

AN - SCOPUS:27144504250

SN - 0302-9743

VL - 3648

SP - 931

EP - 940

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 11th International Euro-Par Conference, Euro-Par 2005

Y2 - 30 August 2005 through 2 September 2005

ER -

Efficient bufferless routing on leveled networks

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this