Abstract: In IP network, tomography method can perform fault diagnosis by analyzing the end-to-end properties with low costs. However, most existing tomography based techniques have the following problems: 1) the end-to-end detected number is not sufficient to determine the state of each link; 2) as the scale of the network goes up, the diagnosis time may become unacceptable. To address these problems, a new congested link diagnosis algorithm based on Bayesian model was proposed in this paper. This method firstly modeled the problem as a Bayesian network, and then simplified the network by two steps and limited the number of multiple congested links. Therefore, the proposed method could greatly reduce the computational complexity and guarantee the diagnostic accuracy. Compared with the existing diagnosis algorithm which is called Clink, the proposed algorithm has higher diagnostic accuracy and shorter diagnosis time.

Key words: IP network, fault diagnosis, end-to-end probe, Bayesian network, congestion link location

摘要： 通过端到端路径的性能判断IP网络运行状态的方法可以以较小的代价诊断网络故障，但目前已有的端到端技术仍然存在两个主要问题：1)端到端的探测数量不足以准确定位每条链路的拥塞状态；2)随着网络规模的扩大，诊断所消耗的计算时间过长，无法达到实时性的要求。为解决以上问题，提出一种基于贝叶斯模型的高效拥塞链路诊断算法。所提算法将拥塞定位问题建立成贝叶斯模型，将模型进行二次化简，并限制了同时发生拥塞的链路个数，从而在保证一定准确度的基础上大大降低了推理的计算复杂度。通过仿真与Planetlab实验将所提算法与Clink算法进行了对比，实验结果证明，所提算法具有更高的诊断准确度和更短的诊断时间。

关键词: IP网, 故障诊断, 端到端探测, 贝叶斯网, 拥塞链路定位