Effective Monitor Placement in Internet Networks
|
| Title | Effective Monitor Placement in Internet Networks |
| Authors | |
| 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. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2009-09-01 |
| Source | Journal of Networks Vol 4, No 7 (2009): Special Issue: Security of Wireless Communication Systems |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |