互聯(lián)網(wǎng)拓?fù)鋽?shù)據(jù)獲取方法研究綜述*

楊 慧 ， 李春林 ， 孫 治 ， 張志勇

（1.網(wǎng)絡(luò)空間安全四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；2.中國(guó)電科網(wǎng)絡(luò)空間安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；3.中國(guó)電子科技網(wǎng)絡(luò)信息安全有限公司，四川 成都 610041）

0 引 言

互聯(lián)網(wǎng)由大約50 000個(gè)自治域系統(tǒng)（Autonomous Systems，AS）或網(wǎng)絡(luò)組成，其中大多數(shù)網(wǎng)絡(luò)都由不同的組織擁有和管理，涵蓋不同的地理區(qū)域，用于不同的目的，并且由不同的物理基礎(chǔ)設(shè)施構(gòu)建而成。例如，這些自治系統(tǒng)網(wǎng)絡(luò)可以是網(wǎng)絡(luò)服務(wù)提供商、內(nèi)容提供商、內(nèi)容分發(fā)網(wǎng)絡(luò)、教育網(wǎng)絡(luò)等。這些構(gòu)建方式和目的的多樣性、大規(guī)模、分布式、異構(gòu)性等特征，使得測(cè)量互聯(lián)網(wǎng)的全球拓?fù)浣Y(jié)構(gòu)本質(zhì)上是困難且極具挑戰(zhàn)性的。目前沒(méi)有任何實(shí)體或組織具有整個(gè)互聯(lián)網(wǎng)或其單個(gè)組成或自治域的完整拓?fù)洚?huà)像（即“基本事實(shí)”）。此外，不存在其唯一目的是發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)涞膮f(xié)議或服務(wù)[1-2]。兩種最常用的拓?fù)浒l(fā)現(xiàn)技術(shù)，即traceroute和BGP（Border Gateway Protocol，邊界網(wǎng)關(guān)協(xié)議），它們最初設(shè)計(jì)用于完全不同的目的：由V. Jacobson引入的traceroute是一個(gè)網(wǎng)絡(luò)調(diào)試工具[3-4]；而B(niǎo)GP是當(dāng)今全球互聯(lián)網(wǎng)中事實(shí)上的標(biāo)準(zhǔn)域間路由協(xié)議[5]。盡管存在這些困難和挑戰(zhàn)，但對(duì)互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)的研究在過(guò)去15至20年間一直吸引著網(wǎng)絡(luò)和非網(wǎng)絡(luò)研究人員。非網(wǎng)絡(luò)研究人員將互聯(lián)網(wǎng)或其拓?fù)浣Y(jié)構(gòu)視為復(fù)雜和大規(guī)模技術(shù)網(wǎng)絡(luò)的主要案例，主要關(guān)注其結(jié)構(gòu)特征的研究和預(yù)測(cè)其行為；網(wǎng)絡(luò)研究社區(qū)的研究人員更加關(guān)注因特網(wǎng)的各種拓?fù)鋵傩匀绾斡绊懢W(wǎng)絡(luò)協(xié)議、網(wǎng)絡(luò)應(yīng)用和服務(wù)的性能。因此，更好地了解互聯(lián)網(wǎng)拓?fù)浼捌渲饕卣鲗⑹咕W(wǎng)絡(luò)研究人員能夠設(shè)計(jì)出更好的網(wǎng)絡(luò)協(xié)議或服務(wù)，并在更現(xiàn)實(shí)的條件下對(duì)其進(jìn)行評(píng)估。此外，準(zhǔn)確的互聯(lián)網(wǎng)地圖對(duì)于不斷嘗試改進(jìn)或優(yōu)化代理，副本服務(wù)器和數(shù)據(jù)中心等網(wǎng)絡(luò)資源分配的網(wǎng)絡(luò)工程師和運(yùn)營(yíng)商非常有幫助。同樣，擁有詳細(xì)而完整的互聯(lián)網(wǎng)拓?fù)鋱D可以為安全相關(guān)問(wèn)題研究提供支撐。

互聯(lián)網(wǎng)拓?fù)渫ǔＲ詧D的方式呈現(xiàn)，其中節(jié)點(diǎn)表示有意義的網(wǎng)絡(luò)實(shí)體，節(jié)點(diǎn)之間的連接表示實(shí)體之間的關(guān)系。在此基礎(chǔ)上，互聯(lián)網(wǎng)拓?fù)渲饕兴姆N不同的尺度或分辨率，從最精細(xì)到最粗略依次為IP（Internet Protocol，互聯(lián)網(wǎng)協(xié)議）接口級(jí)、路由器級(jí)、PoP（Point of Presence，接入點(diǎn)）級(jí)和AS級(jí)。鑒于此，本文將按劃分尺度的不同對(duì)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)的獲取和推斷方法進(jìn)行概述和展望。

1 IP接口級(jí)拓?fù)?/h2>

IP接口級(jí)拓?fù)渲泄?jié)點(diǎn)表示具有特定IP地址的網(wǎng)絡(luò)接口，接口屬于主機(jī)或路由器，節(jié)點(diǎn)和IP之間存在一對(duì)一的映射[6-7]。兩個(gè)節(jié)點(diǎn)之間的連接表示節(jié)點(diǎn)之間的直接網(wǎng)絡(luò)層連接，這種特性表明IP接口級(jí)拓?fù)浜雎粤硕咏粨Q機(jī)等網(wǎng)絡(luò)層之下的設(shè)備。因此，IP接口級(jí)拓?fù)渲械逆溌凡⒉豢偸屈c(diǎn)到點(diǎn)鏈路。

traceroute是目前應(yīng)用最廣泛的IP接口級(jí)拓?fù)錅y(cè)量工具，它最早由V. Jacobson于1987年研制出來(lái)。發(fā)起traceroute探測(cè)的源結(jié)點(diǎn)通過(guò)操控IP報(bào)文頭部的TTL值來(lái)觸發(fā)報(bào)文轉(zhuǎn)發(fā)路徑上的各個(gè)設(shè)備對(duì)自己進(jìn)行反饋，從而解析出到達(dá)目的結(jié)點(diǎn)的完整路由路徑。V. Jacobson開(kāi)發(fā)的traceroute基礎(chǔ)版本基于ICMP（Internet Control Message Protocol，因特網(wǎng)控制報(bào)文協(xié)議）協(xié)議，后來(lái)也陸續(xù)出現(xiàn)了基于UDP（User Datagram Protocol，用戶(hù)數(shù)據(jù)報(bào)協(xié)議）和TCP（Transmission Control Protocol，傳輸控制協(xié)議）協(xié)議的traceroute工具[8]，以便使探測(cè)報(bào)文能夠以更大概率穿越防火墻等報(bào)文過(guò)濾設(shè)施。M. Luckie等人通過(guò)實(shí)驗(yàn)對(duì)比了基于以上三種協(xié)議的traceroute工具解析路由路徑的能力，發(fā)現(xiàn)基于ICMP的traceroute探測(cè)報(bào)文到達(dá)探測(cè)目的的成功率最高，而基于UDP的traceroute工具雖然能夠發(fā)現(xiàn)更多IP鏈路，但探測(cè)報(bào)文到達(dá)探測(cè)目的的成功率最低[9]。隨著路由技術(shù)的發(fā)展，越來(lái)越多的路由器通過(guò)負(fù)載均衡技術(shù)提升網(wǎng)絡(luò)的路由中繼能力，導(dǎo)致網(wǎng)絡(luò)中的兩個(gè)IP接口之間同時(shí)使用多條路由路徑進(jìn)行通信。多徑路由場(chǎng)景下，傳統(tǒng)traceroute工具可能產(chǎn)生實(shí)際并不存在的虛假鏈路。針對(duì)基于流的多徑路由策略，B.Augustin等人設(shè)計(jì)了Paris traceroute[4]，為同一次探測(cè)的探測(cè)報(bào)文分配相同的流標(biāo)識(shí)，能夠有效解決這一問(wèn)題。但對(duì)于基于報(bào)文的多徑路由場(chǎng)景，該問(wèn)題依然沒(méi)有較好解決方案。

每一次完整的traceroute探測(cè)可以解析出探測(cè)源到目的結(jié)點(diǎn)的一條路由路徑，為了獲得整個(gè)網(wǎng)絡(luò)的完整拓?fù)?，需要從多個(gè)探測(cè)源向一系列目的結(jié)點(diǎn)發(fā)起traceroute探測(cè)，然后將獲得的多條路徑進(jìn)行融合。顯然，探測(cè)源集合和目的結(jié)點(diǎn)集合的選擇會(huì)直接影響最終網(wǎng)絡(luò)拓?fù)涞耐暾浴Ｃ鎸?duì)規(guī)模極其龐大的因特網(wǎng)，這項(xiàng)工作非常具有挑戰(zhàn)性，人們?yōu)榇搜芯坎渴鹆硕鄠€(gè)大規(guī)模探測(cè)系統(tǒng)。這些探測(cè)系統(tǒng)在全球各地?fù)碛袛?shù)量不等的探測(cè)源結(jié)點(diǎn)，有的依賴(lài)于專(zhuān)屬的測(cè)量設(shè)備[10-11]，有的則是借助諸如PlanetLab的通用測(cè)量平臺(tái)資源[7，12-13]。早期研究表明，通過(guò)增加探測(cè)源的方式并不能持續(xù)有效地增強(qiáng)探測(cè)系統(tǒng)提高所得網(wǎng)絡(luò)拓?fù)渫暾缘哪芰14]，因此CAIDA的拓?fù)涮綔y(cè)系統(tǒng)重點(diǎn)關(guān)注合理選擇探測(cè)目標(biāo)結(jié)點(diǎn)，僅使用較少數(shù)量的探測(cè)源[10-11]。然而近期研究卻指出，通過(guò)合理增加探測(cè)源能夠保證獲得更完整的網(wǎng)絡(luò)拓?fù)?，新發(fā)現(xiàn)了大量IXP（Internet eXchange Point，互聯(lián)網(wǎng)交換中心）對(duì)等鏈路[15]。R. Beverly等人提出通過(guò)加大測(cè)量周期及探測(cè)次數(shù)，在較長(zhǎng)時(shí)間里進(jìn)行多次測(cè)量獲得更完整的網(wǎng)絡(luò)拓?fù)洌瑫r(shí)獲得其動(dòng)態(tài)變化特征[16]。但是該方法面臨著數(shù)據(jù)一致性的問(wèn)題：如果曾經(jīng)發(fā)現(xiàn)的鏈路在后續(xù)測(cè)量階段再也不曾出現(xiàn)，那么該鏈路是否依然存在。

traceroute采用基于不同協(xié)議的探測(cè)包克服防火墻過(guò)濾等問(wèn)題，但依然存在其他不足，如：中間路由器可能采用多種策略決定應(yīng)答探測(cè)報(bào)文的具體IP接口，甚至使用錯(cuò)誤的IP地址或者不作任何應(yīng)答（匿名路由器）。為了克服這些問(wèn)題，研究人員從其他角度設(shè)計(jì)了一些新的探測(cè)方法，作為traceroute的補(bǔ)充。E. Katz-Bassett等人綜合利用IP報(bào)頭的“路由記錄”選項(xiàng)字段，源路由和源地址偽裝技術(shù)，研制出反向traceroute工具，在探測(cè)源與探測(cè)目標(biāo)間的正反向路徑不對(duì)稱(chēng)的情況下獲得反向路徑[17]。M. E. Tozal等人基于同一個(gè)子網(wǎng)中的IP地址結(jié)構(gòu)特征，提出一系列子網(wǎng)推斷準(zhǔn)則，發(fā)現(xiàn)探測(cè)源到探測(cè)目標(biāo)的路徑經(jīng)過(guò)的子網(wǎng)，相較于traceroute只能發(fā)現(xiàn)部分IP接口，顯著提升了拓?fù)浒l(fā)現(xiàn)能力[18-19]。

2 路由器級(jí)拓?fù)?/h2>

