一种高效的末跳路由发现技术

刘 洋， 方滨兴

(哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001)

0 引 言

末跳路由器是测量点到目标IP地址的IP路径上，与目标IP直接相连的最后一跳路由器。高效末跳路由器发现技术，实现用尽可能少的探测包发现到目标的末跳路由器。

高效末跳路由器发现包含了对网络距离的快速获取，可以为实现更高效的traceroute探测[1-3]提供依据。例如在已知到目标的网络距离D时，traceroute可以让TTL从D开始反向测量，遇重复探测IP提前停止，这样能显著地降低测量冗余；或者一次性同时发送TTL从1到D的所有探测包，在不引入额外测量负载的同时，显著减少测量时间(O(D^2)到O(D))。此外，因为终端IP的末跳路由器和目标IP的拓扑邻近性，则有助于对二者进行IP地理定位[4-5]。

获取末跳路由器最朴素的办法是进行完整的traceroute测量，但是仅就发现末跳路由器这一目的来说，对中间路由的测量并无必要。如果已知到目标的距离，发送一个探测包能够获取末跳路由器。文献[6]中采用向目标发送大端口侦测包的方法，根据回复的字段来推断到目标的距离。但是，考虑到往返路径的不对称性等原因，基于大端口侦测包的方法用于网络距离预测可能存在偏差。此外，并不是所有终端都会对测量包给予回复，事实上，本文实验所用到的存活主机仅有20%左右的主机会做出应答，这也为获取所有末跳路由器带来了困难。

针对上述问题，本文结合网络距离预测和二分策略的traceroute技术，提出了更通用的高效末跳路由器发现方法。本文的安排如下：首先，研究了基于ICMP端口不可达报文的网络距离估计方法的设计实现，讨论了一种基于二分法的网络距离及末跳路由获取方法。然后给出实验结果与分析。最后，对本文的工作进行总结与展望。

1 基于ICMP端口不可达报文的网络距离计算

1.1 从ICMP端口不可达报文提取网络距离

ICMP协议是互联网中报文消息控制协议，通过调研发现，向目标发送UDP大端口报文,目标会返回端口不可达报文， ICMP端口不可达报文结构如图1所示。图1中左侧为ICMP报文的结构，分别由IP头、ICMP头以及ICMP负载组成。其中，ICMP负载部分包含探测源发送给目标的原始报文数据。从原始报文的IP头部，就能够提取到生存时间TTL，研究将这个TTL值定义为raw_ttl。探测源发送初始TTL值为init_ttl的UDP报文，该报文到达目标时生存时间TTL值减小到raw_ttl。因此，init_ttl减去raw_ttl的值是中间路由器的数目，而路由器数目加1也就是源到目标的网络距离。至此，基于现有理论可知，一共发送2个探测包可获取末跳路由器信息。

图1 ICMP端口不可达报文结构

1.2 末跳路由器发现设计与实现

为了捕获目标返回的ICMP消息和末跳路由器信息，需要2个监听器(Listener)分别监听ICMP端口不可达报文和ICMP生存时间超时报文。该方法的时序图如图2所示。

图2 基于ICMP端口不可达获取末跳路由器时序图

Fig. 2 Obtaining the end-hop router timing diagram based on the ICMP port unreachable

具体设计流程可表述为：首先，UDP Sender构造UDP大端口探测包发送给目标主机，若目标主机指定端口未开放，返回ICMP端口不可达报文，此报文的数据部分填充为原始UDP报文；当本地ICMP端口不可达Listener捕获到目标主机返回的报文后，从报文的ICMP负载部分提取UDP大端口探测包中的生存时间raw_ttl，根据raw_ttl计算网络距离；向目标主机发送TTL为网络距离减1的探测包，此探测包到达目标主机的末跳路由器时TTL值刚好减为零，触发末跳路由器返回生存时间超时报文，本地ICMP生存时间超时Listener会捕获末跳路由器返回的报文，从报文中提取末跳路由器信息。

2 基于二分法的网络距离估计

文中前一节提出基于ICMP端口不可达报文的末跳路由发现方法高效而稳定，唯一的不足就是并非全部目标主机会响应UDP大端口报文。因此，需要寻找一种普适性的方法，这种方法既要发出尽可能少的探测包，又能够获取全部存活主机的末跳路由器。为此，本节提出基于二分法的网络距离估计，相对于传统traceroute来说有效减少发包数量。对此部分，本文将给出阐释分述如下。

2.1 二分法判定网络距离

Traceroute在收到目标回复时停止探测，在此之前由于探测包设置的生存时间TTL小于网络距离，导致中间路由器回复ICMP生存时间超时消息，包括末跳路由器。因此，研究中可以得出只要满足2个条件，可以确定网络距离为D，同时也获取了末跳路由器。对这2个条件可做总体概述如下。

(1)向目标发送初始TTL等于D的探测包，目标主机返回响应报文。

(2)向目标发送初始TTL等于D减1的探测包，收到生存时间超时报文。

为了尽快满足(1)、(2)两个条件，探测包生存时间TTL不必设置成从1开始探测。如果发送方收到生存时间超时报文，说明此时探测包设置的TTL比较小，探测包还未到达目标主机，TTL值就减为0，需要增大探测包的生存时间。如果发送方收到目标主机返回的报文，说明探测包设置的TTL值不小于网络距离D，此时减小下次发送探测包的生存时间。研究知道网络中任意2个节点的网络距离一般不会超过30跳，发送方到目标的网络距离在1～30之间，因此可以用二分法逐渐快速逼近真实的网络距离。事实上，此方法在获知网络距离的同时，已经获取了末跳路由器信息，因为(2)中的生存时间超时报文由末跳路由器返回。

