于永雷

【摘 要】網(wǎng)絡(luò)中路由器拓?fù)浒l(fā)現(xiàn)是研究網(wǎng)絡(luò)結(jié)構(gòu)和行為的重要基礎(chǔ)。路由器多址綜合問題是拓?fù)浒l(fā)現(xiàn)中的一個(gè)難題。在總結(jié)現(xiàn)有的路由器多址綜合解決方法后提出一種新的方法——鄰居-子網(wǎng)綜合法。與以往方法相比，該方法可信度提高、效率變快，效果更加明顯，較好地解決了路由器多址綜合問題。

【關(guān)鍵詞】拓?fù)浒l(fā)現(xiàn)；路由器多址綜合方法；鄰居-子網(wǎng)綜合方法

0.概述

通過對網(wǎng)絡(luò)拓?fù)涞姆治隹梢园l(fā)現(xiàn)網(wǎng)絡(luò)中存在的各種特性，例如魯棒性（robustness）、可靠性、安全性、傳輸效率等一些關(guān)系到網(wǎng)絡(luò)發(fā)展的重要方面，同時(shí)也是推動協(xié)議發(fā)展、網(wǎng)絡(luò)管理等的重要動力，例如在不影響現(xiàn)有網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)上提出新的網(wǎng)絡(luò)應(yīng)用。因此，網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)作為拓?fù)浞治龅幕A(chǔ)是非常重要的。

目前，有很多組織和學(xué)者致力于網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)和研究，主要有 CAIDA的Skitter工程、NLANR的AMP工程、PlanetLab的Scriptroute 探測基礎(chǔ)設(shè)施、Tel Aviv大學(xué)的DIMES工程等。這些項(xiàng)目和工程中探測網(wǎng)絡(luò)拓?fù)涞闹饕椒ㄊ鞘褂肨raceRoute對若干已知的目標(biāo) IP地址進(jìn)行探測。在這些項(xiàng)目中為了對整個(gè)Internet有比較全面的了解，通常在全世界范圍內(nèi)布置一些探測節(jié)點(diǎn)對整個(gè)Internet中的可達(dá)地址進(jìn)行探測，或者使用源選路由的TraceRoute對網(wǎng)絡(luò)進(jìn)行 探測。

TraceRoute也存在著各種問題，例如目標(biāo)地址集的選取問題、匿名路由器問題、路徑變化問題、路由器多址綜合問題。本文提出了一種新的路由器多址綜合問題的解決方 法——鄰居-子網(wǎng)綜合法，使多址綜合的可信度提高、效率變快、資源利用減少、效果更加明顯。

1.路由器多址綜合問題的一般解決方法

一個(gè)路由器一般有若干個(gè)接口，每個(gè)接口都有獨(dú)立的IP地址。TraceRoute過程中返回的ICMP響應(yīng)報(bào)文地址為探測報(bào)文經(jīng)過的接口地址而不是路由器本身的標(biāo)識地址。于是確定哪些地址是同臺路由器的地址便成了一個(gè)非常重要的問題，稱為路由器多址綜合（IP Alias Resolution）問題或路由器別名綜合問題。這個(gè)問題直接關(guān)系到所得拓?fù)涞臏?zhǔn)確性和完整性。目前主要的解決方法有對路由器的UDP高端口探測、反向DNS查詢、IP報(bào)文ID值判定、雙向TraceRoute子網(wǎng)綜合等。

1.1 DNS反向查詢

DNS 反向查詢是指在 DNS 服務(wù)器上查詢到 IP 地址對應(yīng)的域名（DNS Name）。一個(gè)路由器包括若干個(gè)接口，每個(gè)接口都有各自的IP地址。不同的接口地址可能對應(yīng)不同的域名，但如果在域名命名時(shí)采取系統(tǒng)化方法，那么通過分析域名就可以確定這些IP地址是否屬于同一個(gè)路由器。一個(gè)路由器的多個(gè)接口地址也可能對應(yīng)同一個(gè)域名，此時(shí)域名相同的IP地址都屬于同一個(gè)路由器。還可以在獲取路由器一個(gè)接口IP地址的域名后，對其進(jìn)行DNS查詢來獲取該路由器的其他接口地址。

DNS反向查詢所得結(jié)果可信度高，是一種很有效的方法。但是當(dāng)一些路由器并沒有分配域名，或者沒有按照系統(tǒng)化結(jié)構(gòu)化的方法分配域名時(shí)，DNS反向查詢法就失效。

1.2 UDP高端口探測

