Diagnosing Link-Level Anomalies Using Passive Probes

In this paper, we develop passive network tomography techniques for inferring link-level anomalies like excessive loss rates and delay from path-level measurements. Our approach involves placing a few passive monitoring devices on strategic links within the network, and then passively monitoring the performance of network paths that pass through those links. In order to keep the monitoring infrastructure and communication costs low, we focus on minimizing (1) the number of passive probe devices deployed, and (2) the set of monitored paths. For mesh topologies, we show that the above two minimization problems are NP-hard, and consequently, devise polynomial-time greedy algorithms that achieve a logarithmic approximation factor, which is the best possible for any algorithm. 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.