A fault tolerant multistage interconnection network and its fault diagnosis: the ring-banyan network

In this paper, we describe the fault tolerant schemes for the multistage in terconnection network (MIN) and its fault diagnosis. first, we present a fa ult tolerant MIN and an adaptive self-routing scheme for the network. It ca n provide more multiple paths than the previous networks between an input/o utput pair of a network by adding extra links between switching elements in the same stage and modifying the self-routing scheme of the regular MIN. T he presented routing scheme is as simple as that of the regular MIN, which is based on the topological relationships among the switching elements (SEs ) that render a packet to the same destination with the regular self-routin g. We also show the SEs in a stage are arranged regularly each stage of the banyan network is constructed with sequences of a cyclic group of SEs, whi ch are discovered in this paper. We present an algebraic proof to show the correctness of the routing scheme. We also present an analysis to provide q uantitative comparisons with the replicated networks. Second, we consider t he fault models in the fault detection and the location schemes. We present a new fault diagnosis scheme for the network.