Routing without flow control

C. Busch; M. Herlihy; R. Wattenhofer

doi:10.1145/378580.378582

Routing without flow control

C. Busch, M. Herlihy, R. Wattenhofer

Research output: Contribution to conference › Paper › peer-review

13 Scopus citations

Abstract

We present the first dynamic hot-potato routing algorithm that does not require any form of explicit flow control: A node may inject a message into the network (n × n mesh) whenever a link is free. In the worst case, a node may have to wait an expected O(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected O(n) time steps. Both measures are optimal up to a constant factor.

Original language	English (US)
Pages	11-20
Number of pages	10
DOIs	https://doi.org/10.1145/378580.378582
State	Published - 2001
Externally published	Yes
Event	13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001) - Crete Island, Greece Duration: Jul 3 2001 → Jul 6 2001

Conference

Conference	13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001)
Country/Territory	Greece
City	Crete Island
Period	7/3/01 → 7/6/01

ASJC Scopus subject areas

Software
Safety, Risk, Reliability and Quality

Access to Document

10.1145/378580.378582

Cite this

@conference{ad2c2495713c45bbbbb26b326aeb2b71,

title = "Routing without flow control",

abstract = "We present the first dynamic hot-potato routing algorithm that does not require any form of explicit flow control: A node may inject a message into the network (n × n mesh) whenever a link is free. In the worst case, a node may have to wait an expected O(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected O(n) time steps. Both measures are optimal up to a constant factor.",

author = "C. Busch and M. Herlihy and R. Wattenhofer",

year = "2001",

doi = "10.1145/378580.378582",

language = "English (US)",

pages = "11--20",

note = "13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001) ; Conference date: 03-07-2001 Through 06-07-2001",

}

TY - CONF

T1 - Routing without flow control

AU - Busch, C.

AU - Herlihy, M.

AU - Wattenhofer, R.

PY - 2001

Y1 - 2001

N2 - We present the first dynamic hot-potato routing algorithm that does not require any form of explicit flow control: A node may inject a message into the network (n × n mesh) whenever a link is free. In the worst case, a node may have to wait an expected O(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected O(n) time steps. Both measures are optimal up to a constant factor.

AB - We present the first dynamic hot-potato routing algorithm that does not require any form of explicit flow control: A node may inject a message into the network (n × n mesh) whenever a link is free. In the worst case, a node may have to wait an expected O(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected O(n) time steps. Both measures are optimal up to a constant factor.

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

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

U2 - 10.1145/378580.378582

DO - 10.1145/378580.378582

M3 - Paper

AN - SCOPUS:0034824311

SP - 11

EP - 20

T2 - 13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001)

Y2 - 3 July 2001 through 6 July 2001

ER -

Routing without flow control

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this