双参数网络拓扑论文范文

1结合双参数测量方法

针对上述方法存在的不足，本文在其基础之上提出一种结合双参数测量方法，使得新方法受网络负载的影响较小，且推断准确度较上述方法有所提高．主要分为2个阶段测量：第一阶段测量各个叶子节点的高度，用以将逻辑拓扑构造为实际的物理网络拓扑；第二阶段测量节点对之间的性能参数值（丢包率和时延抖动），并根据公式计算节点间相关性值，推测网络的拓扑结构．

1.1测量网络节点的高度发送多组短数据包序列到网络中的各个边缘节点，短数据包的携带信息包括其发送序号、递增的TTL值等，发送时刻的TTL值也是短数据包在分组序列中的序号．原理是：短分组每次到达一个节点，TTL值减1，当TTL值为0时，将此分组丢弃；当有数据包到达目的叶子节点时，停止发送数据包，统计到达的数据包的序号；将此过程执行多次，在最终统计的多个结果中筛选最优值，此最优值即为叶子节点在网络树中所处的高度．某一组短数据包序列如图3所示

1.2节点相关性计算改进的三元分组序列测量的性能参数包括时延抖动和丢包率，将时延抖动和丢包率按比例结合，即可作为节点间的相关性．上述计算相关性的方式，在丢包较严重时主要依据为丢包率，而在丢包较轻时，主要依据为时延抖动，达到在任何负载情况下都能准确表征节点之间的相关性．

1.3网络拓扑推断算法算法的思路：按节点的层次信息将叶节点进行聚类，并依据双参数结合得到的相关性值逐层向上推断网络的拓扑树．推断算法：Step4：将Step3中构造的各个子树整合到一起，构成一棵整体拓扑树，即为推断的网络拓扑．下面以具有普遍代表意义的4层树状拓扑为例，来进行拓扑推断，原始实验拓扑如图4所示．1）按节点层次将节点分类．2）将每层中的节点按照兄弟关系进行分类组合，按兄弟关系初步构造子树结构，如图5所示．3）比较最下2层的节点间的相关性大小，并构造拓扑树的下两层子树，如图6所示．4）按Step2的规则，在相邻两层节点小集合中选择具有代表性的节点进行相关性比较，并按规则1～规则3构造子树，并将有重节点的子树合并，得到合并后的子树结构，如图7所示．5）将Step3中得到的子树进行整合，最终推测出网络的整体拓扑，如图8所示．

2仿真实验及性能分析

2.1仿真实验基于NT技术的网络拓扑推断是根据在边缘节点收集到的信息，推断中间节点的连接情况．以图4为例，在NS2［9］环境下进行了多个仿真实验，实验中采用树状拓扑结构．背景流量以TCP为主同时包含适当的UDP，采用发送时间受控的可变速率CBR数据包用来模拟网络负载情况．假定网络内部节点采用随机检测（RED）丢包策略，与叶节点相连的链路带宽均为500kbit／s，时延为10ms；其他链路带宽为1Mbit／s，时延为15ms；内部节点缓冲区大小为20．三元分组列车内两个短分组之间的时间间隔为10ms，每轮发送的三元分组列车序列由50个三元分组组成，在不同的网络负载情况下，进行多轮测量．根据样本丢包率的取值区间［0，0．01］，［0．01，0．1］，［0．1，0．2］将网络负载分为较轻、适中和较重3种情况．采用了树编辑距离［10］作为评价推断拓扑的有效性参数，其代表了推断树与原拓扑树之间转换的最小开销．用横坐标表示探测包的发送轮数，纵坐标表示树编辑距离，在3种情况下分别将单参数算法与综合双参数的算法进行比较，按照加载的负载为较轻、适中和较重3种情况仿真后的结果分别如图9、图10、图11所示．图9～图11为仿真试验中使用不同推断算法获得网络逻辑拓扑时，树编辑距离收敛的结果．图9是网络负载较轻的情况下，两种算法的比较，图中显示，负载较轻情况下单参数测量与双参数测量的效果近似相同，当探测包的发送轮数大于80（即探测包个数为400）时，树编辑距离的收敛速度均趋于稳定．图10显示网络负载适中情况下，2种算法的推测的有效性，显然，双参数的推测效果优于单参数，但此时基于单参数的推测算法还是有效的．图11为网络负载较严重的情况下，2种算法的效果比较，此时，可以看出，单参数方法的推测准确度明显降低，而双参数方法的收敛受到网络负载的影响并不很明显．显然综合参数的算法，在任意负载情况下均具有有效性，故其准确度和有效性均优于单参数的算法．

2.2性能分析对于图4所示拓扑，按照一般的拓扑推断方法，要发送的探测包的叶节点对数量将是C215＝105对，而使用本文提出的方法，叶节点对的个数是45对，探测包的发送量减少了57％．但此方法对于探测包的发送量与拓扑结构关系较大，若目标网络的拓扑是满二叉树，且所有节点均在最下层，则目标节点对个数为n（n－1）2对；最好情况下仅需（n－1）对目标地址对即可完成网络拓扑的推断，如除了最下层，每层仅有一个叶节点的二叉树．总体而言，网络结构层次越复杂，越能突出此算法的优势．但此方法的推断准确度不受目标网络拓扑结构的影响，任何形式的拓扑均能由此方法推出，且准确度高于一般的推断方法，可通过仿真实验证明．

3结束语

本文提出的推断方法适用于任意规模、任意负载情况的网络拓扑推断，且在目标网络拓扑较复杂时，能在很大程度上减少探测包的发送量，减轻了额外往网络中注入的流量．但是在探测包的缩减方面还有待提升，还未将算法的应用推广到网状拓扑的推断中．

作者：吴辰文孔德弟谢云燕单位：兰州交通大学电子与信息工程学院