2.2 基于二分法的网络距离算法

二分法通过不断缩小初始设置的TTL范围直到确定真实的网络距离。算法流程如图3所示。算法设计流程可表述如下：对于给定的初始TTL范围[1，30]，每次探测包的初始TTL取范围的中间值mid_ttl；如果收到生存时间超时报文，记录time_exceeded_flag为mid_ttl，TTL范围应取右半边[mid_ttl，30]；如果收到目标主机回复的报文，说明mid_ttl大于等于实际网络距离，记录echo_reply_flag=mid_ttl，范围应该取左半边[1，mid_ttl]，以此类推，直到满足公式(1)为止。该式可写作如下数学形式：

echo_reply_flag=time_exceeded_flag+1.

(1)

图3 二分法获取末跳流程图

算法设计步骤详见如下：

Step1初始化left_ttl=1,right_ttl=30,Distance=-1;

Step2mid_ttl=(left_ttl+right_ttl)>>1;

Step3发送初始TTL=mid_ttl的探测包;

Step4若收到time to live exceeded回复，left_ttl=mid_ttl+1,time_exceeded_flag=mid_ttl;

Step5若收到目标主机的回复，right_ttl=mid_ttl-1,echo_reply_flag=mid_ttl;

Step6如果echo_reply_flag等于time_exceeded_flag+1,Distance=echo_reply_flag, 跳到Step 7;否则跳到Step 2;

Step7返回网络距离Distance。

3 实验结果及分析

3.1 末跳路由器发现对比实验

实验选取10万个目标主机，分别使用ICMP端口不可达、二分法和传统traceroute方式进行末跳路由器获取，分别对比其发包量以及末跳路由器获取情况，并对实验结果进行分析。

实验结果如图4所示。10万个目标主机中，发现71 000个存活主机。其中，traceroute获取末跳路由器数目为48 602个，基于ICMP端口不可达方法获取末跳路由器数目为9 811，二分法获取末跳路由器数目为43 010个。相比于传统方法，二分法获取率下降了11%，基于ICMP端口不可达方法获取率仅为traceroute的20%。

图4 traceroute和二分法末跳路由器获取量对比图

Fig. 4 Comparison of traceroute and end-hop router acquisition

在发包量方面，统计实验结果显示ICMP端口不可达方法发包量为19 622个，二分法发包总数为250 929，传统traceroute发包总数为675 604。由于每种方法获取的末跳路由器数目不一致，因此不能仅是对比其发包量一项，而应考查平均发包量，即发包量总数除以获取末跳路由器的数目就是平均发包量，测试对比结果如图5所示。由图5分析可知，ICMP端口不可达方法平均发包量为2，符合理论值。二分法平均发包为5.17个，这是由二分法区间[1，30]决定的，经过5次二分可以将区间范围缩小到1，因此5.17符合二分法理论发包值。而传统traceroute是每次探测包ttl加1，对于目标主机其发包量即为源到目标的实际网络距离值。13.9说明10万个目标主机中，源到目标主机的平均网络距离为13.9。二分法相对于传统方法的发包率降低了63.02%，ICMP端口不可达方法降低了85%。

3.2 实验结果分析

针对traceroute获取而二分法未获取到目标开展进一步分析后发现，二分法需要每次取区间的中值作为本次探测包的生存时间TTL值，如果没有收到对此探测包的回应，就无法根据返回包的类型继续缩小区间，二分法就无法进行，导致无法获取网络距离，也就无法获取末跳路由器。这是二分法的末跳路由器获取率低于传统方法的原因。分析上述问题可知，未收到回应报文的原因往往是探测包设置的生存时间小于网络距离，否则发送方会收到来自目标的响应报文。因此，将区间左侧边界增加1，重新进行二分计算本次探测包设置的TTL值，以此类推。改进后再经实验测试发现改进后二分法和traceroute相比末跳路由器发现率基本一致(见图5)。

图5 末跳路由器获取平均发包量对比

Fig. 5 The end-hop router obtains the average amount of sent packets

根据实验结果，ICMP端口不可达方法末跳获取率仅为20%左右，分析发现网络中仅有20%左右的目标对UDP大端口报文做出响应，此方法不具有普适性。相反，二分法获取网络距离和末跳的本质和traceroute一致，因此末跳路由获取量大致相等。结合ICMP端口不可达方法发包少以及二分法末跳获取率高且稳定的特点，研究中将2种方法进行整合。先对目标使用ICMP端口不可达方法，对于未获取的目标再使用二分法进行获取，理论上整合后的方案平均发包量应该介于2种方法之间。同样选取10万个目标，对合并后的方案进行末跳路由器获取。统计合并后方案的末跳获取量与traceroute相当，但平均发包量为5.6，反而高于2种方法。

分析发现，由于ICMP端口不可达方法只对20%左右的目标有效，但是也需要对每个目标发送UDP大端口报文。由于这部分无效的发包，导致平均发包量不降反升。综上论述可知，采用二分法进行末跳路由器发现能够发现较为完整的末跳路由器信息，若不考虑末跳路由器发现的完整性，使用ICMP端口不可达方法能够显著降低发包量。

4 结束语

本文提出了一种高效的末跳路由器探测方法。相比于traceroute发包量平均降低了60%，本文方法在最少时仅需要2个探测包即可获取末跳路由器。末跳路由器发现只关注目标主机的最后一跳信息，将其作为一项新型的拓扑关系数据，对网络拓扑测量、IP地理位置定位具有一定的参考价值。在未来网络测量的研究中，这种特殊的网络拓扑信息则有着重要的应用和研究价值。