Network Reliability E-Book

Sanjay Kumar Chaturvedi

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Performability Engineering Series
• Sprache: Englisch

Seitenzahl: 283

Veröffentlichungsjahr: 2016

Beschreibung

In Engineering theory and applications, we think and operate in terms of logics and models with some acceptable and reasonable assumptions. The present text is aimed at providing modelling and analysis techniques for the evaluation of reliability measures (2-terminal, all-terminal, k-terminal reliability) for systems whose structure can be described in the form of a probabilistic graph. Among the several approaches of network reliability evaluation, the multiple-variable-inversion sum-of-disjoint product approach finds a well-deserved niche as it provides the reliability or unreliability expression in a most efficient and compact manner. However, it does require an efficiently enumerated minimal inputs (minimal path, spanning tree, minimal k-trees, minimal cut, minimal global-cut, minimal k-cut) depending on the desired reliability. The present book covers these two aspects in detail through the descriptions of several algorithms devised by the "reliability fraternity" and explained through solved examples to obtain and evaluate 2-terminal, k-terminal and all-terminal network reliability/unreliability measures and could be its USP. The accompanying web-based supplementary information containing modifiable Matlab® source code for the algorithms is another feature of this book. A very concerted effort has been made to keep the book ideally suitable for first course or even for a novice stepping into the area of network reliability. The mathematical treatment is kept as minimal as possible with an assumption on the readers' side that they have basic knowledge in graph theory, probabilities laws, Boolean laws and set theory.

Leseprobe

Contents

Cover

Half Title page

Title page

Copyright page

Preface

Acknowledgements

Chapter 1: Introduction

1.1 Graph Theory: A Tool for Reliability Evaluation

1.2 Large versus Complex System

1.3 Network Reliability Measures: Deterministic versus Probabilistic

1.4 Common Assumptions

1.5 Approaches for NSP Network Reliability Evaluation

Exercises

References

Chapter 2: Reliability Evaluation of General SP-Networks

2.1 Notation and Assumptions

2.2 Unit-Reliability and Failure Models

2.3 Module Representation of Reliability Graphs

2.4 Misra Matrix Method

2.5 Algorithm

2.6 Implementation and Documentation

2.7 Remarks

Exercises

References

Chapter 3: Path Sets Enumeration

3.1 Enumeration of (s, f) Connected Path Sets

3.2 Enumeration of All-node Connected Path Sets: Spanning Tree

3.3 Number of Spanning Trees

3.4 Enumeration of k-node Connected Path Sets: k-Trees

Appendix 3A.1: Enumeration of Path Sets Algorithm, Illustration and Matlab® Code Notation

Appendix 3A.2: Sample program I/O for Figure 3A.1

Exercises

References

Chapter 4: Cut Sets Enumeration

4.1 (s, f) Cut Sets Enumeration

4.2 Global Cut Sets Enumeration

Appendix 4A.1: Node Fusion Technique and Generation of Node Set Combination

Appendix 4A.2: Code for Checking Validity of a Node Set and Converting Node-Sets into Link Cutsets

Appendix 4A.3: Sample Program I/O for Network Graph of Figure 4.3

Appendix 4A.4: g-Terminal Reliability Evaluation Program Sample I/O for Example of Figure 4.3

Exercises

References

Chapter 5: Reliability Evaluation using MVI Techniques

5.1 Notation and Assumptions

5.2 Preliminaries

5.3 MVI Methods

5.4 Method 3: Hybrid Methods-HM

5.5 Applying HM-1 and HM-2

5.6 Global and k-terminal Reliability with SDP Approach

5.7 Unreliability with SDP Approach

5.8 Some Suggested Guidelines

Appendix 5A.1: Program Output of g-reliability Expression for the Figure 5.1(b).

Appendix 5A.2: Program Output of k-terminal Reliability Expression for Figure 5.1(b).

Appendix 5A.3: Program Output of k-terminal Reliability Expression for Figure 5.1(b).

Exercises

References

Chapter 6: Unified Framework and Capacitated Network Reliability