路由器級(jí)別的拓?fù)渫ǔＪ菍?duì)屬于同一路由器的接口進(jìn)行分組的結(jié)果，實(shí)現(xiàn)這個(gè)目標(biāo)的技術(shù)則被稱(chēng)作別名解析[12]。路由器級(jí)拓?fù)渲械母鱾€(gè)結(jié)點(diǎn)或?qū)?yīng)具有單個(gè)網(wǎng)絡(luò)接口的端主機(jī)，或?qū)?yīng)具有多個(gè)網(wǎng)絡(luò)接口的路由器，連接則反映了兩個(gè)結(jié)點(diǎn)之間存在的網(wǎng)絡(luò)層鏈接。

Pansiot等人提出了一種針對(duì)目標(biāo)IP的不可到達(dá)端口進(jìn)行探測(cè)的別名解析方法：為了識(shí)別某個(gè)IP地址A的別名，探測(cè)源向A的某個(gè)未使用端口發(fā)送一個(gè)TCP或者UDP探測(cè)包，A所在的路由器可能會(huì)選擇一個(gè)不同于A的IP接口B向探測(cè)源反饋端口不可達(dá)報(bào)文，探測(cè)源收到響應(yīng)報(bào)文后即可發(fā)現(xiàn)A、B屬于同一個(gè)路由器[20]。該方法雖然不會(huì)引入假陽(yáng)性錯(cuò)誤，但是目標(biāo)路由器并不總是采用另一個(gè)IP地址作為響應(yīng)報(bào)文的源IP，甚至?xí)苯雍雎远丝诓豢蛇_(dá)的探測(cè)報(bào)文，因此它通常只能發(fā)現(xiàn)一小部分IP別名。

IP報(bào)文頭部的ID字段被用于幫助網(wǎng)絡(luò)通信的接收方進(jìn)行報(bào)文重組。對(duì)于某些路由器，不管它發(fā)出的IP報(bào)文具體經(jīng)由該路由器的哪個(gè)接口發(fā)出，所有報(bào)文共享同一個(gè)ID計(jì)數(shù)器。因此，這類(lèi)路由器連續(xù)發(fā)出的IP報(bào)文具有逐一遞增的ID。基于這一現(xiàn)象，N. Spring等人在Rocketfuel項(xiàng)目中提出了Ally算法進(jìn)行別名解析[12]。Ally分別向兩個(gè)可能的別名IP地址的未使用端口發(fā)送UDP探測(cè)包，探測(cè)包對(duì)應(yīng)的ICMP端口不可到達(dá)響應(yīng)被分別封裝在兩個(gè)IP數(shù)據(jù)包中，記其ID分別為x、y。探測(cè)源收到所有響應(yīng)報(bào)文后向先到達(dá)的響應(yīng)報(bào)文對(duì)應(yīng)的IP發(fā)送第三個(gè)探測(cè)包，記這個(gè)探測(cè)包的響應(yīng)報(bào)文ID為z，如果x＜y＜z成立而且z-x小于某個(gè)門(mén)限，那么被測(cè)量的兩個(gè)IP被判定為別名。以下情況都可能導(dǎo)致Ally會(huì)產(chǎn)生假陰性錯(cuò)誤（False Negative）：路由器配置了較大的ID遞增步長(zhǎng)，或者各個(gè)接口使用獨(dú)立的計(jì)數(shù)器[21]；甚至探測(cè)包或者響應(yīng)報(bào)文在傳輸過(guò)程中遭受時(shí)延抖動(dòng)。此外，Ally每次僅對(duì)兩個(gè)IP地址進(jìn)行探測(cè)和解析，工作效率較低，難以推廣到大規(guī)模網(wǎng)絡(luò)中：對(duì)于n個(gè)目標(biāo)IP地址，它的探測(cè)復(fù)雜度為O(n2)。A. Bender等人提出的RadarGun對(duì)目標(biāo)IP地址進(jìn)行多次探測(cè)，通過(guò)對(duì)比各個(gè)IP地址的ID增長(zhǎng)速率來(lái)識(shí)別別名地址，能夠有效解決該問(wèn)題，其探測(cè)復(fù)雜度為僅O(n)[22]。K. Keys等人綜合Ally和RadarGun的優(yōu)勢(shì)，采用滑動(dòng)時(shí)窗的思想解決探測(cè)復(fù)雜度高的問(wèn)題，所提出的方法能夠?qū)嶋H應(yīng)用于當(dāng)前互聯(lián)網(wǎng)，同時(shí)兼顧了解析結(jié)果的準(zhǔn)確性[23]。

