Probabilistic Analysis of Network Availability

In recent years, quantitative verification concerning network availability has received increasing attention due to its practical importance in network management. Existing work extends upon qualitative verification and tries to answer whether a network would have any link overload under failures and dynamic traffic. The simple yes-or-no question falls short of accurately characterizing the robustness of a network under uncertainties, which the operators are in dire need of. Thus, we argue that it is necessary to design a probabilistic framework to analyze network availability comprehensively. We propose Pita, a novel network analysis framework that outputs the overall probability of the network being unavailable under a range of failure scenarios and traffic demands. We formalize the problem and show that it is #P-hard which does not admit deterministic approximation solutions. We further develop an improved randomized approximation that exploits the structural property of our problem to reduce the computational cost of the so-called boundary oracle procedure, a key bottleneck of the approximation, without any accuracy loss. Evaluation with real topologies shows that Pita provides up to 2.25x speedup over state-of-the-art solutions, and can be effectively used in many network management tasks such as identifying high-risk failure scenarios, and aiding robust traffic engineering design.

I. Introduction

Internet-scale services ranging from search, advertisement, and social networks require stringent performance and availability guarantees from the underlying networks. Yet managing a network at scale is inherently difficult, especially under uncertainties such as failures and dynamic traffic. In this regard, various verification tools have been developed to verify that certain important properties can be guaranteed in the network. Most of them focus on verifying qualitative properties that are path-related [4], [15], [25], [32], e.g., reachability [32], path isolation (two paths do not share any links) [25], waypointing (traffic traverses a chain of services) [4], etc.