On the fault-tolerant, high-performance multistage interconnection networks for ATM switching and multiprocessing

Abstract

In this thesis, we propose new fault-tolerant, high-performance multistage interconnection networks (MIN``s) and new fully-adaptive, deflection, self-routing schemes for the networks. These networks can provide more alternate paths than the related previous networks between an input/output pair of a network by adding extra links between switching elements (SE``s) in the same stage and modifying the self-routing scheme of the regular MIN. These routing schemes use not only the augmented links but also all already existing links to make the path when a fault, or a conflict, is occurred. Furthermore these networks are the internal packet-lossless MIN``s, and have the same number of SE``s as the banyan network. The presented fully-adaptive self-routing schemes are as simple as that of the regular MIN, which is based on the topological properties of the banyan network, which are discovered in this thesis. We show the SE``s in a stage are arranged regularly from an algebraic point of view: each stage of the banyan network is composed of the sequences of a cyclic group of SE``s. To derive the self-routing schemes, therefore, we can use not only the inter-stage relationships as the banyan network, but also the intra-stage relationships and even all relationships of all SE``s of the banyan network. Simple local routing decisions can be made, while the penalty is small. The SE``s of these schemes have a uniform structure respectively. We present algebraic proofs to show the correctness of the routing schemes, and present analytic reliability and performance analysis to provide quantitative comparisons with the banyan network, some augmented banyan networks, and other networks. Of the special notes is the finding that the networks are more cost-effective than the regular MIN and other augmented MIN``s in terms of the reliability, and even than the replicated MIN``s in terms of the performance. We also present the fault diagnosis methodology.