traceroute測(cè)量得到的IP接口級(jí)拓?fù)渥陨硪舶藙e名解析所需的相關(guān)信息。首先，在相同traceroute路徑中出現(xiàn)的IP不可能互為別名，這是因?yàn)檎Ｇ闆r下數(shù)據(jù)報(bào)文在網(wǎng)絡(luò)中傳輸時(shí)，不會(huì)多次經(jīng)過(guò)同一個(gè)路由器，形成路由回路。其次，如果分屬兩條路徑的兩個(gè)IP地址A和B的下一跳同為一個(gè)IP地址C，那么A和B很有可能屬于同一個(gè)路由器。基于以上現(xiàn)象，N. Spring等人提出啟發(fā)式方法進(jìn)行別名解析[24]。該方法的缺點(diǎn)在第二個(gè)啟發(fā)式規(guī)則假設(shè)IP地址C所在鏈路為點(diǎn)對(duì)點(diǎn)型鏈路，否則會(huì)產(chǎn)生假陽(yáng)性錯(cuò)誤。M. H. Gunes等人提出的AAR[25]一定程度上克服了以上不足，他們首先根據(jù)一系列規(guī)則推測(cè)traceroute數(shù)據(jù)中所有IP可能所在的子網(wǎng)，然后將各條traceroute路徑按照子網(wǎng)對(duì)齊，解析IP別名，該方法可被視作N. Spring等人工作的一般化。M. H. Gunes等人在AAR的基礎(chǔ)上提出改進(jìn)方案APAR[26]，通過(guò)對(duì)AAR的分析結(jié)果進(jìn)行探測(cè)驗(yàn)證，能夠進(jìn)一步提高AAR的準(zhǔn)確性。

此外，網(wǎng)絡(luò)中的路由器開(kāi)啟了對(duì)某些查詢(xún)報(bào)文的響應(yīng)功能?；谠摋l件，簡(jiǎn)單網(wǎng)絡(luò)測(cè)量協(xié)議（Simple Network Measurement Protocol，SNMP） 和 因 特 網(wǎng)組管理協(xié)議（Internet Group Management Protocol，IGMP）可分別用于在本地局域網(wǎng)和因特網(wǎng)中發(fā)現(xiàn)路由器結(jié)點(diǎn)[27]。

3 PoP級(jí)拓?fù)?/h2>

PoP是屬于同一AS的路由器集中區(qū)[28]。因?yàn)锳S通常會(huì)以分層方式構(gòu)建其物理網(wǎng)絡(luò)，AS中的PoP互連形成AS的“骨干”，并且由PoP對(duì)其客戶(hù)或終端用戶(hù)提供訪問(wèn)能力。目前學(xué)術(shù)界和工業(yè)界對(duì)于PoP的定義尚無(wú)嚴(yán)格統(tǒng)一的定義：互聯(lián)網(wǎng)服務(wù)提供商們認(rèn)為他們用來(lái)部署路由器結(jié)點(diǎn)的某棟建筑，或者能夠享用其服務(wù)的用戶(hù)所在的某個(gè)城市地區(qū)都可算作是一個(gè)PoP結(jié)點(diǎn)；學(xué)術(shù)界則通常將屬于某個(gè)相同AS并為其用戶(hù)和其他PoP提供連接的路由器集群定義為一個(gè)PoP結(jié)點(diǎn)。但沒(méi)有疑問(wèn)的是，結(jié)點(diǎn)的地理位置屬性在PoP級(jí)拓?fù)渲杏葹橹匾oP級(jí)拓?fù)渲械拿總€(gè)結(jié)點(diǎn)通常用該AS的AS號(hào)和該P(yáng)oP的地理位置進(jìn)行標(biāo)識(shí)。若某兩個(gè)PoP屬于相同AS，那么它們之間的鏈路被稱(chēng)作骨干鏈路；否則，稱(chēng)這兩個(gè)PoP之間的鏈路為對(duì)等鏈路。因此，節(jié)點(diǎn)表示屬于AS的PoP，連接表示兩個(gè)PoP的路由器之間存在的物理連接。

