基于变结构离散动态贝叶斯IP网络拥塞链路推理

2016-11-24陈宇周巍段哲民钱叶魁赵鑫

通信学报 2016年8期

陈宇，周巍，段哲民，钱叶魁，赵鑫

(1. 西北工业大学电子信息学院，陕西西安 710072；2. 郑州航空工业管理学院电子通信工程学院，河南郑州 450015；3. 通信网信息传输与分发技术重点实验室，河北石家庄050000；4. 解放军防空兵学院导弹系，河南郑州 450052；5. 解放军防空后学院弹炮一体系，河南郑州 450052)

陈宇1,2,3，周巍1，段哲民1，钱叶魁4，赵鑫5

针对CLINK算法在路由改变时拥塞链路推理性能下降的问题，建立一种变结构离散动态贝叶斯网模型，通过引入马尔可夫性及时齐性假设简化该模型，并基于简化模型提出一种IP网络拥塞链路推理算法（VSDDB）。利用逐次超松弛迭代算法求解链路拥塞先验概率唯一解，基于贝叶斯最大后验准则，借助加权启发式贪心搜索算法推理拥塞链路集合。实验验证了VSDDB算法具有更好的推理性能。

IP网络；变结构离散动态贝叶斯；拥塞链路推理；Boolean模型

1 引言

随着IP网络规模的迅速扩大[1]，网络结构日益多样，多链路拥塞现象频有发生，人工定期检查已不能适应当前大规模网络的需要。因此，借助先进的手段进行有效、准确的IP网络内部拥塞链路推理对网络维护和管理非常重要。

基于ICMP(Internet control message protocol)的主动探测技术[2]仅通过部分端到端(E2E,end-to-end)路径的多次快照(snapshots)获取E2E路径的性能及拓扑信息，借助贝叶斯理论等推理待测IP网络中各链路性能的方法较基于SNMP(simple network management protocol)的被动探测技术具有实时性好、需获取的数据量小且不涉及用户隐私等优点，被广泛应用于互联网内部链路性能测量中。自 1996年Vardi首次提出在互联网链路性能推理中使用类似医学层析扫描(tomography)技术以来，借助主动探测的tomography技术推理IP网络内部链路性能的方法主要包括以下两大类。第一类方法使用多播方式[3]或多簇单播模拟多播的方式[4～6]，通过构建待测IP网络系统线性方程组求解各链路分组丢失率数值。此类方法需投入复杂的基础设施建设[7]，且对各E2E路径性能探测的时间相关性要求非常高，并假设链路性能服从某种特定分布或具有时空独立性和平稳性等[8]。出于安全等因素，当前互联网中大部分路由器对单播的支持度高于多播，时间相关性难以保证，且tomography技术是借助尽可能少的E2E路径性能测量结果推理网络内部各链路性能，常导致构建的系统线性方程组系数矩阵欠定，无法求得唯一解。另外，随着IP网络规模的扩大，线性方程组系数矩阵的维数增大，求解中涉及复杂的求逆计算，甚至导致算法失效。第二类方法将各E2E探测路径及链路性能借助 Boolean代数值进行表示[5,9,10]。Nguyen[11]、Padmanabhan[9]和 Duffield[5]等提出借助不相关的 E2E路径性能探测，推理 IP网络中最有可能发生拥塞的链路集合，简化了链路性能推理过程。文献[11]提出了经典的链路拥塞推理算法CLINK，较先前不使用先验概率的MCMC(Monte Carlo Markov chain)[9]算法及使用一致先验概率的SCFS (smallest consistent failure set algorithm)[5]算法在推理性能上有较大程度的提高。

文献[11]同时指出，IP网络的路由改变会影响推理性能，其认为链路拥塞会持续数个小时，但未考虑路由变化对当前链路推理性能带来的影响。乔焰等[12]将路由变化作为噪声干扰，通过在拥塞链路推理贝叶斯网模型中加入转移概率，提高了推理精度。但是，由于IP网络各AS区域多采用动态路由算法(如OSPF)，对IP网络进行拥塞链路推理时，路由将根据链路状态发生动态改变，造成推理过程中IP网络拓扑结构的变化，从而引起IP网络构建的贝叶斯网推理模型的结构变化，不仅在参数上发生改变。因此，上述方法均不能对动态路由IP网络进行准确建模，拥塞链路推理将产生一定误差。另外，多链路拥塞造成的IP网络高时延和高分组丢失现象，还有可能涉及违反 SLA(service-level agreement)等相关服务等级协定[1]。因此，网络管理者需要及时准确地定位拥塞链路，并采取相应的处理。

