Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection

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 : To reduce monitoring cost, the number of monitors that are to be deployed has to be minimized and the overhead of monitoring flows on the underlying network has to be reduced. In a recent work, we demonstrated, using ILP formulations, that there is a trade-off between these two minimization objectives. However, we have shown that the trade-off could be efficiently balanced by optimizing monitor location and anomaly detection costs jointly. The problem is NP-complete, hence ILPs could not deliver solutions for large networks. In this paper, we address the scalability issues. We propose two greedy algorithms that optimize monitor location cost and anomaly detection cost jointly. The first algorithm is based on an exhaustive heuristic that explores all paths that are candidate to be monitored, in order to select a subset of paths that reduces the total monitoring cost. On the opposite, the second algorithm is based on a selective heuristic that avoids exploring all the candidate paths to further improve scalability. The main challenge of this heuristic is to not degrade the solution quality. The two algorithms have been evaluated through extensive simulations on networks of hundred of billions of paths. The comparison of the solutions delivered by the two algorithms to each other and to the solutions delivered by the ILP demonstrates that the selective algorithm provides near-optimal solutions, while achieving a desirable scalability with respect to the network size and significant reduction of the computation time.
Type de document :
Communication dans un congrès
IEEE Internation Conference on Communications (ICC), Jun 2011, Kyoto, Japan. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00648155
Contributeur : Emna Salhi <>
Soumis le : lundi 5 décembre 2011 - 11:26:01
Dernière modification le : jeudi 5 avril 2018 - 12:30:14
Document(s) archivé(s) le : mardi 6 mars 2012 - 02:30:17

Fichier

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

Identifiants

  • HAL Id : hal-00648155, version 1

Citation

Emna Salhi, Samer Lahoud, Bernard Cousin. Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection. IEEE Internation Conference on Communications (ICC), Jun 2011, Kyoto, Japan. 2011. 〈hal-00648155〉

Partager

Métriques

Consultations de la notice

339

Téléchargements de fichiers

90