基于IPv6 AS級復雜網絡的特征分析與建模

劉 冰 楊 學 楊 琪 馬永征

(中國互聯網絡信息中心 北京 100190)

0 引 言

隨著互聯網技術的迅猛發展和網絡規模的日益擴大，IPv4協議在IP地址數量、安全性、移動性、服務質量等方面的不足日漸凸顯，IPv6應運而生。伴隨著IPv6網絡規模的持續增長及各項相關技術的日趨完善，其重要性逐漸提高，網絡結構也越發復雜。而全球互聯網由自治系統(Autonomous System，AS)互相連接而構成，AS的工作方式、復雜的相互關系和自身屬性都在很大程度上決定了整個網絡的流量和行為[1]?；ヂ摼WAS級拓撲關系能夠反映出網絡空間內各AS間的關聯情況，據此可進一步分析得到其相互間的輸入輸出策略。因此，AS間的連接關系是網絡拓撲結構中至關重要的一環，針對IPv6 AS級網絡拓撲的分析和研究成為網絡管理和網絡安全控制的重要方向[2]。通過對IPv6網絡拓撲的全面分析和建模，可以獲得不同組織機構之間的關聯關系和路由策略情況，為整體網絡空間的優化提供了依據；能夠加深對IPv6網絡發展的全面理解，有利于對未來IPv6網絡發展趨勢作出更好的判斷；能夠進一步深入分析IPv6網絡的內在機制，對更加有效地部署和規劃下一代互聯網有重要的指導作用，對國家的網絡管理和維護具有深遠的意義。

目前，IPv6 AS級網絡結構已經非常復雜(如圖1所示)，然而國內外對網絡拓撲結構及模型的研究依然主要集中在IPv4層面，對IPv6網絡拓撲的分析成果較少，僅有為數不多的基于IPv6地址構成的網絡拓撲特征量的研究[3-6]。本文以時間為主線，通過對IPv6 AS級網絡的靜態特征和網絡特性隨時間的演化進行分析，并利用網絡建模技術對未來IPv6 AS網絡發展趨勢作出分析和預測。

圖1 2018年IPv6 AS復雜網絡示例圖

1 數據采集與預處理

1.1 數據采集

AS之間一般是借助專線或者公共網絡的接入點實現連接的，而路由宣告和傳送是利用AS間的路由協議——邊界網關協議(Border Gateway Protocol，BGP)[7]確定的，BGP協議使AS可以根據其實際情況選擇不同的路由策略來完成路由選擇。本文基于RouteViews項目[8]獲取BGP路由數據，提取出相關的AS信息做進一步分析。

RouteViews項目由俄勒岡大學(University of Oregon)先進網絡技術中心創立，用戶可以從互聯網上的幾個不同骨干和位置獲取有關全球路由系統的實時BGP信息。RouteViews項目的初衷是能夠向互聯網服務提供商(ISP)提供查詢其他網絡前綴的服務幫助，使其能夠很方便地調試他們接受到的網絡訪問，以便優化其自身網絡情況。近幾年內，該項目已經在學術和科研項目[9]等方面得到了廣泛應用。1997年11月起，RouteViews項目就已經開始收集相關的BGP數據，截至2019年4月已有24個數據采集點，分別并行地采集全球互聯網的BGP數據。我們通過具體數據比對發現，24個數據采集點中除位于肯尼亞、佩斯和貝爾格萊德的3個采集點外，其他采集點各自獲取的AS總數基本一致，邊總數(即AS節點連接數)相差不大，對網絡結構狀的分析影響有限。因此，為簡單起見，本文在分析IPv6的AS級復雜網絡特征與拓撲結構時，僅選取RouteViews項目位于俄勒岡的IPv6專用采集點[10](route-views6)2003年5月至2018年5月共15年的IPv6 BGP路由表原始數據。

1.2 數據預處理

目前，RouteViews項目的BGP數據采集工作是以2小時為周期進行，每天數據共有12個壓縮包，我們通過解析與合并，對該12個壓縮包提取出的AS和對應邊取合集，作為一天的BGP數據。由于從2003年至2018年長達15年的BGP數據反映了互聯網在IPv6維度方面的網絡結構動態演化過程，對每月或每年數據進行數據合并會屏蔽掉時間序列的特性(以月數據為例，將整個月的數據進行合并時，會屏蔽掉節點的撤銷與新增等時間過程信息。例如：1月2日新增了節點AS1，25日撤銷了該節點，當前網絡結構中宣告節點應該不包含此AS，但將1月1日-1月31日的數據做合并后，AS列表中將會出現此節點，與實際網絡狀態不符)。因此，我們取每月最后一天的數據代表該月的情況，取每年最后一天的數據代表該年的情況，以此保證時序信息，使數據更加符合實際情況。

BGP原始數據包解壓后為MRT格式，需要通過BGP數據包解析工具[11]將此二進制文件轉換為可讀格式。解析原始數據后提取AS_PATH字段的ASN相關數據，AS_PATH屬性包含了一個有序的ASN列表，描述了到達目標網絡所要經過的ASN序列。AS_PATH屬性只有在BGP發言者向外部邊界網關協議(EBGP)的鄰居發布路由時，才會將自己本地系統的ASN作為最后一個元素添加到序列的最左邊，而在向內部邊界網關協議(IBGP)鄰居發布路由時，并不會修改AS_PATH屬性。因此，在提取AS網絡結構的邊數據時，需要根據AS_PATH屬性中的ASN序列特性(右邊為起始ASN，左邊為目標ASN)成對提取。

AS_PATH具有4種類型：

1) AS_SEQUENCE(用于路由AS路徑記錄)。

2) AS_SET(用于聚合路由的明細路由AS集合)。

3) AS_CONFED_SEQUENCE(用于聯盟路由AS路徑記錄)。

4) AS_CONFED_SET(用于聯盟聚合路由)。

在BGP路由表中的顯示格式[12]，如圖2所示。

圖2 AS_PATH顯示格式

在對AS_PATH進行提取時，需進行如下處理：

1) 壓縮處理。例如AS_PATH為“47065 1200 1200 5555”，可壓縮為“47065 1200 5555”。由于BGP協議允許路由器將本地AS連續多次添加到AS_PATH屬性中，使整體路由長度變大，干擾對等體路由的決策，因此在數據提取時需對此類路徑做壓縮處理。

2) 單節點路徑。例如“47065”或“{47065}”，僅提取AS號加入節點數據列表中。

3) 多節點路徑。例如“47065 1200 5555”，按照從右到左的順序提取邊的起始和終止節點。

4) 包含AS_SET多節點路徑。例如“47065,{1200;3209;3320},5555”，拆分“{}”內的AS號與括號外的AS號分別組成新序列為“47065 1200 5555”、“47065 3209 5555”、“47065 3320 5555”，再重復步驟3)。

5) 過濾包含AS_CONFED_SEQUENCE或AS_CONFED_SET的路徑。

6) 過濾存在回路的AS_PATH。一般情況下，回路是由管理員手動設置BGP規則而導致的人為失誤，因此，本文在處理數據時對此類數據進行了清洗。

經過上述處理后提取出的AS網絡結構的頂點和邊數據，需要再分別進行去重和格式異常數據清洗操作，去除數據本身對算法的干擾，便于進一步分析該網絡拓撲結構的演化情況。

2 特征與建模

針對大規模復雜網絡的整體結構的研究，主要的途徑是利用各種方法計算和分析其在拓撲結構上的特征，借助一些特征指標來實現對網絡特征分析的量化研究。這些特征參數包括：節點總數、邊總數、平均最短路徑長度、網絡直徑、平均度、最大節點度及其對應節點、節點度大于平均度的節點所占比例、平均集聚系數、網絡核數、社團數和社團模塊度等。本文根據15年的IPv6 AS動態數據從以上特征維度進行了拓撲結構分析，并對富人俱樂部、自相似性、冪律分布等特性進行了驗證。

2.1 靜態特征分析

針對2003年5月-2018年5月的IPv6 BGP數據，統計分析AS級網絡的靜態特征，各維度特征值如表1、表2所示。

表1 IPv6 AS級網絡靜態特征匯總

