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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-00648155
Contributor : Emna Salhi <>
Submitted on : Monday, December 5, 2011 - 11:26:01 AM
Last modification on : Friday, November 16, 2018 - 1:40:18 AM
Long-term archiving on: Tuesday, March 6, 2012 - 2:30:17 AM

File

ICC_11.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00648155⟩

Share

Metrics

Record views

516

Files downloads

171