一種高效的末跳路由發(fā)現(xiàn)技術(shù)

劉 洋， 方濱興

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001)

0 引 言

末跳路由器是測量點(diǎn)到目標(biāo)IP地址的IP路徑上，與目標(biāo)IP直接相連的最后一跳路由器。高效末跳路由器發(fā)現(xiàn)技術(shù)，實(shí)現(xiàn)用盡可能少的探測包發(fā)現(xiàn)到目標(biāo)的末跳路由器。

高效末跳路由器發(fā)現(xiàn)包含了對網(wǎng)絡(luò)距離的快速獲取，可以為實(shí)現(xiàn)更高效的traceroute探測[1-3]提供依據(jù)。例如在已知到目標(biāo)的網(wǎng)絡(luò)距離D時(shí)，traceroute可以讓TTL從D開始反向測量，遇重復(fù)探測IP提前停止，這樣能顯著地降低測量冗余；或者一次性同時(shí)發(fā)送TTL從1到D的所有探測包，在不引入額外測量負(fù)載的同時(shí)，顯著減少測量時(shí)間(O(D^2)到O(D))。此外，因?yàn)榻K端IP的末跳路由器和目標(biāo)IP的拓?fù)溧徑裕瑒t有助于對二者進(jìn)行IP地理定位[4-5]。

獲取末跳路由器最樸素的辦法是進(jìn)行完整的traceroute測量，但是僅就發(fā)現(xiàn)末跳路由器這一目的來說，對中間路由的測量并無必要。如果已知到目標(biāo)的距離，發(fā)送一個(gè)探測包能夠獲取末跳路由器。文獻(xiàn)[6]中采用向目標(biāo)發(fā)送大端口偵測包的方法，根據(jù)回復(fù)的字段來推斷到目標(biāo)的距離。但是，考慮到往返路徑的不對稱性等原因，基于大端口偵測包的方法用于網(wǎng)絡(luò)距離預(yù)測可能存在偏差。此外，并不是所有終端都會對測量包給予回復(fù)，事實(shí)上，本文實(shí)驗(yàn)所用到的存活主機(jī)僅有20%左右的主機(jī)會做出應(yīng)答，這也為獲取所有末跳路由器帶來了困難。

針對上述問題，本文結(jié)合網(wǎng)絡(luò)距離預(yù)測和二分策略的traceroute技術(shù)，提出了更通用的高效末跳路由器發(fā)現(xiàn)方法。本文的安排如下：首先，研究了基于ICMP端口不可達(dá)報(bào)文的網(wǎng)絡(luò)距離估計(jì)方法的設(shè)計(jì)實(shí)現(xiàn)，討論了一種基于二分法的網(wǎng)絡(luò)距離及末跳路由獲取方法。然后給出實(shí)驗(yàn)結(jié)果與分析。最后，對本文的工作進(jìn)行總結(jié)與展望。

1 基于ICMP端口不可達(dá)報(bào)文的網(wǎng)絡(luò)距離計(jì)算

1.1 從ICMP端口不可達(dá)報(bào)文提取網(wǎng)絡(luò)距離

ICMP協(xié)議是互聯(lián)網(wǎng)中報(bào)文消息控制協(xié)議，通過調(diào)研發(fā)現(xiàn)，向目標(biāo)發(fā)送UDP大端口報(bào)文,目標(biāo)會返回端口不可達(dá)報(bào)文， ICMP端口不可達(dá)報(bào)文結(jié)構(gòu)如圖1所示。圖1中左側(cè)為ICMP報(bào)文的結(jié)構(gòu)，分別由IP頭、ICMP頭以及ICMP負(fù)載組成。其中，ICMP負(fù)載部分包含探測源發(fā)送給目標(biāo)的原始報(bào)文數(shù)據(jù)。從原始報(bào)文的IP頭部，就能夠提取到生存時(shí)間TTL，研究將這個(gè)TTL值定義為raw_ttl。探測源發(fā)送初始TTL值為init_ttl的UDP報(bào)文，該報(bào)文到達(dá)目標(biāo)時(shí)生存時(shí)間TTL值減小到raw_ttl。因此，init_ttl減去raw_ttl的值是中間路由器的數(shù)目，而路由器數(shù)目加1也就是源到目標(biāo)的網(wǎng)絡(luò)距離。至此，基于現(xiàn)有理論可知，一共發(fā)送2個(gè)探測包可獲取末跳路由器信息。

