Interconnection Network Reliability Evaluation

Dr. Neeraj Kumar Goyal is currently an Associate Professor in Subir Chowdhury School of Quality and Reliability, Indian Institute of Technology (IIT), Kharagpur, India. He received his PhD degree from IIT Kharagpur in reliability engineering in 2006.His areas of research and teaching are network reliability, software reliability, electronic system reliability, reliability testing, probabilistic risk/safety assessment, and reliability design. He has completed various research and consultancy projects for various organizations, e.g. DRDO, NPCIL, Vodafone, and ECIL. He has contributed several research papers to various international journals and conference proceedings. Dr. S. Rajkumar received his BE (Distinction) and ME (Distinction) degrees from Anna University, India, in 2009 and 2011, respectively. He obtained his PhD from the Indian Institute of Technology Kharagpur, India in 2017. Currently working as an Assistant Professor in Department of ECE at Adama Science and Technology University (ASTU), Ethiopia. His research interests include reliability engineering and interconnection networks. He has contributed notable research papers to international journals.

• Series Editor Preface ixPreface xiii1 Introduction 11.1 Introduction 11.2 Network Reliability Measures 21.3 The Probabilistic Graph Model 41.4 Approaches for Network Reliability Evaluation 61.5 Motivation and Summary 72 Interconnection Networks 112.1 Interconnection Networks Classification 112.2 Multistage Interconnection Networks (MINs) 142.3 Research Issues in MIN Design 152.4 Some Existing MINs Implementations 192.5 Review of Topological Fault Tolerance 202.5.1 Redundant and Disjoint Paths 222.5.2 Backtracking 262.5.3 Dynamic Rerouting 272.6 MIN Topological Review on Disjoint Paths 272.6.1 Single-Disjoint Path Multistage Interconnection Networks 272.6.2 Two-Disjoint Paths Multistage Interconnection Networks 362.6.3 Three-Disjoint Paths Multistage Interconnection Networks 472.6.4 Four-Disjoint Paths Multistage Interconnection Networks 512.7 Hardware Cost Analysis 552.8 Observations 602.9 Summary 613 MIN Reliability Evaluation Techniques 633.1 Reliability Performance Criterion 633.1.1 Two Terminal or Terminal Pair Reliability (TPR) 643.1.2 Network or All Terminal Reliability (ATR) 643.1.3 Broadcast Reliability 653.2 Approaches for Reliability Evaluation 663.2.1 Continuous Time Markov Chains (CTMC) 673.2.2 Matrix Enumeration 673.2.3 Conditional Probability (CP) Method 673.2.4 Graph Models 693.2.5 Decomposition Method 703.2.6 Reliability Block Diagram (RBD) 713.2.7 Reliability Bounds 733.2.7.1 Lower Bound Reliability 753.2.7.2 Upper Bound Reliability 763.2.8 Monte Carlo Simulation 773.2.9 Path-Based or Cut-Based Approaches 783.3 Observations 814 Terminal Reliability Analysis of MIN Layouts 854.1 Chaturvedi and Misra Approach 874.1.1 Path Set Enumeration 884.1.2 Reliability Evaluation using MVI Techniques 964.1.3 Reliability Evaluation Techniques Comparison 994.1.3.1 Terminal Reliability of SEN, SEN+ and SEN+2 1004.1.3.2 Broadcast Reliability of SEN, SEN +, and SEN+2 1014.1.3.3 Comparison 1024.2 Reliability Analysis of Multistage Interconnection Networks 1044.3 Summary 1135 Comprehensive MIN Reliability Paradigms Evaluation 1155.1 Introduction 1155.2 Reliability Evaluation Approach 1195.2.1 Path Set Enumeration 1205.2.1.1 Assumptions 1205.2.1.2 Applied Approach 1215.2.1.3 Path Tracing Algorithm (PTA) 1225.2.1.4 Path Retrieval Algorithm (PRA) 1235.3 Reliability Evaluation Using MVI Techniques 1405.4 Summary 1566 Dynamic Tolerant and Reliable Four Disjoint MIN Layouts 1576.1 Topological Design Considerations 1606.1.1 Topology 1616.1.2 Switch Selection for Proposed 4DMIN 1626.2 Proposed 4-Disjoint Multistage Interconnection Network (4DMIN) Layout 1646.2.1 Switching Pattern 1646.2.2 Redundant and Disjoint Paths 1656.2.3 Routing and Dynamic Rerouting 1666.2.4 Algorithm: Decision Making by Switches at Each Stage 1686.2.5 Case Example 1706.2.6 Disjoint and Dynamic Rerouting Approach in 4DMIN 1726.2.7 Hardware Cost Analysis 1726.3 Reliability Analysis and Comparison of MINs 1746.4 Reliable Interconnection Network (RIN) Layout 1816.4.1 Topology Design 1856.4.2 Switching Pattern 1876.4.3 Routing and Dynamic Rerouting 1896.5 Reliability Analysis and Comparison of MINs 1976.6 Summary 201References 203Index 213