Locating network monitors: Complexity, heuristics, and coverage

There is an increasing interest in passive monitoring of IP flows at multiple locations within an IP network. The objective of such a distributed monitoring system is to sample packets belonging to a large fraction of IP flows in a cost-effective manner by carefully placing monitors and controlling their sampling rates. In this paper, we consider the problem of where to place monitors within the network and how to control their sampling. To address the tradeoff between monitoring cost and monitoring coverage, we propose and study minimum cost and maximum coverage problems under various budget constraints and in the presence of routing changes caused by link failures. We show that all of the problem formulations are NP-hard. We propose greedy heuristics, and show that the heuristics provide solutions quite close to the optimal solutions through experiments using synthetic and real network topologies. In addition, our experiments show that a small number of monitors often suffices to monitor most of the traffic in an entire IP network.