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.

Mon Jul 22 18:45:42 EDT 1996