Effective Monitor Placement in Internet Networks
Yuri J. Breitbart, Feodor F. Dragan, Hassan Gobjuka · Journal of Networks · 2009
Abstract — Various network monitoring and performance evaluation schemes generate considerable amount of traffic, 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 A-Problem and the E-Problem and prove that finding optimal solutions for both A- andE-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. Index Terms — Algorithms, SP-tree, Network Monitoring I.