网络层析成像技术在网络拓扑推断中的应用

《网络层析成像技术在网络拓扑推断中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、网络层析成像技术在网络拓扑推断中的应用赵洪华，陈鸣，仇小锋（解放军理工大学指挥自动化学院南京210007）摘要网络层析成像是根据端到端的测量，通过反演推断获取网络的内部特性。层析成像技术不需要网络内部节点的合作，只需要选择一组接收节点即可完成对网络内部特性的推断，利用网络层析成像技术可以解决网络内部节点不合作的问题。本文讨论了网络层析成像在网络拓扑推断中的测量方法和推断方法，对比了当前的测量方法和推断方法。根据当前的研究讨论了网络层析成像在拓扑推断中的技术难点和下一步研究方向。关键词　网络层析成像；“邻接”分组对；“三明治”分组列车；DBT随着互联网规模的飞

2、速发展，网络结构也在发生着巨大的变化，互联网已经成为人们日常生活不可缺少的一部分，为了更好地使用、管理和控制网络，必须要对网络的拓扑结构有充分的了解。当前有多种网络拓扑推断的方法，基于SNMP的方法[1,2]、基于Traceroute的方法[3~6]和基于BGP路由表[7]的方法，这些方法都需要网络内部节点的合作，而在实际的网络中并不能满足要求，例如通过Traceroute获得的路由中，大约有1/3的路由存在不响应的内部节点[8]。网络层析成像（networktomography）[9~11]基于端到端的技术来获取网络内部的特性，而不需要网络内部节点的合作。

3、网络层析成像首先在网络中设置接收节点，然后向接收节点发送大量的探测包，根据接收节点收到测量数据包的情况分析网络的内部特性。网络层析成像技术的研究分为3个方面：网络拓扑推断，即根据网络性能参数推断网络的拓扑结构，是文中讨论的重点；网络链路级参数推断[12~16]通过接收节点的网络特性分析网络链路级的特性，包括时延分布、丢包率和带宽等参数估计；网络端到端(original-destination)流量估计[17~20]是网络链路级参数推理的反过程，目的是利用链路级的测量数据推断网络端到端的流量。网络层析成像应用在网络拓扑推断中主要分为两个步骤：通过端到端的测量获

4、得端到端的性能参数矩阵；根据端到端的性能参数矩阵推断网络的拓扑结构。1　网络层析成像中的测量方法分析网络中节点的共享链路越多，节点的特性越相近。网络层析成像技术通过端到端的测量获得不同节点的端到端的特性矩阵，这些特性包括丢包率、时延及时延差等。网络层析成像中的测量分为组播网络测量和单播网络测量。在组播网络中网络特性矩阵的测量比较简单，通过在测量源节点向接收节点发送大量的测量数据，在接收节点观察接收到测量分组的情况得出网络的特性矩阵[21,22]。在单播网络中推断网络拓扑同样需要获得网络性能矩阵，单播网络中要获得不同节点之间的相关性比组播网络复杂很多，当前比较

5、常用的有两种方式：“邻接”分组对[22~24]和“三明治”分组列车[11,25]。·“邻接”分组对。“邻接”分组对由两个相同大小的分组组成，分组之间具有较小的时间间隔。两个分组从测量源点出发，目的节点为两个不同的接收节点。在“邻接”分组对中认为两个分组经过相同的链路时具有相同的排队时延。通过“邻接”分组对可以获得不同节点对的性能相关情况，“邻接”分组对测量的性能参数包括丢包率和时延。图1为采用“邻接”分组对的测量。·“三明治”分组列车。“三明治”分组列车由3个数据分组组成，两个短的数据分组中间夹着一个长的数据分组，分组之间具有较小的时间间隔。两个短分组具有相

6、同的目的地址，长分组的目的地址和短分组不同。通过“三明治”分组列车可以获得接收节点对之间的排队时延。图2为采用“三明治”分组列车的测量。无论是在单播网络还是在组播网络，测量时都有两个假定条件：空间独立性，即测量数据包在不同链路上的时延是相互独立的；时间独立性和稳定性，即同一链路上不同测量数据包的时延是相互独立的。“三明治”分组列车在网络负载较小时，效果最优，因为排队时延主要由长数据分组产生，“邻接”分组对在网络适度负载时效果最优，因为网络中的流量能够产生较大的网络时延变化。在组播网络中，测量时发送的分组数量较少，假设需要m组测量数据，每组数据长度为Gbyte

7、，则测量中产生的流量为Flux：Flux=m×G(1)在单播网络的测量中首先要选择目标地址对，假设有N个目标节点，则目标地址对的数量为N×(N－1)，为O(N2)数量级，假设有m组测量数据，每组数据长度为Gbyte，则测量产生的流量Flux为：Flux=m×G×N×(N-1)(2)通过公式(1)和(2)可以发现，在单播网络中测量所发送的数据量要远远大于组播网络，组播网络的数据为常数级，而在单播网络中为O(mN2)级，所以单播网络中目标地址的选择非常重要。2　网络层析成像中的拓扑推断算法分析网络层析成像技术可以用线性模型建模，见公式（3）。yt=AXt+ε（3

8、）其中yt为测量结果向量，A为路由矩阵，Xt为和时间