综上，研究者大多从静态路由入手简化对 IP网络拥塞链路的推理过程，未充分考虑 IP网络动态路由算法策略对算法推理性能造成的影响。针对此问题，本文建立一种变结构离散动态贝叶斯(VSDDB,variable structure discrete dynamic Bayesian)网模型，通过引入马尔可夫性假设及时齐性假设简化该模型；基于该简化模型提出一种 IP网络拥塞链路推理新算法VSDDB，提高了动态路由算法下IP网络拥塞链路推理精度。VSDDB算法针对系统线性方程组系数矩阵的奇异性及稀疏性问题，通过对系数矩阵去相关、补满秩，利用逐次超松弛迭代算法求解拥塞链路先验概率唯一解；最后，基于贝叶斯最大后验(MAP,maximum a-posterior)准则，提出一种加权启发式贪心搜索算法推理当前IP网络中的拥塞链路集合。

本文的主要贡献包括以下3个方面：1)建立动态路由IP网络下的变结构离散动态贝叶斯网模型，通过引入马尔可夫性假设及时齐性假设简化该模型；2)基于该简化模型提出一种IP网络拥塞链路推理新算法VSDDB，有效解决动态路由IP网络中的多拥塞链路推理问题；3)模拟、仿真及实测网络实验比较验证了本文提出新算法VSDDB的推理性能优于经典CLINK算法。

2 网络模型及相关定义

2.1 贝叶斯网模型

为了方便对IP网络内部的拥塞链路推理，简要描述 IP网络拥塞链路推理时需构建的贝叶斯网模型。贝叶斯网模型是一种表示因果关系的有向无环图模型 G=(ν,ε)。其中，ν代表节点，ε代表连接节点的有向边。本文基于引言所述的主动探测技术中的第二类方法，借助Boolean代数模型对动态路由IP网络进行拥塞链路推理。首先，对 IP网络中各E2E路径及途经链路的状态变量作出如下定义。

定义1IP网络中各E2E路径的状态变量集合为各E2E路径途经链路的状态变量集合为路径拥塞时，yi=1；反之， yi=0。同理，链路拥塞时， xj=1；反之，xj=0。

其中，np为待测IP网络E2E路径总数，nc为E2E路径途经链路总数。在构建IP网络拥塞链路推理贝叶斯网模型时，Y为模型中的观测变量(证据节点)，X为隐藏变量(隐藏节点)，各E2E路径及途经链路的连接关系构成模型的有向边。如探测出E2E路径Pi(i=1,2,…,np)拥塞( yi=1)，则对IP网络拥塞路径途经的各链路拥塞推理问题可转化为已知贝叶斯网模型中的观测变量Y，对隐藏变量X最有可能的一组取值的选取问题。贝叶斯网模型节点联合概率为

其中， pa(xj)为节点xj的父节点。根据各E2E路径探测性能，借助贝叶斯网模型推理出最有可能发生拥塞的链路集合，可利用最大评分参量(argmax)进行求解

其中，P( Y)仅与网络状态及探测结果有关，与链路选取无关，则式(2)可简化为

引理1[13]取最大值时，当满足如下条件：1)如果 yi=0，且 Dij=1，则 xi=0；2)如果 yi=1，则必然存在至少一个 xi=1，使 Dij=1。

由于E2E路径性能正常时，该路径途经各链路的性能也正常；路径拥塞时，该路径途经各链路中至少有一条链路发生了拥塞。故E2E路径与途经各链路之间应存在如式(4)所示的概率关系。

因此，在推理IP网络内部拥塞链路时，正常路径途经的各链路必为正常状态，不必再进行性能推理。即可将正常路径对应的观测变量yi及相关隐藏变量xj（途经链路状态变量）以及有向边从IP网络构建的贝叶斯网推理模型中移除。

