An algorithm for calculating flow-based network survivability

Survivability of a network is one of the most important issues in designing present-day communication networks. The k-edge survivability of a given network is defined as the percentage of total traffic surviving the worst case failure of k edges. Although several researches calculated k-edge survivability on small networks by enumeration, no prior research has considered how to calculate k-edge survivability on large networks. In this paper, we develop an efficient procedure to obtain lower and upper bounds on the k-edge survivability of a network.