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.