Next: 4 Remarks Up: 3 Routing around faults Previous: 3.3.5 A final look

## 3.4 Removing the additional edges

The algorithm of Section 3.3 augments the multibutterfly network with two types of edges. First edges are added from each switch to switches in the same block. Then edges are added from each switch to both the upper and lower blocks at the next level. The second type of edges are easily removed. Their tasks can be performed by the d routing edges leading from each switch to the upper and lower blocks at the next level.

Removing the first type of edges is more problematic. The basic idea is to simulate them using the d routing edges. We begin by observing that a randomly-wired splitter is likely to have expansion both from the inputs to the outputs and from the outputs to the inputs [7, 12]. Let be the expansion property from the output blocks (taken together) to their input block. Then , and will be close to 2d-1, provided that is sufficiently small. A set of input switches in a block of size M has at least output neighbors (counting those in both the upper and lower blocks). These outputs in turn have at least input neighbors, provided . Thus, as long as none of the output neighbors are faulty, they can be used to simulate expansion within the block. This expansion can be used in place of in the algorithm of Section 3.3. What if some of these output neighbors are faulty? This problem can be solved by declaring a switch to be faulty if any of its output neighbors are faulty (without propagating any faults) before the reconfiguration process begins. This trick may multiply the number of faults in the network by a factor of 2d, but if a switch survives then all of its output neighbors were initially working.

Next: 4 Remarks Up: 3 Routing around faults Previous: 3.3.5 A final look

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996