一種高效的末跳路由發現技術

劉 洋， 方濱興

(哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 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地理位置定位具有一定的參考價值。在未來網絡測量的研究中，這種特殊的網絡拓撲信息則有著重要的應用和研究價值。