Interconnection Network Reliability Evaluation
Description
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).
More details
Other editions
Additional editions
Persons
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.
Content
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
1
Introduction
1.1 Introduction
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 [1]. 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 fact that every component or system can fail and its failure probability increases with size and complexity.
Therefore, it is essential to compute and assure the reliability of these networks, which are growing and becoming complex. Reliability modeling and computation is necessary for reliability and safety assurance of these networks [2]. It also helps to identify weak links. These weak links can be improved cost effectively using reliability design techniques. Recent developments in communication hardware industry has resulted in increasingly reliable and non-repairable (need to be replaced when got bad 1) network components. However new designs involve new components, which tend to be less reliable. A good network design [3] involving fault tolerance and redundancies can deliver better system reliability at lesser cost. This allows new designs to be released faster and works reliably even when components are not mature enough from reliability point of view.
The computation of reliability measures [4] for a large and complex communication network, up to the desired level of accuracy, is time consuming, complex and costly. It has not been realistic to model and compute the reliability of real-life communication networks, which are quite large, using desktop computer due to large execution time and high memory requirements. Such computations are usually performed on high-end processors for critical systems only. Reliability professionals and researchers have carried out a lot of research and developed techniques to minimize these efforts and develop a practical tool for all the communication network designers [4-6].
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.
1.2 Network Reliability Measures
Earlier attempts to measure network reliability belong to two distinct classes: deterministic and probabilistic [1, 2]. The deterministic measures assumed that the network is subjected to a destructive force with complete knowledge of the network topology. The reliability is measured in terms of the least amount of damage required to make the network inoperative.
Deterministic measures thus provide simple bounds on the reliability of the network, since they are often measured for the network's worst-case environment. For example, in the terminal pair reliability problem, two deterministic measures of reliability are:
- The minimum number of edges that must be destroyed or removed to disrupt the communication between the specified nodes (s and t), which is simply the number of edges in a minimum cardinality cutset, and
- The minimum number of nodes that must be destroyed or removed to disrupt the communication between the specified nodes (s and t).
Both of these measures are computable in polynomial time. However, one of the main problems with deterministic measures is these give rise to some counter intuitive notions of network reliability. For example, consider the networks shown in Figure 1.1. According to second deterministic measure of the graph's reliability, the graphs of Figure 1.1 (a) and Figure 1.1 (b) are equally reliable since both of these require minimum three nodes to be destroyed for breaking the s-f node connectivity.
Figure 1.1 Example networks for deterministic reliability measurement.
However intuitively one can easily find out that graph (a) is the more reliable among the two. The same problem arises when the cardinality of a minimum (s, t)-cut set is used as a measure of unreliability. Consider the graphs shown in Figure 1.2. Both graphs (a) and (b) have a minimum cardinality for (s, t) cut of size one, which implies both networks are equally reliable.
This clearly shows that deterministic measures of reliability are insufficient to correctly relate network components used in network layout with network reliability. Moreover, failure of network components is probabilistic in nature therefore only probabilistic measures can define system reliability appropriately.
Figure 1.2 Another set of example networks for deterministic reliability measurement.
Therefore, for evaluating reliability of a network using probabilistic measures, one can associate a statistical probability of failure/ success with each component of the network in order to obtain a statistical measure of overall unreliability/reliability of the network. This notion supports an accepted definition of reliability as the probability that a system or device is operational under stated environment for a given mission time. To avoid conflicts that arise with various levels of operation within a network's hierarchy, only the topology of the network is considered. This allows a network to be modeled by a graph where the nodes of the graph represent the communication centers and communication links are represented by its edges.
1.3 The Probabilistic Graph Model
Communication networks are generally modeled using network graph [3]. The network graph G (V,E) consists of a set V of n number of nodes (or vertices) and a set E of l number of edges (or links). For reliability evaluation, probabilistic graph is used which takes these sets V and E of nodes and links as random variables. In probabilistic graph of communication networks, nodes represent the computers/ switches/transceivers/routers and edges represent various types of communication links connecting these nodes. For reliability analysis, graphical models of networks are considered to be simple, efficient and effective.
Probabilistic graph models are developed and presented in this book. Depending on the state (working or failed) of nodes (or vertices) and/or links (or edges), the network can be considered either working or failed. A general assumption of statistical independence among nodes and links failures is followed throughout. It implies that the probability of a link or node being operational is not dependent of the states of the other links or nodes in the network. The inherent assumption here is that the link failures are caused by random events which affect all network components individually.
However, this assumption may not be completely correct while modeling a real communication network as more than one component in a particular area may fail due to natural causes such as a major storm or an earthquake. In such cases, dependency analysis and common cause failure modelling can be used over the analysis performed with assumption of statistical independence. This assumption is often made because of difficulties in obtaining information about the dependencies of link failures and increased modeling and computational rigor. In fact, such dependencies may not be known. Thus, without the assumption of statistical independence the problem becomes much more difficult to solve.
Depending on the connectivity objective of nodes [4-6], the network reliability evaluation problem can be sub-divided into following different cases:
- Two terminal or terminal pair reliability (TPR) problems: The most common communication operation is to send messages from a source node s to a terminal node t. The terminal pair reliability of a network is defined as the probability of having at least one operational path between the nodes s and t. In case of directed networks, it is usually called (s,t) connectedness.
- Global or all terminal reliability (ATR) problems: The all terminal reliability of a network is defined as the probability that for every node pair (Ni,Nj) there exist an operational path to connect them; or equivalently, the probability that there exist a working spanning tree. In the directed case, all terminal reliability is the probability that the directed graph contains at least a spanning tree rooted at the source node s.
- K-terminal reliability (KTR) problems: The k-terminal reliability ensures that a specified set of k-nodes of the network are able to communicate with each other and it is defined as the probability that a path exists between every pair of nodes belonging to the specified set of k nodes of the network.
Generally, communication network performance is defined not only by the connectivity between nodes but also by the minimum capacity it can transfer between the nodes. The reliability measure considering both capacity and connectivity, as essential performance criterion, is known as capacity related reliability (CRR). It is defined as the probability that required amount of flow is transferred from source node s to terminal node t. Evaluation of above network reliability measures (indices) has attracted a lot of attention from researchers and many approaches have been developed so far. Next section presents a brief summary of these approaches.
