Randomized protocols for low-congestion circuit routing in multistage interconnection networks

Richard Cole; Bruce M. Maggs; Friedhelm Meyer auf der Heide; Michael Mitzenmacher; Andrea W. Richa; Klaus Schroder; Ramesh K. Sitaraman; Berthold Vocking

Randomized protocols for low-congestion circuit routing in multistage interconnection networks

Richard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andrea W. Richa, Klaus Schroder, Ramesh K. Sitaraman, Berthold Vocking

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

31 Scopus citations

Abstract

In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

Original language	English (US)
Title of host publication	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
Editors	Anon
Publisher	ACM
Pages	378-388
Number of pages	11
State	Published - 1998
Event	Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA Duration: May 23 1998 → May 26 1998

Other

Other	Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing
City	Dallas, TX, USA
Period	5/23/98 → 5/26/98

ASJC Scopus subject areas

Software

Cite this

Cole, R, Maggs, BM, auf der Heide, FM, Mitzenmacher, M, Richa, AW, Schroder, K, Sitaraman, RK & Vocking, B 1998, Randomized protocols for low-congestion circuit routing in multistage interconnection networks. in Anon (ed.), Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM, pp. 378-388, Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, USA, 5/23/98.

@inproceedings{d1cab1a3eab34208ae48c6581b127718,

title = "Randomized protocols for low-congestion circuit routing in multistage interconnection networks",

abstract = "In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.",

author = "Richard Cole and Maggs, {Bruce M.} and {auf der Heide}, {Friedhelm Meyer} and Michael Mitzenmacher and Richa, {Andrea W.} and Klaus Schroder and Sitaraman, {Ramesh K.} and Berthold Vocking",

year = "1998",

language = "English (US)",

pages = "378--388",

editor = "Anon",

booktitle = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "ACM",

note = "Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing ; Conference date: 23-05-1998 Through 26-05-1998",

}

TY - GEN

T1 - Randomized protocols for low-congestion circuit routing in multistage interconnection networks

AU - Cole, Richard

AU - Maggs, Bruce M.

AU - auf der Heide, Friedhelm Meyer

AU - Mitzenmacher, Michael

AU - Richa, Andrea W.

AU - Schroder, Klaus

AU - Sitaraman, Ramesh K.

AU - Vocking, Berthold

PY - 1998

Y1 - 1998

N2 - In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

AB - In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

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

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

M3 - Conference contribution

SP - 378

EP - 388

BT - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

A2 - Anon, null

PB - ACM

T2 - Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing

Y2 - 23 May 1998 through 26 May 1998

ER -

Randomized protocols for low-congestion circuit routing in multistage interconnection networks

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this