next up previous
Next: 1.5 Related work Up: 1 Introduction Previous: 1.3 Randomly-wired splitter networks

1.4 Our results

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 tex2html_wrap_inline1393 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 tex2html_wrap_inline1397 inputs and tex2html_wrap_inline1399 outputs between which a simple variant of the greedy algorithm can route any tex2html_wrap_inline1401 permutations in tex2html_wrap_inline1403 steps. Note that this is the best that we could hope for in general, since the adversary can always choose to isolate tex2html_wrap_inline1405 inputs and tex2html_wrap_inline1407 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 tex2html_wrap_inline1411 faults are randomly-placed in the multibutterfly, with probability near 1, the network can still deterministically route a permutation on tex2html_wrap_inline1415 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 tex2html_wrap_inline1421 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.

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996