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

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

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



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

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

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

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

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

1引言

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

目前,有些学者已经提出一些基于网络层析成像技术的链路丢包率推断算法.文献[3,6]提出两种基于极大似然估计的链路丢包率推断算法.其中文献[3]提出的DE(Direct Estimator)算法通过求解高阶方程计算链路丢包率;文献[6]提出采用EM(Expectation Maximization)算法通过执行一个迭代过程逐步搜索高维解空间进行求解.该类算法精度最高,但当网络规模较大时,算法复杂度极高.文献[7,9]首先搜索网络中的拥塞链路,通过将非拥塞链路从路由矩阵中去除,以化简路由矩阵,然后进行链路丢包率求解.该类算法具有较低的算法复杂度,但在链路丢包率计算过程中将部分丢包率不为零的链路从路由矩阵中去除,因此会产生一定的误差,且该类算法均建立在网络中拥塞链路比例较小的假设条件之下.文献[10]提出一种自底向上的链路丢包率估计算法,首先估计叶链路丢包率,然后再自底向上逐层求解链路丢包率.该算法利用兄弟链路之间的相关性,直接给出解析解,极大地降低了算法复杂度,但在逐层求解的过程中引入累积误差,导致算法精度有所降低.文献[11]对自底向上的方法进行改进,在计算链路k的成功传输概率统计父节点收到探测包个数时,忽略了节点k的父节点收到,但同时在链路k和链路k的兄弟节点都丢包的探测包,影响了算法精度.文献[12]将EM算法和自底向上算法合并,首先采用自底向上方法直接求解叶链路丢包率,然后将求解的叶链路丢包率作为初始值,采用EM算法推断内部链路丢包率.该算法解决了自底向上方法内部链路丢包率估计引入累积误差的问题,但估计内部链路时,仍通过执行迭代过程搜索高维解空间进行求解,因而算法复杂度仍较高.文献[13]提出的FPA(Fast Path-based Approach)算法利用子树丢包之间的相关性,直接求解链路丢包率,该算法具有较低的算法复杂度,但由于该算法在求解过程中忽略了部分全局信息,算法精度有所降低.

本文根据网络丢包的特性,提出了一种基于子树丢包模式的链路丢包率推断算法,在保证精度的前提下,提升推断过程的计算速度,减少链路丢包率测量的总时间.

2模型与假设

2.1网络模型

用T=(V,L)表示逻辑树状网络拓扑模型[3,13],其中V为节点集合,代表网络中的路由器和主机,L为连接节点的链路集合.节点O∈V为T的根节点.节点集合R⊂V(无子节点的节点)表示所有的叶节点,即探测报文接收节点,|R|为叶节点个数.每个非叶节点k都至少有一个子节点,节点k的子节点集合用c(k)表示.每个非根节点k有且仅有一个父节点,用f(k)表示.链路(f(k),k)∈L记为链路k.定义f1=f且fn(k)=f(fn-1(k)),其中n为正整数.用集合a(k)={i∈V|∃n>0,i=fn(k)}表示节点k的祖先节点,用集合U=V{O}表示非根节点集合,用集合I=UR表示非叶节点非根节点集合,即网络内部节点集合.T(k)=(V(k),L(k))表示以节点k为根的子树,其叶节点集合为R(k)=R∩V(k);

2.2丢包模型假设

与大多数文献[10～13]一样,本文假设:

(1)在探测周期内,网络拓扑结构不发生变化;

(2)链路丢包过程为相互独立的伯努利(Bernoulli)过程,即同一探测包经过不同的链路的丢包事件相互独立,不同探测包经过同一链路的丢包事件相互独立.

对每一个链路k∈L,用αk(1)∈[0,1]表示探测包从节点f(k)经过链路k被成功传输的概率,即αk(1)=P{xk=1|xf(k)=1};αk(0)=1-αk(1)表示探测包经过链路k被丢失的概率,即链路丢包率.定义|L|(|L|为链路个数)维向量A=(α1(0),α2(0),…,α|L|(0))为全部链路的丢包率,A即为要通过统计方法推测的参数.

L(X;A)=lg(P(X;A))

(1)

通过极大似然估计,可得链路丢包率估计值为:

(2)

2.3基于EM的链路丢包率估计

