Fine-grain diagnosis of overlay performance anomalies using end-point network experiences

Overlay networks were proposed to improve Internet reliability and facilitate a rapid deployment of new services. Non-invasive diagnosis of performance problems is the key capability for overlay service management in order to adapt to dynamic network conditions in a timely manner. Existing overlay diagnosis approaches assume extensive knowledge about the network, and require monitoring sensors or active measurements. In this paper, we propose a novel diagnosis technique to localize performance anomalies and determine the packet loss contribution for each network component. Our approach is purely based on endpoint packet loss observations to reason about the location of observed packet loss without active probing or sensor deployment. We formulate the problem as a constraint-satisfaction problem using constraints derived from network loss invariants and end-user observations. Our solution also circumvents the possibilities of insufficient or malicious end-user participation. We evaluate our approach extensively using simulation and experimentation, and demonstrate the accuracy, effectiveness and scalability of our approach for various network sizes, participation levels and spurious amounts.