劉 冰 楊 學(xué) 楊 琪 馬永征

(中國互聯(lián)網(wǎng)絡(luò)信息中心 北京 100190)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展和網(wǎng)絡(luò)規(guī)模的日益擴大，IPv4協(xié)議在IP地址數(shù)量、安全性、移動性、服務(wù)質(zhì)量等方面的不足日漸凸顯，IPv6應(yīng)運而生。伴隨著IPv6網(wǎng)絡(luò)規(guī)模的持續(xù)增長及各項相關(guān)技術(shù)的日趨完善，其重要性逐漸提高，網(wǎng)絡(luò)結(jié)構(gòu)也越發(fā)復(fù)雜。而全球互聯(lián)網(wǎng)由自治系統(tǒng)(Autonomous System，AS)互相連接而構(gòu)成，AS的工作方式、復(fù)雜的相互關(guān)系和自身屬性都在很大程度上決定了整個網(wǎng)絡(luò)的流量和行為[1]?；ヂ?lián)網(wǎng)AS級拓?fù)潢P(guān)系能夠反映出網(wǎng)絡(luò)空間內(nèi)各AS間的關(guān)聯(lián)情況，據(jù)此可進一步分析得到其相互間的輸入輸出策略。因此，AS間的連接關(guān)系是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中至關(guān)重要的一環(huán)，針對IPv6 AS級網(wǎng)絡(luò)拓?fù)涞姆治龊脱芯砍蔀榫W(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全控制的重要方向[2]。通過對IPv6網(wǎng)絡(luò)拓?fù)涞娜娣治龊徒＃梢垣@得不同組織機構(gòu)之間的關(guān)聯(lián)關(guān)系和路由策略情況，為整體網(wǎng)絡(luò)空間的優(yōu)化提供了依據(jù)；能夠加深對IPv6網(wǎng)絡(luò)發(fā)展的全面理解，有利于對未來IPv6網(wǎng)絡(luò)發(fā)展趨勢作出更好的判斷；能夠進一步深入分析IPv6網(wǎng)絡(luò)的內(nèi)在機制，對更加有效地部署和規(guī)劃下一代互聯(lián)網(wǎng)有重要的指導(dǎo)作用，對國家的網(wǎng)絡(luò)管理和維護具有深遠的意義。

目前，IPv6 AS級網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)非常復(fù)雜(如圖1所示)，然而國內(nèi)外對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及模型的研究依然主要集中在IPv4層面，對IPv6網(wǎng)絡(luò)拓?fù)涞姆治龀晒^少，僅有為數(shù)不多的基于IPv6地址構(gòu)成的網(wǎng)絡(luò)拓?fù)涮卣髁康难芯縖3-6]。本文以時間為主線，通過對IPv6 AS級網(wǎng)絡(luò)的靜態(tài)特征和網(wǎng)絡(luò)特性隨時間的演化進行分析，并利用網(wǎng)絡(luò)建模技術(shù)對未來IPv6 AS網(wǎng)絡(luò)發(fā)展趨勢作出分析和預(yù)測。

圖1 2018年IPv6 AS復(fù)雜網(wǎng)絡(luò)示例圖

1 數(shù)據(jù)采集與預(yù)處理

1.1 數(shù)據(jù)采集

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

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

1.2 數(shù)據(jù)預(yù)處理

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

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

AS_PATH具有4種類型：

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

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

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

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

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

圖2 AS_PATH顯示格式

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

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

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

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

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

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

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

經(jīng)過上述處理后提取出的AS網(wǎng)絡(luò)結(jié)構(gòu)的頂點和邊數(shù)據(jù)，需要再分別進行去重和格式異常數(shù)據(jù)清洗操作，去除數(shù)據(jù)本身對算法的干擾，便于進一步分析該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化情況。

2 特征與建模

針對大規(guī)模復(fù)雜網(wǎng)絡(luò)的整體結(jié)構(gòu)的研究，主要的途徑是利用各種方法計算和分析其在拓?fù)浣Y(jié)構(gòu)上的特征，借助一些特征指標(biāo)來實現(xiàn)對網(wǎng)絡(luò)特征分析的量化研究。這些特征參數(shù)包括：節(jié)點總數(shù)、邊總數(shù)、平均最短路徑長度、網(wǎng)絡(luò)直徑、平均度、最大節(jié)點度及其對應(yīng)節(jié)點、節(jié)點度大于平均度的節(jié)點所占比例、平均集聚系數(shù)、網(wǎng)絡(luò)核數(shù)、社團數(shù)和社團模塊度等。本文根據(jù)15年的IPv6 AS動態(tài)數(shù)據(jù)從以上特征維度進行了拓?fù)浣Y(jié)構(gòu)分析，并對富人俱樂部、自相似性、冪律分布等特性進行了驗證。

2.1 靜態(tài)特征分析

針對2003年5月-2018年5月的IPv6 BGP數(shù)據(jù)，統(tǒng)計分析AS級網(wǎng)絡(luò)的靜態(tài)特征，各維度特征值如表1、表2所示。

表1 IPv6 AS級網(wǎng)絡(luò)靜態(tài)特征匯總

表2 IPv6 AS級網(wǎng)絡(luò)靜態(tài)特征匯總

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

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

2.2 網(wǎng)絡(luò)特性驗證

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

圖3 核心20%節(jié)點與全部節(jié)點特征對比

2.2.1冪律分布

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

Y=aX-b

(1)

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

logY=logaX-b=loga-blogX

(2)

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

