F. Thomson Leighton and Bruce M. Maggs
Abstract-This paper describes simple deterministic -step algorithms for routing permutations of packets in multibutterflies and randomly-wired splitter networks. The algorithms are robust against faults (even in the worst case), and are efficient from a practical point of view. As a consequence, we find that the multibutterfly is an excellent candidate for a high-bandwidth low-diameter switching network underlying a shared-memory machine.
Index Terms-Fault tolerance, interconnection network, multibutterfly, multi-stage network, routing algorithm.