A Greedy Scheme for Designing Delay Monitoring Systems of IP Networks

This chapter presents efficient techniques for monitoring link and path delays in a Service Provider or Enterprise IP network. The proposed two-phased approach attempts to minimize both the monitoring infrastructure costs as well as the additional traffic due to probe messages. In the first phase, it computes the locations of a minimal set of monitoring stations such that all network links are covered. Subsequently, in the second phase, the scheme computes a minimal set of probe messages that are transmitted by the stations to measure link delays. Since, both the station selection problem as well as the probe assignment problem are NP-hard, we propose greedy approximation algorithms that achieve a logarithmic approximation factor for the station selection problem and a constant factor for the probe assignment problem. These approximation ratios are provably very close to the best possible bounds for any algorithm.