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

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

0 引言

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

互聯(lián)網(wǎng)拓撲是指互聯(lián)網(wǎng)中節(jié)點及其鏈接根據(jù)不同粒度分成接口級、路由器級、PoP(機房)級和自治域級等網(wǎng)絡拓撲層級[1]，各級拓撲概念如表1所示。盡管已經(jīng)存在的拓撲測量技術(shù)日趨成熟，然而基于基礎(chǔ)的Traceroute測量獲取地區(qū)級別互聯(lián)網(wǎng)拓撲仍存在工程上的挑戰(zhàn)。首先，由于IP地址本身不帶有地理位置屬性，因此難以直接獲得地區(qū)內(nèi)互聯(lián)網(wǎng)完整IP地址范圍；其次，可用的測量點以及測量能力難以完整地發(fā)現(xiàn)給定地址范圍內(nèi)的互聯(lián)網(wǎng)拓撲。針對上述問題，本文介紹一個互聯(lián)網(wǎng)拓撲測量工程實踐，概述當前拓撲測量技術(shù)；介紹一個基于虛擬虛擬服務器的測量平臺——VTopo；分析了VTopo對區(qū)域互聯(lián)網(wǎng)拓撲測量的效率與完整性，并與CAIDA Ark測量項目進行了比較。

表1 各層級網(wǎng)絡拓撲含義

1 拓撲測量技術(shù)與平臺概述

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

表2 網(wǎng)絡拓撲測量工具/技術(shù)列舉

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

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

表3 網(wǎng)絡拓撲測量平臺及其特點

2 一個基于虛擬專用服務器的拓撲測量系統(tǒng)

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

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

3 互聯(lián)網(wǎng)拓撲測量結(jié)果與分析

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

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

Traceroute數(shù)據(jù)可以看成IP路徑的集合P，由P產(chǎn)生拓撲圖G，此外根據(jù)是否有轉(zhuǎn)發(fā)行為，定義網(wǎng)絡拓撲圖中的路由器節(jié)點集合為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地址(跳過匿名路由器，即在Traceroute中回復為“*”的跳，只在鏈接屬性中保留連續(xù)的匿名路由器跳數(shù))；G是以IP地址在網(wǎng)絡層的相鄰關(guān)系(一條IP路徑上相鄰兩跳IP地址)為邊，以所有在IP路徑中出現(xiàn)的IP地址為節(jié)點的拓撲圖；路由器節(jié)點集合是在IP路徑中的中間跳IP地址或者不是本次Traceroute測量目標(ti)的末跳IP地址。

按照上述定義生成測量區(qū)域的網(wǎng)絡拓撲圖VTopo，并與CAIDA進行對比分析，本文給出了如表4所示的拓撲規(guī)模對比結(jié)果。對比的項目包括拓撲中的節(jié)點數(shù)、路由器節(jié)點數(shù)、鏈接數(shù)、路由器鏈接數(shù)4種。其中，節(jié)點數(shù)是節(jié)點集合的大小，路由器節(jié)點數(shù)是路由器節(jié)點集合R的大小，鏈接數(shù)是邊集E的大小，路由器鏈接數(shù)是端點都在R中的鏈接組成的集合的大小。

為了分析VTopo和CAIDA的重合關(guān)系，對于每一個比較項，表4列舉了VTopo和CAIDA的文氏圖中各個部分的元素數(shù)目。其中，VTopo和CAIDA共同發(fā)現(xiàn)的部分是VTopo∩CAIDA；VTopo和CAIDA單獨發(fā)現(xiàn)的部分分別是VTopo-VTopo∩CAIDA和CAIDA-VTopo∩CAIDA。此外，為了評價VTopo平臺新發(fā)現(xiàn)拓撲的能力，表4還給出了VTopo新發(fā)現(xiàn)拓撲的比例，即VTopo單獨發(fā)現(xiàn)數(shù)/VTopo發(fā)現(xiàn)總數(shù)。觀察表4，可以得到如下發(fā)現(xiàn)：

表4 VTopo與CAIDA測量結(jié)果比較(單位：萬)

(1)新發(fā)現(xiàn)拓撲比例上，VTopo平臺新發(fā)現(xiàn)拓撲的比例較高，尤其新發(fā)現(xiàn)終端的比例較高，說明VTopo平臺的測量結(jié)果是對CAIDA平臺完整性上的較大補充。

(2)發(fā)現(xiàn)拓撲規(guī)模上，VTopo發(fā)現(xiàn)拓撲的規(guī)模大于CAIDA同時期測量發(fā)現(xiàn)的拓撲規(guī)模：發(fā)現(xiàn)的節(jié)點數(shù)、鏈接數(shù)都是CAIDA發(fā)現(xiàn)的近3倍。這說明通過對特定地區(qū)目標的針對性測量可以顯著地增加發(fā)現(xiàn)地區(qū)內(nèi)網(wǎng)絡拓撲的完整性。

(3)發(fā)現(xiàn)路由器拓撲上，VTopo發(fā)現(xiàn)的路由器節(jié)點總數(shù)是CAIDA的2倍，但占總節(jié)點數(shù)量的比例小于CAIDA。這說明了VTopo能貢獻更多處在網(wǎng)絡拓撲核心部分的完整性，隨著發(fā)現(xiàn)拓撲規(guī)模的不斷增加發(fā)現(xiàn)新路由器節(jié)點的效率會有所下降。

為了評價VTopo測量發(fā)現(xiàn)拓撲的效率，對發(fā)現(xiàn)拓撲的規(guī)模隨Traceroute測量次數(shù)的增長情況作了統(tǒng)計，如圖2所示。

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

在圖2(a)，2(b)中分別給出了在進行前5億7 000 萬次Traceroute時，拓撲中新發(fā)現(xiàn)節(jié)點和新發(fā)現(xiàn)鏈接的增長情況，圖中數(shù)據(jù)點在橫坐標以10萬次Traceroute測量為間隔進行采樣。圖中的直線是對數(shù)據(jù)點線性回歸分析后得到的線性模型的預測直線，圖2(a)和圖2(b)中線性回歸的r2分數(shù)分別為0.994和0.996，呈現(xiàn)較強的線性性，預測直線的斜率分別為0.30和0.34，這說明平均一次Traceroute測量僅能發(fā)現(xiàn)不足一個新的IP級節(jié)點和鏈接，這說明實驗中的Traceroute測量存在較高的冗余。

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

4 結(jié)論

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