互联网中的“网络路径测量”

网络路径测量，利用多模式的网络路径联邦探测技术，实现准确、完整、高效的网络路径探测，大规模地采集重点方向国家（地区）IP的网络路径数据。

1、经典的网络路径探测技术

图 1 traceroute工作原理

经典网络路径探测技术的工作原理如图1所示，源主机向目标主机发送一组连续的、具有生存周期（TTL）的、不同类型（TCP、ICMP或UDP）的网络探测包。第一个网络探测包的TTL值为1，每经过一个路由器时，路由器会将TTL值减1，当TTL值减为0时，路由器返回一个ICMP超时消息（Time Exceeded）。下一个网络探测包的TTL加1并继续探测，直到达到目标主机，并返回主机不可达信息（Unreachable message）。这一系列消息可以逐步显示在源主机和目标主机之间的网络传输路径，完成主动网络路径探测。

图2 经典的网络路径探测技术存在的问题

随着网络规模的扩大，路由器中往往设置负载均衡，减少各个接口IP承担的负载压力。经典的网络路径探测技术没有考虑路由器的负载均衡情况，因此在探测过程中，会产生假边，造成路由器连接度数膨胀的问题。如图2所示，路由器L使用了负载均衡技术，源IP可以通过L-A-C-E和L-B-D-E这2条路径到达目标IP。经典的网络路径探测技术未考虑负载均衡的问题，连续两跳的网络探测包并不保证走同一条路径，因此有可能得到L-A-D-E这条虚假的网络路径。其中，A和D之间本来没有连接关系的两个路由器，但是经典的网络路径探测技术却认为A和D存在连接关系，增加了路由器A的连接度数，导致收集到的网络拓扑是错误的。

2、四种新型的、多模式的网络路径联邦探测技术

为了适应不同的探测目的和多样的探测节点性能，主动网络路径联邦探测模块使用了四种自主研发的、多模式的探测技术，分别是Accurate traceroute、Complete traceroute、Fast traceroute和FAC traceroute，从而实现网络路径探测的准确、完整、高效的需求。

与经典的网络路径探测技术相比，Accurate traceroute在探测过程中发送具有相同流标识的探测包，确保网络拓扑路径的正确性；Complete traceroute在每一跳使用含有不同流标识的包进行多次探测，穷举下一跳的所有接口IP，尽可能地发现从探测节点到目标IP之间的所有路径，确保网络拓扑路径的完整性。Fast traceroute利用网络路径类树形结构的特性，减少靠近探测源和目标IP的路由器接口探测量，提高了探测效率，确保网络路径收集的高效性。FAC traceroute结合Accurate traceroute、Complete traceroute和Fast traceroute各自的特点，不仅保证收集网络拓扑的正确性和完整性，还确保收集网络拓扑路径的高效性。

（1）模式一，Accurate traceroute探测技术

互联网中路由器的负载均衡有3种类型，分别是基于流的负载均衡（per-flow）、基于目标网络的负载均衡（per-destination）和基于数据包的负载均衡（per-packet）。

基于流的负载均衡将属于特定流的数据包转发到同一接口来工作，流标识由IP报文头部中的若干字段值组合形成，通常由源地址、源端口、目标地址、目标端口和协议5个字段值组合形成。基于目标网络的负载均衡与基于流的负载均衡类似，只是转发数据包时仅考虑目标地址，即将目标地址相同的数据包转发到同一接口。

基于数据包的负载均衡是最不常用的负载均衡方法，可以在多条链路上随意的连续发送数据包，而不用考虑主机或用户的具体情况。

基于数据包的负载均衡采用轮转机制来确定每个数据包走哪条路径到达目的地址。

Accurate traceroute技术对发往同一个目标IP的一系列探测数据包保持流标识不变，从而很好的解决了由per-flow和per-destination类型的负载均衡器带来的假连接和环路等问题。与经典网络路径探测技术相比，Accurate traceroute的发包量相同，但能够确保获取到的网络拓扑路径是正确的。

（2）模式二，Complete traceroute探测技术

主动网络路径联邦探测模块中的Complete traceroute探测技术，能够在置信度分别为95％和99％时，得到完整的路由器级别网络拓扑信息，大大提升网络拓扑测量的完整性。

置信度是指发送k个探测包时，发现n个下一跳节点的概率, 计算公式见公式 1。公式1用整体概率1减去包含发现1个接口、发现2个接口和发现n-1个接口的概率，最后得到最少能够发现n个接口的概率。

以发送8个包并发现2个接口为例说明公式1的含义，当有2个接口时，发送8个包，公式1的值为99.22%，即（1 -*)8*2-1-1），也就是说发送8个包并发现2个接口的概率是99.22%。

