• 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.

  HTML Postscript Compressed Postscript
  Back to other publications

  Back to my home page