表2 IPv6 AS級網絡靜態特征匯總

由表1可見，自2003年至2018年，IPv6 ASN總數和邊總數增長迅猛，特別是2010年以后尤為突出。隨著網絡拓撲的復雜性越來越高，最大度值也隨之逐年增大，通過分析發現自2008年之后，ASN為6 939的節點一直是持有最大度的節點，顯示了其在整個網絡拓撲中的重要性。進一步研究發現，AS6939是颶風電氣有限責任公司(Hurricane Electric LLC)持有的主要AS編號，該公司是目前全球領先的原生IPv6互聯網骨干網和主機托管服務商，根據歐洲互聯網交換聯盟(Euro-IX)的說法，該公司是世界上最大的交換中心參與者，運營了世界上以對等數目計算的最大IPv6網絡，其中大多數是原生IPv6對等會話。該公司同時還提供了免費IPv6隧穿服務[13]，為IPv4用戶或無法接入IPv6網絡的用戶通過隧道提供IPv6服務。

由表1可知，除網絡直徑、網絡核數和社團數這些特征隨網絡規模的擴大而有較明顯增長外，平均度、平均最短路徑長度、平均集聚系數和社團模塊度等靜態特征基本穩定，只有輕微波動，說明網絡容量雖然大幅度擴增，但其全局靜態特征變化不大，網絡環境相對穩定。從度的維度分析，由平均度、最大度的值和節點度大于平均度的占比可知，只有少數節點度很大(即“富節點”)，大部分節點的度很小，大致符合冪律分布[14]；同時，節點度大于平均度所占比例緩慢降低，說明隨著網絡規模的不斷擴大，度值大的節點所占比例越來越小，新加入的節點更傾向于與度值大的節點連接，即這些富節點更傾向于選擇彼此進行相連，則會形成“富人俱樂部”[15]。從時間的維度分析，網絡特征在動態時間上表現出的穩定性很有可能是因為具有自相似性[16]。因此，針對IPv6 AS級網絡拓撲可能存在的這些特性，我們將進行進一步的驗證和分析。

2.2 網絡特性驗證

依據AS宣告的IPv6數量對AS進行排序，取前20%的AS節點及邊數據重新計算全局網絡特征，然后與全部AS節點的計算情況進行比對，結果如圖3所示(由于平均最短路徑長度、平均集聚系數、平均度等特征的變化曲線與網絡直徑特征的曲線走勢完全一致，因此圖3中只展示節點總數、邊總數和網絡直徑三個特征曲線)，可以看出其發展趨勢基本一致。由此可見，2003年-2018年IPv6 AS級網絡拓撲結構隨時間演化的過程符合二八定律，其中排名前20%的節點對網絡結構的變化起著決定性影響，發揮著關鍵性作用。

圖3 核心20%節點與全部節點特征對比

2.2.1冪律分布

冪律是指節點具有的連線數和節點數目的乘積為一個定值，即幾何平均值是定值。也就是說節點數量和連線數量成反比，表現為在對數坐標上畫出來會得到一條斜向下的直線。根據冪律分布公式：

Y=aX-b

(1)

通過對兩邊取以10為底的對數，得到：

logY=logaX-b=loga-blogX

(2)

令y=logY,x=logX,且c=loga為常數，公式變形為：

y=c-bx

(3)

即針對冪律公式的X和Y取雙對數后，在坐標軸上應呈現線性方程圖。

將上述概念應用到網絡拓撲結構領域，節點間連線數量表現為各節點的度值，因此判斷網絡拓撲是否符合冪律分布，需對網絡的度分布情況做分析驗證。

我們根據2003年-2018年IPv6 AS數據，分別統計每年網絡節點的度分布情況，如圖4中各子圖的左圖所示(此處僅展示其中6年的圖)，橫坐標為度值，縱坐標為該度值對應的節點數在所有節點中的占比。由圖可見，在整個網絡結構中，度越大的節點數量越少，而度越小的節點數量越多，初步推斷滿足冪律分布的特性。為使結論更具準確性，進一步對該數據做線性擬合，得到圖4各子圖的右圖，其中PE表示冪律分布的冪指數，SSR表示殘差平方和的值。殘差平方和是在線性模型中評估模型擬合程度的一個標準，其值越小說明線性模型擬合率越高，即越符合冪律分布特性。由圖4可知，每年的IPv6 AS網絡均滿足冪律分布且冪指數幾乎保持不變,線性模型擬合率約為0.01左右，擬合率極高。