公式的含义是整体概率1减去发送8个包仅发现1个接口的概率；而8个包仅发现1个接口的概率是从2个接口中任选一个接口，并且8个包都从该接口通过，即*)8。表6是置信度分别为95和99%时，接口数与发包数的对应关系。

Complete traceroute包含以下三个步骤：

• 步骤一，使用不同的流标识，进行多次探测，穷举获取与当前跳连接的所有下一跳路由器接口IP；
• 步骤二，发送k个额外的具有相同流标识的探测数据包以判断该路由器是per-flow类型还是per-packet类型的负载均衡器，若这些探测数据包沿相同的路径转发，则该路由器是per-flow类型负载均衡的路由器；否则，该路由器是per-packet类型负载均衡的路由器。
• 步骤三，在置信度95%或者99%下，在探测节点到目标IP的探测过程中迭代执行步骤一和步骤二，通过穷举得出与当前跳连接的所有下一跳路由器接口IP，并判断出该节点是否存在负载均衡，输出从探测节点到目标IP的拓扑信息，完成探测节点到目标IP的探测。

​

图 3 Complete traceroute的发包数量

在置信度99%时，发送的探测数据包的累加数量如图3所示。即使 在第1跳和第2跳仅有一个接口IP的情况下，Complete traceroute探测技术在99%的信心度下仍然要发送8个包来确认没有其他的接口IP。如果中间路由器是负载均衡路由器，那么就需要更多的探测包，如图中的第三跳和第四跳。因此，与经典的网络路径探测技术相比，Complete traceroute探测技术所消耗的时间长、探测量大，对探测节点的网络带宽有更高要求。

Complete traceroute探测技术能够发现端到端路由中所有的路径，解决了网络拓扑测量中的不完整性和不准确性问题。同时，通过设定置信度，能够在置信度分别为95%和99%时得到网络拓扑的完整信息，大大提升了网络拓扑测量的完整性和准确性。

（3）模式三，Fast traceroute联邦探测技术

基于互联网树状模型的拓扑快速发现，Fast traceroute联邦探测技术使用全局停止集和本地停止集来记录曾经探测过的路由器接口IP。其中，全局停止集记录以目标IP为根的树中曾探测到的路由器接口IP，本地停止集记录以探测源为根的树中曾经探测到的路由器接口IP。Fast traceroute从指定的跳数h开始，以h+1，h+2的方向向前进行探测，直到遇到其它探测源曾探测到的接口IP停止；然后从指定的跳数h开始，以h-1，h-2的方向向后进行探测，直到遇到曾经探测到的接口IP停止。

Fast traceroute工作原理如图4所示，Fast traceroute有两棵树，一棵树是以探测源为根的树，另一颗树以目标IP为根的树。若探测源src2向目标dst进行探测时，遇到了探测源src1探测目标dst时的路由器A，那么就停止探测。这是因为路由器A与目标dst之间的路径已经由探测源src1探测目标dst时得到了。

图 4 Fast traceroute工作原理

与经典的网络路径探测技术相比，这种联邦探测技术在对靠近探测源和目标IP的路由器探测时，Fast traceroute发送的探测数据包数量很少，能够比经典网络路径探测技术更快速的进行探测，确保网络拓扑路径的高效收集效率。0

（4）模式四，FAC traceroute

主动网络路径联邦探测模块中的FAC traceroute处理流程包含四个步骤，如图5所示。

• 第一步，向指定的TTL开始进行探测，收到响应后，检索该接口IP是否在本地停止集中出现过。若没有出现过，则将该接口IP加入到本地停止集中，同时TTL减一向后进行探测直到探测节点。探测时发送含有相同流标识的数据包。若出现过，则跳转到第二步；
• 第二步，发送具有不同流标识的探测数据包，探索该跳是否有其它的接口IP。如果没有找到新的接口IP，则从该跳开始使用Complete  traceroute向前进行探测；若找到了新的接口IP，则跳转到第三步；
• 第三步，发送具有不同流标识的探测数据包向后进行探测，直到找到仅有一个接口IP的跳，然后从该跳开始使用Complete  traceroute进行探测；

 图 5 FAC traceroute的处理流程

第四步，使用Complete traceroute向前探测时，把探测的接口IP同时存储到本地停止集和全局停止集中。若探测到的接口IP在全局停止集中时或者达到目标IP时，则停止探测。

FAC traceroute同时具备了Complete traceroute和Fast traceroute的特性，既能够完整地、准确地获取网络拓扑，也能够高效地获取网络路径数据。