尹文涛,杨京礼,姜守达,魏长安

(哈尔滨工业大学自动化测试与控制系,黑龙江哈尔滨 150080)



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

尹文涛,杨京礼,姜守达,魏长安

(哈尔滨工业大学自动化测试与控制系,黑龙江哈尔滨 150080)

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

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

1引言

随着计算机网络规模的扩大,以及网络安全需求的不断提高,传统的基于网络中间节点协作的网络测量方法面临巨大挑战.网络层析成像技术[1]将医学上的计算机层析成像思想引入到计算机网络测量中,根据在网络边界上获得的端到端的测量数据来分析和推断网络拓扑结构[2]、链路丢包率[3,4]、链路时延[5]等网络内部性能参数,对网络中的故障链路进行诊断和定位.网络层析成像技术可以在无需中间节点协作……