同路由器級(jí)拓?fù)漕?lèi)似，現(xiàn)有研究中最普遍的PoP級(jí)拓?fù)錅y(cè)量技術(shù)也是通過(guò)對(duì)更小尺度的IP接口級(jí)拓?fù)?、路由器?jí)拓?fù)溥M(jìn)行結(jié)點(diǎn)聚合，從而得到PoP級(jí)拓?fù)?。其中，N. Spring等人研制的Rocketfuel系統(tǒng)是此類(lèi)工作的先驅(qū)[12]。他們首先采用別名解析算法Ally從traceroute數(shù)據(jù)中識(shí)別出別名IP，然后根據(jù)一系列DNS（Domain Name System，域名系統(tǒng)）命名規(guī)則推測(cè)IP地址的地理位置，最后將位于相同地理位置的IP集合聚合為PoP結(jié)點(diǎn)，從而得到PoP級(jí)拓?fù)?。H. V. Madhyastha等人對(duì)Rocketfuel進(jìn)行了多方位的改進(jìn)[7]：綜合多個(gè)別名解析算法[25，29]提升IP別名識(shí)別的精度，并克服了DNS命名規(guī)則解析的某些缺陷[30]。Tian等人用IP地理位置數(shù)據(jù)庫(kù)替代由DNS信息推測(cè)得到的地理信息[13]，并采用啟發(fā)式方法根據(jù)地理位置信息將IP地址聚類(lèi)為PoP結(jié)點(diǎn)。

PoP級(jí)拓?fù)浞从沉烁鱾€(gè)AS在部署自己的網(wǎng)絡(luò)基礎(chǔ)設(shè)施時(shí)為了達(dá)到可擴(kuò)展性和可維護(hù)性而形成的層次化結(jié)構(gòu)。網(wǎng)絡(luò)管理者通常參考設(shè)備制造商建議的某些固定模式設(shè)計(jì)PoP架構(gòu)，從而保障PoP的服務(wù)性能，提供更好的連接服務(wù)[31-32]。因此，互聯(lián)網(wǎng)絡(luò)中各個(gè)AS的大多PoP都具有相似的內(nèi)部結(jié)構(gòu)?；诖?，F(xiàn)eldman和Y. Shavitt等人針對(duì)時(shí)延信息進(jìn)行分析，在IP接口級(jí)拓?fù)渲邪l(fā)現(xiàn)此類(lèi)重復(fù)模式，識(shí)別PoP結(jié)點(diǎn)[33-34]。

4 AS級(jí)拓?fù)?/h2>

AS級(jí)拓?fù)渲械拿總€(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)其中設(shè)備采用相同路由策略的自治系統(tǒng)，并用唯一標(biāo)識(shí)AS號(hào)進(jìn)行區(qū)分。連接表示兩個(gè)AS之間的商業(yè)業(yè)務(wù)關(guān)系，這些關(guān)系反映了AS之間交換流量時(shí)誰(shuí)向誰(shuí)付費(fèi)，因此這些連接本質(zhì)上是虛擬的而不是物理的，它是一個(gè)抽象，通常代表兩個(gè)AS之間的多個(gè)物理連接[35]。它們之間的連接類(lèi)型可能是Customer-Provider，Peer-Peer和 Sibling-Sibling。AS連 接 對(duì)應(yīng)的物理實(shí)體通常是兩個(gè)AS的PoP之間的多條物理鏈路。