6.1 The Unified Framework

6.2 Capacitated Reliability Measure: An Introduction

6.3 Algorithm Description

6.4 The CRR Evaluation Algorithm

6.5 A Complete Example

6.6 Experimental Results, Comparison and Discussion

References

Chapter 7: A LAN and Water Distribution Network: Case Studies

7.1 Case Study-I: IIT Kharagpur LAN Network

7.2 Case Study-II: Real-Type of Large Size Unsaturated Water Distribution Networks

References

Epilogue

References

Bibliography

Index

Network Reliability

Scrivener Publishing100 Cummings Center, Suite 541JBeverly, MA 01915-6106

Performability Engineering SeriesSeries Editors: Krishna B. Misra ([email protected])and John Andrews ([email protected])

Scope: A true performance of a product, or system, or service must be judged over the entire life cycle activities connected with design, manufacture, use and disposal in relation to the economics of maximization of dependability, and minimizing its impact on the environment. The concept of performability allows us to take a holistic assessment of performance and provides an aggregate attribute that reflects an entire engineering effort of a product, system, or service designer in achieving dependability and sustainability. Performance should not just be indicative of achieving quality, reliability, maintainability and safety for a product, system, or service, but achieving sustainability as well. The conventional perspective of dependability ignores the environmental impact considerations that accompany the development of products, systems, and services. However, any industrial activity in creating a product, system, or service is always associated with certain environmental impacts that follow at each phase of development. These considerations have become all the more necessary in the 21st century as the world resources continue to become scarce and the cost of materials and energy keep rising. It is not difficult to visualize that by employing the strategy of dematerialization, minimum energy and minimum waste, while maximizing the yield and developing economically viable and safe processes (clean production and clean technologies), we will create minimal adverse effect on the environment during production and disposal at the end of the life. This is basically the goal of performability engineering.

It may be observed that the above-mentioned performance attributes are interrelated and should not be considered in isolation for optimization of performance. Each book in the series should endeavor to include most, if not all, of the attributes of this web of interrelationship and have the objective to help create optimal and sustainable products, systems, and services.

Publishers at ScrivenerMartin Scrivener ([email protected])Phillip Carmical ([email protected])

Copyright © 2016 by Scrivener Publishing LLC. All rights reserved.

Co-published by John Wiley & Sons, Inc. Hoboken, New Jersey, and Scrivener Publishing LLC, Salem, Massachusetts.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

For more information about Scrivener products please visit www.scrivenerpublishing.com.

Library of Congress Cataloging-in-Publication Data:

ISBN 978-1-119-22356-6

(Saint Kabir wrote this verse to sing the glory of Guru, without whose help, one cannot cross this ocean of worldly life. He asks, “If both, Guru and God in form of Govind were to appear at the door, whose feet will I worship first?” He answers, “It has to be the Guru’s feet first, because without him, how would I have recognized (known) God?”)

Fondly dedicated toProf. Krishna B. Misra (My Guru)- Veena (Guru Maa)

And my very own small worldSanjekta(Daughter), Shaurya(Son), Ekta(Wife) and Uma-(late) Aditya (parents)

Preface

The growth of reliability has assumed a new dimension in the recent years primarily because of the consequential impact(s) of failures of present day’s complex systems that may lead to day-to-day annoyance to the operational efficiency and uneconomical maintenance, and even to the extent of endangering life to our planet where a compromise with quality and reliability might be disastrous.

Although several books have been published in the area of reliability theory and practice, no book has been published on the topics covered in this book as the information presented in this book has either been confined to journals or given some space as a part of a chapter in a book. The topics covered in this book will interest not only the reliability community but also the teachers/educators and students of electrical, computer science, electronics, communication engineering with their allied areas. The text of this book is envisioned to be useful and can also serve as a one-semester course to senior undergraduate, graduate or postgraduate students in engineering. For researchers, practising engineers, managers, and designers, it would serve as a valuable reference and primer in the area of network reliability.

