This paper investigates the problem of deploying network traffic monitors with optimized coverage and cost in an IP network. Deploying a network-wide monitoring infrastructure in operational networks is necessary for practical reasons. We investigate two representative solutions, a router-based solution called NetFlow and an interface-based solution called CMON. Several cost factors are associated with deploying either NetFlow or CMON in a network. We argue that enabling monitoring to cover a major portion of traffic instead of the entire traffic will achieve significant cost savings while at the same time give operators enough insight to their network. We use NetFlow as an example and develop a technique to achieve the optimal cost-coverage tradeoff. Specifically, we aim to solve the Optimal NetFlow Location Problem (ONLP) for a given coverage ratio. We analyze various cost factors to enabling NetFlow in such a network. We model the problem as an Integer Linear Program (ILP). We develop two greedy heuristics to cope with such problems of large scales given its NP-hard nature. The performance of the ILP and heuristics is demonstrated by numerical results and the LM heuristic is able to achieve sub-optimal solutions within 1-2% difference from the optimal solutions in a mixed router environment. It is observed that we can achieve 55% cost savings by covering 95% instead of 100% of the network traffic. We then extend our methodology to deploying CMON into such a network. The associated cost with deploying NetFlow and CMON is compared. The results demonstrate that CMON is more cost-effective when a small coverage ratio is desired because of its more modular nature.
['Hui Zang', 'Antonio Nucci']
Traffic monitor deployment in IP networks