Localization of Single Link-Level Network Anomalies: Problem Formulation and Heuristic
Emna Salhi, Samer Lahoud, Bernard Cousin · 2013
Abstract—Achieving accurate, cost-efficient, and fast anomaly localization is a highly desired feature in computer networks. A necessary and sufficient condition on the set of paths that need to be monitored upon detecting a single link-level anomaly in order to localize its source unambiguously have been established. However, this paper demonstrates that this condition is sufficient but not necessary. A necessary and sufficient condition that reduces the localization overhead, cost and delay significantly, as compared to the existing condition, is established. Furthermore, an ILP algorithm that selects monitoring paths and monitor locations which satisfy the established condition jointly, thereby enabling a trade-off between the number and locations of monitoring devices and the quality of monitoring paths, is devised. The problem is shown to be N P-hard through a polynomialtime reduction from the N P-hard facility location problem, and therefore, a scalable near-optimal heuristic is proposed. The effectiveness and the correctness of the proposed anomaly localization scheme are verified through theoretical analysis and extensive simulations. Index Terms—Network monitoring, network diagnosis, anomaly localization, anomaly detection, link-level anomalies. I.