Anomaly Detection and Diagnosis Using Passive Monitoring

In this paper, we propose techniques for building a low-cost passive monitoring infrastructure for detection and diagnosis of link-level anomalies from path level measurements. Specifically, we attempt to compute appropriate locations of passive monitoring devices in a network and the paths to be monitored by these devices such that the monitoring infrastructure cost and data communication cost, in terms of number of monitored paths, is minimal. For general mesh topologies, we propose greedy algorithms, which can achieve logarithmic approximation factors, for monitor placement and path selection. We show that for the problems of monitor placement and path selection for anomaly detection in general graph topologies, getting better approximation guarantees are hard. We also consider tree topologies typical of enterprise networks, and show that while similar NP-hardness results hold, constant-factor approximation algorithms are possible for such topologies.