基于丢包率的多播网络拓扑推断算法

吴辰文，茹俊年，刘香丽，李志昌

兰州交通大学电子与信息工程学院，兰州730070

1 引言

本文基于丢包率的多播网络拓扑推断算法，目前所有基于丢包率的多播网络拓扑推断算法都以有线网络为基础。文献[1-2]描述了一种利用探测包丢包状况推断二叉树拓扑结构的BLT（Binary Loss Tree）算法，在判断兄弟节点的过程中引入了静态判决门限值ε，将BLT算法从二叉树拓扑推广到一般树，提出了通用树拓扑推断算法GLT（General Loss Tree）。但是BLT和GLT算法都不能够准确地识别出只有一个子节点的节点。针对该问题，文献[3]对BLT算法加以改进，提出BHC（Binary Hamm ing Count）算法，该算法根据测量端到端的探测包丢包情况，结合节点的层次信息计算节点之间的海明距离，能够快速准确地推测出网络拓扑。但当网络中某些链路出现丢包较为严重时，BHC算法将失效。为了解决BHC算法失效问题，提出BFHC，通过比较与分析，证明了本文算法能有效提高拓扑推断的准确性。

2 算法描述

2.1 BHC算法描述

利用多播丢包模型[1]，假设源节点0发送n个探测包，n(u1)表示节点u1收到的探测包数，nu1u2表示节点u1、u2同时收到的探测包数，同理，nu1u2…um表示节点u1，u2，…，um同时收到的探测包数。求链路丢包率有如下推导公式，若u1，u2，…，um是兄弟节点，则u1对应的链路丢包率的估计值âu1为：

BHC算法提出可以通过读取探测包的TTL值来获取节点u的跳数值u.hop。探测包经过的路由数越多，其跳数值越大，由此引入了节点的层次信息。已知0为发送节点，R为接收节点集合，根据跳数值对接收节点集进行分类，从跳数值最大为h=maxu∈R(u.hop)的节点集Lm(m=k)开始，从Lm中选择海明码距[4]最小的两个节点u，v作为兄弟节点，节点u，v间的海明码距表示为：

其中，n代表源节点发送的探测包数；⊕代表异或操作。

根据

判断v′是否为u，v的兄弟节点，用a(r)表示它们的父节点，且将r加入跳数值为r.hop=m-1的节点集。令m=m-1，然后重复上述过程自底向上组织兄弟节点，直至根节点。在多数情况下，BHC算法推断出的拓扑能够较好地收敛于真实拓扑。但是当网络中某些链路丢包较为严重时，BHC算法的准确度会明显下降。多播网络拓扑示例如图1所示。其中，4、5为兄弟节点；7为其非兄弟节点。若l→4对应的路径与1→5对应的路径丢包情况相似，而1→7对应的链路丢包特别严重时，兄弟节点间的海明码距Hd(u4，u5)就很可能比非兄弟节点间的海明码距Hd(u5，u7)大（如表2），此时BHC方法失效。

图1 待推测的二叉拓扑图

2.2 HGLT算法描述

在HGLT[5-6]算法中，通过计算比较兄弟节点的最近父节点与非兄弟节点的最近父节点的估计值来区分兄弟节点是否为兄弟节点。如图1所示，4、5节点的最近父节点为2，而4、5、7的最近父节点为1，计算n(1)(1-ε)＜n(2)来区分7是否为4、5的兄弟节点。

2.3 改进的BFHC算法描述

在BFHC[7-9]算法中需要推断出4、5、7的最近共同父节点，如无法推断出4、5、7父节点的情况，并且在链路丢包率严重的情况下也能正确推断出真实的网络拓扑，为此提出改进的BFHC算法步骤如下：

（1）利用公式（1）计算各接收节点的丢包率。

（2）在Lm集合中，利用公式（2）计算Lm集合中具有最小海明码距的节点；如果接收点的丢包率相近，则可判断u，v为兄弟节点，否则，转（3）。

（3）此时，有一条链路的丢包率相对于其他节点的丢包率过大（丢包率严重的情况下）时，利用公式（3）计算v′是否为u、v的兄弟节点已失效，所以改进的算法是通过式（2）计算结果判断u、v为兄弟节点，并计算出u、v的父节点为a(r)。

（4）根据兄弟节点对父节点的贡献大于非兄弟节点对父节点的贡献，可以采用公式（4）判断v′是否为u、v的兄弟节点，公式为：

以待推测的二叉拓扑图1为例。其中，4、5为兄弟节点；7为其非兄弟节点。若l→4对应的路径与1→5对应的路径丢包情况相似，而1→7对应的链路丢包特别严重时，通过计算Hd(2，7)(1-ε0)＜Hd(2，5)来区别7是否为4、5的兄弟节点。

