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

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

作　　者：尹文涛[1] 杨京礼[1] 姜守达[1] 魏长安[1] 

机构地区：[1]哈尔滨工业大学自动化测试与控制系,黑龙江哈尔滨150080

出　　处：《电子学报》2016年第3期565-571,共7页Acta Electronica Sinica

基　　金：黑龙江省博士后基金(No.LBHZ11171)

摘　　要：为提高网络链路丢包率的测量速度,本文提出一种基于子树丢包模式的链路丢包率推断算法.该算法通过选择合理的链路丢包率初始值以减少迭代次数;根据端到端测量结果将网络拓扑划分为传输状态确定性区域和非确定性区域,避免确定性区域冗余分解造成的时间开销;通过对非确定性区域子树丢包模式按层分解,以子树丢包模式为基本计算单元,减少非确定性区域链路丢包的重复分解过程,提高链路丢包率计算速度.仿真结果表明,该算法能在不损失测量精度的前提下,减少链路丢包率测量总时间,提高测量速度.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 netw ork topology into one area in w hich the transmission state is determinate,and several areas in w hich 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 w ith identical accuracy.

关 键 词：网络测量 网络层析成像 链路丢包率 丢包模式 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]