定义 2将观测变量、相关隐藏变量及连接有向边从贝叶斯网模型中移除，剩余的贝叶斯网模型为 IP网络拥塞链路推理中的拥塞贝叶斯网模型。

2.2 变结构离散动态贝叶斯网模型

为了构建动态路由算法下 IP网络拥塞链路推理的贝叶斯网模型，首先引入如下定义。

定义 3如果组成一个离散动态贝叶斯网络，不同时刻的离散静态贝叶斯网络的结构或参数发生变化，则这类离散动态贝叶斯网络称为变结构离散动态贝叶斯网络[14]。

对待测IP网络各E2E路径N次snapshots，学习链路拥塞先验概率的过程中，如IP网络拓扑结构发生n次改变，则可得到n个静态贝叶斯网模型，将每个静态贝叶斯网模型对应时间(snapshots次数)间隔看作一个时间片(T)。因此，根据定义3，对动态路由 IP网络构建的拥塞链路推理变结构离散动态贝叶斯网模型可由多个时间片下的静态贝叶斯网模型组成。为了简化推理过程，引入 2个基本假设[15]。

假设 1一阶马尔可夫性假设，即给出当前系统状态，将来的系统状态和过去是独立的。

假设 2时齐性假设，即各时间片中节点的条件概率与各时间片间的转移概率不随时间发生变化。

根据假设1、2，变结构离散动态贝叶斯网模型可由推理时刻前N次snapshots对应的初始时间片T1和推理时刻时间片 T2下的静态贝叶斯网模型，通过节点接口(共有链路)联接而成。简化模型如图1所示。

图1 变结构离散动态贝叶斯网模型

由图1可知，链路lh，lj，…，lk均存在于时间片T1和时间片T2的拥塞E2E路径中，构成两时间片的节点接口，两时间片下的路径拥塞状态变量（观测变量）、链路状态变量（隐藏变量）及拓扑关系分别构成各时间片下的静态贝叶斯网模型，由节点接口联结构成动态路由算法下IP网络拥塞链路推理模型。

如IP网络配置为静态路由算法策略，则在进行拥塞链路推理时，N次snapshots中路由始终不发生变化，则推理模型中仅包含一个时间片下的静态贝叶斯网模型。因此，本文对动态路由算法下的 IP网络构建的变结构离散动态贝叶斯网推理模型即简化为 CLINK算法中构建的静态贝叶斯网推理模型。

2.3 IP网络选路矩阵模型

IP网络选路矩阵模型D的构建方法如下定义。

定义4IP网络选路矩阵D的各行为E2E路径 Pi(i=1,2,…,np)，各列为 IP网络中所有链路lj(j=1,2,…,nc)。按照跳数(hop)级别顺序从小到大依次排列；当某条 E2E路径 Pi途经某条链路 lj时，选路矩阵 D对应位置处的元素值 Dij=1，否则Dij=0。

链路拥塞先验概率学习过程中，根据各E2E路径 traceroute探测获取的途经链路，可构建各时间片下的选路矩阵D。为了减少ping实际发分组探测的路径数，根据矩阵特性，可对选路矩阵D去相关化简，得到矩阵 ′D，去除线性相关路径后并不影响矩阵特性及矩阵列数(即链路覆盖范围不变)。对各E2E路径通过ping性能探测后，在 ′D中去除正常路径及途经链路对应的矩阵行元素及列元素，即可得到拥塞矩阵Dd，再次去相关化简后，即可得化简拥塞矩阵即链路拥塞先验概率求解系统线性方程组中的系数矩阵。

3 VSDDB算法

基于待测 IP网络构建的变结构离散动态贝叶斯网简化模型，本文提出一种动态路由算法下的IP网络拥塞链路推理算法（VSDDB）。算法原理如图2所示。

图2 VSDDB算法设计原理

