- Fast algorithms for routing around faults in
multibutterflies and randomly-wired splitter networks. F. T.
Leighton and B. M. Maggs, IEEE Transactions on Computers,
Vol. 41, No. 5, May 1992, pp. 578-587.
- This paper describes a simple, practical, deterministic algorithm for
routing permutations of packets in N-input multibutterfly networks.
The algorithm is robust in the presence of faults. For example, even
if an adversary selects f switches in the network to fail, the
algorithm can still route any permutation between some set of N-O(f)
inputs and N-O(f) outputs in O(log N) time. Furthermore, if
every switch fails independently with some fixed probability p, the
network can route any permutation between some set of Theta(N)
inputs and Theta(N) outputs in O(log N) time.
- Back to other
- Back to my home page