Impact of Raising Switching Stages on the Reliability of Interconnection Networks

Mohsen Jahanshahi

1. Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.
Email: [email protected]
2. Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.
IEEE Senior Member, Email: [email protected]
*Corresponding author

Multistage Interconnection Networks (MINs) are a cost-effective idea for connection between different nodes in multi-processor systems. In the meantime, understanding the impact of increasing the number of stages (i.e. a famous method for improving fault tolerance) on the reliability of these networks is essential. Last studies on this challenging issue, revealed that adding one switching stage to MINs is preferable to two in terms of reliability. However, there were some non-negligible gaps in previous researches: (i) The probability of failure for terminal nodes was not considered in the calculation of reliability. (ii) Numerical results were only based on the small size of the network, i.e. 8 × 8. (iii) Reliability analyses were time-independent. (iv) The lack of some important parameters such as the mean time to failure and availability was noticeable. Therefore, this paper will take a more comprehensive analysis of reliability to meet the above specifications.

Shuffle-exchange networks, Reliability, Fault tolerance, Mean time to failure, Failure rate, Availability

Fathollah Bistouni, Mohsen Jahanshahi (2020). Impact of Raising Switching Stages on the Reliability of Interconnection Networks. Journal of the Institute of Electronics and Computer, 2, 93-120. https://doi.org/10.33969/JIEC.2020.21007.

