互聯(lián)網(wǎng)拓?fù)錅y(cè)量技術(shù)與工程實(shí)踐

余卓勛，張 宇，賈召鵬，鄭 兒

(1.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150000；2.華北計(jì)算機(jī)系統(tǒng)工程研究所，北京 100083)

0 引言

網(wǎng)絡(luò)空間測(cè)繪對(duì)網(wǎng)絡(luò)空間中虛實(shí)組件、結(jié)構(gòu)關(guān)系和交互規(guī)律進(jìn)行測(cè)量與繪制，是站在更高層次上了解、控制、管理和建設(shè)網(wǎng)絡(luò)空間的基礎(chǔ)。對(duì)網(wǎng)絡(luò)空間中互聯(lián)網(wǎng)拓?fù)溥M(jìn)行測(cè)量是構(gòu)建網(wǎng)絡(luò)空間基礎(chǔ)設(shè)施“地圖”的主要方式之一，對(duì)一個(gè)地區(qū)的互聯(lián)網(wǎng)進(jìn)行拓?fù)錅y(cè)量可以為發(fā)現(xiàn)地區(qū)網(wǎng)絡(luò)基礎(chǔ)設(shè)施中脆弱環(huán)節(jié)和消除斷網(wǎng)風(fēng)險(xiǎn)提供重要依據(jù)。

互聯(lián)網(wǎng)拓?fù)涫侵富ヂ?lián)網(wǎng)中節(jié)點(diǎn)及其鏈接根據(jù)不同粒度分成接口級(jí)、路由器級(jí)、PoP(機(jī)房)級(jí)和自治域級(jí)等網(wǎng)絡(luò)拓?fù)鋵蛹?jí)[1]，各級(jí)拓?fù)涓拍钊绫?所示。盡管已經(jīng)存在的拓?fù)錅y(cè)量技術(shù)日趨成熟，然而基于基礎(chǔ)的Traceroute測(cè)量獲取地區(qū)級(jí)別互聯(lián)網(wǎng)拓?fù)淙源嬖诠こ躺系奶魬?zhàn)。首先，由于IP地址本身不帶有地理位置屬性，因此難以直接獲得地區(qū)內(nèi)互聯(lián)網(wǎng)完整IP地址范圍；其次，可用的測(cè)量點(diǎn)以及測(cè)量能力難以完整地發(fā)現(xiàn)給定地址范圍內(nèi)的互聯(lián)網(wǎng)拓?fù)?。針?duì)上述問(wèn)題，本文介紹一個(gè)互聯(lián)網(wǎng)拓?fù)錅y(cè)量工程實(shí)踐，概述當(dāng)前拓?fù)錅y(cè)量技術(shù)；介紹一個(gè)基于虛擬虛擬服務(wù)器的測(cè)量平臺(tái)——VTopo；分析了VTopo對(duì)區(qū)域互聯(lián)網(wǎng)拓?fù)錅y(cè)量的效率與完整性，并與CAIDA Ark測(cè)量項(xiàng)目進(jìn)行了比較。

表1 各層級(jí)網(wǎng)絡(luò)拓?fù)浜x

1 拓?fù)錅y(cè)量技術(shù)與平臺(tái)概述

經(jīng)過(guò)20多年的發(fā)展，互聯(lián)網(wǎng)拓?fù)錅y(cè)量研究和測(cè)量技術(shù)已逐漸成熟。按表1中各層次拓?fù)淞信e了主要的測(cè)量技術(shù)，如表2所示。它們?yōu)榇笠?guī)?；ヂ?lián)網(wǎng)拓?fù)錅y(cè)量提供了基礎(chǔ)性技術(shù)支撐?；ヂ?lián)網(wǎng)拓?fù)錅y(cè)量技術(shù)的本質(zhì)是對(duì)路由協(xié)議進(jìn)行測(cè)量，最主要的技術(shù)是Traceroute[2]。Traceroute是一種通過(guò)向目標(biāo)IP地址順序發(fā)送TTL遞增的探測(cè)包，利用中間路由器返回的TTL超時(shí)回復(fù)或目標(biāo)的回復(fù)來(lái)獲取測(cè)量點(diǎn)到目標(biāo)之間IP路徑的方法；路由器級(jí)、PoP級(jí)、自治域級(jí)等更高層次級(jí)別拓?fù)錅y(cè)量主要建立在接口級(jí)拓?fù)浠A(chǔ)上，對(duì)接口級(jí)拓?fù)涔?jié)點(diǎn)進(jìn)行聚合。