圖1 ICMP端口不可達(dá)報(bào)文結(jié)構(gòu)

1.2 末跳路由器發(fā)現(xiàn)設(shè)計(jì)與實(shí)現(xiàn)

為了捕獲目標(biāo)返回的ICMP消息和末跳路由器信息，需要2個(gè)監(jiān)聽器(Listener)分別監(jiān)聽ICMP端口不可達(dá)報(bào)文和ICMP生存時(shí)間超時(shí)報(bào)文。該方法的時(shí)序圖如圖2所示。

圖2 基于ICMP端口不可達(dá)獲取末跳路由器時(shí)序圖

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

具體設(shè)計(jì)流程可表述為：首先，UDP Sender構(gòu)造UDP大端口探測包發(fā)送給目標(biāo)主機(jī)，若目標(biāo)主機(jī)指定端口未開放，返回ICMP端口不可達(dá)報(bào)文，此報(bào)文的數(shù)據(jù)部分填充為原始UDP報(bào)文；當(dāng)本地ICMP端口不可達(dá)Listener捕獲到目標(biāo)主機(jī)返回的報(bào)文后，從報(bào)文的ICMP負(fù)載部分提取UDP大端口探測包中的生存時(shí)間raw_ttl，根據(jù)raw_ttl計(jì)算網(wǎng)絡(luò)距離；向目標(biāo)主機(jī)發(fā)送TTL為網(wǎng)絡(luò)距離減1的探測包，此探測包到達(dá)目標(biāo)主機(jī)的末跳路由器時(shí)TTL值剛好減為零，觸發(fā)末跳路由器返回生存時(shí)間超時(shí)報(bào)文，本地ICMP生存時(shí)間超時(shí)Listener會捕獲末跳路由器返回的報(bào)文，從報(bào)文中提取末跳路由器信息。

2 基于二分法的網(wǎng)絡(luò)距離估計(jì)

文中前一節(jié)提出基于ICMP端口不可達(dá)報(bào)文的末跳路由發(fā)現(xiàn)方法高效而穩(wěn)定，唯一的不足就是并非全部目標(biāo)主機(jī)會響應(yīng)UDP大端口報(bào)文。因此，需要尋找一種普適性的方法，這種方法既要發(fā)出盡可能少的探測包，又能夠獲取全部存活主機(jī)的末跳路由器。為此，本節(jié)提出基于二分法的網(wǎng)絡(luò)距離估計(jì)，相對于傳統(tǒng)traceroute來說有效減少發(fā)包數(shù)量。對此部分，本文將給出闡釋分述如下。

2.1 二分法判定網(wǎng)絡(luò)距離

Traceroute在收到目標(biāo)回復(fù)時(shí)停止探測，在此之前由于探測包設(shè)置的生存時(shí)間TTL小于網(wǎng)絡(luò)距離，導(dǎo)致中間路由器回復(fù)ICMP生存時(shí)間超時(shí)消息，包括末跳路由器。因此，研究中可以得出只要滿足2個(gè)條件，可以確定網(wǎng)絡(luò)距離為D，同時(shí)也獲取了末跳路由器。對這2個(gè)條件可做總體概述如下。

(1)向目標(biāo)發(fā)送初始TTL等于D的探測包，目標(biāo)主機(jī)返回響應(yīng)報(bào)文。

(2)向目標(biāo)發(fā)送初始TTL等于D減1的探測包，收到生存時(shí)間超時(shí)報(bào)文。

為了盡快滿足(1)、(2)兩個(gè)條件，探測包生存時(shí)間TTL不必設(shè)置成從1開始探測。如果發(fā)送方收到生存時(shí)間超時(shí)報(bào)文，說明此時(shí)探測包設(shè)置的TTL比較小，探測包還未到達(dá)目標(biāo)主機(jī)，TTL值就減為0，需要增大探測包的生存時(shí)間。如果發(fā)送方收到目標(biāo)主機(jī)返回的報(bào)文，說明探測包設(shè)置的TTL值不小于網(wǎng)絡(luò)距離D，此時(shí)減小下次發(fā)送探測包的生存時(shí)間。研究知道網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)距離一般不會超過30跳，發(fā)送方到目標(biāo)的網(wǎng)絡(luò)距離在1～30之間，因此可以用二分法逐漸快速逼近真實(shí)的網(wǎng)絡(luò)距離。事實(shí)上，此方法在獲知網(wǎng)絡(luò)距離的同時(shí)，已經(jīng)獲取了末跳路由器信息，因?yàn)?2)中的生存時(shí)間超時(shí)報(bào)文由末跳路由器返回。

