Robust Monitoring of Link Delays and Faults in IP Networks
Robust Monitoring of Link Delays and Faults in IP Networks
复制标题
DOI：
10.1145/1217722
复制
发表时间：
2003-07
期刊：
影响因子：
--
通讯作者：
Yigal Bejerano;R. Rastogi
中科院分区：
文献类型：
--
作者：
Yigal Bejerano;R. Rastogi
在本文中，我们开发了用于监控服务提供商或企业IP网络中的链路延迟和故障的故障恢复技术。我们的两阶段方法试图将监控基础设施成本和探测消息带来的额外流量降至最低。在第一阶段，我们计算最小监测站的位置，以便覆盖所有网络链路，即使在存在几个链路故障的情况下也是如此。随后，在第二阶段，我们计算站点发送的探测消息的最小集合，以测量链路延迟并隔离网络故障。我们证明了站点选择问题和探测器分配问题都是NP难的。然后，我们提出了贪婪近似算法，该算法对于站点选择问题实现了对数近似因子，对于探测器分配问题实现了常数因子。可以证明，这些逼近比非常接近任何算法的最佳可能界
In this paper, we develop failure-resilient techniques for monitoring link delays and faults in a Service Provider or Enterprise IP network. Our 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, we compute the locations of a minimal set of monitoring stations such that all network links are covered, even in the presence of several link failures. Subsequently, in the second phase, we compute a minimal set of probe messages that are transmitted by the stations to measure link delays and isolate network faults. We show that both the station selection problem as well as the probe assignment problem are NP-hard. We then 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