Emna Salhi, Samer Lahoud, and Bernard Cousin (2011)
Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection
In: ICC 2011 Communications QoS, Reliability and Modeling Symposium (ICC'11 CQRM), Kyoto, Japan.
To reduce monitoring cost, the number of monitors to be
deployed have to be minimized and the overhead of
monitoring flows on the underlying network have to be
reduced. In a recent work, we demonstrated, using ILP
formulations, that there is a trade-off between theses two
minimization objectives. However, we have shown that the
trade-off could be efficiently balanced by jointly
optimizing monitor location and anomaly detection costs.
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
jointly optimize monitor location cost and anomaly
detection cost. 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 the 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.