算法主要包括以下2个方面。1)各链路拥塞先验概率求解。首先，根据N次E2E路径snapshots中的traceroute获取到的各E2E路径途经链路，可构建T1及 T2的选路矩阵D1及D2，通过矩阵化简可得出及；然后，根据 N次 E2E路径snapshots中的ping获取T1及T2各E2E路径性能探测结果，分别求解出各E2E路径拥塞概率及并去除正常路径及途经链路在矩阵及中的对应的行及列，再次化简后得到各拥塞矩阵及，通过去相关、补满秩操作获取及；分别构建两时间片下链路拥塞先验概率求解 Boolean线性方程组，及分别为两时间片下线性方程组稀疏系数矩阵；最后，利用逐次超松弛迭代算法求解链路拥塞先验概率唯一解推理当前时刻拥塞链路集合。根据当前1次snapshots获取拥塞路径；然后，基于贝叶斯MAP准则，设计加权启发式贪心搜索算法，推理拥塞路径中最有可能发生拥塞的链路集合。

3.1 链路拥塞先验概率求解

IP网络中，各E2E拥塞路径的整体传输率iΨ与路径途经各链路的传输率jϕ之间满足式(5)关系[16]。

其中，iΨ为第i条路径整体传输率，jϕ为该路径下途经的第 j条链路的传输率。为对应各自时间片下 IP网络构建的化简拥塞矩阵的元素值。根据定义4，当第j条链路存在于路径Pi中，否则，为了简化推理过程，根据定义1，对E2E拥塞路径及途经各链路的性能关系利用Boolean代数模型进行表述，如式(6)所示。

其中，“∨”为Boolean值最大化操作符。为了对拥塞链路先验概率进行求解，对式(6)两边取数学期望，并转换后可得

其中，nε为拥塞路径途经链路数，为去相关后的 E2E路径的拥塞概率可通过 N 次snapshots中ping探测出的各E2E路径状态Boolean值求和取平均得出，用表示。为便于计算，对式(7)两边取对数，整理后可得

根据动态路由算法选路策略，当IP网络中某链路截断或持续拥塞达到一定时间后，会重新进行E2E路径途经链路的选取。因此，在拥塞链路先验概率学习过程中，N次snapshots中对IP网络构建的选路矩阵 D可能会发生改变。由此，带来式(8)中的改变，从而造成链路拥塞先验概率pj求解误差。另外，在借助tomography技术进行拥塞链路推理时，通常利用尽可能少的E2E路径探测，覆盖尽可能多的链路，并且通过前述2次去相关化简操作，易造成式(8)中对应的E2E路径数小于算法覆盖的链路数。使式(8)所示Boolean线性方程组系数矩阵欠定，无法求得唯一解。

因此，需对式(8)进行系数矩阵扩展补满秩操作。由于系数矩阵各行代表各线性无关拥塞路径。因此，可将两拥塞路径视为一条路径进行关联处理，对两矩阵行相应链路进行“∨”操作，构建的扩展路径行。各扩展路径行对应的扩展矩阵各元素用表示。将各元素与与扩展矩阵各元素合并，并再次去相关化简后，可构造满秩系数矩阵其为秩等于nε的方阵，k值大小取决于的值，nε为拥塞路径途径链路数，为对应的拥塞路径数。

式(11)为 Boolean代数线性方程组，直接求解存储量和计算量均过大，特别是此方程组系数矩阵各元素为Boolean代数值0或1，非零值较少，为典型的稀疏矩阵。当矩阵主元nε)时，无法计算。即使主元但当其绝对值很小时，的逆矩阵作为除数，因舍入误差的存在也会使计算带来较大误差。本文将稀疏矩阵系数线性方程组迭代求解逐次超松弛(SOR,successive over-relaxation)方法引入到 IP网络链路拥塞先验概率Boolean线性方程组求解中。

3.2 当前时刻拥塞链路推理

在动态路由算法下的IP网络中，基于变结构离散动态贝叶斯网简化模型，根据当前1次snapshots获取到的各E2E路径性能结果进行拥塞链路推理，链路拥塞后验概率如式(12)所示。

其中，nε′为推理时刻拥塞链路总数。对式(17)取对数可得

当各 E2E路径探测过程中未发生路由改变，式(19)的推理过程即简化为静态路由算法下的IP网络内部拥塞链路推理经典算法CLINK[11]的拥塞链路推理过程。由此可见，本文提出的VSDDB算法是对 IP网络内部拥塞链路推理的一般方法。

3.3 算法步骤及伪代码

VSDDB算法在拥塞链路推理时，借助加权启发式贪心搜索算法[17]寻找最优解，算法伪代码如下所示。