表2 網(wǎng)絡(luò)拓?fù)錅y(cè)量工具/技術(shù)列舉

表3枚舉了測(cè)量平臺(tái)的四種類型，并總結(jié)了其在目標(biāo)選擇自由度、地理位置分布、數(shù)量和可用性等方面的特點(diǎn)。其中，CAIDA Ark[16]平臺(tái)作為三方公開(kāi)數(shù)據(jù)平臺(tái)的代表，具有數(shù)量較多分布較廣的節(jié)點(diǎn)，周期性對(duì)整個(gè)Internet進(jìn)行大規(guī)模網(wǎng)絡(luò)拓?fù)涮綔y(cè)；本文采集該平臺(tái)的測(cè)量數(shù)據(jù)作為分析比較的基線，用來(lái)評(píng)估測(cè)量的完整性。這些平臺(tái)雖然各有優(yōu)勢(shì)，但都存在可用性差(第三方測(cè)量平臺(tái))或測(cè)量點(diǎn)數(shù)量不足(部署可控監(jiān)測(cè)點(diǎn))、部署不靈活等問(wèn)題。

虛擬專用服務(wù)器(Virtual Private Sever，VPS)服務(wù)的興起為搭建更健壯、更靈活的大規(guī)模拓?fù)錅y(cè)量平臺(tái)提供了新的契機(jī)。VPS不光具有可伸縮、易部署、易遷移、可用性強(qiáng)等IAAS(Infrastructure As A Service)的天然優(yōu)勢(shì)，還具有節(jié)點(diǎn)眾多，地理位置分布廣泛的特點(diǎn)。這些節(jié)點(diǎn)所在的數(shù)據(jù)中心因?yàn)闃I(yè)務(wù)的需要，通常部署在接入網(wǎng)絡(luò)的位置，在網(wǎng)絡(luò)拓?fù)渖吓c終端用戶比較鄰近；這些VPS測(cè)量節(jié)點(diǎn)與CAIDA位于教育研究網(wǎng)絡(luò)的測(cè)量節(jié)點(diǎn)和Looking Glass位于核心骨干網(wǎng)絡(luò)的測(cè)量節(jié)點(diǎn)形成互補(bǔ)，可以為網(wǎng)絡(luò)拓?fù)錅y(cè)量貢獻(xiàn)更多的完整性。

表3 網(wǎng)絡(luò)拓?fù)錅y(cè)量平臺(tái)及其特點(diǎn)

2 一個(gè)基于虛擬專用服務(wù)器的拓?fù)錅y(cè)量系統(tǒng)

測(cè)量平臺(tái)的系統(tǒng)架構(gòu)如圖1所示，包括目標(biāo)生成、測(cè)繪邏輯和VPS平臺(tái)三個(gè)部分；目標(biāo)生成部分以目標(biāo)地區(qū)的地區(qū)代碼作為輸入，從合并后的地理定位數(shù)據(jù)庫(kù)中提取出目標(biāo)地區(qū)的IP地址范圍；測(cè)量邏輯部分是拓?fù)錅y(cè)量的核心組件，負(fù)責(zé)測(cè)量任務(wù)的調(diào)度與控制，調(diào)度模塊將地區(qū)內(nèi)的測(cè)量目標(biāo)分配給最佳的測(cè)量節(jié)點(diǎn)，并通過(guò)分布式任務(wù)隊(duì)列將任務(wù)分發(fā)給VPS平臺(tái)的對(duì)應(yīng)監(jiān)測(cè)點(diǎn)；監(jiān)測(cè)點(diǎn)異步地執(zhí)行測(cè)量任務(wù)并實(shí)時(shí)回傳測(cè)量結(jié)果。此外，在進(jìn)行適應(yīng)性測(cè)量時(shí)，測(cè)繪邏輯模塊還會(huì)根據(jù)當(dāng)前測(cè)量點(diǎn)回傳的測(cè)量結(jié)果來(lái)進(jìn)一步指導(dǎo)測(cè)量任務(wù)的調(diào)度，原始任務(wù)調(diào)度-測(cè)量-測(cè)量結(jié)果指導(dǎo)調(diào)度修改-按照新的調(diào)度繼續(xù)測(cè)量，依此類推，形成閉環(huán)。還有，大規(guī)模拓?fù)錅y(cè)量中的路徑和時(shí)延信息也可以作為修正IP地理定位結(jié)果的信息來(lái)源，為下一輪的地區(qū)網(wǎng)絡(luò)拓?fù)錅y(cè)量提供更精確的IP地址范圍。

圖1 VTopo測(cè)量平臺(tái)的系統(tǒng)架構(gòu)

3 互聯(lián)網(wǎng)拓?fù)錅y(cè)量結(jié)果與分析

首先在選擇測(cè)量目標(biāo)時(shí)，從同時(shí)期(2019年3月4日)的BGP路由表和5個(gè)地理定位數(shù)據(jù)庫(kù)中，提取出該地區(qū)內(nèi)96萬(wàn)個(gè)可路由的IP前綴，并將其拆分成401萬(wàn)個(gè)粒度為“/24”的子網(wǎng)作為目標(biāo)前綴列表；然后，使用測(cè)量平臺(tái)的150個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)獨(dú)立測(cè)量目標(biāo)列表中401萬(wàn)個(gè)“/24”前綴，各節(jié)點(diǎn)使用互不相同的偏移選擇前綴中的IP地址；同時(shí)，為了不給目標(biāo)網(wǎng)絡(luò)帶來(lái)過(guò)高的網(wǎng)絡(luò)負(fù)載，限制最高發(fā)包速率pps(packet per second)為150。

測(cè)量按照上述調(diào)度方法進(jìn)行10天探測(cè)，共得到了16億2 641萬(wàn)條Traceroute數(shù)據(jù)。采集CAIDA Ark 60個(gè)測(cè)量節(jié)點(diǎn)3月同時(shí)期共20天的測(cè)量數(shù)據(jù)，共8億6 300萬(wàn)條Traceroute。對(duì)二者進(jìn)行了預(yù)處理，從IP路徑中提取出IP接口級(jí)別的拓?fù)鋱D，分別記作VTopo和CAIDA。為了評(píng)估拓?fù)浒l(fā)現(xiàn)的完整性，對(duì)發(fā)現(xiàn)的拓?fù)湟?guī)模進(jìn)行了計(jì)算，并與CAIDA Ark平臺(tái)同時(shí)期規(guī)模相近的數(shù)據(jù)集合進(jìn)行了重合關(guān)系比較；然后，為了評(píng)估測(cè)量效率，對(duì)發(fā)現(xiàn)拓?fù)湟?guī)模隨發(fā)起Traceroute測(cè)量的次數(shù)的變化率進(jìn)行了分析。

Traceroute數(shù)據(jù)可以看成IP路徑的集合P，由P產(chǎn)生拓?fù)鋱DG，此外根據(jù)是否有轉(zhuǎn)發(fā)行為，定義網(wǎng)絡(luò)拓?fù)鋱D中的路由器節(jié)點(diǎn)集合為R，這些概念的定義如下：