UDP高端口探測是指對路由器某個(gè)接口IP地址發(fā)送UDP高端口（應(yīng)為不可用端口）探測報(bào)文，此時(shí)路由器返回的ICMP報(bào)文中的源地址為路由器的標(biāo)識地址（一般為路由器接口地址中的最小值或最大值）。因此，在對不同 IP地址進(jìn)行UDP高端口探測時(shí)，如果返回的 ICMP報(bào)文源地址相同，那么這些 IP地址就屬于同一個(gè)路由器。在對接口IF1和 IF2的地址進(jìn)行UDP高端口探測時(shí)，RouterA會回送一個(gè)端口不可達(dá)的ICMP報(bào)文（ICMP1，ICMP2），這些 ICMP 報(bào)文中源地址都為 RouterA的標(biāo)識地址（設(shè)為 IF0）。由此可知，IF1和 IF2這2個(gè)接口地址屬于同一個(gè)路由器。

一些路由器對UDP高端口探測報(bào)文并不處理，所以，探測源接收不到ICMP報(bào)文。還有一些路由器對返回的ICMP報(bào)文的地址配置為其出口或者入口地址，而不是路由器標(biāo)識地址。此時(shí)該方法失效。

1.3 IP報(bào)文ID值判定 根據(jù)IP報(bào)文中的ID屬性（identity）判定多個(gè)IP地址是否屬于同一個(gè)路由器

一般情況下，路由器發(fā)送IP報(bào)文的ID值是遞增的。

有些路由器發(fā)送的IP報(bào)文中的ID值是隨機(jī)的，而且可能因網(wǎng)絡(luò)延時(shí)，2個(gè)刺激報(bào)文到RouterA的時(shí)間間隔較大，這時(shí)返回的IP報(bào)文的ID值差別也比較大。 此時(shí)該方法失效。

2.鄰居-子網(wǎng)綜合法

各種多址綜合問題解決方法都存在這樣或那樣的問題，下面提出一個(gè)解決路由器多址綜合問題的更好方法——鄰居-子網(wǎng)綜合法。按TraceRotue方向，鄰居-子網(wǎng)綜合法將獲得3條路徑：…->IP0->IP1->IP2->…，…->IP0->IP1->IP3-> … 和 …->IP0->IP1->IP4->…。從這 3 條路徑中可以看出，IP1分別與下一跳IP2，IP3和IP4相鄰，那么擁有 IP1 的路由器必定還有另外 3個(gè)接口分別與IP2，IP3和IP4相連，假設(shè)它們的接口地址分別為 IP2， IP3和 IP4。IP2/IP2， IP3/IP3和 IP4/IP4這6個(gè)接口的3對地址分別屬于同一個(gè)網(wǎng)段，ISP為了節(jié)省地址空間，這些網(wǎng)段一般使用31或30位子網(wǎng)掩碼。

為了得出 IP2的具體地址，首先計(jì)算出與 IP2處于同一個(gè)/31網(wǎng)段中的另一個(gè)地址，并使用UDP高端口探測或IP報(bào)文 ID 值判斷法判斷這個(gè)地址與 IP1是否屬于同一個(gè)路由器。如果是則結(jié)束，如果不是則對/30段中另外2個(gè)地址進(jìn)行判斷。如果是則結(jié)束，如果依然不是，則放棄對IP2的綜合。依次對IP1所有對應(yīng)鄰居進(jìn)行以上操作。

至此只完成了對該路由器的第1次綜合，還必須對IP2和其他由以上方法得出的該路由器的接口再次進(jìn)行上述操作。如此循環(huán)，直到把所有發(fā)現(xiàn)的該路由器的接口地址全部綜合后，才完成對該路由器的多址綜合。

3.實(shí)驗(yàn)效果

為了檢驗(yàn)本方法的實(shí)用性，對某 AS 的所有地址段進(jìn)行TraceRoute，并對其中的路由器地址（570 個(gè)）分別使用 DNS反向查詢、UDP高端口探測、鄰居-子網(wǎng)綜合法進(jìn)行多址綜合，可以發(fā)現(xiàn)，鄰居-子網(wǎng)綜合法的別名率遠(yuǎn)遠(yuǎn)高于其他方法，雖然回包率比反向 DNS 查詢法低，但是綜合率遠(yuǎn)遠(yuǎn)低于其他3種方法，說明鄰居-子網(wǎng)綜合法相對其他方法更加有效。

4.結(jié)束語

目標(biāo)網(wǎng)絡(luò)探測中路由器多址綜合問題是一個(gè)非常重要的問題。本文針對這個(gè)問題提出了鄰居-子網(wǎng)綜合法，相對其他方法實(shí)現(xiàn)更加簡單，多址綜合結(jié)果更加準(zhǔn)確、完整、覆蓋范圍更廣。

以后的工作除了對路由器多址綜合問題繼續(xù)深入研究外，還要針對目標(biāo)地址集的選取問題、匿名路由器問題、路徑變化問題等在路由器級拓?fù)浒l(fā)現(xiàn)過程中的難題進(jìn)行研究，進(jìn)一步加強(qiáng)路由器級拓?fù)浒l(fā)現(xiàn)的準(zhǔn)確性、完整性和有效性。 [科]