Evaluating Network Vulnerability with the Mincuts Frequency Vector

Overview & Synopsis

We consider the problem of evaluating the behavior of a communication network face to the possible disruption of some of its components. We) are interested in the case when there is no available statistical information about the dependability properties of the network components. Instead of working with reliability metrics in a stochastic context, we analyze vulnerability measures in a deterministic framework. This approach allows us to propose a solution to other classes of problems (not easily handled in reliability theory). For instance, we can consider the problem of evaluating the capacity of a network to resist to external attacks. We can also address the problem of quantifying the network ability to satisfy some capacity constraints in transporting information. In the paper, we propose a definition of vulnerability allowing the numerical evaluation of these aspects of a communication system. We show that it verifies some intuitively desirable properties, which is not the case of previously proposed means of vulnerability analysis. Last, we discuss the algorithmic issues related with the evaluation of the proposed metric.