Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection

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.