Next: 3.3.1 Blocks with too Up: 3 Routing around faults Previous: 3.2 The Leighton-Maggs algorithm

## 3.3 On-line reconfiguration

This section presents an algorithm for determining which switches to remove from the network in time. The algorithm is on-line in the sense that the computation is performed entirely by the switches, without the aid of any off-line computation. As in Section 3.2, the reconfiguration of the network consists of two parts. First, each splitter must determine if the number of faults in its input block exceeds an fraction, and, if so, then it must erase itself. This part is difficult because each splitter must count its own faults and distribute the count to its working switches, even though the splitter itself may contain many faults. Second, faults are propagated from the outputs of the network towards the inputs. A switch is declared faulty if more than of its upper or lower output edges lead to switches that are faulty, but not erased. After erasure and fault propagation, all of the remaining faulty switches are erased.

The erasure part consists of two tasks. First, we must identify those blocks that contain too many faults and must be erased. Then for each splitter, each input switch must be told whether either of the two output blocks in the splitter have been erased. To help with these tasks, we add some edges to the network. In particular, each switch is connected in a random fashion to other switches in the same block. These edges will be used solely for the purpose of counting, and not for routing. They increase the VLSI layout area of the network by at most a constant factor. For sufficiently small, but fixed, , with probability close to 1, every set S of switches in a block of size M will have at least neighbors [7, 12]. We will choose to be small so that will be close to .

Next: 3.3.1 Blocks with too Up: 3 Routing around faults Previous: 3.2 The Leighton-Maggs algorithm

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