Pθ//推理时刻拥塞路径集合；

Lε//推理时刻拥塞路径途经链路集合；

n(k)//推理时刻链路 lk存在于多少条 E2E路径中；

plk//包含链路lk的所有E2E路径；

输出：Ω//拥塞链路推理集合。

1)初始化Ω=φ；//初始化拥塞链路推理集合

2)初始化Pϑ=Pθ；//初始化推理时刻拥塞路径集合

3)计算 pκ；

6)while (Pϑ≠φ)do

8)Ω=Ω+ {lk|lk∈ Lε}；//添加此lk到拥塞链路覆盖集合Ω

9)更新 Lε=Lε− {lk}；//从集合Lε中去除已推理的链路lk

10)更新 Pϑ=Pϑ− { plk|lk∈ plk}；//从集合Pϑ中去除包含lk的所有路径

11)end while

4 实验评价

为了客观评价VSDDB算法的拥塞链路推理性能，分别采用模拟、Emulab仿真及Internet实测实验，比较验证算法推理性能。为了更好地验证提出算法在不同网络环境中的拥塞链路推理性能，模拟及仿真实验中，利用 Brite拓扑生成器[18]分别生成 3种不同类型、规模的 IP网络拓扑模型：Waxman、BA及GLP。在Eclipse MARS.1平台下导入不同网络拓扑模型，并利用随机数模型模拟多链路拥塞场景。

4.1 参数设置及评价指标

路径拥塞阈值参数 path-congestion-threshold：默认设置N=30，path-congestion-threshold=0。对各E2E路径30次snapshots中，E2E路径分组丢失率低于设置阈值(0.05)时，路径正常，否则，路径拥塞。为了验证 IP网络拥塞程度不同的情况对算法性能带来的影响。模拟实验中，引入拥塞链路数占待测IP网络链路数之间的比例参数congestion-link-ratio来仿真网络拥塞程度，设置congestion-link-ratio为0.05～0.6，模拟拥塞链路数由少到多发生改变；为了模拟 IP网络中路由变化频繁程度对算法推理性能的影响，引入路由变化参数 route-changingthreshold，以连续snapshots中链路持续拥塞次数作为路径变路由的触发条件，默认设置 routechanging-threshold=4。利用检测率(DR,detection rate)及误报率(FPR,false positive rate)对算法性能进行评估[11]。DR及FPR均为各参数不变情况下，连续实验10次取平均后结果。

其中，F为推理时刻实际发生拥塞的链路，X为算法推理出的拥塞链路。

4.2 模拟实验评价

本文提出的VSDDB算法及重现CLINK算法均采用JAVA语言在Eclipse MARS.1平台下进行编写。利用Brite拓扑生成器分别生成150个节点的Waxman、BA及 GLP模型文件，导入 Eclipse MARS.1平台，搭建IP网络拓扑结构。链路拥塞事件利用随机数发生器以congestion-link-ratio比例在每次snapshots中进行模拟，包括链路拥塞先验概率学习中的30次snapshots以及当前时刻拥塞链路推理中的 1次 snapshots。设置 route-changingthreshold=4作为各 E2E路径变路由阈值，并模拟OSPF中最短路径优先策略重新选路。在相同的链路覆盖范围、拥塞链路事件场景下，利用本文提出的VSDDB算法与经典CLINK算法分别在不同类型及节点规模网络中进行拥塞链路推理实验，比较2种算法的推理性能。其中，VSDDB算法在3种不同 IP网络模型中的推理结果用实线表示，CLINK算法用虚线表示。

4.2.1 不同拥塞程度下的算法性能比较

设置 congestion-link-ratio为 0.05～0.6，来模拟待测IP网络不同的链路拥塞程度，随着数值增大（链路拥塞数目增加），网络拥塞程度加重。2种算法的拥塞链路推理检测率及误报率如图3所示。

图3 不同拥塞链路比例下2种算法推理性能比较

