The Distributed Network Monitoring Model with Bounded Delay Constraints

We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subject to delay constraint on the aggregating path. We show that this problem is NP\|hard and propose approximation algorithm proving the approximation ratio with ln m +1, where is the number of monitoring nodes. At last we extend our modal with more constraint of bounded delay variation.