TY - JOUR
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
N1 - Funding Information:
* This work has been funded by the CCETr Rennes, France. Patent Pending. ** T616com-Paris, D6partement Signal, 46, rue Barrault, F-75634 Paris Cedex 13, France. {courvill,duhamel}@sig.enst.fr. *** CNET-CCETr, rue du Clos Courtel, F-35512 Cesson-S6vign6, France. E-mail : {courvill,duhamel}@sig.enst.fr.
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
U2 - 10.1145/276698.276790
DO - 10.1145/276698.276790
M3 - Conference article
AN - SCOPUS:0031644240
SN - 0734-9025
SP - 378
EP - 388
JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
T2 - Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing
Y2 - 23 May 1998 through 26 May 1998
ER -