Fault tolerance of multistage interconnection networks (MINs) has been an important issue for many years. Multiple-pass routing is a technique to make a MIN fault tolerant without adding redundant circuits. The basic idea of multiple-pass routing is to route a packet through a faulty MIN several times, if necessary, until it is delivered to its proper destination. In order to utilize multiple-pass routing schemes, a faulty MIN must possess the dynamic full access (DFA) property. We present a simple procedure for testing the DFA property of a faulty MIN based on a theorem from graph theory. The testing procedure can be applied to find all the subsystems possessing DFA property. Besides, we also introduce the concept of possessing the DFA property within k passes. The shortest path algorithms are applied to check whether or not a faulty MIN possesses the DFA property within k passes.
展开▼