next up previous
Next: 3.1 Worst case faults Up: Fast Algorithms for Routing Previous: 2.4 Other improvements

3 Routing around faults


In this section, we prove that the multibutterfly is a highly fault-tolerant network. We start by considering worst case faults in Section 3.1 and then consider the less malevolent case of random faults in Section 3.2. For simplicity, we will assume that tex2html_wrap_inline1935 , although similar results can be proved for smaller d. On-line algorithms for reconfiguring around faults are discussed in Section 3.3.

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