P={pi|pi=(h(i,1),…,hi,ki)}

G=G(V,E)

V={h|?i,j≤ki,h=hij}

E={(a,b)|?i,j≤ki,(a,b)=(hi,j,hi,j+1)}

R={h|?i,j

其中hij代表第i條IP路徑的第j跳IP地址(跳過(guò)匿名路由器，即在Traceroute中回復(fù)為“*”的跳，只在鏈接屬性中保留連續(xù)的匿名路由器跳數(shù))；G是以IP地址在網(wǎng)絡(luò)層的相鄰關(guān)系(一條IP路徑上相鄰兩跳IP地址)為邊，以所有在IP路徑中出現(xiàn)的IP地址為節(jié)點(diǎn)的拓?fù)鋱D；路由器節(jié)點(diǎn)集合是在IP路徑中的中間跳IP地址或者不是本次Traceroute測(cè)量目標(biāo)(ti)的末跳IP地址。

按照上述定義生成測(cè)量區(qū)域的網(wǎng)絡(luò)拓?fù)鋱DVTopo，并與CAIDA進(jìn)行對(duì)比分析，本文給出了如表4所示的拓?fù)湟?guī)模對(duì)比結(jié)果。對(duì)比的項(xiàng)目包括拓?fù)渲械墓?jié)點(diǎn)數(shù)、路由器節(jié)點(diǎn)數(shù)、鏈接數(shù)、路由器鏈接數(shù)4種。其中，節(jié)點(diǎn)數(shù)是節(jié)點(diǎn)集合的大小，路由器節(jié)點(diǎn)數(shù)是路由器節(jié)點(diǎn)集合R的大小，鏈接數(shù)是邊集E的大小，路由器鏈接數(shù)是端點(diǎn)都在R中的鏈接組成的集合的大小。

為了分析VTopo和CAIDA的重合關(guān)系，對(duì)于每一個(gè)比較項(xiàng)，表4列舉了VTopo和CAIDA的文氏圖中各個(gè)部分的元素?cái)?shù)目。其中，VTopo和CAIDA共同發(fā)現(xiàn)的部分是VTopo∩CAIDA；VTopo和CAIDA單獨(dú)發(fā)現(xiàn)的部分分別是VTopo-VTopo∩CAIDA和CAIDA-VTopo∩CAIDA。此外，為了評(píng)價(jià)VTopo平臺(tái)新發(fā)現(xiàn)拓?fù)涞哪芰Γ?還給出了VTopo新發(fā)現(xiàn)拓?fù)涞谋壤?，即VTopo單獨(dú)發(fā)現(xiàn)數(shù)/VTopo發(fā)現(xiàn)總數(shù)。觀察表4，可以得到如下發(fā)現(xiàn)：

表4 VTopo與CAIDA測(cè)量結(jié)果比較(單位：萬(wàn))

(1)新發(fā)現(xiàn)拓?fù)浔壤?，VTopo平臺(tái)新發(fā)現(xiàn)拓?fù)涞谋壤^高，尤其新發(fā)現(xiàn)終端的比例較高，說(shuō)明VTopo平臺(tái)的測(cè)量結(jié)果是對(duì)CAIDA平臺(tái)完整性上的較大補(bǔ)充。

(2)發(fā)現(xiàn)拓?fù)湟?guī)模上，VTopo發(fā)現(xiàn)拓?fù)涞囊?guī)模大于CAIDA同時(shí)期測(cè)量發(fā)現(xiàn)的拓?fù)湟?guī)模：發(fā)現(xiàn)的節(jié)點(diǎn)數(shù)、鏈接數(shù)都是CAIDA發(fā)現(xiàn)的近3倍。這說(shuō)明通過(guò)對(duì)特定地區(qū)目標(biāo)的針對(duì)性測(cè)量可以顯著地增加發(fā)現(xiàn)地區(qū)內(nèi)網(wǎng)絡(luò)拓?fù)涞耐暾浴?/p>

