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


Journal Article

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 Authors

Cited Authors

  • Cole, R; Maggs, BM; auf der Heide, FM; Mitzenmacher, M; Richa, AW; Schroder, K; Sitaraman, RK; Vocking, B

Published Date

  • January 1, 1998

Published In

Start / End Page

  • 378 - 388

International Standard Serial Number (ISSN)

  • 0734-9025

Citation Source

  • Scopus