A very concerted effort has been made to keep the book ideally suitable for first course or even for a novice stepping into the area of network reliability. The mathematical treatment is kept as minimally as possible with an assumption on the readers’ side that they have basic knowledge in graph theory, probabilities laws, Boolean laws and set theory. A number of solved examples have been provided to make the topics pellucid with some exercises given at the end of chapters for readers to voluntarily test themselves and to have a better command of the material. The references provided at the end of each chapter are no way complete as no book of this size can claim to give a comprehensive survey of the subject spanning over a several decades. But they indeed serve as a platform and guiding factor for further research in this area.

In engineering theory and applications, we think and operate in terms of logics and models with some acceptable and reasonable assumptions. Reliability theory is not an exception where a rather popular model for studying and analysing computer/ communication/ transportation/ water/ electrical networks is as a probabilistic graph with a characteristic of edges and/or nodes subject to failures. The network reliability modelling and analysis is an important issue in system design, manufacture and maintenance, wherein the performance of a network depends upon the probability of a specified set of nodes being communicable or not being communicable. The popular measures of network reliability in vogue are 2-terminal reliability with or without capacity constraint on links, k-terminal and all-terminal reliability. The publications of hundreds of research papers in the last few decades on the assessment of such measures indicate the importance of this area.

Among the several approaches of network reliability evaluation, the multiple-variable-inversion sum-of-disjoint product (MVI-SDP) approach finds a well-deserved niche as it provides the reliability expression in a most efficient and compact manner. However, it does require an efficiently enumerated minimal inputs (minimal path, spanning tree, minimal k-trees, minimal cut, minimal global-cut, minimal k-cut) depending on the desired reliability. The present book is a maiden endeavour by the author to cover these two aspects in detail through the application of various techniques devised by the ‘reliability fraternity’ and could be its USP.

The author does not claim to be an ace programmer, and has provided very efficient and user friendly Matlab® programs which can be downloaded at www.scrivenerpublishing.com However, they are amenable to such modifications for the readers who love to do programming. The book is organized as follows.

Chapter 1 introduces the basic definitions, terminology, common assumptions with a broad category of techniques to tackle and evaluate network reliability problems. Chapter 2 succinctly provides the commonly employed hazard models and basic building blocks of a reliability block diagram. It describes a flexible Misra Matrix Method to solve a General series-parallel system reliability model consisting of various types of redundancies.

Chapter 3 pertains to the notion of network connectivity with respect to a specified set of nodes of the network graph termed as Minimal Path Sets, in general or 2-terminal, k-terminal and all-terminal minimal path sets, in particular. It describes several methods of enumeration to such requirement for measuring network reliability metrics. The chosen methods are simple enough for classroom teaching but become powerful once implemented on a computer using a suitable programming language.

Chapter 4 deals with the dis-connectivity criteria of a network reliability graph under a specified set of nodes termed as Minimal Cut Sets, in general or 2-terminal, k-terminal and all-terminal minimal cut sets, in particular. It also provides a general algorithm developed by the author to enumerate them. It also explains various sub-problems encountered in enumerations and their solutions thereof.

Chapter 5 discusses and describes Sum-of-Disjoint-Product based MVI approaches such as KDH88, CAREL, HM-1 and HM-2 to obtain and evaluate 2-terminal, k-terminal and all-terminal network reliability/unreliability measures.

Chapter 6 puts network reliability methodology and measures discussed in earlier chapters under a unified framework and extend 2-terminal reliability measure to link’s capacity-based reliability measure-CRR and describe a methodology to obtain the measure under such scenario.

In the last Chapter 7, the author has provided two case studies to show the approaches in action.

The author has tried his level best to make the text complete with logical flow and free of omissions. Nevertheless, as a student of reliability engineering, the author realises that ‘failures are inevitable and can never ever be predicted in advance, and cannot be eliminated’ but they and their consequences can definitely be minimized and mitigated. The author takes full responsibility for all those that still remain and shall be grateful if any such shortcomings or suggestions be brought to his notice.

Comments and suggestions regarding the book are most welcome and can be sent to [email protected].