2.4 结果分析

通过表1计算可知，当所有接收节点链路丢包率相近时，BHC算法可以推断出网络拓扑；由表2计算可知，当某一条链路出现丢包严重时，BHC算法将失效；由表3计算可知，当某一节点出现丢包率严重时，非兄弟节点与父节点接收探包数的估计值要大于兄弟节点。因此，通过比较节点集中的接收节点与父节点所接收探包数的估计值来区分兄弟节点是可行的。

表1 BHC算法计算值

表2 BHC算法失效计算值

表3 BFHC算法计算值

在BFHC算法中，以图1为例，4、5为兄弟节点，根据4、5可知其父节点为2，当7节点丢包率严重时，利用式（4）判断7是否为节点4、5的兄弟节点。另外，本文算法可给定初始化区间让其选择一个判决门限初值ε0，此时ε0不一定小于所有内部链路的丢包率，然后在每一次判断出兄弟节点的同时，由式（1）估算出该节点对应的链路丢包率，再根据式（3）、（4）计算海明码距，并动态地调整ε值，从而可以提高拓扑推断的准确率。

3 仿真实验与性能分析

HGLT算法在叶节点无法识别其父节点时，将无法识别其最近的共同祖先节点，此时HGLT算法也会失效。本文以BHC算法为基础，利用NS2仿真平台，通过BHC算法与BFHC比较与分析，来验证BFHC算法的有效性。如图1所示。为了能够正确推断出网络拓扑，NS2仿真环境设置如下：边缘链路参数为带宽10M b/s，延迟10 m s；内部链路参数为带宽5 M b/s，延迟10 ms。每个路由传输的缓冲区大小为10个数据包，并且支持多播路由，采用Droptail丢包策略。背景流量以TCP为主，同时包含适当的UDP，UDP流量采用符合Pareto分布的开关型模型；探包产生过程符合Poisson分布。在数据采集过程中，统计的数据是不完全数据，采集频率越小，统计数据的误差就越大；反之，误差越小，为了使数据更加精确，根据上面设置的仿真环境，采集100次不同时间段的观测数据进行统计分析。

从图2可看出，当各链路丢包率相似时，随着发送探测包数的增加，两种算法的性能几乎一致。

图2 丢包率相似时拓扑推断准确率随发包发送数量的变化

如图3所示，在链路丢包较为严重时，BHC算法达到的最高准确率为85%，即使发送包的数量不断增加，拓扑推测准确率也不会上升；而在BFHC中，当发送包数量增加时，推断拓扑越接近真实拓扑。

图3 丢包率严重时拓扑推断准确率随发包发送数量的变化

综上所述，BFHC的整体性能明显优于BHC算法，能够有效地改善拓扑推断的准确性。

4 结束语

为了克服BHC算法在某些链路丢包严重时拓扑推断误差较大的缺点，本文提出BFHC算法，根据非兄弟节点与父节点接收探包数的估计值要大于兄弟节点这一特性，利用它们之间的海明码距Hd，并在计算中动态地调整门限值ε，可有效地推断出网络拓扑结构。

[1]Duffield N G，Horow itz J，Presti F L，et a1.Multicast topology inference from measured end-to-end loss[J].IEEE Transactions on Information Theory，2002，48（1）：26-45.

[2]李勇军，蔡皖东，王伟，等.基干端到端报文丢失的网络拓扑推测算法研究[J].通信学报，2007，28（10）：85-91.

[3]Tian Hui，Shen Hong.Multicast-based inference for topology and network：internal loss performance from end-to-end measure[J].Computer Communications，2006，29（11）：1936-1947.

[4]赵涛，蔡皖东，李惠贤.基于汉明距离的传感器网络分层拓扑发现算法[J].华中科技大学学报，2008（10）：82-86.

[5]吴文佳，张建中，张元鹏.基于丢包率的多播网络拓扑推断算法[J].计算机工程，2010，36（1）：124-126.

[6]Rabbat M，Nowak R，Coates M.Multiple source，multiple destination network tomography[C]//Proc of IEEE INFO Com’04，Hong Kong，China.New York：IEEE Press，2004.

[7]Bu Tian，Duffield N，Presti F L，et al.Network tomography on general topologies[C]//Proc of ACM SIGMETRICS.New York：ACM，2010：21-30.

[8]Wu Chenwen.Study on topology inference method based on clustering and NT technology[C]//Proceedings of ICCSE2010，2010：977-980.

[9]吴辰文，闫毅郎.基于时间阈值丢包率估计的网络断层扫描技术[J].计算机工程，2011，37（9）：130-132.