next up previous
Next: 2 Butterflies and Multibutterflies Up: A Parallel Algorithm for Previous: A Parallel Algorithm for

1 Introduction

Recently Leighton and Maggs showed that a multibutterfly network can sustain many faults and still route packets efficiently [6]. In particular, they showed that an N-input multibutterfly network can tolerate f worst-case faults, and still route any tex2html_wrap_inline561 permutationsgif from some set of tex2html_wrap_inline567 inputs to some set of tex2html_wrap_inline569 outputs in tex2html_wrap_inline571 time. In the case of random faults, the performance is even better. Even if every switch fails with some fixed constant probability, an N-input multibutterfly can route tex2html_wrap_inline575 permutations between some set of tex2html_wrap_inline577 inputs and tex2html_wrap_inline579 outputs in tex2html_wrap_inline581 time. (For a description of these and related results see [6].)

The Leighton-Maggs strategy for tolerating faults consists of two parts. First the network is reconfigured. Reconfiguring a network consists of identifying those parts that contain too many faults to be useful for routing, and removing them from the network. The goal is to leave intact as much of the working hardware as possible, while maintaining the important structural properties of the network. In the case of the multibutterfly, the crucial property is expansion (defined in Section 2). The Leighton-Maggs reconfiguration algorithm reduces the expansion of the network somewhat. However, as long as the reconfigured network has some expansion it is possible to apply a routing algorithm that was designed to run on a fault-free multibutterfy. Thus, the second part of the strategy is to apply an off-the-shelf multibutterfly routing algorithm, such as Upfal's permutation routing algorithm [12].

One of the drawbacks of the Leighton-Maggs reconfiguration algorithm is that it is performed by an off-line computer with knowledge of the state of the entire routing network. This paper presents an on-line algorithm for reconfiguring the network in tex2html_wrap_inline583 time. The algorithm is performed entirely by the network, even though many of its switches may be faulty.

The remainder of this paper consists of two sections. In Section 2 we describe butterfly and multibutterfly networks. In Section 3 we review the reconfiguration algorithm of Leighton and Maggs and then describe the on-line algorithm.



next up previous
Next: 2 Butterflies and Multibutterflies Up: A Parallel Algorithm for Previous: A Parallel Algorithm for



Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996