An Active Measurement Approach for Link Faults Monitoring in ISP Networks

摘要

Link failures are common in IP networks. In this paper, we develop a technique for diagnosing link failures in Service Provider or Enterprise IP networks using active measurement. The technique attempts to minimize both the monitoring infrastructure costs as well as the additional traffic due to probe messages. Both the station selection problem and the probe message assignment problem are NP-hard, and we propose approximation algorithms for these problems. We also apply our algorithms to existing ISP networks using topologies inferred by the Rocketfuel tool. The results can be used by ISP operators to trade off between accuracy of diagnosis and monitoring costs.