Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks

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.

• 1 Introduction
  • 1.1 Dilated butterflies
  • 1.2 Splitter networks
  • 1.3 Randomly-wired splitter networks and multibutterflies
  • 1.4 Our results
  • 1.5 Related work
  • 1.6 Outline
• 2 Routing without faults
  • 2.1 The algorithm
  • 2.2 The analysis
  • 2.3 Improving the constant factors
  • 2.4 Other improvements
• 3 Routing around faults
  • 3.1 Worst case faults
  • 3.2 Random faults
  • 3.3 On-line reconfiguration
• 4 Experiments
• 5 Remarks
• 6 Acknowledgments
• References
• About this document ...