Sanjay K. Chaturvedi

Kharagpur, India

March, 2016

Acknowledgements

The author would like to express his gratitude to the people who have motivated or helped at various stages of writing this book. Although, the skeleton of the text was drawn in the author’s mind long back, the impetus to bring it to fruition was provided by Professor Krishna B. Misra - a ‘Guru’ of eminence who had shown the research path to the author and to many others as well.

Admittedly, it would not have been possible to complete this task without painstaking secretarial assistance provided by my student-friend, Lt Col Rajvinder Singh for proof-reading, incorporating numerous corrections on several drafts, and formatting. My research scholars, notably Mr. Gaurav Khanna (for collating the references and executing the software codes on several examples); Mr. Rajarajan, Mr. Tauheed Ahamed and Ms. Shabnam Samima deserve special thanks for providing assistance as and when it was needed.

The author also owes special thanks to his colleagues Prof. V. N. A. Naikan (Head of our Centre) and Prof. Neeraj Goyal for their helpful comments and suggestions at the early stages of this task.

Finally, the author would like to express his sincere thanks to the authority of his institution, Indian Institute of Technology, Kharagpur, India, for providing the necessary facility, aura and environment to undertake this project.

Chapter 1

Introduction

As the systems grow in size and complexity, they become more prone to failures and it becomes essential to ensure their performance by carrying out reliability analysis. Here, the word system connotes any assemblage of functional units and may be used to denote a complete installation or equipment. A system may be quite gigantic such as computer communication networks or it could be as small as an integrated circuitry.

The problem of determining the reliability of systems, whose components can have one or more failure modes, often arises in variety of applications, ranging from telecommunication, transportation, power systems, and mechanical systems to integrated circuits and computer communication systems or large software structure. Therefore, all such systems can naturally be expressed as in the form of a network, arising from the interconnections of various system subdivisions. For instance, a telecommunication or a computer communication network may have vertices representing the physical locations of computers or transmitters/receivers and may have several edges representing the communication links between different sites. Depending on whether vertices or edges work or fail, the network itself can be considered to be either working or failed.

For the applications cited above, continued availability of communication between specified vertices of a network is an important requirement. With the widespread use of and dependence upon such networks, it becomes imperative for these networks to be highly reliable. Hence the networks are often designed with the criteria of having several communication paths between any two vertices.

Ideally, if completely diverse path between every pair of vertices were available, the probability of existing at least one communication path between any two vertices at a given time would be very high. However, cost of designing and maintaining such networks inhibit this solution. As a compromise, networks are designed in such a way that any two vertices connected through a few disjoint path sets; additional path sets that have common links are also made available.

A major problem in this area lies with the task of determining reliability of such a network and it is desirable to have some quantitative measure of a given network’s performance.

1.1 Graph Theory: A Tool for Reliability Evaluation

Graph theory has drawn increased interest of scientists and engineers in the last several decades. The main reason for this accelerated interest in graph theory is in its demonstrated ability to solve problems from a wide variety of areas. Because of their intuitive diagrammatic representation, graphs have been found extremely useful in modelling systems arising in physical science, engineering, social sciences and economic problems and reliability engineering has not been an exception.

The application of graph theory to reliability studies received little attention till 1970. Ever since the application of the graph theory for network reliability evaluation was suggested by (Misra & Rao, 1970), a large number of studies have appeared in the literature. To quote (Singh & Proctor, 1976): “Until 1970, the subject received little attention with the exception of (Shooman, 1968) popular text Probabilistic Reliability, published in 1968. Nevertheless, he did little more than mention the topic. However (Misra & Rao, 1970), 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.

