面向地理空間的網絡拓撲結構特征分析*

張志勇，許瑩瑩，馮肖楊，賈繼康，李 斌，許 卡

（1.中國電子科技集團公司第三十研究所，四川 成都 610041；2.中電科網絡安全科技股份有限公司，四川 成都 610095）

0 引言

網絡空間測繪旨在通過探測全球網絡空間的節點分布和連接關系，構建全球網絡空間地圖，近年來成為網絡空間安全領域備受關注的熱點方向[1-2]。其中，互聯網拓撲提供了生成網絡空間地圖的基礎底圖信息，因此對網絡空間拓撲的探測、還原是網絡空間測繪中非常重要的研究內容之一。此外，通過對互聯網拓撲結構的特征進行分析，能夠幫助發現目標網絡的骨干節點、關鍵路由，識別目標在網絡結構層面的脆弱性，對幫助提升目標網絡安全防護能力、優化目標網絡架構和性能具有重要意義。

現有的拓撲測繪工作主要圍繞網絡拓撲模型建模、拓撲結構還原、結構特征分析等方向展開。其中，網絡拓撲模型按照從宏觀到微觀的順序，主要分為自治域（Autonomous System，AS）級、接入點（Point of Presence，PoP）級、路由器級和IP 接口級4 個層級[3-4]。各個層級的網絡拓撲模型中，節點分別指代不同對象，因而相應的網絡拓撲模型揭露了網絡空間在不同空間尺度的結構特點。此外，Gunes 等人[5]和Tozal 等人[6]提出了構建子網級拓撲的理念和實現算法，子網級拓撲可被視作路由器級拓撲的對偶模型。

為了獲得網絡空間在各個層級的拓撲，通常采用自下而上的思路進行。首先采用如Traceroute 之類的IP 路徑探測工具[7]獲得海量IP 路徑，并基于此還原得到IP 接口級拓撲。在IP 接口級拓撲的基礎上，執行IP 別名解析[8]，將屬于相同路由器的IP 集合合并為路由器節點，可獲得路由器級拓撲。針對PoP 級拓撲，則在路由器級拓撲基礎上，結合路由器的地理位置信息和局部連接特征，將多個路由器聚合為PoP 節點。對于AS 級拓撲，一方面可根據IP 級拓撲以及IP-AS 映射關系間接生成AS 鏈路，另一方面可結合邊界網關協議（Border Gateway Protocol，BGP）路由信息[9]中的AS Path 字段直接獲得AS 鏈路。CAIDA 根據AS 間的連接關系特征，推斷AS 之間的商業服務關系[10]，將AS 鏈路劃分為P2C、P2P、Sibling 等，構建了比較完整的全球AS 級網絡拓撲。

基于還原得到的網絡拓撲，業界圍繞對拓撲的結構特征分析開展了大量工作。Subramanian 等人提出Sark 模型分析AS 的層級結構，按照AS 在全球互聯網中的地位將其劃分為核心傳輸層、骨干傳輸層、邊緣傳輸層、邊緣接入層、邊緣層5 個類別[11]。CAIDA 的AS Rank 項目[12]利用AS 的客戶集規模作為度量AS 重要性的指標并對全球所有AS 進行排名。劉曉等人[13]分析了全球互聯網的結構特征演化趨勢，發現全球互聯網整體上在朝著扁平化、去中心化的方向發展。這種趨勢一方面是源自內容分發網絡（Content Delivery Network，CDN）技術的興起和內容提供者的增加，導致作為流量終點的內容提供者更靠近作為流量發起的用戶；另一方面，互聯網交換中心（Internet eXchange Point，IXP）的大量出現使得AS 之間對等（Peer to Peer，P2P）關系的代價越來越小，很多底層的AS 通過建立對等關系來降低傳輸的代價。朱金玉等人[14]和程麗君等人[15]則分別提出了一種識別國家/地區邊界節點和識別目標網絡骨干節點的方法，能夠從海量路由器或者IP 中發現對特定網絡具有重要意義的特殊目標，可以為基于拓撲信息的上層應用提供有效支撐。

然而，現有工作主要在網絡層展開，并沒有將網絡空間和地理空間有機結合。為此，本文基于IP接口級拓撲構建了面向地理空間的網絡拓撲模型，對國家/地區間的路由關系和連通特征進行分析，揭露了不同地理區域之間的路由關系特征。本文貢獻總結如下：

（1）將現有的網絡拓撲模型從網絡域遷移到地理域，建立面向地理空間的網絡拓撲，其中每個節點可對應具體的地理區域，如國家/地區、城市；

（2）在面向地理空間的網絡拓撲基礎上，研究了各個國家/地區在全球網絡通信中扮演的角色，通過具體度量參數對其重要性進行量化刻畫，為彌補國家網絡建設短板提供有益參考。

