Effective Monitor Placement in Internet Networks

Abstract

Various network monitoring and performance evaluation schemes generate considerable amount of traf- fic, which affects network performance. In this paper we describe a method for minimizing network monitoring overhead based on Shortest Path Tree (SPT) protocol. We describe two different variations of the problem: the AProblem and the E-Problem and prove that finding optimal solutions for both A- and E-problems is NP-hard. We also show that in general, an A-problem solution requires a significantly higher network overhead than an E-problem solution. We propose optimal approximation algorithms for the A- and E-problems and few different heuristics for the E-problem. Namely, we show that one can compute in polynomial time an O(ln|V |)-approximate solution for each of these problems. We analyze the performance of our approximation algorithms and heuristics on large graphs generated using Power-Law model. Performance results show that our heuristic algorithms for both problems achieve from 50% to 90% improvement in the network overhead comparatively with earlier algorithms that appeared in literature.