Читать книгу Interconnection Network Reliability Evaluation - Neeraj Kumar Goyal - Страница 16

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.