[1] Fathollah Bistouni and Mohsen Jahanshahi. "Determining the reliability importance of switching elements in the shuffle-exchange networks." International Journal of Parallel, Emergent and Distributed Systems (2018): 1-29.
[2] Fathollah Bistouni and Mohsen Jahanshahi. "Reliability analysis of multilayer multistage interconnection networks." Telecommunication Systems 62.3 (2016): 529-551.
[3] Neeraj Kumar Goyal and S. Rajkumar. "Multi-source multi-terminal reliability evaluation of interconnection networks." Microsystem Technologies 23.1 (2017): 255-274.
[4] Nima Jafarzadeh, et al. "Low Energy yet Reliable Data Communication Scheme for Network-on-Chip." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34.12 (2015): 1892-1904.
[5] Mohsen Jahanshahi and Fathollah Bistouni. Crossbar-Based Interconnection Networks: Blocking, Scalability, and Reliability. Springer, Switzerland, 2018.
[6] Dimitris C. Vasiliadis, George E. Rizos, Costas Vassilakis, and E. Glavas. "Modelling and performance evaluation of a novel internal-priority routing scheme for finite-buffered multistage interconnection networks." International Journal of Parallel, Emergent and Distributed Systems 26.5 (2011): 381-397.
[7] John Garofalakis and Eleftherios Stergiou. "Analytical model for performance-evaluation of multistage interconnection networks supporting multi-class priority service." International Journal of Parallel, Emergent and Distributed Systems 26.5 (2011): 399-427.
[8] Nur Arzilawati Md Yunus and Mohamed Othman. "Empirical analysis of terminal reliability in multistage interconnection networks." Computational Intelligence and Efficiency in Engineering Systems. Springer International Publishing, 2015. 157-169.
[9] Nitin, Garhwal, Shruti, and Neha Srivastava. "Designing a fault-tolerant fully-chained combining switches multi-stage interconnection network with disjoint paths." Journal of Supercomputing 55.3 (2011): 400-431.
[10] Roselin Petagon and Jeeraporn Werapun. "Embedding the optimal all-to-all personalized exchange on multistage interconnection networks+." Journal of Parallel and Distributed Computing 88 (2016): 16-30.
[11] Mehrnaz Moudi and Mohamed Othman. "A GreedyZero algorithm to minimise the conflicts in an Optical Multistage Interconnection Network." Journal of Network and Computer Applications 41 (2014): 312-318.
[12] Dimitris C. Vasiliadis, George E. Rizos, and Costas Vassilakis. "Class-based weighted fair queuing scheduling on quad-priority Delta Networks." International Journal of Parallel, Emergent and Distributed Systems 27.5 (2012): 435-457.
[13] Dietmar Tutsch and Günter Hommel. "MLMIN: a multicore processor and parallel computer network topology for multicast." Computers & Operations Research 35.12 (2008): 3807-3821.
[14] Eleftherios Stergiou and John Garofalakis. "Quantitative analysis of multilayer switching networks providing multiple internal routes." International Journal of Communication Systems (2018). https://doi.org/10.1002/dac.3785
[15] Indra Gunawan. "Redundant paths and reliability bounds in gamma networks." Applied Mathematical Modelling 32.4 (2008): 588-594.
[16] Indra Gunawan. "Reliability prediction of distributed systems using Monte Carlo method." International Journal of Reliability and Safety 7.3 (2013): 235-248.
[17] Fathollah Bistouni and Mohsen Jahanshahi. "Rearranging links: a cost-effective approach to improve the reliability of multistage interconnection networks." International Journal of Internet Technology and Secured Transactions 8.3 (2018): 336-373.
[18] Mohsen Jahanshahi and Fathollah Bistouni. "Improving the reliability of the Benes network for use in large-scale systems." Microelectronics Reliability 55.3 (2015): 679-695.
[19] Mohsen Jahanshahi and Fathollah Bistouni. "A new approach to improve reliability of the multistage interconnection networks." Computers & Electrical Engineering 40.8 (2014): 348-374.
[20] Fathollah Bistouni and Mohsen Jahanshahi. "Improved extra group network: a new fault-tolerant multistage interconnection network." Journal of Supercomputing 69.1 (2014): 161-199.
[21] Fathollah Bistouni and Mohsen Jahanshahi. "Pars network: a multistage interconnection network with fault-tolerance capability." Journal of Parallel and Distributed Computing 75 (2015): 168-183.
[22] Fathollah Bistouni and Mohsen Jahanshahi. "Scalable crossbar network: a non-blocking interconnection network for large-scale systems." The Journal of Supercomputing 71.2 (2015): 697-728.
[23] S. Rajkumar and Neeraj Kumar Goyal. "Reliable multistage interconnection network design." Peer-to-Peer Networking and Applications 9.6 (2016): 979-990.
[24] Nur Arzilawati Md Yunus and Mohamed Othman. "Reliability Evaluation and Routing Integration in Shuffle Exchange Omega Network." Journal of Networks 9.7 (2014): 1732-1737.
[25] Fathollah Bistouni and Mohsen Jahanshahi. "Formulating broadcast reliability equations on multilayer multistage interconnection networks." The Journal of Supercomputing 71.11 (2015): 4019-4041.
[26] Fathollah Bistouni and Mohsen Jahanshahi. "Evaluating failure rate of fault-tolerant multistage interconnection networks using Weibull life distribution." Reliability Engineering & System Safety 144 (2015): 128-146.
[27] James T. Blake and Kishor S. Trivedi. "Multistage interconnection network reliability." IEEE Transactions on Computers 38.11 (1989): 1600-1604.
[28] Indra Gunawan. "Reliability analysis of shuffle-exchange network systems." Reliability Engineering & System Safety 93.2 (2008): 271-276.
[29] Fathollah Bistouni and Mohsen Jahanshahi. "Analyzing the reliability of shuffle-exchange networks using reliability block diagrams." Reliability Engineering & System Safety 132 (2014): 97-106.
[30] Daniel P. Siewiorek, et al. "A case study of C.mmp, Cm*, and C.vmp: Part II—Predicting and calibrating reliability of multiprocessor systems." Proceedings of the IEEE 66.10 (1978): 1200-1220.
[31] James T. Blake and Kishor S. Trivedi. "Reliability analysis of interconnection networks using hierarchical composition." IEEE Transactions on Reliability 38.1 (1989): 111-120.
[32] Chita R. Das and Laxmi N. Bhuyan. "Bandwidth availability of multiple-bus multiprocessors." IEEE Transactions on Computers 100.10 (1985): 918-926.
[33] Mark L. Ayers. Telecommunications System Reliability Engineering, Theory, and Practice.  John Wiley & Sons, Hoboken, New Jersey. 2012.
[34] Fathollah Bistouni and Mohsen Jahanshahi. "Reliability Analysis of Ethernet Ring Mesh Networks." IEEE Transactions on Reliability 66.4 (2017): 1238-1252.
[35] Liudong Xing. "Reliability evaluation of phased-mission systems with imperfect fault coverage and common-cause failures." IEEE Transactions on Reliability 56.1 (2007): 58-68.
[36] S. Prabhudeva and A. K. Verma. "Coverage modeling and reliability analysis using multi-state function." International Journal of Automation and Computing 4.4 (2007): 380-387.
[37] Kuo-Hsiung Wang, Tseng-Chang Yen, and Jen-Ju Jian. "Reliability and sensitivity analysis of a repairable system with imperfect coverage under service pressure condition." Journal of Manufacturing Systems 32.2 (2013): 357-363.
[38] Madhu Jain. "Availability prediction of imperfect fault coverage system with reboot and common cause failure." International Journal of Operational Research 17.3 (2013): 374-397.
[39] Kishor S. Trivedi. Probability and Statistics with Reliability, Queueing, and Computer Science Applications. Wiley, New York, 2008.
[40] Jau-Chuan Ke, Ssu-Lang Lee, and Ying-Lin Hsu. "On a repairable system with detection, imperfect coverage and reboot: Bayesian approach." Simulation Modelling Practice and Theory 16.3 (2008): 353-367.
[41] Jau-Chuan Ke and Tzu-Hsin Liu. "A repairable system with imperfect coverage and reboot." Applied Mathematics and Computation 246 (2014): 148-158.
[42] Madhu Jain and Rakesh Kumar Meena. "Fault tolerant system with imperfect coverage, reboot and server vacation." Journal of Industrial Engineering International 13.2 (2017): 171-180.