In performing the reliability analysis of large and complex systems, it is almost impossible to treat system in its entirety. The logical approach is to decompose the system into its smaller functional entities composed of units, subsystems or components. Even a unit can be quite a sizeable subsystem. A unit can further be broken into elements each of which can only be a circuit or a part. In general, the hierarchical order is: system, subsystems, units, equipment, parts and components. The operational relationship amongst its constituent entities is provided through the logical relationship of system failure (or success) with the failure (or success) of its parts. These relationships are depicted through what is commonly known as the reliability logic diagram (RLD). Based on the functional interaction that subsystems or elements of a subsystem can have, the entities may fall in either of these categories viz., series, parallel, series-parallel (SP) or parallel-series (PS). However, certain design considerations or complex failure mode may produce a system in which its representation by pure parallel or series or their combination may not be possible or appropriate. In general, almost all practical systems fall in this category and are better known as non-series-parallel systems (NSP).

The reliability analysis and evaluation of NSP system are quite complicated, memory intensive and time consuming as well. However, any technique, which computes reliability of NSP systems, can easily be applied to series/parallel systems as well. Many of the series-parallel (or parallel-series) system are represented through Reliability Logic or Block Diagram. However, particularly for NSP systems, simpler ways to represent the system through a graph like structure.

Figure 1.1 An undirected reliability graph of a network.

Figure 1.2 A directed reliability graph of a network.

On the basis of reliability, networks/systems modelled through graphs have been classified as:

Undirected network

Directed network

Mixed network.

1.1.1 Undirected Network

It is a connected graph G for a system wherein nodes are connected by undirected edges. An undirected edge is an edge with no head or tail (no arrow shown). Undirected edges in a graph are used to indicate two-way communication links between nodes. They are represented as unordered node pairs (i, j) joined by the communication link or edge. An edge is said to be incident upon two nodes if the two nodes are joined by the edge.

Example 1.1: The graph in Figure 1.1 is an example of an undirected network where, node-set and edge-set are:

VE 

1.1.2 Directed Network

It is another form of a system representation through connected graph G wherein each edge has an orientation. Obviously, a source node would not have any edge incidents on it whereas a destination node would not have any edge emerging out of it. Some text also refers directed edges as arcs representing a unidirectional communication links between two nodes depicting the information flow in the direction that an arc points. An arc from node i to node j is represented as an ordered pair (i, j), where i is called the tail and j is called the head of the arc. Figure 1.2 is an example of a directed network, where node-set and edge set are:

VE 

In a directed graph, a strongly connected component is a maximal set of nodes for which there exists a directed path between every ordered pair of nodes in the component, such that the paths pass only through nodes that are also in the component. Figure 1.3 shows two examples of strongly connected components and Figure 1.4 shows two examples of components that are not strongly connected.

Figure 1.3 Strongly connected components.

Figure 1.4 Weakly connected components.

1.1.3 Mixed Network

A mixed network G is a graph in which some edges may be directed and some may be undirected. It is determined by the triplet (V, E, D) where V is the set of nodes, E is the set of undirected edges and D is the set of directed edges. The underlying undirected graph is obtained by deleting the orientation of the arcs in D. An orientation of a mixed graph means, that we orient the undirected edges (and leave the directed ones). Figure 1.5 shows such depiction.

Figure 1.5 A mixed reliability graph of a network.

Summarily, each item (component/part/subdivision etc …) of a system can be represented by a two terminal graph. Then the logical interconnection of various items form a network like structure and is better known as a probabilistic graph of the system due to the associated probability of success/failure of its each items, and this structure can also be designated as a system or a network (Misra, 1992). To analyse such networks is an extremely difficult, time consuming and laborious task, almost impossible to do manually. Thus, the use of computer becomes absolutely necessary for which one would need a computer-coding scheme representing the network that can easily and suitably be manipulated by the algorithms in addition to computer-programs to provide a solution to the problem.

The commonly used schemes to code these networks have been: incidence matrix, adjacency matrix and adjacency list representation. However, the most popular, simplest and easily manipulative coding scheme for a moderate size network has been the adjacency matrix or connection matrix scheme. The connection matrices for the some cases are as shown in Table 1.1.

Table 1.1 Adjacency matrix representation of a graph.

1.2 Large versus Complex System

At this juncture, it would be worthwhile to distinguish between- what is large and complex?

1.2.1 Large System

