2-PASS REARRANGEABILITY IN FAULTY BENES NETWORKS

Existing fault-tolerant routing schemes for Benes networks either cons ider only the control line stuck-at faults, or handle the switch fault s by some graceful degradation routing schemes that reconfigure the ne twork into a smaller system with minimal loss. Now, even in the presen ce of a single switch fault in an N x N Benes network B(n), (n = log(2 )N), no N x N permutation can be realized in a single pass. In this pa per, we attempt to characterize the switch fault sets in B(n), in the presence of which the network is always capable of realizing any arbit rary N x N permutation P in two passes, such that any source-destinati on path is set up in a single pass, no recirculation is needed, but th e whole set of N source-destination paths of P is partitioned in two s ubsets and are realized in two successive passes. We propose an algori thm that will detect if the switch fault set present in a B(n), belong s to this class; if it is yes, we present another algorithm that compu tes the fault-tolerant routing to realize any arbitrary permutation P in two passes. This scheme enables us to make B(n) fault-tolerant in t he presence of a restricted class of multiple switch faults, without a ny recirculation through intermediate nodes, or any reconfiguration of the system. (C) 1996 Academic Press, Inc.