FAULT IDENTIFICATION AND ROUTING IN BENES NETWORKS

An N x N Benes network B(n) (n = log(2) N), being a rearrangeable netw ork, can realize any N x N permutation in a single pass. But even in t he presence of a single switch fault in B(n), two passes are necessary to realize any N x N permutation. In this paper, we attempt to charac terize the switch fault sets in B(n), in the presence of which the net work is always capable of realizing any arbitrary N x N permutation P in two passes, such that every source-destination connection is set up in a single pass, i.e., no recirculation is needed, but the whole set of N source-destination connections of P is partitioned in two subset s and are realized in two successive passes. An algorithm has been dev eloped to test if the faulty B(n) is capable of realizing any arbitrar y permutation in two passes by our technique; if it is yes, another al gorithm also has been presented that computes the fault-tolerant routi ng to realize any arbitrary permutation P in two passes, through the f aulty B(n). Finally, for this routing technique, the exact locations o f the faults are not important, only the information of some optimal r egions around the fault is sufficient. This feature actually enables u s to develop very fast and simple procedures for identification of fau lty regions of B(n), in the presence of multiple switch faults. Theref ore, this fault-tolerant routing scheme enables us to make B(n) fault- tolerant in the presence of an easily-testable class of multiple switc h faults, without any recirculation through intermediate nodes, or any reconfiguration of the system.