基于往返时延的网络拓扑推断

　　网络拓扑推断是网络层析成像技术[1～3](Net-work tomography)的最新应用之一,网络拓扑推断根据网络中节点性能特性的相关性来推断网络的拓扑结构。研究表明,网络中节点的共享链路越多,节点的性能特性越相近(即相关性越大)[4]。当前基于网络层析成像技术的拓扑推断都是采用网络的单向性能特性计算节点的相关性作为推断的依据,所采用的网络单向性能参数包括:单向时延、单向丢包率、单向排队时延等。采用网络的单向性能参数计算节点的相关性推断时的效果较好,但同时也受到很多限制,例如需要测量源节点和测量目标节点的配合,节点间的时钟同步等。

　　如果在推断中采用网络的往返性能则可以减少限制,并且仅需要一个测量源。本文提出了一种基于往返时延的拓扑推断算法,基于往返时延的拓扑推断不需要节点间的配合和时钟同步,与基于网络单向性能参数的拓扑推断相比更易于实施和部署,适用范围更广。

　　1　相关研究

　　基于网络层析成像的拓扑推断主要分为两个步骤:①通过端到端的测量获得测量源节点到测量目标节点的端到端性能参数,根据端到端性能参数计算出测量目标节点间的相关性值;②根据测量目标节点间的相关性值推断网络的拓扑结构。

　　在单播网络中需要通过特殊的方法获得测量源到测量目标节点的端到端性能,然后计算测量目标节点间的相关性值。当前比较常用的测量方法主要有:“邻接”分组对方法[5～7]和“三明治”分组列车方法[8]。2种方法的基本思想是相邻的分组在共享链路具有相同的网络特性,通过这2种方法,每次测量2个目标节点的性能,以获得2个节点间的相关性。通过“邻接”分组对方法测量节点的丢包率和端到端时延,根据丢包率和时延计算的相关性参数为成功

　　传输率和时延协方差,通过“三明治”分组列车可以测量的节点的性能参数是排队时延,排队时延可作为节点间的相关性参数。

　　当前比较常用的拓扑推断算法包括:DBT算法[7]、ALT算法[8]、MLT算法[9]和分层算法[10]等。DBT算法根据节点的相关性推断网络的拓扑结构,该算法采用自底向上的推断,推断的拓扑结构为二叉树形的网络拓扑结构;ALT算法在DBT算法的基础上进行了改进,在推断过程中加入了概率密度函数的概念,可以在局部范围内选择最优解,并

　　且推断的拓扑结构扩展为普通的结构;MLT算法是基于最大似然估计的全局搜索算法,该算法在所有可能的拓扑树集合中搜索最优的拓扑树,当节点数较多时计算量较大;分层算法是基于聚类的拓扑推断算法,该算法按节点的相关性进行聚类,直到生成一棵完整的树。