2.2 基于二分法的網(wǎng)絡(luò)距離算法

二分法通過不斷縮小初始設(shè)置的TTL范圍直到確定真實(shí)的網(wǎng)絡(luò)距離。算法流程如圖3所示。算法設(shè)計(jì)流程可表述如下：對于給定的初始TTL范圍[1，30]，每次探測包的初始TTL取范圍的中間值mid_ttl；如果收到生存時(shí)間超時(shí)報(bào)文，記錄time_exceeded_flag為mid_ttl，TTL范圍應(yīng)取右半邊[mid_ttl，30]；如果收到目標(biāo)主機(jī)回復(fù)的報(bào)文，說明mid_ttl大于等于實(shí)際網(wǎng)絡(luò)距離，記錄echo_reply_flag=mid_ttl，范圍應(yīng)該取左半邊[1，mid_ttl]，以此類推，直到滿足公式(1)為止。該式可寫作如下數(shù)學(xué)形式：

echo_reply_flag=time_exceeded_flag+1.

(1)

圖3 二分法獲取末跳流程圖

算法設(shè)計(jì)步驟詳見如下：

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

Step2mid_ttl=(left_ttl+right_ttl)>>1;

Step3發(fā)送初始TTL=mid_ttl的探測包;

Step4若收到time to live exceeded回復(fù)，left_ttl=mid_ttl+1,time_exceeded_flag=mid_ttl;

Step5若收到目標(biāo)主機(jī)的回復(fù)，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返回網(wǎng)絡(luò)距離Distance。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 末跳路由器發(fā)現(xiàn)對比實(shí)驗(yàn)

實(shí)驗(yàn)選取10萬個(gè)目標(biāo)主機(jī)，分別使用ICMP端口不可達(dá)、二分法和傳統(tǒng)traceroute方式進(jìn)行末跳路由器獲取，分別對比其發(fā)包量以及末跳路由器獲取情況，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析。

實(shí)驗(yàn)結(jié)果如圖4所示。10萬個(gè)目標(biāo)主機(jī)中，發(fā)現(xiàn)71 000個(gè)存活主機(jī)。其中，traceroute獲取末跳路由器數(shù)目為48 602個(gè)，基于ICMP端口不可達(dá)方法獲取末跳路由器數(shù)目為9 811，二分法獲取末跳路由器數(shù)目為43 010個(gè)。相比于傳統(tǒng)方法，二分法獲取率下降了11%，基于ICMP端口不可達(dá)方法獲取率僅為traceroute的20%。

圖4 traceroute和二分法末跳路由器獲取量對比圖

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

在發(fā)包量方面，統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果顯示ICMP端口不可達(dá)方法發(fā)包量為19 622個(gè)，二分法發(fā)包總數(shù)為250 929，傳統(tǒng)traceroute發(fā)包總數(shù)為675 604。由于每種方法獲取的末跳路由器數(shù)目不一致，因此不能僅是對比其發(fā)包量一項(xiàng)，而應(yīng)考查平均發(fā)包量，即發(fā)包量總數(shù)除以獲取末跳路由器的數(shù)目就是平均發(fā)包量，測試對比結(jié)果如圖5所示。由圖5分析可知，ICMP端口不可達(dá)方法平均發(fā)包量為2，符合理論值。二分法平均發(fā)包為5.17個(gè)，這是由二分法區(qū)間[1，30]決定的，經(jīng)過5次二分可以將區(qū)間范圍縮小到1，因此5.17符合二分法理論發(fā)包值。而傳統(tǒng)traceroute是每次探測包ttl加1，對于目標(biāo)主機(jī)其發(fā)包量即為源到目標(biāo)的實(shí)際網(wǎng)絡(luò)距離值。13.9說明10萬個(gè)目標(biāo)主機(jī)中，源到目標(biāo)主機(jī)的平均網(wǎng)絡(luò)距離為13.9。二分法相對于傳統(tǒng)方法的發(fā)包率降低了63.02%，ICMP端口不可達(dá)方法降低了85%。

