This book presents novel and efficient tools, techniques and approaches for reliability evaluation, reliability analysis, and design of reliable communication networks using graph theoretic concepts. In recent years, human beings have become largely dependent on communication networks, such as computer communication networks, telecommunication networks, mobile switching networks etc., for their day-to-day activities. In today's world, humans and critical machines depend on these communication networks to work properly. Failure of these communication networks can result in situations where people may find themselves isolated, helpless and exposed to hazards. It is a fact that every component or system can fail and its failure probability increases with size and complexity. The main objective of this book is to devize approaches for reliability modeling and evaluation of such complex networks. Such evaluation helps to understand which network can give us better reliability by their design. New designs of fault-tolerant interconnection network layouts are proposed, which are capable of providing high reliability through path redundancy and fault tolerance through reduction of common elements in paths. This book covers the reliability evaluation of various network topologies considering multiple reliability performance parameters (two terminal reliability, broadcast reliability, all terminal reliability, and multiple sources to multiple destinations reliability).

This book presents novel and efficient tools, techniques and approaches for reliability evaluation, reliability analysis, and design of reliable communication networks using graph theoretic concepts.In recent years, human beings have become largely dependent on communication networks, such as computer communication networks, telecommunication networks, mobile switching networks etc., for their day-to-day activities. In today's world, humans and critical machines depend on these communication networks to work properly. Failure of these communication networks can result in situations where people may find themselves isolated, helpless and exposed to hazards. It is a fact that every component or system can fail and its failure probability increases with size and complexity.The main objective of this book is to devize approaches for reliability modeling and evaluation of such complex networks. Such evaluation helps to understand which network can give us better reliability by their design. New designs of fault-tolerant interconnection network layouts are proposed, which are capable of providing high reliability through path redundancy and fault tolerance through reduction of common elements in paths. This book covers the reliability evaluation of various network topologies considering multiple reliability performance parameters (two terminal reliability, broadcast reliability, all terminal reliability, and multiple sources to multiple destinations reliability).

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