next up previous
Next: 4 Experiments Up: 3 Routing around faults Previous: 3.2 Random faults

3.3 On-line reconfiguration


Deciding which switches to remove from the network using the procedure described in Sections 3.1 and 3.2 is straightforward if we can reconfigure the network off-line. On-line reconfiguration is more challenging, however. The hard part is deciding locally which splitters contain too many faults at the input, since this calculation must be performed in the presence of faults. Fast on-line algorithms for this task are described by Goldberg, Plotkin, and Maggs in [9].

Once the splitters containing too many faults are erased, then it is a simple matter to propagate faults back through the network. Each switch simply checks its up and down output neighbors to see how many are faulty. As we will see in Section 4, the multibutterfly can tolerate a surprisingly large number of random faults without having to erase any inputs or outputs at all, so this simple fault propagation technique may be sufficient for reconfiguring multibutterflies in practice.

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