互聯網拓撲測量技術與工程實踐

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

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

0 引言

網絡空間測繪對網絡空間中虛實組件、結構關系和交互規律進行測量與繪制，是站在更高層次上了解、控制、管理和建設網絡空間的基礎。對網絡空間中互聯網拓撲進行測量是構建網絡空間基礎設施“地圖”的主要方式之一，對一個地區的互聯網進行拓撲測量可以為發現地區網絡基礎設施中脆弱環節和消除斷網風險提供重要依據。

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

表1 各層級網絡拓撲含義

1 拓撲測量技術與平臺概述

經過20多年的發展，互聯網拓撲測量研究和測量技術已逐漸成熟。按表1中各層次拓撲列舉了主要的測量技術，如表2所示。它們為大規模互聯網拓撲測量提供了基礎性技術支撐?；ヂ摼W拓撲測量技術的本質是對路由協議進行測量，最主要的技術是Traceroute[2]。Traceroute是一種通過向目標IP地址順序發送TTL遞增的探測包，利用中間路由器返回的TTL超時回復或目標的回復來獲取測量點到目標之間IP路徑的方法；路由器級、PoP級、自治域級等更高層次級別拓撲測量主要建立在接口級拓撲基礎上，對接口級拓撲節點進行聚合。

表2 網絡拓撲測量工具/技術列舉

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

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

表3 網絡拓撲測量平臺及其特點

2 一個基于虛擬專用服務器的拓撲測量系統

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

圖1 VTopo測量平臺的系統架構

3 互聯網拓撲測量結果與分析

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

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

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

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

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

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

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

(2)發現拓撲規模上，VTopo發現拓撲的規模大于CAIDA同時期測量發現的拓撲規模：發現的節點數、鏈接數都是CAIDA發現的近3倍。這說明通過對特定地區目標的針對性測量可以顯著地增加發現地區內網絡拓撲的完整性。

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

為了評價VTopo測量發現拓撲的效率，對發現拓撲的規模隨Traceroute測量次數的增長情況作了統計，如圖2所示。

圖2 VTopo測量發現率

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

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

4 結論

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