Some aspects of multistate interconnection networks: routing, rearrangeability and fault-tolerance
Seung‐Woo Seo · 1993
This dissertation deals with a variety of topics regarding multistage interconnection networks (MINs), including routing algorithm, the rearrangeability problem and the fault-tolerance issue. The 2$log\sb{2}N$- or 2($log\sb{2}N$ $-$ 1)-stage MINs are made by concatenating two $log\sb{2}N$-stage unique path networks. It is shown that there exists a topological equivalence among these $2log\sb{2}N$-stage networks. A class of $2log\sb{2}N$-stage networks including the concatenation of two omega networks are treated in detail, and the sufficient conditions for proper routing are discussed. A general routing algorithm is developed that routes a class of symmetric networks. The algorithm routes the network from center stages to outer stages at both the input and output sides simultaneously. The algorithm presented is simpler and more flexible than the well-known looping algorithm, in that it can be applied adaptively according to the structure of a network. It can be applied to routing the network regardless of the center stage connection patterns, i.e., straight, skewed straight, simple butterfly or skewed butterfly, as long as the network is symmetric. Based on the routing algorithm, we examine the rearrangeability of the omega+omega network. By proving that the $2log\sb{2}N$-stage omega+omega network is rearrangeable, we improve the best known upper bound in the number of stages in a shuffle-exchange network to $2log\sb{2}N$. In addition to the generality, it is shown that the algorithm can provide a higher degree of fault-tolerance than any other algorithms known so far. We show that, with alternate ways in realizing a permutation, any single control fault can be tolerated, and show also that some double faults can be tolerated under some conditions. From the practical point of view, we also propose a fault-tolerating network called composite banyan network. The $log\sb{2}N$-stage composite banyan network is composed of 3 $\times$ 3 switching elements. Instead of using a complex numerical calculation to find a path, the proposed network uses a simple routing tag to find paths between any source and destination pairs. It is shown that the composite banyan network is faster, more reliable and more cost-efficient than any other networks that use 3 $\times$ 3 switching elements.