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.