In this paper, we provide a substantially simpler analysis of the
greedy routing algorithm on multibutterflies, and as a consequence,
derive much smaller constant factors for the 
time bound.
The analysis uses a potential function argument that may eventually
prove to be useful for other routing problems as well.
More importantly, we show that the multibutterfly is highly
fault-tolerant. In particular, we prove that no matter how an
adversary chooses f switches to fail, there will be at least
inputs and 
outputs between which a simple variant of
the greedy algorithm can route any 
permutations in 
steps. Note that this is the best that we could hope for in
general, since the adversary can always choose to isolate 
inputs and 
outputs by carefully selecting f faults. In
the more commonly studied model of randomly located faults
[10, 25, 26], we can do even better.
For example, even if 
faults are randomly-placed in
the multibutterfly, with probability near 1, the network can still
deterministically route a permutation on 
inputs and
outputs. Thus the multibutterfly becomes the first bounded-degree
network known to be able to sustain large numbers of faults with only
minimal degradation in performance.
We also consider the experimental performance of the algorithms for
N=1024 inputs. Interestingly, we find that randomly-wired splitter
networks with multiplicity 2 outperform 2-dilated butterflies with
equivalent hardware on random routing problems, even if the splitter
network has 100 faults. On worst-case routing problems such as
transpose and bit reversal, the randomly-wired splitter networks
perform substantially better than the dilated butterflies, which take
steps. Hence, randomly-wired splitter networks
appear to be good candidates for high-bandwidth, low-diameter
switching networks underlying a shared-memory machine such as the BBN
butterfly.