(b) 2006年

(c) 2009年

(d) 2012年

(e) 2015年

(f) 2018年圖4 2003年-2018年IPv6 AS網絡度分布及冪律分布圖

2.2.2富人俱樂部特性

富人俱樂部的連通性一般通過參數富人俱樂部系數φ(r/N)來度量，其計算方法是求取整個網絡中前r個度值最大的節點所構成的網絡中的邊數L與這r個節點間兩兩互連能夠存在的最大邊數r(r-1)/2間的比值(節點總數為N)，即：

(4)

當φ(r/N)時，表示前r個度最大的節點組成的富人俱樂部為一個完全連通的子圖。

利用式(4)，我們計算得到2003年-2018年IPv6 AS級網絡富人俱樂部系數隨時間的演化情況，結果如表3所示，其中，r在5到20每隔5取值一次，計算一次富人俱樂部系數。根據表可知：一方面，自2003年至2018年，同一r值下，AS網絡每年的富人俱樂部系數值均有小幅的上下振動，但變化不大，相對穩定；另一方面，隨著r取值越來越大，富人俱樂部系數會隨之減小，說明富人俱樂部中的富節點數量越多其內部連通性就會相對越差，少量富節點構成的富人俱樂部其內部連通性越強，甚至接近于全連通狀態。

表3 每年由度值排名前r的節點構成的富人俱樂部 的連通性統計

圖5是選取2018年的IPv6 AS級真實網絡數據，最大度為4 268，4個子圖分別表示度大于500、300、100、50的網絡結構圖。可以明顯看出：度大于50的節點已經屈指可數，度大的節點占整個網絡規模的極少數，只有少數節點連接的邊數很多，絕大多數的節點度很小；度大的節點間相互連接密切，體現了網絡的富人俱樂部特性。

圖5 2018年IPv6 AS網絡度大的節點連接情況

2.2.3自相似性

自相似性作為分形理論的一個重要特性，越來越多地引起了廣大研究者的興趣和關注。在復雜網絡中，對其自相似性的研究意義主要在于以自相似度研究為基礎來準確進行鏈路預測、有效檢測社團網絡以及探索復雜網絡的演化機制等[17]。目前，針對復雜網絡自相似性的研究主要集中在對其節點或自身局部的相似性的研究，而在復雜網絡全局拓撲特性層面上的相似度研究極少甚至沒有。本文主要基于統計和分析全局的復雜網絡拓撲結構特征來驗證2003年-2018年動態網絡的自相似程度。

1) Hurst指數。赫斯特指數(Hurst Exponent) 又稱自相似參數，是用來衡量時間序列是否有長期記憶的一個指標，可以通過計算全局網絡靜態特征的Hurst指數來估計時間序列的自相關系數，以此評估網絡拓撲結構的自相似性[18]。目前，針對時間序列的 Hurst指數的估計方法問題，國內外已經提出了 R/S分析法、絕對值法、周期圖法等多種方法[19]。本文選用最常用的R/S分析方法(即重新標度的極差分析法，簡稱重標極差分析法)，針對AS網絡主要特征維度的時間序列，計算各維度的Hurst指數。R/S分析法描述如下：

給定一時間序列xi，i=1,2,…,N，對于任意正整數n，定義累計和序列為：

(5)

計算相應的樣本方差：

(6)

則R/S的統計值為：

n≥1

(7)

若存在如下關系:

? 若H=0.5，則表示該時間序列差分后的自相關系數等于0，即時間序列前后變化沒有關聯, 該時間序列是一個相互獨立的隨機序列。

? 若0.5

? 若0

2) 計算Hurst。針對2003年-2018年IPv6 AS網絡的節點總數、邊總數、平均度、平均最短路徑長度和平均集聚系數等全局靜態特征組成的時間序列，計算各單特征時間序列的Hurst指數，具體步驟如下：