1 面向地理空間的拓撲結構特征分析

1.1 拓撲模型及其構建方法

用圖模型G=(V,E) 表示IP 級拓撲，其中：V={vi|i=1,2,…,n}是節點集合，每個節點vi對應一個IP 地址；E={(v,v')|v∈V,v'∈V,v≠v'}是鏈路集合，每條鏈路是一個IP 地址二元組。為了構建IP級拓撲，通常采用Traceroute 等IP 路徑探測工具，在多個探測源上獨立地對整個IPv4 地址空間進行探測，獲得大量IP 路徑信息。用P={pj|j=1,2,…,m}表示探測獲得的所有IP 路徑構成的集合。每條IP路徑實質上是一個IP 地址序列，用p=(k1,k2,…,kl)表示，其中，每個ki(i=1,2,…,l)均為該路徑經過的一個IP 地址。從每條IP 路徑可抽取得到一系列IP 節點和鏈路用于構建IP 級拓撲。對于路徑p=(k1,k2,…,kl)，它經過的每個IP 地址ki(i=1,2,…,l)均為V中的節點，經過的任意兩個連續IP 地址構成的二元組(ki,ki+1)(i=1,2,…,l-1)均為E中的鏈路。若將路徑p視作IP 地址集合，則也可用v∈p表示路徑p經過了IP 地址v。對給定的IP 級拓撲G=(V,E)和路徑集合P，記經過節點v∈V的路徑構成的集合為P(v)={p|p∈P,v∈p}，記經過鏈路e=(v,v')∈E的路徑構成的集合為P(e)=P((v,v'))={p|p∈P,v∈p,v'∈p}。

利用IP 地址的地理位置信息，可將上述IP 級拓撲模型轉換為面向地理空間的網絡拓撲，用圖O=(U,L)表示。其中，U為節點集合，U中每個節點表示一個地理位置。根據實際使用需求，地理位置的粒度可能取值為大洲、國家、城市等不同級別的地理區域。假如U中每個節點對應一個城市，則O為城市級網絡拓撲，反映了不同城市之間的網絡連接關系。對于兩個地理節點u,u'∈U(u≠u')而言，如果原始的IP 級拓撲G=(V,E)中存在兩個節點v,v'∈V所處的地理位置分別為u,u'，且有(v,v')∈E，則(u,u')∈L是圖O=(U,L)的一條邊。

類似的，將IP 路徑p=(k1,k2,…,kl)中每個IP 地址按照其所處的地理區域映射為地理節點形成地理節點序列，并在地理節點序列中將連續且重復的地理節點合并后，可以得到該IP 路徑在地理空間中對應的路徑，將其稱為p的地理路徑，用p°表示。例如，對于某條IP 路徑p=(k1,k2,k3,k4,k5)，假定其經過的5 個IP 地址中，k1和k2位于城市c1，k3位于城市c2，k4和k5位于城市c3，則p的地理路徑為p°=(c1,c2,c3)。

將P中所有IP 路徑的地理路徑構成的集合記為p°。其中，p°(u)={p°|p°∈P°,u∈p°}表示經過地理節點u的所有地理路徑。顯然，可能存在多條不同的IP 路徑被映射為同一條地理路徑。例如，若存在另一條路徑其經過的5 個IP 地址中，和位于城市c1，位于城市c2，和位于城市c3，則p'的地理路徑和上文中p的地理路徑同為p°=(c1,c2,c3)。為此，用I(p°)表示地理路徑p°∈P°對應的IP 路徑數。

1.2 節點重要性評估方法

為了掌握一個地理區域在實現全球網絡互聯互通時所發揮的作用，采用復雜網絡分析中常見的中心性指標對地理區域的重要性進行度量，具體包括中介中心性、距離中心性和度中心性3 個度量指標。

1.2.1 基于中介中心性的節點重要性度量方法

原始的中介中心性以經過某個節點的最短路徑數來刻畫該節點的重要性。對于節點v∈V，它的中介中心性為：

式中：Pst為任意兩個不同節點之間的最短路徑構成的集合；Pst(v)為Pst中經過節點v的路徑子集；#為對集合求元素個數的運算符。

根據式（1）計算節點的中介中心性時，需要計算任意兩個不同節點之間的最短路徑。對于網絡拓撲而言，計算原始的中介中心性存在兩個問題：（1）網絡規模太大，導致計算任意兩個節點之間的最短路徑的計算復雜度太高；（2）更重要的是，網絡中任意兩個節點之間實際采用的通信路徑和理論上的最短路徑可能并不一致。為此，對給定的IP級拓撲G=(V,E)和路徑集合，節點v∈V的中介中心性為：

顯然，式（2）用實際測量得到的路徑集合替換原始中介中心性中的最短路徑，能夠避免原始中介中心性面臨的兩個問題。

在式（2）的基礎上，提出針對地理區域的網絡拓撲節點的中介中心性計算方法，具體為：

1.2.2 基于距離中心性的節點重要性度量方法

在連通圖中，一個節點越靠近圖的中心，該節點離其他節點的距離就越近。對于節點v∈V，它的歸一化的接近中心性可由下式計算得到：

式中：d(v,v')為節點v和節點v'之間的最短路徑。

在式（4）的基礎上，對接近中心性取倒數，將每個地理路徑p°的長度作為該路徑的起點和終點之間的距離，用I(p°)作為權重進行加權計算，可得針對地理區域的網絡拓撲節點u的距離中心性計算方法為：

1.2.3 基于度中心性的節點重要性度量方法

度中心性是衡量節點重要程度的最直接的度量。針對地理區域的網絡拓撲節點u的度中心性計算方法如下：

度中心性CD(u)實質上是和節點u在網絡上直接相連的其他節點的數量。

2 實驗評估

2.1 實驗數據集

實驗所用的IP 路徑數據來自CAIDA 的全球IPv4 拓撲探測數據集[16]。CAIDA 在全球部署了數十個探測節點，周期性地對全球IPv4 地址空間的“/24”前綴進行IP 路徑探測，并將1 年前的數據開放給研究人員使用。為了研究拓撲結構特征隨時間變化的情況，選取了2018 年、2020 年、2022 年的數據進行分析。每一年的數據都選取了一整輪的測量結果，即測量數據中的目標IP 能夠覆蓋全球IPv4 地址空間的所有“/24”前綴。

為了以地理區域為單位進行研究，使用Maxmind的IP 地址地理定位數據集[17]作為映射標準，將IP路徑中出現的每個IP 地址映射到相應的國家/地區，并按照1.1 節所述方法生成地理路徑。

需要注意的是，按照前文方法計算節點重要性之前，需要首先濾除以下兩類異常路徑：（1）由于匿名路由器導致的不完整路徑，即由于路徑存在連續幾跳節點不響應而導致路徑探測提前終止；（2）由于IP 地址地理定位信息不完整導致路徑中存在無法定位的IP 地址，即無法將路徑經過的所有IP 地址映射到相應國家/地區。所有的節點重要性度量指標均基于正常路徑進行計算，以排除異常路徑對最終結果的干擾。

2.2 中介中心性評估結果

表1 展示了中介中心性最高的10 個國家/地區的詳細情況。可以看到，在2018 年、2020 年和2022 年，中介中心性最高的4 個國家都是美國、英國、法國和德國，且美國的中介中心性總是遠高于其他國家。隨著排名向后，國家/地區的重要性下降得很快，而且隨著時間的推移，排名靠前的國家/地區的中介中心性在逐漸上升。這意味著互聯網中占支配地位的國家/地區的支配程度越來越高，即冪律分布現象越來越明顯。

表1 中介中心性最高的10 個國家/地區

2.3 距離中心性評估結果

表2 展示了距離中心性最低的10 個國家/地區的詳細情況，即距離互聯網中心最近的10 個國家/地區。可以看到，距離中心性在這幾年并沒有明顯的變化，出現在排行榜中的國家/地區比較分散，而且有許多不知名小國家出現在排行榜中。

表2 距離中心性最低的10 個國家/地區

其中，美國在3年的統計中都出現在了排行榜中，中國大陸則在2018 年和2020 年分別排名第9 和第2。

2.4 度中心性評估結果

表3 展示了度中心性最高的10 個國家/地區的詳細情況。可以看到，對于排名前幾位的國家/地區，度中心性和中介中心性的結果比較一致，美國、英國、德國、法國排名一直都比較高。

表3 度中心性最高的10 個國家/地區

然而，同一個國家的度中心性理論上應隨著時間推移而逐漸增加，但是實驗結果則并非如此，這可能是由于不同年度的路徑數據集的完整性不同而造成的。因此，度中心性不像中介中心性那樣具有歸一化的效應，對數據質量的依賴比較強。

3 結語

互聯網拓撲是構建網絡空間地圖的必要信息，其結構特征反映了網絡空間的地形特點。結合網絡拓撲信息和節點的地理位置信息，提出了面向地理空間的網絡拓撲模型構建方法，并針對各個國家/地區，通過中介中心性、距離中心性、度中心性等參數對其在全球互聯網中的重要性進行度量。利用CAIDA 提供的開放數據開展實驗分析，實驗結果表明，中介中心性能夠更為客觀地反映國家/地區在互聯網中的重要性，且美國占主要支配地位。本項工作能夠幫助加深對互聯網拓撲結構及其變化趨勢的理解，并為提升國家/地區網絡魯棒性提供有益參考。