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
IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
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.
Type de document :
Rapport
[Research Report] 2013
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00770596
Contributeur : Emna Salhi <>
Soumis le : jeudi 28 février 2013 - 11:10:09
Dernière modification le : mercredi 16 mai 2018 - 11:23:33
Document(s) archivé(s) le : mercredi 29 mai 2013 - 04:05:09

Fichier

Journal2v1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00770596, version 2

Citation

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

Partager

Métriques

Consultations de la notice

607

Téléchargements de fichiers

119