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

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:

1 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

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