Localization of Single Link-Level Network Anomalies

Achieving accurate, cost-efficient, and fast anomaly localization is a highly desired feature in computer networks. Prior works, examining the problem of single link-level anomaly localization, have claimed that a necessary condition for localizing anomalies unambiguously is to deploy resources that enable the monitoring of a set of paths distinguishing between all links of the network pairwise. In this paper, we show that the number of pair of links that are to be distinguished can be cut down drastically using an already established anomaly detection solution. This results in reducing the localization overhead and cost significantly. Furthermore, we show that all potential anomaly scenarios can be derived offline from the anomaly detection solution. Therefore, we compute full localization solutions, i.e. monitors that are to be activated and paths that are to be monitored, for all potential anomaly scenarios offline. This results in a significant minimization of the localization delay. We devise an anomaly localization technique that selects monitor locations and monitoring paths jointly; thereby enabling a trade-off between the number and locations of monitoring devices and the quality of monitoring paths. The problem is formulated as an integer linear program (ILP), and is shown to be NP-hard through a polynomial-time reduction from the NP-hard facility location problem. The effectiveness and the correctness of the proposed anomaly localization scheme are verified through theoretical analysis and extensive simulations.