如图3(a)所示，不同IP网络模型下，2种算法的检测率均呈下降趋势。VSDDB算法的检测率明显高于 CLINK算法。VSDDB算法在 GLP模型下检测率最高，其次是BA和Waxman模型。在动态路由IP网络下，CLINK算法的推理性能较不变路由时[11]明显降低，由于 GLP模型幂率性强，共有链路数多，因此，基于最小链路覆盖理论[11]在 GLP模型下进行多链路拥塞推理时，路由变化对算法的推理性能影响最大。如图3(b)所示，不同IP网络模型下，VSDDB算法的误报率较CLINK算法略有降低。由图3可知，随着拥塞链路比例的增大，VSDDB算法的性能下降趋缓，稳定性优于CLINK算法。综合比较2种算法的检测率、误报率及稳定性特征，VSDDB算法的推理性能优于CLINK算法。

4.2.2 不同变路由频率下的算法性能比较

为了验证VSDDB算法在不同IP网络环境下的推理性能，利用链路连续拥塞次数触发路由表更新来模拟 IP网络变路由的情况。分别设置 routechanging-threshold为 1～4代表路由改变的阈值参数。如 route-changing-threshold=4，表示链路在连续4次snapshots中均为拥塞状态时，途经该链路的E2E路径将发生路由改变；数字越小表明待推理IP网络中各E2E路径的路由变化频率越频繁；反之，路由变化越慢。对150个节点的Waxman、BA及GLP模型 IP网络中，分别设置 congestionlink-ratio=0.1，route-changing-threshold不同的实验场景，2种算法的拥塞链路推理检测率及误报率如图4所示。

图4 不同路由变化阈值参数下2种算法推理性能比较

如图4(a)所示，在动态路由IP网络中，路由变化频率越快，2种算法在不同模型下的检测率均越低，误报率均越高。检测率随路由变化频率的增大呈线性下降趋势。VSDDB算法在GLP模型下的检测率最高，BA及Waxman模型下次之，并且相差不大；而CLINK算法在GLP模型下检测率最低，BA及Waxman模型下次之，同样是由于GLP模型的强幂率特性所致。由图 4(b)可知，2种算法均在GLP模型下的误报率最低，其次是BA及Waxman模型。综合2种算法在不同模型下的检测率及误报率，VSDDB算法的推理性能优于CLINK算法。

4.2.3 不同网络规模下的算法推理性能比较

为了验证本文提出的 VSDDB算法在不同IP网络规模下的拥塞链路推理性能。利用Brite拓扑生成器以默认参数生成节点数(nodenumber)从50～350变化的 Waxman、BA及 GLP模型。分别设置 congestion-link-ratio=0.2，route-changingthreshold=4，2种算法的拥塞链路推理检测率及误报率如图5所示。

图5 不同网络规模下2种算法推理性能比较

如图5(a)所示，2种算法在GLP模型下的检测率最高，其次是BA及Waxman模型；如图5(b)所示，2种算法在GLP模型下的误报率最低，其次是BA及Waxman模型。在不同规模的IP网络中，VSDDB算法的检测率及误报率均较CLINK算法稳定。综合 2种算法在不同模型下的检测率、误报率及稳定性特征，VSDDB算法的推理性能优于CLINK算法。

4.3 Emulab仿真实验评价

实际IP网络拓扑大部分服从幂率特性，因此，在Emulab实验平台上使用Brite拓扑生成器以默认参数生成20个节点，服从强幂率规则分布的GLP模型Brtie文件；通过导入Brite文件，搭建待测IP网络，并将探针及性能监控台接入待测网络；由性能监控台给各发分组路由器探针下达探测任务，并将测得数据上传至性能监控台分别利用VSDDB及CLINK算法进行拥塞链路推理。

Emulab仿真实验平台设置如下。1)网络拓扑：设置仿真IP网络各链路带宽100 Mbit/s，时延15 ms；2)选路协议：IP网络采用OSPF协议，E2E路径服从最短路径优先选路规则。设置链路拥塞时延大于8 min后重新选路，各路由器的路由表在2 min内可实现稳定，链路在2 min内可恢复正常数据传输；3)链路状态：采用LM1模型[9]，链路拥塞时分组丢失率服从[0.05,1]均匀分布；链路正常时分组丢失率服从[0,0.01]均匀分布。为每条链路赋初始分组丢失率后，链路分组丢失服从Gilbert过程，即链路状态在拥塞与正常之间波动。处于正常状态时不分组丢失；处于拥塞状态时全分组丢失。链路每隔2 min以congestion-link-ratio比例按照随机数规律变化产生拥塞事件。本次Emulab仿真实验仅对路由器节点Node6进行发分组探针部署，主动发分组探测 E2E路径数 12条，链路覆盖数18条。链路拥塞先验概率学习过程中，性能监控台每隔2 min对探针发送1次snapshots指令。设置congestion-link-ratio=0.1，2种算法的拥塞链路推理性能比较如表1所示。

