A fast network link loss inference algorithm based on subtree loss pattern

作者：Yin Wen Tao; Yang Jing Li; Jiang Shou Da^*; Wei Chang An

来源：Acta Electronica Sinica, 2016, 44(3): 565-571.

DOI：10.3969/j.issn.0372-2112.2016.03.011

• Algorithm partition
• Decomposition process
• End-to-end measurement
• Inference algorithm
• Loss patterns
• Network measurement
• Network tomography
• Packet loss rates

In order to improve the efficiency of link loss inference algorithm, a novel inference algorithm based on subtree loss pattern is proposed. The iterations of the algorithm are reduced by obtaining a more appropriate initialization of loss rates. According to the outcomes of end-to-end measurements, this algorithm partitions the network topology into one area in which the transmission state is determinate, and several areas in which the transmission state is indeterminate. By decomposing all the indeterminate areas, a subtree loss pattern database is constructed. The loss rate is calculated based on the loss pattern. Through reducing the redundancy decomposition process, it can speed up the process of the inference of the link loss rate. Simulation results show that the algorithm can reduce the time of link loss rate inference with identical accuracy.

• 出版日期2016