Randomized protocols for low-congestion circuit routing in multistage interconnection networks
Publication
, Journal Article
Cole, R; Maggs, BM; auf der Heide, FM; Mitzenmacher, M; Richa, AW; Schroder, K; Sitaraman, RK; Vocking, B
Published in: Conference Proceedings of the Annual Acm Symposium on Theory of Computing
January 1, 1998
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.
Duke Scholars
Published In
Conference Proceedings of the Annual Acm Symposium on Theory of Computing
DOI
ISSN
0734-9025
Publication Date
January 1, 1998
Start / End Page
378 / 388
Citation
APA
Chicago
ICMJE
MLA
NLM
Cole, R., Maggs, B. M., auf der Heide, F. M., Mitzenmacher, M., Richa, A. W., Schroder, K., … Vocking, B. (1998). Randomized protocols for low-congestion circuit routing in multistage interconnection networks. Conference Proceedings of the Annual Acm Symposium on Theory of Computing, 378–388. https://doi.org/10.1145/276698.276790
Cole, R., B. M. Maggs, F. M. auf der Heide, M. Mitzenmacher, A. W. Richa, K. Schroder, R. K. Sitaraman, and B. Vocking. “Randomized protocols for low-congestion circuit routing in multistage interconnection networks.” Conference Proceedings of the Annual Acm Symposium on Theory of Computing, January 1, 1998, 378–88. https://doi.org/10.1145/276698.276790.
Cole R, Maggs BM, auf der Heide FM, Mitzenmacher M, Richa AW, Schroder K, et al. Randomized protocols for low-congestion circuit routing in multistage interconnection networks. Conference Proceedings of the Annual Acm Symposium on Theory of Computing. 1998 Jan 1;378–88.
Cole, R., et al. “Randomized protocols for low-congestion circuit routing in multistage interconnection networks.” Conference Proceedings of the Annual Acm Symposium on Theory of Computing, Jan. 1998, pp. 378–88. Scopus, doi:10.1145/276698.276790.
Cole R, Maggs BM, auf der Heide FM, Mitzenmacher M, Richa AW, Schroder K, Sitaraman RK, Vocking B. Randomized protocols for low-congestion circuit routing in multistage interconnection networks. Conference Proceedings of the Annual Acm Symposium on Theory of Computing. 1998 Jan 1;378–388.
Published In
Conference Proceedings of the Annual Acm Symposium on Theory of Computing
DOI
ISSN
0734-9025
Publication Date
January 1, 1998
Start / End Page
378 / 388