(1) 將時間序列[x1,x2,…,xN]按不同片段長度分別進行均分。比如，按照下列4種片段長度劃分，其中N表示整個時間序列的總長度：

① 片段長度n=N，均分后共1個片段；

(2) 計算每個片段的均值E、累積離差序列及其極差R和標準差S。

(3) 計算每個片段的R/S值，并求其在步驟(1)的不同分割方法下對應的平均值。

(4) 計算差分序列的自相關系數H：

通過上述步驟，得到R/S雙對數，分別計算其斜率得到Hurst指數結果，如表4所示。結果顯示，各特征維度時間序列Hurst指數均在0.8以上，表明IPv6 AS級網絡在時間維度上是自相似的，過去和未來具有正相關性，且自相似程度很高，具有持續性。因此，可以通過過去和當前的網絡特征情況推測未來的發展趨勢和狀態。

表4 各全局靜態特征時間序列Hurst指數

2.3 網絡建模

為了更準確地預測和評估未來IPv6 AS級互聯網的發展趨勢，基于對IPv6 AS網絡歷年來拓撲結構及特征的上述分析結果，考慮到網絡演化過程中出現的變化，本文在分析網絡拓撲特性的基礎上，利用差分自回歸移動平均模型(ARIMA(p,d,q))對主要特征的時間序列進行了建模，為未來的拓撲變化趨勢作出預測。

2.3.1基礎模型

ARMA(p,q)模型是目前已經相對成熟和完善的用于分析時間序列的重要模型之一，它分為兩個主要步驟，其中AR代表p階自回歸過程，MA代表q階移動平均過程，其公式如下：

Zt=φ1Zt-1+φ2Zt-2+…+φpZt-p+at-

θ1at-1-…-θqat-q

(8)

簡化后得到：

φp(B)Zt=θq(B)at

(9)

式中：

φp(B)=1-φ1B-φ2B2-…-φpBpφq(B)=1-θ1B-θ2B2-…-θqBq

而ARIMA(p,d,q)模型是在ARMA模型的基礎上增加了差分的操作，用來得到平穩序列，保證數據的穩定性，其中d是差分的階數。

2.3.2平穩性檢驗及處理

序列平穩性是進行時間序列分析的前提條件，對時間序列進行建模的過程是基于大數定理和中心極限定理的，而其要求的樣本同分布原則與序列平穩性異曲同工。為了保證結論的可靠性和準確性，必須滿足此原則。例如，在輸入和輸出變量均平穩的情況下，可以通過t統計量來對標準化系數的顯著性進行驗證；而在輸入和輸出變量均不平穩的情況下，該標準化系數不再滿足t分布，如果繼續用t對其顯著性進行驗證和分析，則會增加拒絕原假設的概率，最終導致錯誤結論的產生[19]。針對非平穩時間序列直接建立回歸，很容易產生偽回歸。所以，在進行時間序列分析前，必須進行平穩性檢驗和處理，確保序列是平穩的，以避免回歸分析中存在偽回歸。

以節點總數的時間序列為例，自2003年至2018年IPv6 AS網絡的節點總數是逐年增加的，如圖6(a)所示，結合2.2.3自相似性的計算結果可知，該時間序列的自相關系數是基本穩定的，并沒有跟隨時間的增加而變化，由于平穩序列的自相關系數會快速衰減，因此該時間序列并非平穩序列。為得到平穩序列，對其進行1階差分，得到圖6(b)仍然不平穩，繼續進行2階差分得到圖6(c)，經二次差分后的時間序列在均值和方差上趨于平穩。

(a) 時間序列原圖 (b) 1階差分處理

(c) 2階差分處理圖6 節點總數時間序列差分過程示意圖

