Designing a Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network with Disjoint Paths

摘要

Multi-stage Interconnection Networks (MINs) are designed to achieve fault-tolerance and collision solving by providing a set of disjoint paths. Ching-Wen Chen and Chung-Ping Chung had proposed a fault-tolerant network called Combining Switches Multi-stage Interconnection Network (CSMIN) and an inaccurate algorithm that provided two correct disjoint paths only for some source-destination pairs. This paper provides a more comprehensive and accurate algorithm that always generate correct routing-tags for two disjoint paths for every source-destination pair in the CSMIN. The 1-fault tolerant CSMIN causes the two disjoint paths to have regular distances at each stage. Moreover, our algorithm backtracks a packet to the previous stage and takes the other disjoint path in the event of a fault or a collision in the network. Furthermore, to eliminate the backtracking penalties of CSMIN, we propose a new design called Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network (FCSMIN). It has similar characteristics of 1-fault tolerance and two disjoint paths between any source-destination pair, but it can tolerate only one link or switch fault at each stage without backtracking. Our simulation and comparative analysis result shows that FCSMIN has added advantages of destination-tag routing, lower hardware costs, strong reroutability, lower preprocessing overhead, and higher fault-tolerance power in comparison to CSMIN.