在每次探测中,仅有叶节点的探测结果为可观测数据(用Y=XR=(xk:k∈R)表示),而网络内部节点的探测结果是未知的,因此不能使用式(2)直接求解链路的丢包率.文献[6]提出用EM算法求解链路丢包率,主要通过以下两步进行求解:

(3)

其中

(4)

(5)

可得链路k的丢包率估计值为:

(6)

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

3.1链路丢包率初始值计算

现有EM算法链路丢包率初始值一般任意给定,迭代次数较多.由于更精确的链路丢包率初始值能减少EM算法迭代次数,从而提高算法速度,本文提出一种快速链路丢包率估计算法,利用该算法求得的结果对EM算法链路丢包率进行初始化.

(7)

其中,nr1和nr2分别表示被分支r1、r2接收到的探测包个数,n(xr1=1,xr2=1)表示同时被分支r1、r2成功接收到的探测包个数.对所有的内部节点k,都可以根据式(7)计算出探测包在路径p0,k上的成功传输概率.对于叶节点r,由于叶节点探测结果是可以观测到的,故路径p0,r上的成功传输概率估计值可以直接求出:

(8)

用式(7)和(8)求出所有非根节点的路径成功传输概率后,即可根据父子节点的路径成功传输概率关系求出所有链路的丢包率:

(9)

本文采用式(9)得出的链路丢包率估计值,作为EM算法链路丢包率初始值.

3.2网络拓扑传输状态独立区域划分

由于仅有叶节点的探测结果是可以观测到的,而网络内部节点的探测结果是不能观测到的,故对于一次探测过程,仅有叶节点和成功接收到该探测包的叶节点的祖先节点的探测结果是可以确定的,其他节点的探测结果是不能确定的.对任意链路k=(f(k),k),根据叶节点探测结果可以得到该链路对应的父子节点的探测结果有如表1所示五种情况.其中第1、2种情况链路传输状态是确定的,第3、4、5种情况链路的传输状态是不确定的.根据链路传输状态是否确定,将整个网络链路分为两个部分,传输状态确定性区域A(L;y)和传输状态非确定性区域B(L;y).在该次探测过程中,探测包在A(L;y)中的所有链路都被成功传输或丢失,而在B(L;y)中的所有链路上的传输状态是不确定的.如图2 所示拓扑,当叶节点探测结果为y=(1,0,1,0,0,0,0,1,0,0,0,0,0)时,探测包在图中实线表示的链路上被成功传输,在虚线表示的链路上被丢失,在点划线表示的链路上探测包的传输状态不能确定.故A(L;y)为图中实线和虚线表示的链路集合,B(L;y)为图中点划线表示的链路集合.

表1　节点探测结果及对应链路传输状态

当节点k的探测结果不确定时,其全部非叶子孙节点的探测结果都是不确定的,由表1可得,当链路k的传输状态不确定时,其全部的子孙链路的传输状态都是不确定的.因此,B(L;y)中链路可构成一系列没有公共节点的子树.用Tf(k)表示节点k的父节点f(k)与子树T(k)构成的子树,则图2中传输状态不确定链路构成子树Tf(2)和Tf(10).由链路丢包的独立性假设,可得这些没有公共节点的子树传输状态相互独立.令Bk(L;y)=L(Tf(k)),可将B(L;y)进一步划分成一系列传输状态非确定性独立区域{Bk(L;y)}k.图2中B(L;y)可以划分成独立区域B2(L;y)和B10(L;y),如图3所示.

3.3子树丢包模式

(10)

(11)

(12)

故对于非叶节点所对应的丢包模式,用式(10)计算出叶节点对应丢包模式的概率后,即可按照式(12)自底向上计算出所有内部节点对应的丢包模式概率.

(13)

3.4链路丢包率计算

对于叶节点r,由于叶节点探测结果是可以观测到的,故叶节点接收到的探测包个数:

(14)

令

(15)

代入式(4)可得

(16)

(17)

(18)

3.5算法复杂度分析

表2　丢包模式及计算相应变量所需乘法次数

4仿真

为对本文提出LIALP算法性能进行验证,本文从链路丢包率测量精度与速度两个方面对算法进行考察,并与现有EM算法[6]和FPA算法[13]进行比较.

4.1MATLAB模型仿真

