Startseite > Publikationen > Publikationen

Publikationen

Cole, Richard;Maggs, Bruce;Meyer auf der Heide, Friedhelm;Mitzenmacher, Michael;Richa, Andrea;Schröder, Klaus;Sitaraman, Ramesh;Vöcking, Berthold:

Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.

STOC 1998 : S. 378 - 388, Jun. 1998

Abstract

In this paper we study randomized algorithms for circuit switching on the butterfly and related multistage networks. Our goal is to devise algorithms that construct circuits (or paths) for the messages such that the congestion, dilation, and setup time are small. We introduce two new circuit routing algorithms: the collision protocol and the minimum protocol. Utilizing the collision protocol, we show that any static permutation routing problem on the n-input two-fold butterfly network BBn can be routed with congestion O(loglog n / logloglog n), dilation 2 log n, and setup time O(log n loglog n) with high probability. Next, using the minimum protocol, we show that any dynamic permutation routing problem on the n-input two-fold butterfly network BBn can be routed with congestion O(loglog n), with high probability. The dilation of the paths is 2 log n and the setup time for each new message is O(log n). Prior to this work, every known algorithm for the dynamic permutation routing problem on butterfly and related networks required Omega(log n/loglog n) congestion. Finally, as a further application of our techniques, we propose a novel design for a data server.

Dateien

hni1827.pdf



Bibtex

@article{hniid=1827,
author = {Cole, Richard and Maggs, Bruce and Meyer auf der Heide, Friedhelm and Mitzenmacher, Michael and Richa, Andrea and Schr{\"o}der, Klaus and Sitaraman, Ramesh and V{\"o}cking, Berthold},
title = {Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks},
journal = {STOC 1998},
pages = {378 - 388},
month = jun,
year = {1998},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1827