As stated at the beginning that the word system connotes any assemblage of functional units and may be used to denote a complete installation or equipment. A system can be represented by a graph where a nodesrepresents a component/unit/subsystem and a link represents their functional connectivity.

When used in relation to a system, the word large connotes anything, which is greater than the average size, extent, quantity, or amount in comparison to another similar thing or some reference object. Hence, it is a relative word and it is hard to specify a system’s largeness in the absence of a reference.

Let the network shown in Figure 1.6 represents a communication network with the transmitter, s, sending data or information to a receiver, f.

Figure 1.6 A large network.

These (s, f) points have been connected through a number of intermediate links and relay-transmitters. There may be hundreds and thousands of relay-transmitters connecting the transmitter and the receiver help them to communicate. This configuration could be representing a large network. Therefore, the largeness is in relation to the number of units or elements that a system consists of. A large system need not necessarily be a complex system.

1.2.2 Complex System

The word complex connotes a structure consisting of interconnected or interwoven parts or elements, which are difficult to analyse, understand, or handle.

Therefore, a complex system is a system, which consists of interconnected or interwoven parts (components) such that it becomes difficult to analyse it in respect of its reliability or a particular problem due to the constraints imposed by the existing techniques, algorithms, software (such as programming languages, operating systems) and hardware (such as memory).

To further clarify the complexity of a network in a clearer and simpler way; let us consider the system given in Figure 1.7, which is obtained from Figure 1.6 by introducing some interconnecting links between the relay-transmitters pair.

Figure 1.7 A large and complex network.

The information now could be sent through many several alternative paths created by the addition of interconnections. On adding more interconnections, there would be an exponential rise in the number of paths to carry the information from s to f. In other words, the complexity of a network increases with the additions of new interconnecting links transforming a large network to become more and more complex.

In reliability engineering, the large network shown in Figure 1.6 is simply a series-parallel arrangement of units, which can be analysed easily with the help of well-known probability laws of intersection and union. Such types of systems can be decomposed and are reducible to a single entity.

However, the system shown in Figure 1.7 is not reducible through series and parallel models and as such is known as non-series parallel system. Such a system not only requires better approaches and methodologies but also requires a better hardware and software platform for its analysis. SP or PS networks are generally non-complex systems whereas NSP systems fall in complex system category. The complexity of the NSP systems increases with the insertion of more and more interconnecting links connecting various nodes of the system.

1.2.3 Large and Complex System

Therefore, a large and complex system is one, which has not only multitude of system elements but has several interconnecting links as well. Summarily, the whole explanation of large and complex systems could be put in the following way:

A system may be a large system but not necessary be complex if it is reducible and has necessarily a SP (or PS) structure. The reliability of such systems can be evaluated very fast and the time to obtain reliability does not vary polynomially. However, if a system has lots of interconnections and is not reducible is called as a complex system. The complexity of the system increases, time to obtain reliability varies non deterministic polynomial in time.

1.3 Network Reliability Measures: Deterministic versus Probabilistic

Diverse network reliability problems entail different performance measures for the system, which are classified based on the network models. Some networks, such as urban road networks, entail traffic characteristic like waiting time, travel time, congestion etc. Transportation networks are usually studied to determine the maximum capacity flow between (s, f) node and/or characteristic of shortest path. For some cases, transmission speed and capacity could be the performance measure of interest. One can refer to (Sheir, 1991) for an overview of the subject. However, reliability theory, in general, and in this text, in particular, studies the network based on one of the most important network reliability measure, viz., specified node-set connectivity in probabilistic sense.

(Frank & Frisch, 1970) and (Wilkov, 1972) made earlier attempts to provide various definitions of system reliability. They identified two distinct classes of reliability measures:

Deterministic, and

Probabilistic.

The deterministic criteria made use of discrete measures to define the reliability of a network. The assumption made when dealing with deterministic measures is that the network is subjected to a destructive force or an enemy who has complete knowledge of the topology of the network. The purpose of this intelligent enemy is to destroy or disrupt network communication. Thus the main measure of reliability is the least amount of damage the enemy must be able to inflict to render the network inoperative.

