caa a22 4500 445852143 CHVBK 20180317145416.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s11227-009-0336-z doi (NATIONALLICENCE)springer-10.1007/s11227-009-0336-z Designing a Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network withDisjoint Paths [Elektronische Daten] [Nitin,, Shruti Garhwal, Neha Srivastava] 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. Springer Science+Business Media, LLC, 2009 Multi-stage Interconnection Network nationallicence Combining Switches Multi-stage Interconnection Network nationallicence Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network nationallicence Collision solving nationallicence Routing-tag Algorithm nationallicence Rerouting tag nationallicence Distance-tag algorithm and Disjoint Paths nationallicence Nitin, Department of Computer Science and Engineering and Information Technology, Jaypee University of Information and Technology, Waknaghat, 173215, Solan, Himachal Pradesh, India aut Garhwal Shruti Accenture Services Private Limited, Building 1B, Raheja Mindspace, 500081, Madhapur, Hyderabad, India aut Srivastava Neha Accenture Services Private Limited, Tower 5, Cybercity, 143, Magarpatta City, Hadapsar-Mundhwa Road, 411013, Hadapsar, Pune, India aut The Journal of Supercomputing Springer US; http://www.springer-ny.com 55/3(2011-03-01), 400-431 0920-8542 55:3<400 2011 55 11227 https://doi.org/10.1007/s11227-009-0336-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11227-009-0336-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Nitin Department of Computer Science and Engineering and Information Technology, Jaypee University of Information and Technology, Waknaghat, 173215, Solan, Himachal Pradesh, India aut NATIONALLICENCE 700 1- Garhwal Shruti Accenture Services Private Limited, Building 1B, Raheja Mindspace, 500081, Madhapur, Hyderabad, India aut NATIONALLICENCE 700 1- Srivastava Neha Accenture Services Private Limited, Tower 5, Cybercity, 143, Magarpatta City, Hadapsar-Mundhwa Road, 411013, Hadapsar, Pune, India aut NATIONALLICENCE 773 0- The Journal of Supercomputing Springer US; http://www.springer-ny.com 55/3(2011-03-01), 400-431 0920-8542 55:3<400 2011 55 11227 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer