A Distributed Network Monitoring Model with Link Constraint

Distributed network monitoring system could obtain up-to-date performance information of the network effectively. The monitoring and aggregating procedure require the establishment of reliable, low delay and low cost aggregating routes. Hence the aggregating procedure is constrained by the link delay and the round hops. Addressed in this paper are the problem of optimizing a distributed monitoring system and the problem of optimally upgrading the existing monitoring infrastructure as the network evolves. It is shown that both problems are NP hard, and could be mapped to the well-known weighted set cover problem by assigning the weight function. A greedy algorithm could be used to solve these problems with an approximation ratio ln n+1, where n is the number of monitored nodes. Furthermore, how to choose an appropriate link constraint value by simulation is discussed.