王 黎，张润生

（中国电子科技集团公司第五十四研究所，石家庄 050081）

基于最大似然的网络拓扑推断技术研究（三）

王 黎，张润生

（中国电子科技集团公司第五十四研究所，石家庄 050081）

（接7月刊）

5 仿真实验与结果分析

5.1 实验1

本实验比较不同方差因子条件下HT E[8]、LNI[12]、本文算法的拓扑推断性能。

仿真设置：实验所用的拓扑结构如图6所示。每一对叶子节点{i,j}，用Matlab生成满足单调性和一致性条件的K=100个节点相关性采样数据。这些数据为节点对共享链路上的所有子链路的测度数据之和，如节点10和11的相关性为链路(0,12)，(12,14)，(14,18)三条子链路上的测度数据之和。每条子链路的测度数据服从均值为γ1，方差为σ1的高斯分布。其中γ1～uniform(1,5)，σ1＝θ(1/)，θ为方差因子，Nnorm=10，N=K/Nnorm。本实验检验LNI、HTE、本文算法在方差因子θ从1到7的拓扑推断性能。本文使用推断正确概率和推断拓扑与原拓扑的树编辑距离评价算法性能。正确推断概率为正确推断次数与仿真总次数之比，树编辑距离[8]定义为从一个树图映射到另外一个树图所需的编辑操作之和，表征两个树图的相似程度，树编辑距离越小，表示两个树图越相似，即推断树状拓扑与原树状拓扑的树编辑距离越小，拓扑推断的效果越好。假设检验中显著性水平α＝0.005。

图6 仿真使用的逻辑拓扑

图7 拓扑推断树编辑距离

由于比对算法LNI对惩罚因子λ依赖性较大，因此这里我们分别取λ为2，2.5，3，4，8来检验LNI算法的性能。图7为三种算法在不同方差因子条件下的树编辑距离，图8是三种算法不同方差因子下的成功概率，可见随着方差因子的增大，叶子节点相关性采样数据的方差增大，三种算法的拓扑推断精度也随之下降。对于LNI算法，在不同的惩罚因子λ条件下，其性能差异较大，可以近似认为λ取2.5时获得最好的性能。比较三种算法，HTE算法的性能最差，LNI算法的惩罚因子取值较为合理时，可以获得相对更好的性能，而本文算法不论是树编辑距离还是正确推断概率都与LNI算法取最优λ时的性能相当。

5.2 实验2

本实验通过网络仿真软件Opnet产生网络叶子节点相关性采样数据，应用HTE[8]、LNI[12]、本文算法推断网络拓扑。

仿真设置：网络拓扑如图9所示，节点0为源主机节点，其他叶子节点为目的主机节点，节点13，14，15，16，17，18，19为路由器节点，端节点与路由器之间的使用速率为T1(1.544Mb/s)的链路，路由器之间的链路采用速率为E1(2.048Mb/s)的链路。每条链路上的背景流量由Opnet中自带的ip_traffic_ flow生成，端节点与路由器之间的链路背景流量设置为100Kb/s，路由器之间的链路背景流量设为300Kb/s，为体现背景流量的自相似性，背景流量都由50条ip_traffic_flow组成，每个ip_traffic_flow速率都相等，包间隔服从pareto分布，包大小服从负指数分布[18]。应用三明治包[8]方法进行叶子节点相关性采样，其中大包和小包分别为500字节，10字节。仿真中每对叶子节点相关性采样数K分别取100,140,180,220,260,300，Nnom=20，N=K/Nnom，在不同的K条件下分别独立仿真1000次。假设检验中显著性水平α＝0.005。

图9 Opnet仿真拓扑图

图10 拓扑推断树编辑距离

对于LNI算法，λ分别取为6，8，10，12。图10和图11分别给出了三种算法在不同的探测包数目条件下的树编辑距离和正确推断拓扑的概率。结合实验1，我们可以看出在实验1中本文算法的性能优势较LNI的最优情况不明显，而实验2中本文算法的性能优势更加明显，其主要原因是，HTE算法中的有限混合模型和LNI算法中的惩罚最大似然模型对数据高斯性有很强的依赖性，在实验1中直接产生高斯分布数据，而实验2中的数据由OPNET软件通过三明治包测量得到，显然直接测得的相关性数据不服从高斯分布，我们通过对其分组求均值来近似高斯分布，但由于本文中分组求均值的样本数Nnom=20，而中心极限定理一般要求在Nnom≥30才能较好的逼近高斯分布[16]，故实验数据对高斯的近似程度不高；而本文算法最终是使用t分布随机变量的函数进行假设检验，文献[17]指出t分布的运用对正态（高斯）假设不敏感，虽然寻找最相关子树时的最大似然模型也用到了高斯假设，但通过解该模型可得子树相关性最终可表示成样本数据的算术均值，算术均值对正态假设的依赖性也不高，因此实验2中本文算法相对LNI算法和HTE算法有更优的性能。

图11 拓扑推断正确概率

6 结束语

基于最大似然的网络拓扑推断技术，相对于传统的拓扑推断技术，其在网络拓扑分析中的应用前景更加宽广。本文以网络拓扑探测为出发点，将网络限定为规模较小的IP网络，假设探测节点已接入目标网络，探讨了此情景下基于最大似然的网络拓扑推断问题。提出了应用广义似然比子树序贯合并的树状网络拓扑推断算法。相对于惩罚最大似然算法及其改进算法，本文算法不需要设置惩罚因子，因此稳健性更高。文中的数值仿真实验表明，我们提出的拓扑推断算法对于推断规模较小的IP网络拓扑结构，具有较高的推断精度。基于最大似然的网络拓扑推断技术的研究目前仍处于基础研究阶段，本文仅在一定的限制条件下，对简单的网络拓扑分析问题进行研究，其在实际应用还有待进一步深入探讨。■

（全文完）

10.3969/J.ISSN.1672-7274.2016.08.010

TN911 文献标示码：A

1672-7274（2016）05-0038-02