于永雷

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

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

0.概述

通過(guò)對(duì)網(wǎng)絡(luò)拓?fù)涞姆治隹梢园l(fā)現(xiàn)網(wǎng)絡(luò)中存在的各種特性，例如魯棒性（robustness）、可靠性、安全性、傳輸效率等一些關(guān)系到網(wǎng)絡(luò)發(fā)展的重要方面，同時(shí)也是推動(dòng)協(xié)議發(fā)展、網(wǎng)絡(luò)管理等的重要?jiǎng)恿Γ缭诓挥绊懍F(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 探測(cè)基礎(chǔ)設(shè)施、Tel Aviv大學(xué)的DIMES工程等。這些項(xiàng)目和工程中探測(cè)網(wǎng)絡(luò)拓?fù)涞闹饕椒ㄊ鞘褂肨raceRoute對(duì)若干已知的目標(biāo) IP地址進(jìn)行探測(cè)。在這些項(xiàng)目中為了對(duì)整個(gè)Internet有比較全面的了解，通常在全世界范圍內(nèi)布置一些探測(cè)節(jié)點(diǎn)對(duì)整個(gè)Internet中的可達(dá)地址進(jìn)行探測(cè)，或者使用源選路由的TraceRoute對(duì)網(wǎng)絡(luò)進(jìn)行 探測(cè)。

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

1.路由器多址綜合問(wèn)題的一般解決方法

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

1.1 DNS反向查詢

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

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

1.2 UDP高端口探測(cè)

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

一些路由器對(duì)UDP高端口探測(cè)報(bào)文并不處理，所以，探測(cè)源接收不到ICMP報(bào)文。還有一些路由器對(duì)返回的ICMP報(bào)文的地址配置為其出口或者入口地址，而不是路由器標(biāo)識(shí)地址。此時(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)綜合法

各種多址綜合問(wèn)題解決方法都存在這樣或那樣的問(wèn)題，下面提出一個(gè)解決路由器多址綜合問(wèn)題的更好方法——鄰居-子網(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對(duì)地址分別屬于同一個(gè)網(wǎng)段，ISP為了節(jié)省地址空間，這些網(wǎng)段一般使用31或30位子網(wǎng)掩碼。

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

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

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

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

4.結(jié)束語(yǔ)

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

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