表1 Emulab仿真实验算法推理性能比较

从表1可以看出，由于CLINK算法未考虑IP网络中动态路由对算法推理性能带来的影响，导致算法推理性能下降。

4.4 Internet实测实验评价

为了验证VSDDB算法在实际Internet网络中拥塞链路推理性能，在 50个节点组成的某高校局域网中以最大链路集合覆盖方式部署待测网络各路由器探针，主动探测发分组E2E路径数225条。由于实测 Internet网络内部各链路分组丢失率数值无法准确获知，即在Internet实测实验中，缺少式(20)中的标准答案（Benchmark）F，无法利用检测率及误报率公式判断算法的拥塞链路推理性能。

因此，为了能够验证本文提出VSDDB算法在实测Internet网络中的推理性能，借鉴文献[11]在实际 Internet中进行路径性能一致性判断的方法，对推理算法进行性能评价。路径性能一致性判断的定义如下：将当前拥塞链路推理时刻探测出的拥塞路径分成大小相等的2个集合，即推理集合Ι及验证集合P，根据集合Ι中各拥塞路径，利用算法进行各途经拥塞链路的推理；根据拥塞链路所在路径为拥塞路径的原理，确定验证集合P中推理出的拥塞路径，并与验证集合P中的拥塞路径进行对比，如路径推理结果与实测路径拥塞结果一致，则算法推理结果准确。2种算法的拥塞链路推理性能比较如表2所示。

表2 Internet实测实验算法推理性能比较

由表2所示，实测实验结果同样验证了本文提出的 VSDDB算法拥塞链路推理性能优于 CLINK算法。

5 结束语

本文提出了一种动态路由 IP网络中的拥塞链路推理新方法 VSDDB。通过引入马尔可夫假设及时齐性假设，对动态路由 IP网络拥塞链路推理问题，建立变结构离散动态贝叶斯网简化模型；利用逐次超松弛算法迭代求解各链路拥塞先验概率，并基于贝叶斯最大后验准则，提出一种加权启发式贪心搜索方法推理拥塞链路集合。模拟、仿真及Internet实测实验比较验证了VSDDB具有更好的推理性能。

[1]潘胜利,张志勇,费高雷,等. 网络链路性能参数估计的层析成像方法综述[J].软件学报,2015,26(9):2356-2372.PAN S L,ZHANG Z Y,FEI G L,et al. Survey on network tomography for link performance parameter evaluation[J]. Journal of Software,2015,26(9): 2356-2372.

[2]杨洋,杨家海,王会,等. IP网络时延敏感型业务流自适应负载均衡算法[J].通信学报,2015,36(3):131-141.YANG Y,YANG J H,WANG H,et al. Towards load adaptive routing based on link critical degree for delay-sensitive traffic in IP networks[J]. Jouranl on Communications,2015,36(3): 131-141.

[3]MAO Y Y,KSCHISCHANG F R,LI B H,et al. A factor graph approach to link loss monitoring in wireless sensor networks [J]. IEEE Journal on Selected Areas in Communications,2005,23(4): 820-829.

[4]DUFFIELD N G,PRESTI F L,PAXSON V,et al. Inferring link loss using striped unicast probes[C]//IEEE INFOCOM’01,Anchorage,IEEE Communications Society. c2001: 915-923.

[5]DUFFIELD N G. Network tomography of binary network performance characteristics[J]. IEEE Trans. on Information Theory,2006,52(12):5373-5388.

[6]COATES M,NOWAK R. Network loss inference using unicast end-to-end measurement[C]//ITC Conf. on IP Traffic,Modeling and Management. Monterey: IEEE Computer Society,c2000: 28.

[7]ADAMS A,BU T,ĆACERES R,et al. The use of end-to-end multicast measurements for characterizing internal network behavior[J].IEEE Communications Magazine,2000,38(5): 152-159.