3.2 實(shí)驗(yàn)結(jié)果分析

針對traceroute獲取而二分法未獲取到目標(biāo)開展進(jìn)一步分析后發(fā)現(xiàn)，二分法需要每次取區(qū)間的中值作為本次探測包的生存時(shí)間TTL值，如果沒有收到對此探測包的回應(yīng)，就無法根據(jù)返回包的類型繼續(xù)縮小區(qū)間，二分法就無法進(jìn)行，導(dǎo)致無法獲取網(wǎng)絡(luò)距離，也就無法獲取末跳路由器。這是二分法的末跳路由器獲取率低于傳統(tǒng)方法的原因。分析上述問題可知，未收到回應(yīng)報(bào)文的原因往往是探測包設(shè)置的生存時(shí)間小于網(wǎng)絡(luò)距離，否則發(fā)送方會收到來自目標(biāo)的響應(yīng)報(bào)文。因此，將區(qū)間左側(cè)邊界增加1，重新進(jìn)行二分計(jì)算本次探測包設(shè)置的TTL值，以此類推。改進(jìn)后再經(jīng)實(shí)驗(yàn)測試發(fā)現(xiàn)改進(jìn)后二分法和traceroute相比末跳路由器發(fā)現(xiàn)率基本一致(見圖5)。

圖5 末跳路由器獲取平均發(fā)包量對比

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

根據(jù)實(shí)驗(yàn)結(jié)果，ICMP端口不可達(dá)方法末跳獲取率僅為20%左右，分析發(fā)現(xiàn)網(wǎng)絡(luò)中僅有20%左右的目標(biāo)對UDP大端口報(bào)文做出響應(yīng)，此方法不具有普適性。相反，二分法獲取網(wǎng)絡(luò)距離和末跳的本質(zhì)和traceroute一致，因此末跳路由獲取量大致相等。結(jié)合ICMP端口不可達(dá)方法發(fā)包少以及二分法末跳獲取率高且穩(wěn)定的特點(diǎn)，研究中將2種方法進(jìn)行整合。先對目標(biāo)使用ICMP端口不可達(dá)方法，對于未獲取的目標(biāo)再使用二分法進(jìn)行獲取，理論上整合后的方案平均發(fā)包量應(yīng)該介于2種方法之間。同樣選取10萬個(gè)目標(biāo)，對合并后的方案進(jìn)行末跳路由器獲取。統(tǒng)計(jì)合并后方案的末跳獲取量與traceroute相當(dāng)，但平均發(fā)包量為5.6，反而高于2種方法。

分析發(fā)現(xiàn)，由于ICMP端口不可達(dá)方法只對20%左右的目標(biāo)有效，但是也需要對每個(gè)目標(biāo)發(fā)送UDP大端口報(bào)文。由于這部分無效的發(fā)包，導(dǎo)致平均發(fā)包量不降反升。綜上論述可知，采用二分法進(jìn)行末跳路由器發(fā)現(xiàn)能夠發(fā)現(xiàn)較為完整的末跳路由器信息，若不考慮末跳路由器發(fā)現(xiàn)的完整性，使用ICMP端口不可達(dá)方法能夠顯著降低發(fā)包量。

4 結(jié)束語

本文提出了一種高效的末跳路由器探測方法。相比于traceroute發(fā)包量平均降低了60%，本文方法在最少時(shí)僅需要2個(gè)探測包即可獲取末跳路由器。末跳路由器發(fā)現(xiàn)只關(guān)注目標(biāo)主機(jī)的最后一跳信息，將其作為一項(xiàng)新型的拓?fù)潢P(guān)系數(shù)據(jù)，對網(wǎng)絡(luò)拓?fù)錅y量、IP地理位置定位具有一定的參考價(jià)值。在未來網(wǎng)絡(luò)測量的研究中，這種特殊的網(wǎng)絡(luò)拓?fù)湫畔t有著重要的應(yīng)用和研究價(jià)值。