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

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:

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.