y=c-bx

(3)

即針對冪律公式的X和Y取雙對數(shù)后，在坐標(biāo)軸上應(yīng)呈現(xiàn)線性方程圖。

將上述概念應(yīng)用到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)領(lǐng)域，節(jié)點間連線數(shù)量表現(xiàn)為各節(jié)點的度值，因此判斷網(wǎng)絡(luò)拓?fù)涫欠穹蟽缏煞植?，需對網(wǎng)絡(luò)的度分布情況做分析驗證。

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

(b) 2006年

(c) 2009年

(d) 2012年

(e) 2015年

(f) 2018年圖4 2003年-2018年IPv6 AS網(wǎng)絡(luò)度分布及冪律分布圖

2.2.2富人俱樂部特性

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

(4)

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

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

表3 每年由度值排名前r的節(jié)點構(gòu)成的富人俱樂部 的連通性統(tǒng)計

圖5是選取2018年的IPv6 AS級真實網(wǎng)絡(luò)數(shù)據(jù)，最大度為4 268，4個子圖分別表示度大于500、300、100、50的網(wǎng)絡(luò)結(jié)構(gòu)圖?？梢悦黠@看出：度大于50的節(jié)點已經(jīng)屈指可數(shù)，度大的節(jié)點占整個網(wǎng)絡(luò)規(guī)模的極少數(shù)，只有少數(shù)節(jié)點連接的邊數(shù)很多，絕大多數(shù)的節(jié)點度很小；度大的節(jié)點間相互連接密切，體現(xiàn)了網(wǎng)絡(luò)的富人俱樂部特性。

圖5 2018年IPv6 AS網(wǎng)絡(luò)度大的節(jié)點連接情況

2.2.3自相似性

自相似性作為分形理論的一個重要特性，越來越多地引起了廣大研究者的興趣和關(guān)注。在復(fù)雜網(wǎng)絡(luò)中，對其自相似性的研究意義主要在于以自相似度研究為基礎(chǔ)來準(zhǔn)確進行鏈路預(yù)測、有效檢測社團網(wǎng)絡(luò)以及探索復(fù)雜網(wǎng)絡(luò)的演化機制等[17]。目前，針對復(fù)雜網(wǎng)絡(luò)自相似性的研究主要集中在對其節(jié)點或自身局部的相似性的研究，而在復(fù)雜網(wǎng)絡(luò)全局拓?fù)涮匦詫用嫔系南嗨贫妊芯繕O少甚至沒有。本文主要基于統(tǒng)計和分析全局的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征來驗證2003年-2018年動態(tài)網(wǎng)絡(luò)的自相似程度。

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

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

(5)

計算相應(yīng)的樣本方差：

(6)

則R/S的統(tǒng)計值為：

n≥1

(7)

若存在如下關(guān)系:

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

? 若0.5

? 若0

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

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

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

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

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

(4) 計算差分序列的自相關(guān)系數(shù)H：

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

表4 各全局靜態(tài)特征時間序列Hurst指數(shù)

2.3 網(wǎng)絡(luò)建模

為了更準(zhǔn)確地預(yù)測和評估未來IPv6 AS級互聯(lián)網(wǎng)的發(fā)展趨勢，基于對IPv6 AS網(wǎng)絡(luò)歷年來拓?fù)浣Y(jié)構(gòu)及特征的上述分析結(jié)果，考慮到網(wǎng)絡(luò)演化過程中出現(xiàn)的變化，本文在分析網(wǎng)絡(luò)拓?fù)涮匦缘幕A(chǔ)上，利用差分自回歸移動平均模型(ARIMA(p,d,q))對主要特征的時間序列進行了建模，為未來的拓?fù)渥兓厔葑鞒鲱A(yù)測。

2.3.1基礎(chǔ)模型

ARMA(p,q)模型是目前已經(jīng)相對成熟和完善的用于分析時間序列的重要模型之一，它分為兩個主要步驟，其中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模型的基礎(chǔ)上增加了差分的操作，用來得到平穩(wěn)序列，保證數(shù)據(jù)的穩(wěn)定性，其中d是差分的階數(shù)。

2.3.2平穩(wěn)性檢驗及處理

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

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

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

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

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

2.3.3模型識別

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

圖8 節(jié)點總數(shù)時間序列二次差分后的偏自相關(guān)圖

2.3.4樣本擬合

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

圖9 節(jié)點總數(shù)時間序列與模型預(yù)測結(jié)果對比圖

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

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

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

2.4 分析與評價

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

3 結(jié) 語

本文通過對2003年-2018年15年間的IPv6 AS級網(wǎng)絡(luò)靜態(tài)特征及網(wǎng)絡(luò)特性的分析，觀察網(wǎng)絡(luò)規(guī)模擴增過程中各特征量的變化，總結(jié)IPv6 AS級網(wǎng)絡(luò)拓?fù)涞难莼?guī)律，并通過建模分析網(wǎng)絡(luò)拓?fù)錉顟B(tài)，預(yù)測發(fā)展趨勢。根據(jù)分析結(jié)果可以推測，未來IPv6 AS級網(wǎng)絡(luò)規(guī)?？傮w會繼續(xù)呈上升趨勢增長，但平均度、平均最短路徑長度、平均集聚系數(shù)和社團模塊度等全局靜態(tài)特征變化不大，未來將依然處于相對穩(wěn)定的狀態(tài)，這符合IPv6 AS級網(wǎng)絡(luò)特性和發(fā)展規(guī)律。