AS級(jí)拓?fù)涞脑紨?shù)據(jù)主要來(lái)自三個(gè)方面：BGP路由信息、traceroute測(cè)量數(shù)據(jù)、互聯(lián)網(wǎng)路由注冊(cè)信息（Information Resource，IRR）。其中，BGP協(xié)議的設(shè)計(jì)初衷就是為了確定數(shù)據(jù)報(bào)文在AS間，因而B(niǎo)GP路由信息中包含大量AS級(jí)的拓?fù)湫畔?。利用BGP信息獲取AS級(jí)拓?fù)涞墓ぷ髦?，?dāng)屬B. Zhang[36]和P. Mahadevan[37]等人的工作最具代表性。他們通過(guò)在網(wǎng)絡(luò)中部署一系列BGP收集器，采用被動(dòng)測(cè)量的方式獲得網(wǎng)絡(luò)中路由器間交互的BGP信息。Z. M. Mao[38]和R. Bush[5]等人部署的探測(cè)結(jié)點(diǎn)則能夠主動(dòng)向其他路由器廣播BGP路由，根據(jù)對(duì)方的響應(yīng)解析可用信息。

將traceroute測(cè)量得到的IP接口級(jí)拓?fù)渲懈鱾€(gè)IP地址映射到它所屬的AS，如果某條路徑上的兩個(gè)連續(xù)IP分屬不同AS，那么對(duì)應(yīng)的兩個(gè)AS之間存在鏈路，從而根據(jù)traceroute數(shù)據(jù)得到AS級(jí)拓?fù)?。為達(dá)成這一目的，Z. M. Mao等人研究了如何利用BGP路由表和IRR信息簡(jiǎn)歷IP地址到AS的映射[39]。這個(gè)方法的優(yōu)勢(shì)在于能夠獲得更詳細(xì)的AS級(jí)拓?fù)洌喝绻麅蓚€(gè)AS通過(guò)多條不同鏈路連接，這些鏈路在traceroute數(shù)據(jù)顯然能被區(qū)分，因而最后的AS級(jí)拓?fù)淙钥杀Ａ暨@些鏈路的信息。

此外，IRR提供的一系列查詢(xún)數(shù)據(jù)庫(kù)RADb（Routing Assets Database）收錄了當(dāng)前互聯(lián)網(wǎng)的基礎(chǔ)路由信息。全世界已有上千個(gè)機(jī)構(gòu)組織將自己名下的網(wǎng)絡(luò)路由信息發(fā)布到這些數(shù)據(jù)庫(kù)中[40]。經(jīng)過(guò)IRR獲取AS級(jí)拓?fù)湫畔⑹趾?jiǎn)單快捷，無(wú)需再執(zhí)行探測(cè)操作，因而能夠有效避免各類(lèi)探測(cè)方法的缺點(diǎn)。然而，RADb收錄的數(shù)據(jù)由多個(gè)貢獻(xiàn)者自愿提供，因而其可用數(shù)據(jù)的完整性和一致性可能存在問(wèn)題[41]。

5 局限及問(wèn)題

目前針對(duì)不同尺度的網(wǎng)絡(luò)拓?fù)涠即嬖谙鄳?yīng)的測(cè)量或推斷方法，但均存在某些問(wèn)題或局限。traceroute或BGP都不是專(zhuān)門(mén)設(shè)計(jì)用來(lái)測(cè)量網(wǎng)絡(luò)拓?fù)涞姆椒?，由此得出的互?lián)網(wǎng)拓?fù)鋽?shù)據(jù)質(zhì)量和完整性都很難評(píng)估。

traceroute主要用于網(wǎng)絡(luò)故障排除，它被設(shè)計(jì)為通用的可達(dá)性診斷工具，使用它來(lái)發(fā)現(xiàn)互聯(lián)網(wǎng)的接口級(jí)拓?fù)浣Y(jié)構(gòu)是后來(lái)想到的，也是一個(gè)不完美的探索性步驟[42]。第一，路由器對(duì)TTL零探測(cè)的響應(yīng)沒(méi)有唯一的設(shè)置。網(wǎng)絡(luò)運(yùn)營(yíng)商通常選擇以下五種策略之一：不響應(yīng)、使用探測(cè)接口的IP地址響應(yīng)、使用接收探測(cè)消息的接口IP地址響應(yīng)、使用固定接口IP地址響應(yīng)、和使用隨機(jī)IP地址響應(yīng)。除了路由器配置設(shè)置，防火墻也可以配置為防止被探測(cè)的路由器響應(yīng)。第二，traceroute在每一跳上記錄的IP地址不一定是有效的IP地址，這可能是由于向路由器接口錯(cuò)誤分配IP地址的做法導(dǎo)致的。第三，每一跳報(bào)告的RTT值不能用于準(zhǔn)確測(cè)量往返目標(biāo)的延遲。traceroute是一個(gè)前言路由診斷工具，Internet路由中的經(jīng)驗(yàn)法則是兩個(gè)IP之間的路由并不總是對(duì)稱(chēng)的。因此，traceroute探測(cè)所采用的路徑可能與其響應(yīng)所采用的路徑不同。事實(shí)上，兩個(gè)連續(xù)跳之間的延遲變化可能是由于鏈路擁塞，路由器隊(duì)列中的可變延遲或不對(duì)稱(chēng)路由造成的。第四，二層云通常對(duì)于traceroute是不透明的，這些云的明確目的是對(duì)IP層隱藏網(wǎng)絡(luò)基礎(chǔ)設(shè)施。

