混合模型网络拓扑论文

开篇：润墨网以专业的文秘视角，为您筛选了一篇混合模型网络拓扑论文范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

1网络拓扑推断模型

本文将待推断的网络拓扑建模为有向逻辑树T[7]，令T(V,E)，V为节点集合，对应网络中的物理设备(主机、路由器等)，V由根节点s、叶子节点集合D(NrD为叶子节点数目)以及内部节点集合I构成；E为边集合,对应网络中的链路。令根节点s为源节点，树的叶子节点集合D为接收节点。令UsD为端节点，易得U中所有节点的度都为1(假设每个端节点仅与一个路由器相连)。该逻辑树中除根节点之外的所有非叶子节点均至少有两个孩子节点，除根节点之外的任一节点vID均有唯一的父节点f(v)；令(f(v),v),f(v),vV表示v与其父节点之间的链路；令(s,v)为根节点s与节点v之间的链路；令a(i,j),ij,i,jD为节点对{i,j}最深(距根节点最远)的公共父节点；令P(i,j)为{(s,i),(s,j)}的共享链路，即P(i,j)(s,a(i,j))，如图1中节点1和2的最深公共父节点为13，则1和2的共享链路为0,13。定义两叶子节点的相关性为((,))ijNPij，N(P(i,j))表示节点对(i,j)共享链路上的某种性能(排队时延方差、丢包率方差等)的度量，有N(P(i,j))P(i,j)，可见拓扑树中两个叶子节点的共享链路越长，则其相关性越大。叶子节点相关性满足以下条件[3-5]：1)单调性：若P(i,j)为P(k,l)的子链路，i,j,k,lD且ij,kl，则有ijkl。2)一致性：若P(i,j)与P(k,l)为同一链路，即a(i,j)a(k,l)，i,j,k,lD且ij,kl，则ijkl。令叶子节点i,j的相关性ij的估计值为ˆij。只要得到树状拓扑中叶子节点的相关性集合{ˆ,,}ijijD，就可以利用节点之间的相关性测度来推断出树状拓扑结构。

2稳健的网络拓扑推断算法

基于单播的拓扑推断需要向网络发送大量的探测包，这将给目标网络带来较大的流量，因此减少推断网络拓扑需要发送的探测包数目是将层析成像拓扑推断方法推向实际应用的关键。文献[8]提出了基于DFS排序的高效层析成像拓扑推断算法——Margin-Based算法，较以往的算法大大减少了需要测量的相关性数据，但其需要设置固定门限来对节点进行DFS排序，不同的门限对算法的拓扑推断性能影响较大，且该文没有给出一种可行的最优门限选择方法。针对这一问题，本节提出一种基于有限混合模型聚类的稳健高效层析成像拓扑推断算法(RobustMethod)，该算法与Margin-Based算法的本质区别是，该算法通过叶子节点逐步分类获得树状拓扑，而Margin-Based算法是通过多次对叶子节点二分对叶子节点进行深度优先排序(DFS)，然后通过比较相邻叶子节点的相关性大小对排序后的叶子节点合并获得树状拓扑。

算法思想其中D为叶子节点集合，V为拓扑图的顶点集合，\表示删除,f()N表示集合中所有节点的父节点指定为N节点，表示集合中元素个数，表示右边赋值给左边。伪代码中(2)-(5)处理聚类结果为1的情况，此时在链路(0,i)上只有一个内部节点。(6)-(17)处理聚类结果不为1的情况，此时在链路(0,i)上有多个内部节点。(7)-(16)分别对每个内部节点进行处理。

3仿真实验及结果分析

实验1本实验在不同方差因子条件下比较Margin-Based和RobustMethod算法的拓扑推断性能。仿真所用树状拓扑如图3所示，对每一对叶子节点(i,j)，使用Matlab生成满足单调性和一致性条件的节点相似度采样数据，W200。这些采样数据为节点对共享链路上的所有子链路的测度数据之和。每条子链路的测度数据服从均值为l，方差为l的高斯分布。其中~uniform(1,5)l，(1/2)l，为方差因子，N10，normNW/N20。使用推断拓扑与原拓扑的树编辑距离评价算法性能。树编辑距离[5,6]定义为从一个树图映射到另外一个树图所需的编辑操作之和，树编辑距离越小，表示两树图越相似，即推断树状拓扑与原树状拓扑的树编辑距离越小，拓扑推断的效果越好。为了体现不同的初始参考节点的对算法性能影响，每一次实验都随机选取初始参考点。本实验检验Margin-Based和RobustMethod在方差因子从1到7的拓扑推断性能，每个方差因子下独立进行1000次蒙特卡罗实验。