(3)發(fā)現(xiàn)路由器拓?fù)渖?，VTopo發(fā)現(xiàn)的路由器節(jié)點(diǎn)總數(shù)是CAIDA的2倍，但占總節(jié)點(diǎn)數(shù)量的比例小于CAIDA。這說(shuō)明了VTopo能貢獻(xiàn)更多處在網(wǎng)絡(luò)拓?fù)浜诵牟糠值耐暾?，隨著發(fā)現(xiàn)拓?fù)湟?guī)模的不斷增加發(fā)現(xiàn)新路由器節(jié)點(diǎn)的效率會(huì)有所下降。

為了評(píng)價(jià)VTopo測(cè)量發(fā)現(xiàn)拓?fù)涞男?，?duì)發(fā)現(xiàn)拓?fù)涞囊?guī)模隨Traceroute測(cè)量次數(shù)的增長(zhǎng)情況作了統(tǒng)計(jì)，如圖2所示。

圖2 VTopo測(cè)量發(fā)現(xiàn)率

在圖2(a)，2(b)中分別給出了在進(jìn)行前5億7 000 萬(wàn)次Traceroute時(shí)，拓?fù)渲行掳l(fā)現(xiàn)節(jié)點(diǎn)和新發(fā)現(xiàn)鏈接的增長(zhǎng)情況，圖中數(shù)據(jù)點(diǎn)在橫坐標(biāo)以10萬(wàn)次Traceroute測(cè)量為間隔進(jìn)行采樣。圖中的直線是對(duì)數(shù)據(jù)點(diǎn)線性回歸分析后得到的線性模型的預(yù)測(cè)直線，圖2(a)和圖2(b)中線性回歸的r2分?jǐn)?shù)分別為0.994和0.996，呈現(xiàn)較強(qiáng)的線性性，預(yù)測(cè)直線的斜率分別為0.30和0.34，這說(shuō)明平均一次Traceroute測(cè)量?jī)H能發(fā)現(xiàn)不足一個(gè)新的IP級(jí)節(jié)點(diǎn)和鏈接，這說(shuō)明實(shí)驗(yàn)中的Traceroute測(cè)量存在較高的冗余。

導(dǎo)致高冗余的原因可能是每個(gè)測(cè)量點(diǎn)都獨(dú)立測(cè)量所有401萬(wàn)個(gè)“/24”網(wǎng)段，而且測(cè)量順序不是亂序，使得許多屬于同一較大網(wǎng)段的IP地址被連續(xù)測(cè)量多次，增加了測(cè)量失敗的幾率，即很多測(cè)量都只測(cè)到同一路由器就遇到gap停止測(cè)量了；導(dǎo)致線性的原因是Traceroute每次測(cè)量目標(biāo)IP地址都不同，并且測(cè)量完整性尚未達(dá)到最高值，所以盡管測(cè)量冗余較高，但新發(fā)現(xiàn)的拓?fù)湫畔⒖偰芤暂^低的速率線性增長(zhǎng)。

4 結(jié)論

本文介紹了互聯(lián)網(wǎng)拓?fù)錅y(cè)量技術(shù)，實(shí)現(xiàn)了一個(gè)基于VPS的拓?fù)錅y(cè)量平臺(tái)VTopo，試驗(yàn)結(jié)果顯示VTopo與CAIDA Ark數(shù)據(jù)集具有很大的互補(bǔ)性。未來(lái)研究方向?yàn)椋喝绾螌?shí)現(xiàn)適應(yīng)性和多探測(cè)點(diǎn)間協(xié)作式探測(cè)以降低測(cè)量冗余；如何根據(jù)歷史數(shù)據(jù)調(diào)度測(cè)量點(diǎn)以更完整高效地發(fā)現(xiàn)拓?fù)洹?/p>