Distributed link anomaly detection via partial network tomography

We consider the problem of detecting link loss anomalies from end-to-end measurements using network tomography. Network tomography provides an alternative to traditional means of network monitoring by inferring link-level performance characteristics from end-to-end measurements. Existing network tomography solutions, however, insist on characterizing the performance of all the links, which introduces unnecessary delays for anomaly detection due to the need of collecting all the measurements at a central location. We address this problem by developing a distributed detection scheme that integrates detection into the measurement fusion process by testing anomalies at the level of minimal identifiable link sequences (MILSs). We develop efficient methods to configure the proposed detection scheme such that its false alarm probability satisfies a given bound. Meanwhile, we provide analytical bounds on the detection probability and the detection delay. We then extend our solution to further improve the detection performance by designing the probing and fusion process. Our evaluations on real topologies verify that the proposed scheme significantly outperforms both centralized detection based on link parameters inferred by traditional network tomography and distributed detection based on raw end-to-end measurements.