Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Localization of Single Link-Level Network Anomalies: Problem Formulation and Heuristic

Emna Salhi 1 Samer Lahoud 1 Bernard Cousin 1 
1 ATNET - Advanced Technolgy in Networking
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 Integer Linear Programming (ILP) algorithm that selects monitoring paths and monitor locations satisfying 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 NP-hard through a polynomial-time reduction from the NP-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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Emna Salhi Connect in order to contact the contributor
Submitted on : Thursday, February 28, 2013 - 11:10:09 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:23 AM
Long-term archiving on: : Wednesday, May 29, 2013 - 4:05:09 AM


Files produced by the author(s)


  • HAL Id : hal-00770596, version 2


Emna Salhi, Samer Lahoud, Bernard Cousin. Localization of Single Link-Level Network Anomalies: Problem Formulation and Heuristic. [Research Report] 2013. ⟨hal-00770596v2⟩



Record views


Files downloads