[8]LAWRENCE E,MICHAILIDIS G,NAIR V,et al. Network tomography: a review and recent developments[J]. Fan amp;Koul Editors Frontiers in Statistics,2006:345-364.

[9]PADMANABHAN V N,QIU L L,WANG H J. Server-based inference of internet performance[C]//IEEE INFOCOM’03. San Francisco,CA,c2003: 1-15.

[10]BATSAKIS A,MALIK T,TERZIS A. Practical passive lossy link inference[C]//PAM 2005. Springer Berlin Heidelberg,c2005,3431:362-367.

[11]NGUYEN H X,THIRAN P. The Boolean solution to the congested ip link location problem: theory and practice[C]//IEEE INFOCOM’07.Alaska,USA,c2007: 2117-2125.

[12]乔焰,孟洛明,成璐,等. 动态网络中的高效多故障诊断技术[J].北京邮电大学学报,2009,32(6): 1-4.QIAO Y,MENG L M,CHENG L,et al. An efficient approach to multi-fault diagnosis in dynamic networks [J]. Journal of Beijing University of Posts and Telecommunications,2009,32(6): 1-4.

[13]连可,龙兵,王厚军. 基于贝叶斯最大后验概率准则的大型复杂系统故障诊断方法研究[J]. 兵工学报,2008,29(3): 352-356.LIAN K,LONG B,WANG H J. A fault diagnosis approach of the large complex system based on bayes theory[J].Acta Armamentarii,2008,29(3): 352-356.

[14]高晓光,史建国. 变结构离散动态贝叶斯网络及其推理算法[J]. 系统工程学报,2007,22(1): 9-14.GAO X G,SHI J G. Structure varied discrete dynamic Bayesian network and its inference algorithm[J]. Journal of Systems Engineering,2007,22(1):9-14.

[15]RISH I,BRODIE M. Adaptive diagnosis in distributed systems[J].IEEE Transactions on Neural Networks,2005,16(5): 1088-1109.

[16]SHAVITT Y,SUN X,WOOL A,et al. Computing the unmeasured: an algebraic approach to internet mapping [J]. IEEE Jounal on Selected Areas in Communications,2004,22(1): 67-78.

[17]GAREY M R,JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: Freeman Press,1979.

[18]MEDINA A,LAKHINA A,MATTA I,et al. BRITE: an approach to universal topology generation[C]//MASCOTS. Washington,c2001:346-353.

IP network congested link inference based on variable structure discrete dynamic Bayesian

CHEN Yu1,2,3,ZHOU Wei1,DUAN Zhe-min1,QIAN Ye-kui4,ZHAO Xin5

(1. School of Electronic Information,Northwestern Polytechnical University,Xi’an 710072,China;2. School of Electronics and Communication Engineering,Zhengzhou University of Aeronautics,Zhengzhou 450015,China;3. Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory,Shijiazhuang 050000,China;4. Department of Missile,Air Defence Forces Academy of PLA,Zhengzhou 450052,China;5. Department of Antiaircraft Gun-Missile System,Air Defense Forces Academy of PLA,Zhengzhou 450052,China)

Aiming at the inference performance descending of CLINK algorithm in dynamic routing IP network,a kind of variable structure discrete dynamic Bayesian network model was established. Based on the simple model after introducing assumptions of Markov property and time-homogeneity,a kind of congested link inference algorithm VSDDB was proposed.Successive over relaxation iterative algorithm was introduced to solve the link congested prior probabilities,based on the Bayesian maximum a-posterior criterion,a kind of weighted heuristic greedy algorithm was used to infer the set of congested links.The experimental results have shown that the VSDDB algorithm has better inference performance.

IP network,variable structure discrete dynamic Bayesian,congestion link inference,Boolean model

s:The National Basic Research Program of China (973 Program)(No.2013CB329104),The National Natural Science Foundation of China (No.61103225),The Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory Research Fund

TP393

2016-01-11；

2016-07-09

国家重点基础研究发展计划（“973”计划）基金资助项目（No.2013CB329104）；国家自然科学基金资助项目(No.61103225)；通信网信息传输与分发技术重点实验室基金资助项目

10.11959/j.issn.1000-436x.2016151