基于子树丢包模式的链路丢包率快速推断算法

为提高网络链路丢包率的测量速度,本文提出一种基于子树丢包模式的链路丢包率推断算法.该算法通过选择合理的链路丢包率初始值以减少迭代次数;根据端到端测量结果将网络拓扑划分为传输状态确定性区域和非确定性区域,避免确定性区域冗余分解造成的时间开销;通过对非确定性区域子树丢包模式按层分解,以子树丢包模式为基本计算单元,减少非确定性区域链路丢包的重复分解过程,提高链路丢包率计算速度.仿真结果表明,该算法能在不损失测量精度的前提下,减少链路丢包率测量总时间,提高测量速度.

A Fast Network Link Loss Inference Algorithm Based on Subtree Loss Pattern

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 ar-ea in which the transmission state is determinate,and several areas in which the transmission state is indeterminate.By de-composing 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.