Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks
Frank Thomson Leighton, Bruce MacDowell Maggs · IEEE Transactions on Computers · 1992
Simple deterministic O(log N)-step algorithms for routing permutations of packets in multibutterflies and randomly wired splitter networks are described. The algorithms are robust against faults (even in the worst case), and are efficient from a practical point of view. As a consequence, it is found that the multibutterfly is an excellent candidate for a high-bandwidth low-diameter switching network underlying a shared-memory machine.>