- Randomized protocols for low-congestion
circuit routing in multistage interconnection
networks. R. Cole, B. M. Maggs, F. Meyer auf der Heide,
M. Mitzenmacher, A. W. Richa, K. Schroeder, R. K. Sitaraman, and
B. Voecking. Proceedings of the 29th Annual ACM Symposium
on the Theory of Computing (STOC), May 1998, pp. 378-388.
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.
- Back to other
- Back to my home page