Interconnection Network Reliability Evaluation. Neeraj Kumar Goyal

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:

      1 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.

      2 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.

      3 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.

1.4 Approaches for Network Reliability Evaluation

      Misra and Rao [4] developed signal flow graphs: a development recognized as a significant step forward in the evaluation of network reliability. After this, a number of algorithms, techniques and approaches have been suggested in the literature. In fact, today, the use of graph theory has become inseparable from network reliability evaluation. Available literature on reliability evaluation of communication networks, considering only connectivity as performance criterion, can broadly be classified into two paradigms, viz.:

      Path sets or Cut sets approaches (POC) paradigm:

      These use pathsets or cutsets as the starting point for TPR problems, spanning trees for ATR problems and k-trees (k-minimal cutsets) for KTR problems. In this book, the terms path sets and trees are represented by a single term path sets as approaches used for generating them are similar. From the context, whether it is pathset or spanning tree or k-tree can easily be understood. For example, when the context is TPR problem then it is pathset, when context is ATR it is spanning tree and when the context is KTR it is k-tree.

      Reliability evaluation is generally achieved by enumerating pathsets or cutsets of the network. A pathset is defined to be a set of minimal paths connecting source and destination node. A path is set of components whose functioning ensures that the system functions. A cutset is defined to be a set of minimal cuts that disconnects the source and destination nodes. A cut is a set of components whose failure will result in system failure. A minimal path/minimal cut is a path/cut such that no proper subset of minimal path or minimal cut is a minimal path/minimal cut. In other words, if any element is removed from the set (minimal path/minimal cut) then it no longer remains a path or cut.

Non-Path sets or Cut sets approaches (NPOC) paradigm: These approaches do not use path sets or cut sets. These apply reduction or decomposition or transformation or a combination of these approaches to solve the reliability evaluation problems. The non-path (or cut) set approaches may be categorized as following: 1) State enumeration methods 2) Topological methods 3) Transformation methods and 4) Decomposition (Factoring theorem) methods.

1.5 Motivation and Summary

      Main objective of this book is to design new fault tolerant Interconnection network layouts capable of path redundancy among dynamic failures. New INs designs have been proposed and their observed results are found promising when compared with some of the earlier networks.

      A summary of problem wise contributions is discussed next:

      1 INs Topology Review (Chapter 2)Presents an extensive survey of the existing INs topological hardware aspects based on its unexplored Taxonomy of INs performance metrics. In this chapter detailed literature review on interconnection networks has been performed, and an exhaustive taxonomy has been proposed based on the literature review. The chapter also presents advantages and disadvantages of interconnection networks along with a summary of topological characteristics and fault tolerance information of the surveyed interconnection networks in the form of Table.

      2 MIN Reliability Evaluation Techniques Review (Chapter 3)Presents an overall view of the different reliability measures and their importance in evaluating the reliability can be reviewed with examples. A comprehensive review of the various approaches present for evaluation of different reliability measures is also presented. Based on the literature survey a few shortcomings are identified.

      3 Terminal Reliability Analysis of Existing MIN Layouts (Chapter 4)Networks such as telecommunication, transportation, power systems, integrated circuitry and computer communication systems are large and it becomes imperative for economic reasons and safety that these have high reliability. Reliability evaluation of such complex systems has not yet been perfected and there is a lot more that needs to be done. System reliability can be measured in terms of various paradigms such as two terminal, all-terminal and broadcast reliabilities.In this chapter, terminal reliability values of various recent and industrial used MINs topologies are evaluated and compared using existing simple and efficient path-set enumeration method. Path set and cut set techniques are the most widely used techniques for terminal pair reliability evaluation of communication networks as these techniques give a compact reliability expression in sum of disjoint product (SDP) form.These techniques first enumerate minimal path (or cut) set for the network and then evaluate reliability (or unreliability) expressions in the SDP form. Since enumeration of cut set also requires knowledge of basic paths of the network, the path set enumeration becomes a necessity for these techniques. Available disjoint and redundant paths of various existing MINs are evaluated by a simple and efficient path-set enumeration method based on hybrid multi-variable inversion (MVI) algorithm, which gives accurate reliability values. Present reliability evaluation paves the way of research focus on developing higher disjoint, reliable and highly fault-tolerant MINs than the existing topologies.

      4 Comprehensive MIN Reliability Paradigms Evaluation (Chapter 5)This chapter has attempted to evaluate comprehensive reliability paradigms of various recent MINs topologies available from literature using path tracing algorithm. With increasing number of input and output nodes in supercomputer environment reliability evaluation of multi-cast nodes is mandatory. In other words, a network has to transmit a signal or commodity between different pairs of nodes of a network simultaneously. Communication between multiple-sources multiple-destinations offers several advantages like increased performance, improved reliability and decreased costs through resource sharing.So we have extended the traditional reliability evaluation to include a new reliability measure as multisource multi-terminal reliability