为考察算法计算时间和误差随拓扑层数的变化,本文按图5所示方法构造每层节点数目为3,拓扑层数分别为2至9的8个拓扑.所有拓扑的链路丢包率服从均匀分布:αk(0)～Uniform[0,0.2].对每个拓扑,均产生100个丢包率组合,重复进行100次实验,探测包个数为500.图6-7分别给出了本文提出的LIALP算法、EM算法和FPA算法链路丢包率测量计算时间和相对误差随网络拓扑层数的变化.从图6可以看出,本文提出的LIALP算法链路丢包率测量计算时间较现有EM算法有明显降低,而且随着拓扑层数的增加,这种优势更加明显,当网络拓扑层数为8时,LIALP算法计算时间(0.1182s)仅为EM算法计算时间(9.3563s)的1.26%.FPA算法利用子树丢包之间的相关性直接求解链路丢包率,不需要迭代计算,故算法计算速度最快.但由于FPA算法在求解的过程中,将网络拓扑拆分成单个子树后进行计算,忽略了部分全局信息,使得算法精度有所降低.如图7所示,当网络拓扑层数为8时,FPA算法精度较LIALP算法降低19.5%.

为考察在网络不同拥塞程度下算法精度的变化,本文采用图2所示拓扑,所有链路丢包率服从均匀分布:αk(0)～Uniform[αave-0.02,αave+0.02],其中αave为丢包率均值,αave=0.05,0.10,…,0.30.探测包个数为500,重复100次试验.图8给出了链路丢包率测量相对误差随链路丢包率均值的变化情况.从图可以看出,LIALP算法和EM算法测量相对误差明显小于FPA算法,三种算法测量相对误差都随链路丢包率均值的增大而增大,且FPA算法增大的更快.

4.2NS2仿真

增加探测包个数即增加采样点数,能减小链路丢包率测量误差,但是增加探测包个数会导致探测时间增加,从而导致测量总时间增加.本文采用NS2仿真进一步比较算法精度随探测包个数的变化,以及在相同精度条件下链路丢包率测量总时间.采用NS2构建如图2所示的网络.该网络包含20个节点和19条链路.所有链路的带宽均为10Mbps,每条链路的物理传播时延为10ms,队列长度为50,排队模型为FIFO(First In First Out),拥塞避免算法采用尾部丢弃(Drop-tail).仿真背景流由两部分组成:(1)服从Pareto分布的On/Off模型120条UDP流和120条TCP流.发送节点和接收节点在所有节点中随机选择.(2)叠加在每条链路上的服从Pareto分布的On/Off模型UDP流和TCP流.每条链路上的UDP流和TCP流个数均为15至30之间的随机整数.UDP流和TCP流的On期和Off期均为200ms,UDP流的速率为0.5Mbps,TCP流的速率为0.2Mbps.探测包为从根节点向全部叶节点发送的恒定速率多播包,其大小为50Byte,发送速率为0.2Mbps.

表3和图9分别给出了探测包个数为500、1000、…、10000时,三种算法链路丢包率测量计算时间和相对误差的变化情况.从中可以看出,三种算法计算时间都随探测包个数的增加而增大,相对误差都随着探测包的个数的增加而降低.当探测包个数相同时,LIALP算法和EM算法精度最高,FPA算法计算时间最短,但误差最大,故在相同测量精度条件下,FPA算法需要发送的探测包最多.所需探测包个数越多,则探测时间越长,从而导致链路丢包率测量总时间越长.表4给出了当相对误差为1%时,三种算法所需探测包个数、链路丢包率计算时间和测量总时间.从表中可以看出,在误差相同的条件下,FPA算法的链路丢包率计算时间(0.13s)最短,但需要的探测包个数(5000)较LIALP算法和EM算法(3300)多51.5%.LIALP算法链路丢包率测量速度最快,其测量总时间(7.23s)仅为现有EM算法(103.95s)的6.96%,FPA算法(10.13s)的71.37%.

表3　三种算法计算时间(s)随探测包个数的变化

表4　三种算法探测包个数、计算时间和测量总时间

5结论

本文根据网络链路丢包的特性,提出了一种基于子树丢包模式的链路丢包率推断算法.该算法能在保持现有EM算法较高精度的条件下,有效减少链路丢包率测量总时间,提高测量速度.在相同测量精度(相对误差为1%)下,该算法测量速度较现有EM算法提高约13.4倍,较FPA算法提高40%.