Deterministic measures thus can be viewed as simple bounds on the reliability of the network, since they are often measured as the network’s worst-case vulnerability to failure. For example, in the (s, f) connectivity reliability problem, two deterministic measures of reliability are the number of edges and the number of nodes that must be destroyed or removed to disrupt the communication between the specified nodes. The minimum number of edges that must be removed in order to disconnect the nodes s and f is simply the number of edges in a minimum cardinality (s, f)-cut. The minimum number of nodes that must be removed to disconnect s and f is the (node) connectivity between the vertices s & f.

Both of these measures are computable in polynomial time. However, one of the main problems with deterministic measure is that it gives rise to some counterintuitive notions of network reliability. For example, consider the graphs shown in Figure 1.8.

Figure 1.8 Example of deterministic reliability.

According to one deterministic measure that uses (node) connectivity as a measure of the graph’s reliability, the graphs of Figure 1.8(a) and (b) are equally reliable since the (s, f)-connectivity of each graph is three. However, an intuition leads one to believe that graph (a) is the more reliable of the two.

The same problem arises when the cardinality of a minimum (s, f)-cut set is used as a measure of unreliability. Consider the graphs shown in Figure 1.9. Both graphs (a) and (b) have a minimum cardinality (s, f)-cut of size one. This deterministic measure therefore implies that both are equally reliable. This is again counterintuitive, as one expects graph (a) to be the more reliable of the two. This leads to the notion that a more intuitively acceptable measure of reliability might be a probabilistic measure.

Figure 1.9 Another example of deterministic reliability.

Therefore, for measuring the reliability of a network one can associate a statistical probability of failure/success with each of the components of the network in order to obtain a statistical measure of the overall unreliability/reliability of the network. This notion supports an accepted definition of reliability as: “the probability that a given system or device is operational”. This measure of reliability may be interpreted as a long-term average availability. That is, over a specified period of time, what is the probability that the network will remain operational? This also includes a fairly prevalent notion of reliability as the probability that a network is operational at any given moment of 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 modelled by a graph where the nodes of the graph represent the communication centres and communication links are represented by its edges.

The probabilistic methods for determining the reliability of a network generally assume the failure of edges and/or nodes as random events. Using predetermined probabilities that the edges and/or nodes are operational; the probability that the network remains operational is often of interest. A network is considered operational, if it is connected. The probability that the network is connected is often called probabilistic connectedness. This probabilistic model is often more appropriate than the deterministic model since it results in a probability that the network is connected at any point in time.

Based on the probabilistic connectedness of a specified set of nodes, the following three measures are in vogue in reliability texts as reliability measures:

1.3.1 Terminal-pair Reliability Measure

For any arbitrary network, terminal pair reliability (TR) is the probability that a communication path exists between two specified pair of nodes, viz., source node, s, and destination or terminal node, f. Network reliability and System reliability are the other terms being used synonymously for TR in the literature (Colbourn, 1987), (Misra, 1992).

1.3.2 All-Terminal Reliability Measure

All-terminal reliability requires that every node must be able to communicate with every other node of the network. It is defined as the probability that for every pair of nodes (x, y), ∀ x and y ∈ n, in the network, a path exits from node x to y. This is equivalent to stating it as the connectivity problem in graph theory. In the literature, global reliability and g-reliability are the other terms often used synonymously for all-terminal reliability.

The all-terminal reliability problem deals with communication among all nodes in a network. In other words, it is the probability of existence of a minimal set of edges such that all nodes of the network graph remain connected. A graph is connected if there is at least one path between every pair of nodes i.e., in this case a minimal operational sub graph is an operational spanning tree. For a spanning tree to be operational all of its edges must be operational (since it is a minimal operational sub graph), and therefore a spanning tree is in a failed state if any of its edges fail. A graph would have several spanning trees and the number of spanning trees grows exponentially with the graph size (Christofides, 1975), (Deo, 1979).

1.3.3 k-terminal Reliability Measure

k-terminal reliability requires that a set of k-specified set of 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