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 permutations from some set of inputs to some set of outputs in 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 permutations between some set of inputs and outputs in 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 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: 2 Butterflies and Multibutterflies Up: A Parallel Algorithm for Previous: A Parallel Algorithm for

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