参考文献

[1]Coates A,Hero III A O,Nowak R,et al.Internet tomography[J].IEEE Signal Processing Magazine,2002,19(3):47-65.

[2]张润生,李艳斌,李啸天.基于合并分层聚类的网络拓扑推断算法[J].电子学报,2013,41(12):2346-2352.

Zhang Run-sheng,Li Yan-bin,Li Xiao-tian.Agglomeration hierarchical clustering based algorithm for network topology inference[J].Acta Electronica Sinica,2013,41(12):2346-2352.(in Chinese)

[3]Cáceres R,Duffield N G,Horowitz J,et al.Multicast-based inference of network-internal loss characteristics[J].IEEE Transactions on Information Theory,1999,45(7):2462-2480.

[4]Fei G,Hu G.Accurate and effective inference of network link loss from unicast end-to-end measurements[J].IET Communications,2012,6(17):2989-2997.

[5]Zhang Zhi-yong,Fei Gao-lei,Pan Shenli.Afast link delay distribution inference approach under a variable bin size model[J].IEICE Transactions on Communications,2013,96(2):504-507.

[6]Bu T,Duffield N,Presti F L,et al.Network tomography on general topologies[A].ACM SIGMETRICS Performance Evaluation Review[C].New York:ACM,2002.21-30.

[7]Nguyen H X,Thiran P.Network loss inference with second order statistics of end-to-end flows[A].Proceedings of ACM SIGCOMM’07[C].New York:ACM,2007.227-240.

[8]Qiao Yan,Qiu Xue-song,Meng Luo-ming,et al.Efficient loss inference algorithm using unicast end-to-end measurements[J].Journal of Network and Systems Management,2013,21(2):169-193.

[9]顾然,邱雪松,乔焰,等.基于非线性规划的链路丢包率推理算法[J].电子与信息学报,2012,34(6):1425-1431.

Gu Ran,Qiu Xue-song,Qiao Yan,et al.Link loss inference algorithm with nonlinear programming[J].Journal of Electronics & Information Technology,2012,34(6):1425-1431.(in Chinese)

[10]Zhu W,Geng Z.A bottom-up inference of loss rate[J].Computer Communications,2005,28(4):351-365.

[11]Li Y J,Cai W D.Afast multicast-based approach to inferring loss performance[J].Journal of Communication and Computer,2006,3(3):19-24.

[12]Zhang Jian-zhong,Lin Wen,Lin Jun-wu.Multicast-based inference of network internal loss from end-to-end data[A].IEEE 9th International Conference on Signal Processing[C].Beijing:IEEE,2008.2045-2048.

[13]Su H,Li Y,Lin S,et al.Inference of link loss rates by explicit estimation[J].IET Communications,2010,4(5):540-550.

尹文涛男,1983年生于湖北孝感,哈尔滨工业大学自动化测试与控制系博士研究生.主要研究方向为网络测量与网络层析成像技术.

E-mail:huayichu@163com

杨京礼男,1984年生于山东日照,哈尔滨工业大学自动化测试与控制系讲师.主要研究方向为网络测量与网络层析成像技术.

E-mail:icehit0615@163com

姜守达(通信作者)男,1964年出生黑龙江伊春,哈尔滨工业大学自动化测试与控制系教授.主要研究方向为虚拟试验技术,网络测量技术,数字信号处理等.

E-mail:jsd@hit.edu.cn

魏长安男,1981年生于河北承德,哈尔滨工业大学自动化测试与控制系讲师.主要研究方向为虚拟试验技术,自动测试技术等.

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

YIN Wen-tao,YANG Jing-li,JIANG Shou-da,WEI Chang-an

(AutomaticTestandControlInstitute,HarbinInstituteofTechnology,Harbin,Heilongjiang150080,China)

Abstract: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.

Key words:network measurement;network tomography;link packet loss rate;loss pattern

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.011

中图分类号:TP393

文献标识码：A

文章编号：0372-2112 (2016)03-0565-07

基金项目:黑龙江省博士后基金(No.LBHZ11171)

收稿日期:2014-05-08;修回日期:2014-08-27;责任编辑:梅志强