Problem Localization and Quantification Using Formal Evidential Reasoning for Virtual Networks

Overlay (virtual) networks are mainly used to improve Internet reliability and facilitate a rapid deployment of new services. However, in order for overlay services to adapt to dynamic network conditions in a timely manner, efficient diagnosis of performance problems is required. Existing overlay diagnosis approaches assume extensive knowledge about the network and require invasive monitoring sensors or active measurements. In this paper, we propose a novel diagnosis technique to localize performance anomalies and determine the packet loss in each network component. Our approach is purely based on packet loss observations at the end-points to reason about the loss location and severity in the network without any active probing or sensor deployment. We formulate the problem as a constraint-satisfaction problem using network loss properties and end-user observations. Our diagnosis is robust against insufficient observations or malicious end-user participation. We evaluate our approach extensively using simulation and experimentation and demonstrate the accuracy, effectiveness, and scalability of our approach under various network sizes, participation ratio, and malicious observation ratio.