對(duì)于AS級(jí)拓?fù)涠裕褂肂GP推斷AS級(jí)拓?fù)溆幸恍﹥?yōu)點(diǎn)，如與互聯(lián)網(wǎng)注冊(cè)管理機(jī)構(gòu)相比，從BGP收集的數(shù)據(jù)顯示了實(shí)際的可達(dá)性，數(shù)據(jù)通常不會(huì)陳舊過(guò)時(shí)或不正確，BGP更新可以用于研究互聯(lián)網(wǎng)路由動(dòng)態(tài)行為等。但用BGP推斷AS拓?fù)湟泊嬖谝恍┤毕荩饕蚴荁GP僅僅是一種信息隱藏協(xié)議，僅表明可達(dá)性，而不是連通性。AS路徑通告主要用于環(huán)路檢測(cè)。而且，AS可能會(huì)宣布與真實(shí)路徑不相符的AS路徑[43]。此外，BGP不會(huì)通告每個(gè)可用路徑的信息，僅通告最佳路徑，所以備份路徑可能永遠(yuǎn)不會(huì)出現(xiàn)在BGP轉(zhuǎn)儲(chǔ)中。由于路由收集器通常部署在較大的ISP（Internet Service Provider，互聯(lián)網(wǎng)服務(wù)提供商）中，并且大部分位于美國(guó)和歐洲，因此觀察到的AS級(jí)拓?fù)浣Y(jié)構(gòu)偏向于對(duì)這些區(qū)域更加完整。即使路由收集器隨機(jī)放置在不同的AS中，發(fā)現(xiàn)AS關(guān)系的可能性也與使用該鏈路的AS的數(shù)量成正比[5，44]。

由于現(xiàn)有方法存在以上局限，學(xué)者們提倡為特定級(jí)別的互聯(lián)網(wǎng)拓?fù)浒l(fā)現(xiàn)設(shè)計(jì)新的測(cè)量技術(shù)，使研究人員能夠測(cè)量他們想要測(cè)量的東西，而不僅僅是他們可以測(cè)量的東西。

6 結(jié) 語(yǔ)

互聯(lián)網(wǎng)拓?fù)溲芯繉?duì)于網(wǎng)絡(luò)服務(wù)性能分析和優(yōu)化、網(wǎng)絡(luò)安全等具有重要的意義，而此類(lèi)研究依賴(lài)于互聯(lián)網(wǎng)拓?fù)鋽?shù)據(jù)獲取。因大規(guī)模、分布式、異構(gòu)性等特征，使得互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)的獲取本質(zhì)上是極具挑戰(zhàn)性的。本文對(duì)當(dāng)前不同尺度上的互聯(lián)網(wǎng)拓?fù)鋽?shù)據(jù)的獲取方法進(jìn)行了詳細(xì)的綜述，分析了現(xiàn)存方法中普遍存在的局限性?；ヂ?lián)網(wǎng)拓?fù)鋽?shù)據(jù)獲取急需新的思想和更優(yōu)的解決方法，以突破瓶頸，以更好地為網(wǎng)絡(luò)優(yōu)化、網(wǎng)絡(luò)安全服務(wù)。