Fault tolerance of banyan using multiple-pass

In order to utilize multiple-pass routing schemes, a faulty banyan network must possess the dynamic full access (DFA) property. The authors determine a necessary and sufficient condition for a banyan network to possess the DFA property and design a general testing procedure based on the condition. They also enumerate the probability that a banyan network loses the DFA property, given the number of faulty switch elements. It is found that, as long as faults do not occur in switch elements located in the first and last stages, this probability is very small even when there are quite a few faulty switch elements. Therefore, multiple-pass routing schemes can be very useful if the switch elements in the first and last stages are well protected