next up previous
Next: 1 Introduction

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

F. Thomson Leighton tex2html_wrap_inline1131 and Bruce M. Maggs tex2html_wrap_inline1133

Abstract-This paper describes simple deterministic tex2html_wrap_inline1135 -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.

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996
anonymous logging image