由于僅通過圖像觀察存在一定程度的誤差性，因此本文通過單位根檢驗法(Augmented Dickey-Fuller,ADF)進一步驗證二次差分后時間序列的平穩性。由于該序列在年周期性和長期趨勢上表現明顯，我們通過設置窗口為12的移動平均來處理其年周期成分，并通過差分的方法來處理其長期趨勢：假設該時間序列具有單位根，為非平穩序列，對于一個平穩的時序數據，就需要在給定的置信水平上顯著，以拒絕原假設。根據節點總數時間序列原數據，進行ADF檢驗，得到p值為0.998 6，大于99%，說明不能拒絕原假設，即時間序列為非平穩序列；經過一次差分后，進行ADF檢驗，得到p值為0.601 1，即60%左右，說明并不能完全拒絕原假設，即該時間序列具有一定的非平穩性；經過二次差分后，進行ADF檢驗，得到p值為0.001 8，小于1%，說明可以拒絕原假設，即經過二次差分的時間序列為平穩序列，滿足繼續建模分析的條件。

2.3.3模型識別

數據平穩后，需要對模型定階，即確定p、q的階數。首先檢查平穩時間序列的自相關圖(見圖7)和偏自相關圖[21](見圖8)。觀察圖7和圖8，發現置信區間被設置為默認值95%的情況下，滯后階數在1到30之間時自相關和偏相系數都存在明顯的拖尾(自相關12階拖尾，偏自相關13階拖尾)，符合ARMA模型的特點。利用貝葉斯信息準則(BIC)來衡量模型擬合度，獲得最優ARIMA模型。通過計算得到BIC為-1 544.227 2，p為2，q為4時模型擬合度最高，結合差分情況，即完整模型為ARIMA(2,2,4)。

圖8 節點總數時間序列二次差分后的偏自相關圖

2.3.4樣本擬合

確定模型后，對時間序列進行預測。由于模型的擬合過程中進行了差分等預處理，所以通過模型預測得出的值也需要通過反向處理進行數據還原，對還原后的預測序列做可視化處理[22]，得到圖9所示結果(其中，黑線表示模型預測結果，灰線表示原時間序列)。觀察圖9可見，模型擬合率很高，預測效果較為可觀。依據同樣的方法，對其他主要特征進行了同樣的建模與預測，得到圖10。

圖9 節點總數時間序列與模型預測結果對比圖

(a) 邊總數 (b) 最大度

(c) 節點度大于平均度占比(d) 平均最短路徑長度

(e) 最大核數 (f) 社團數圖10 主要特征的時間序列與模型預測結果對比圖

2.4 分析與評價

根據IPv6 AS級網絡動態數據的靜態特征、網絡特性及建模結果可知，2003年-2018年網絡節點總數、邊總數持續增長，最大度呈明顯上升趨勢，網絡直徑、網絡核數和社團數呈現緩慢增長趨勢，平均節點度、平均集聚系數、平均最短路徑長度和社團模塊度均相對穩定，振幅很小，隨著時間的推移幾乎不變；節點度大于平均度所占比例隨時間推移呈現緩慢降低趨勢，說明新增節點更傾向于與度值大的節點建立連接關系；動態網絡的節點度分布情況滿足冪律分布，說明大多數節點的度值很小，只有少數的節點度值較大；動態網絡存在富人俱樂部現象，說明度較大的節點更傾向于與其他度較大的節點建立連接，形成富節點組成的富人俱樂部；動態網絡具有自相似性，說明過去的網絡特征與未來的網絡特征成正相關關系，可以通過過去的網絡狀態預測未來的網絡發展趨勢；利用ARIMA模型可以很好地擬合IPv6 AS級網絡狀態，通過該模型可以較準確地預測未來網絡拓撲的變化情況，對未來網絡的發展趨勢分析有指導作用和長遠意義。

3 結 語

本文通過對2003年-2018年15年間的IPv6 AS級網絡靜態特征及網絡特性的分析，觀察網絡規模擴增過程中各特征量的變化，總結IPv6 AS級網絡拓撲的演化規律，并通過建模分析網絡拓撲狀態，預測發展趨勢。根據分析結果可以推測，未來IPv6 AS級網絡規?？傮w會繼續呈上升趨勢增長，但平均度、平均最短路徑長度、平均集聚系數和社團模塊度等全局靜態特征變化不大，未來將依然處于相對穩定的狀態，這符合IPv6 AS級網絡特性和發展規律。