为研究不同DFS门限对Margin-Based算法性能的影响，我们分别取其门限为0.5、0.7、0.9、1.1、1.3、1.5进行仿真实验。图3给出了两种算法,的树编辑距离性能，由图3可知，随着方差因子增加，Margin-Based算法与本文的RobustMethod算法的树编辑距离都增大；对于不同的门限值Margin-Based算法的树编辑距离差异较大，可见其性能对门限值较为敏感，随着门限取值由小到大变化，Margin-Based算法的性能呈现由差到好再变差的过程，其中门限为0.9时性能近似为最优；而本文的RobustMethod算法应用了有限混合模型对叶子节点分类，无需设置比较门限，因此其拓扑推断过程更为稳健，从图3中可以看出，RobustMethod算法基本可以达到Margin-Based算法取最优门限时的性能。实验2本实验比较Margin-Based算法与RobustMethod算法所需测量的叶子节点相关性个数。在叶子节点数为5，10，15，20，25，30条件下，分别随机生成2000，5000，10000，18000，28000，40000个任意形状的树状拓扑，统计两种算法对这些拓扑需要测量的叶子节点相关性个数，取平均。

图4画出了两种算法在不同叶子节点数目条件下所需测量的叶子节点对相关性个数。从图中可以看出对于不同叶子节点个数的树状拓扑，RobustMethod算法平均需要测量的节点相关性数目要略少于Margin-Based算法，叶子节点个数较少时，二者需要测量的相关性数据数目近似，而随着拓扑节点数目增加，二者的差距逐渐增加。实验3本实验通过网络仿真软件Opnet产生网络采样数据，应用Margin-Based和RobustMethod两种算法推断网络拓扑。网络拓扑如图5所示，节点0为源主机节点，其它叶子节点为目的主机节点，节点16、17、18、19、20为路由器节点，端节点与路由器之间的链路速率为T1(1.544Mb/s)，路由器之间的链路速率为E1(2.048Mb/s)。每条链路上的背景流量都由Opnet中自带的ip_traffic_flow生成，端节点与路由器之间的链路背景流量设置为100Kb/s，路由器之间的链路背景流量设为300Kb/s，为体现背景流量的自相似性，背景流量都由50条ip_traffic_flow组成，每个ip_traffic_flow速率都相等，其包间隔都服从pareto分布，包大小服从负指数分布。应用三明治包方法进行叶子节点相似度采样，其中大包和小包分别为500Byte、10Byte。在不同探测包数目W条件下，通过Opnet软件分别采集1000组独立的叶子节点相关性数据。为体现不同的初始参考节点的对算法性能影响，每一次实验都随机选取初始参考点。

为研究不同DFS门限对Margin-Based算法性能的影响，我们分别取其门限为，0.55，0.65，0.75，0.85，0.95，1.05进行仿真实验。图6给出了Margin-Based和RobustMethod两种算法在不同探测包数(即第2节中的W)条件下的1000次仿真的平均树编辑距离，可见，随着节点对探测包个数的增加，数据集的方差逐步减小，两种算法的性能均有所提高；不同的比较门限对Margin-Based算法的影响较为明显，随着门限由小到大变化，Margin-Based算法的性能也是由差变好再变差，在门限取0.75时可达到最优的性能；而本文的RobustMethod的树编辑距离曲线与Margin-Based算法门限取0.75时近似，因此RobustMethod可以达到Margin-Based算法的最优性能。

4结束语

本文提出一种基于有限混合模型的稳健高效层析成像网络拓扑推断算法，较文献[8]中提出的高效拓扑推断算法，该算法需要测量更少的叶子节点相关性数据，其应用有限混合模型实现对节点的自适应分类，无需设定比较门限，具有更好的稳健性。但由于该算法应用了有限混合模型，在一定程度上增加了算法的运算复杂度，因此今后的工作还需要进一步较少其运算量，以更好地满足对实时性要求。

作者：张润生刘健李艳斌单位：中国电子科技集团公司第五四研究所中国空间技术研究院通信卫星事业部