Interconnection Network Reliability Evaluation (eBook)

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 ix

Preface xiii

1 Introduction 1

1.1 Introduction 1

1.2 Network Reliability Measures 2

1.3 The Probabilistic Graph Model 4

1.4 Approaches for Network Reliability Evaluation 6

1.5 Motivation and Summary 7

2 Interconnection Networks 11

2.1 Interconnection Networks Classification 11

2.2 Multistage Interconnection Networks (MINs) 14

2.3 Research Issues in MIN Design 15

2.4 Some Existing MINs Implementations 19

2.5 Review of Topological Fault Tolerance 20

2.5.1 Redundant and Disjoint Paths 22

2.5.2 Backtracking 26

2.5.3 Dynamic Rerouting 27

2.6 MIN Topological Review on Disjoint Paths 27

2.6.1 Single-Disjoint Path Multistage Interconnection Networks 27

2.6.2 Two-Disjoint Paths Multistage Interconnection Networks 36

2.6.3 Three-Disjoint Paths Multistage Interconnection Networks 47

2.6.4 Four-Disjoint Paths Multistage Interconnection Networks 51

2.7 Hardware Cost Analysis 55

2.8 Observations 60

2.9 Summary 61

3 MIN Reliability Evaluation Techniques 63

3.1 Reliability Performance Criterion 63

3.1.1 Two Terminal or Terminal Pair Reliability (TPR) 64

3.1.2 Network or All Terminal Reliability (ATR) 64

3.1.3 Broadcast Reliability 65

3.2 Approaches for Reliability Evaluation 66

3.2.1 Continuous Time Markov Chains (CTMC) 67

3.2.2 Matrix Enumeration 67

3.2.3 Conditional Probability (CP) Method 67

3.2.4 Graph Models 69

3.2.5 Decomposition Method 70

3.2.6 Reliability Block Diagram (RBD) 71

3.2.7 Reliability Bounds 73

3.2.7.1 Lower Bound Reliability 75

3.2.7.2 Upper Bound Reliability 76

3.2.8 Monte Carlo Simulation 77

3.2.9 Path-Based or Cut-Based Approaches 78

3.3 Observations 81

4 Terminal Reliability Analysis of MIN Layouts 85

4.1 Chaturvedi and Misra Approach 87

4.1.1 Path Set Enumeration 88

4.1.2 Reliability Evaluation using MVI Techniques 96

4.1.3 Reliability Evaluation Techniques Comparison 99

4.1.3.1 Terminal Reliability of SEN, SEN+ and SEN+2 100

4.1.3.2 Broadcast Reliability of SEN, SEN +, and SEN+2 101

4.1.3.3 Comparison 102

4.2 Reliability Analysis of Multistage Interconnection Networks 104

4.3 Summary 113

5 Comprehensive MIN Reliability Paradigms Evaluation 115

5.1 Introduction 115

5.2 Reliability Evaluation Approach 119

5.2.1 Path Set Enumeration 120

5.2.1.1 Assumptions 120

5.2.1.2 Applied Approach 121

5.2.1.3 Path Tracing Algorithm (PTA) 122

5.2.1.4 Path Retrieval Algorithm (PRA) 123

5.3 Reliability Evaluation Using MVI Techniques 140

5.4 Summary 156

6 Dynamic Tolerant and Reliable Four Disjoint MIN Layouts 157

6.1 Topological Design Considerations 160

6.1.1 Topology 161

6.1.2 Switch Selection for Proposed 4DMIN 162

6.2 Proposed 4-Disjoint Multistage Interconnection Network (4DMIN) Layout 164

6.2.1 Switching Pattern 164

6.2.2 Redundant and Disjoint Paths 165

6.2.3 Routing and Dynamic Rerouting 166

6.2.4 Algorithm: Decision Making by Switches at Each Stage 168

6.2.5 Case Example 170

6.2.6 Disjoint and Dynamic Rerouting Approach in 4DMIN 172

6.2.7 Hardware Cost Analysis 172

6.3 Reliability Analysis and Comparison of MINs 174

6.4 Reliable Interconnection Network (RIN) Layout 181

6.4.1 Topology Design 185

6.4.2 Switching Pattern 187

6.4.3 Routing and Dynamic Rerouting 189

6.5 Reliability Analysis and Comparison of MINs 197

6.6 Summary 201

References 203

Index 213