吳元立，司光亞，羅　批

(1.國防大學 信息作戰(zhàn)與指揮訓練教研部, 北京　100091； 2.國防大學 研究生院, 北京　100091；3.中國人民解放軍第309醫(yī)院， 北京　100091)

?

多約束條件下互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓撲生成方法*

吳元立1,2,3，司光亞1，羅批1

(1.國防大學 信息作戰(zhàn)與指揮訓練教研部, 北京100091； 2.國防大學 研究生院, 北京100091；3.中國人民解放軍第309醫(yī)院， 北京100091)

摘要：互聯(lián)網(wǎng)骨干網(wǎng)是網(wǎng)絡流量的中樞傳輸系統(tǒng)，其路由器級拓撲結(jié)構(gòu)對于網(wǎng)絡抗毀性分析具有重要意義。由于難以獲取互聯(lián)網(wǎng)骨干網(wǎng)路由器級的真實拓撲，通過分析骨干網(wǎng)的形成因素，將地理位置、節(jié)點間聯(lián)系強度、基礎設施費用、魯棒性等因素結(jié)合起來，提出一種多約束條件下的互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓撲生成方法。該方法既可以構(gòu)造難以公開獲取網(wǎng)絡測量數(shù)據(jù)的骨干網(wǎng)，也可以用來生成某一骨干網(wǎng)的多種替身拓撲集。通過現(xiàn)實中的互聯(lián)網(wǎng)骨干網(wǎng)作為實例，驗證了方法的有效性。

關鍵詞：互聯(lián)網(wǎng)；拓撲生成；網(wǎng)絡抗毀性

互聯(lián)網(wǎng)實際上是多個網(wǎng)絡互聯(lián)而形成的覆蓋全球的網(wǎng)絡，大型網(wǎng)絡運營商擁有并維護著由路由器和光纖組成的骨干網(wǎng)，這些骨干網(wǎng)是互聯(lián)網(wǎng)流量的中樞傳輸系統(tǒng)，且國家關鍵基礎設施越來越依賴這些骨干網(wǎng)實現(xiàn)業(yè)務協(xié)同，骨干網(wǎng)上的微小擾動會影響整個互聯(lián)網(wǎng)甚至其他關鍵基礎設施的運行[1-2]。由于無法直接在互聯(lián)網(wǎng)骨干網(wǎng)上展開實驗，人們通過構(gòu)建路由器級拓撲，因此，依托建模仿真手段從網(wǎng)絡安全視角研究網(wǎng)絡抗毀性。骨干網(wǎng)路由器級拓撲是對骨干網(wǎng)的抽象表達，節(jié)點代表路由器，邊代表路由器之間的一跳連接關系，路由器級拓撲既可以表示網(wǎng)絡連接關系，也可以直接映射到地理信息系統(tǒng)，并可描述與其他國家關鍵基礎設施的關聯(lián)。由于種種原因，難以獲取互聯(lián)網(wǎng)骨干網(wǎng)路由器級的真實拓撲，因此，如何生成符合現(xiàn)實網(wǎng)絡特性的互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓撲逐漸成為網(wǎng)絡科學領域的研究熱點，美軍X計劃[3]也把生成不同規(guī)模的符合真實網(wǎng)絡特性的路由器級網(wǎng)絡拓撲集作為重點研究方向。

一個自治系統(tǒng)通常由多個路由器通過網(wǎng)絡鏈路相連組成，一些大型的自治系統(tǒng)(如中國電信)所包含的路由器級拓撲可以覆蓋整個國家。不同于自治系統(tǒng)級的邏輯拓撲，路由器級拓撲受到地理位置、網(wǎng)絡運營商經(jīng)費限制以及用戶需求等因素的約束，表現(xiàn)出一種多約束條件下追求目標優(yōu)化的拓撲結(jié)構(gòu)特性。但是，大型網(wǎng)絡運營商不愿意公布其拓撲結(jié)構(gòu)。為了獲取研究互聯(lián)網(wǎng)所需的路由器級拓撲結(jié)構(gòu)，存在靜態(tài)生成和動態(tài)生成兩類方法，靜態(tài)生成是指從拓撲測量得到的數(shù)據(jù)集(如互聯(lián)網(wǎng)應用數(shù)據(jù)分析中心(CenterforAppliedInternetDataAnalysis,CAIDA)[4]和DIMES[5]項目)中去提取實際網(wǎng)絡拓撲結(jié)構(gòu)的方法，動態(tài)生成是指根據(jù)研究獲得的拓撲特性，研究如何生成能夠刻畫互聯(lián)網(wǎng)拓撲結(jié)構(gòu)的方法。文獻[6-8]給出了多種靜態(tài)生成方法，例如，文獻[6]在拓撲數(shù)據(jù)源上使用RocketFuel和SCAN項目的實際測量數(shù)據(jù)，選取了美國主要的網(wǎng)絡運營商，構(gòu)建其骨干網(wǎng)并確定骨干網(wǎng)間的互聯(lián)節(jié)點，試圖盡可能準確、細粒度地構(gòu)建美國互聯(lián)網(wǎng)路由器級骨干網(wǎng)絡模型。但是由于互聯(lián)網(wǎng)規(guī)模大、異構(gòu)、非集中管理等特性[9]以及網(wǎng)絡測量的局限性，這種方法不僅非常費時費力，且結(jié)果并不一定準確、全面。

因此，研究人員更多地依賴動態(tài)生成方法來構(gòu)建路由器級拓撲結(jié)構(gòu)，文獻[10]提出了基于啟發(fā)式的優(yōu)化算法，在生成過程中主要考慮了路由器性能和網(wǎng)絡績效兩個度量指標，生成的拓撲結(jié)構(gòu)具有優(yōu)化設計特點，但該模型缺乏對節(jié)點地理信息的考慮。文獻[11]認為骨干網(wǎng)絡拓撲構(gòu)建的驅(qū)動因素由設施費用、預期性能、地理限制因素、節(jié)點/鏈路失效恢復四方面構(gòu)成，提出了多項式時間的HINT拓撲生成算法，最后通過與AT&T等三個骨干網(wǎng)對比，該方法具有90%以上的相似性，但該方法在構(gòu)造拓撲時所需數(shù)據(jù)源較多，在流量約束方面忽視了流量的非對稱性。TopGen[12]把路由器的技術(shù)限制作為約束條件，提出了一種通用的路由器級拓撲生成方法，該方法依據(jù)帶寬和路由器最大連接限制，將路由器節(jié)點分為核心節(jié)點、邊界節(jié)點、網(wǎng)關節(jié)點和接入節(jié)點，并提出了這些路由器的約束條件和拓撲生成算法。KU-LocGen[13]在節(jié)點地理位置限制的基礎上，提出了包含多種生成模型的路由器級骨干網(wǎng)絡拓撲生成算法，在拓撲生成集合上進行了費用圖譜分析，但缺乏對節(jié)點間強度和網(wǎng)絡魯棒性因素的考慮。以往的研究多是面向自治系統(tǒng)級的邏輯拓撲研究，或是在路由器級拓撲研究中忽視了地理限制、節(jié)點間聯(lián)系強度、基礎設施費用、魯棒性等影響骨干網(wǎng)建設的重要因素。

綜合文獻[11]和文獻[13]的思想，在Waxman模型的基礎上考慮地理限制、基礎設施費用、魯棒性等因素，并引入節(jié)點間聯(lián)系強度作為拓撲生成參數(shù)，本文研究提出一種多約束條件下的互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓撲生成方法。

1拓撲生成方法

1.1Waxman模型

不同于數(shù)萬個節(jié)點的自治系統(tǒng)級拓撲所對應的BA[14]生成模型，擁有數(shù)十個節(jié)點的大型互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓撲往往與Waxman模型更為匹配[15-16]。Waxman模型是隨機圖拓撲生成的代表，類似于Erd?s-Rényi模型，模型將節(jié)點按泊松分布放置在平面上，邊的添加依賴于節(jié)點間歐幾里得距離來決定的概率。對于節(jié)點A和節(jié)點B而言，其連邊概率為：

(1)

其中：d是節(jié)點對之間的歐幾里得距離；L是所有節(jié)點對之間的最大歐幾里得距離；α和β的取值范圍是(0,1)，α代表節(jié)點間連邊的概率，β代表長邊相對于短邊的概率。

1.2骨干網(wǎng)形成因素分析

1)地理位置。BA[14]等傳統(tǒng)算法是針對邏輯拓撲生成的，沒有考慮網(wǎng)絡拓撲節(jié)點的地理位置限制。對大型網(wǎng)絡而言，核心路由器或接入點(PointofPresence,PoP)節(jié)點的位置受到多種經(jīng)濟和政策因素制約，通常部署在多個網(wǎng)絡光纖交匯的人口密集處，而不是如Waxman模型中節(jié)點的隨機分布。本算法面向大尺度的骨干網(wǎng)，用經(jīng)緯度坐標表示節(jié)點的位置。一方面，在生成已有骨干網(wǎng)的不同特性的替身拓撲時，可直接使用其公開的路由器節(jié)點的地理位置。另一方面，對于難以獲取拓撲地理位置的骨干網(wǎng)可通過人口密度數(shù)據(jù)集來估算骨干網(wǎng)路由器節(jié)點可能的地理位置[17]，而地理位置的粒度取決于骨干網(wǎng)的規(guī)模和人口密度數(shù)據(jù)集的精度。例如，國際地球科學信息網(wǎng)絡中心(CenterforInternationalEarthScienceInformationNetwork,CIESIN)[18]提供了多種分辨率的全球人口密度數(shù)據(jù)集，在粒度選擇上可根據(jù)骨干網(wǎng)規(guī)模靈活選擇相應的分辨度，以國家級的骨干網(wǎng)絡為例，可基于1km2分辨率的人口密度數(shù)據(jù)集并指定相應的路由器節(jié)點數(shù)量，采用k-means聚簇算法推算路由器節(jié)點的經(jīng)緯度坐標。k-means算法是基于相似度的聚簇方法，目標是通過迭代計算，使得所有數(shù)據(jù)點與聚簇中心距離的距離總和最小化，此方法常被用來根據(jù)人口密度數(shù)據(jù)集和給定的聚簇中心數(shù)量(路由器節(jié)點數(shù)量)推測可能的聚簇中心點位置[16,19]，這些聚簇中心代表著人口密度的極值點，可用作估算路由器節(jié)點的地理位置。

2)節(jié)點間聯(lián)系強度。路由器節(jié)點間的光纜布線與節(jié)點所在地區(qū)的互聯(lián)網(wǎng)發(fā)展水平息息相關。一般來說，節(jié)點所在地區(qū)的互聯(lián)網(wǎng)發(fā)展水平越好，地區(qū)之間互聯(lián)網(wǎng)信息交換的強度就越大，從保證重要節(jié)點間的服務質(zhì)量并節(jié)省整體建設費用的角度來說，重要節(jié)點間鋪設光纜的可能性就越大。例如中國電信骨干網(wǎng)絡在北京、上海、廣州三個重要城市之間就采用了全互聯(lián)的拓撲連接結(jié)構(gòu)。本文基于Gravity模型計算網(wǎng)絡聯(lián)系強度，Gravity模型源于牛頓的萬有引力定律，即兩個物體之間的作用力與兩個物體的質(zhì)量乘積成正比，與兩個物體的距離的平方成反比。這個物理學的定律通常被社會學家延伸到社會科學等領域用來對地區(qū)間人員、貨物和信息的流動進行建模和分析。通常，根據(jù)公開的人口的數(shù)據(jù)和地理位置信息，用Gravity模型可以計算出兩個地區(qū)之間聯(lián)系的緊密程度，例如城市間的交通運輸聯(lián)系強度。Gravity模型也同樣適用于地區(qū)之間互聯(lián)網(wǎng)流量強度的預測[20-21]，但不同于實體貨物的傳輸，由于網(wǎng)絡的高速傳輸速度，地區(qū)之間的距離對互聯(lián)網(wǎng)流量交換強度幾乎沒有影響，而地區(qū)的互聯(lián)網(wǎng)發(fā)展水平成為地區(qū)間網(wǎng)絡流量聯(lián)系強度的主體因素[22]，因此選擇互聯(lián)網(wǎng)上網(wǎng)人數(shù)作為節(jié)點互聯(lián)網(wǎng)發(fā)展水平的衡量標準。

3)建設費用。費用對路由器級拓撲影響很大，大型網(wǎng)絡運營商希望通過有限的資金來滿足網(wǎng)絡通信服務的需要。所以，即使不把費用作為拓撲生成過程的一部分加以考慮，也要在拓撲生成集合的基礎上進行費用分析，以篩選出滿足特定費用約束的模型參數(shù)集，在這個參數(shù)集上可以進一步分析哪些模型參數(shù)會使網(wǎng)絡效率更高，魯棒性更好。一般來說，一對節(jié)點之間的光纖布線由兩部分。分為一次性的基礎設施投入(購買光纜、光交換設備、挖掘以及光纜的安裝費用)和日常維護費用。挖掘費用與節(jié)點間的距離成正比，光纜的費用取決于其長度和質(zhì)量。由于大型骨干網(wǎng)通?？缭竭|闊疆域，普遍認為挖掘和鋪設費用是光纜費用的主要組成部分[10,23]，即距離成為衡量光纜費用的主要因素。因此，骨干網(wǎng)絡的總體費用C表達如下：

(2)

其中：di,j是節(jié)點i，j之間的距離，單位為km；vc為每千米所需費用。

4)魯棒性。魯棒性對承載著巨大流量的骨干網(wǎng)而言至關重要，互聯(lián)網(wǎng)前身ARPANET的目的就是為了能夠在部分節(jié)點或連邊失效時在剩余節(jié)點之間仍然保持通信可達性。骨干網(wǎng)在設計時需要充分考慮網(wǎng)絡魯棒性，某個拓撲結(jié)構(gòu)若在任意一個網(wǎng)絡要素發(fā)生失效時仍然能夠?qū)⑹苡绊懙木W(wǎng)絡流量重新轉(zhuǎn)發(fā)，那么就可以認為這個網(wǎng)絡拓撲結(jié)構(gòu)具備一定的魯棒性。在圖論中，使得一對節(jié)點分屬于不同的連通片所需去除的一組節(jié)點成為這對節(jié)點的點割集(vertexcutset)。包含節(jié)點數(shù)最少的割集稱為極小割集(minimumcutset)。普遍認為，具有較好魯棒性的網(wǎng)絡拓撲應是一個二連通圖(two-connectedgraph)[24]，即對圖G(V，E)中的任意兩個節(jié)點vi,vj，設k(vi,vj)是vi,vj的極小割集所包含的節(jié)點數(shù)量，那么應滿足：

k(vi,vj)≥2,?vi,vj∈V

(3)

算法1給出了二連接圖的判斷方法，即魯棒性約束算法。

算法1　魯棒性約束

1.3拓撲生成方法

節(jié)點間的連邊概率由式(4)決定：

(4)

(5)

兩個節(jié)點間的連接概率由其地理距離和互聯(lián)網(wǎng)人數(shù)共同決定。對某一特定算法參數(shù)集(包括α，β和強度系數(shù)ω)而言，算法運行一次會得到一個拓撲，由于概率的作用，算法多次計算后會到一個拓撲集合。

2拓撲生成方法評估

2.1數(shù)據(jù)集

選擇中國電信和美國高級網(wǎng)絡服務(AdvancedNetworkService,ANS)兩大互聯(lián)網(wǎng)骨干網(wǎng)作為算法評估的樣本(如圖1所示)，其拓撲數(shù)據(jù)集來自TopologyZoo項目[25]，該項目認為網(wǎng)絡測量方法無法獲得準確、全面的網(wǎng)絡拓撲和拓撲元信息，而網(wǎng)絡服務提供商公布的網(wǎng)絡結(jié)構(gòu)往往較準確，且包含了節(jié)點和鏈路等多種元信息，通過圖形處理手段將全球近百個網(wǎng)絡服務提供商發(fā)布的骨干網(wǎng)絡拓撲圖轉(zhuǎn)換成統(tǒng)一的拓撲數(shù)據(jù)表達。拓撲生成所使用的地理位置直接使用該拓撲數(shù)據(jù)中節(jié)點的經(jīng)緯度坐標，例如位于北京的核心路由器節(jié)點的坐標為(東經(jīng)116.397，北緯39.908)，基于經(jīng)緯度坐標就可以計算得到城市間的距離。

(a) 中國電信(a) China Telecom

(b) 美國ANS(b) America ANS圖1　骨干網(wǎng)拓撲結(jié)構(gòu)Fig.1　Backbone network topology

對算法中節(jié)點聯(lián)系強度計算所需的互聯(lián)網(wǎng)人數(shù)數(shù)據(jù)，中國電信拓撲中各節(jié)點所在城市數(shù)據(jù)來自文獻[26]，美國ANS拓撲中各節(jié)點所在城市數(shù)據(jù)來自文獻[27]。以中國為例，文獻[26]中北京IPv4地址數(shù)的比例為25.65%，上海為4.48%，然后通過式(5)即可算出北京與上海間的流量聯(lián)系強度系數(shù)。

2.2拓撲評估指標

由于每個骨干網(wǎng)拓撲在設計上各有其特點，評估生成的拓撲結(jié)構(gòu)是否與現(xiàn)實拓撲相匹配通常通過一些特定的、可量化的拓撲指標來計算[28]。選取以下三種拓撲參數(shù)作為評估指標：

1)節(jié)點度分布：節(jié)點度分布指網(wǎng)絡中隨機選擇的節(jié)點度為k的概率[29]，是比較網(wǎng)絡拓撲結(jié)構(gòu)的重要指標。

2)最短路徑跳數(shù)：指任意兩個節(jié)點之間的最短路徑跳數(shù)[30]，代表了數(shù)據(jù)包通過路由器轉(zhuǎn)發(fā)的次數(shù)，可用來衡量網(wǎng)絡效率。

3)鏈路長度：鏈路長度指兩個路由器節(jié)點之間的鏈路(通常是光纜)的物理長度，決定著節(jié)點間的鏈路延遲和總體建設費用。

4)網(wǎng)絡效率(全局連通效率)：網(wǎng)絡效率是網(wǎng)絡可靠性的主要指標。定義節(jié)點i到j的連通效率為：

(6)

其中，di,j是節(jié)點i到j的最短路徑跳數(shù)，網(wǎng)絡效率為：

(7)

其中N為網(wǎng)絡節(jié)點總數(shù)。

2.3評估方法

通過Visualstudio2012對1.3節(jié)的算法進行了代碼實現(xiàn)，在節(jié)點數(shù)據(jù)集上采用2.1節(jié)的數(shù)據(jù)。1.3節(jié)算法包含了α和β兩個可變參數(shù)，針對某一個骨干網(wǎng)，在算法評估過程中循環(huán)遍歷α和β的取值范圍(0,1)，每次參數(shù)的增量設為0.01。為了消除隨機數(shù)帶來的偏差，在每個參數(shù)集α和β的計算上重復計算100次，計算并記錄節(jié)點度、最短路徑跳數(shù)和鏈路長度這三個拓撲指標的均值和方差，將其作為與真實拓撲結(jié)構(gòu)比較的標準。因此，為了覆蓋拓撲生成的整個參數(shù)空間，對每個骨干網(wǎng)絡拓撲節(jié)點集合需進行100萬次(100×100×100=1 000 000)指標計算。將生成的拓撲指標與現(xiàn)實網(wǎng)絡拓撲指標匹配較好的參數(shù)集稱為“匹配參數(shù)集”。表1給出了中國電信和ANS真實拓撲結(jié)構(gòu)與“匹配參數(shù)集”拓撲結(jié)構(gòu)的指標對比情況，μ為均值，σ為方差。其中，中國電信的“匹配參數(shù)集”為α= 0.31，β=0.19?？梢钥闯觯ヅ鋮?shù)集的節(jié)點度、最短路徑以及鏈路長度均與真實拓撲較為匹配，可作為構(gòu)建真實拓撲不同替身拓撲的參數(shù)指標。

表1　拓撲指標對比(μ/σ)

注：①匹配參數(shù)集為α= 0.31，β=0.19；

②匹配參數(shù)集為α= 0.14，β=0.66；

③匹配參數(shù)集為α= 0.38，β=0.15；

④匹配參數(shù)集為α= 0.27，β=0.49。

表2距離和流量聯(lián)系強度影響對比

Tab.2Comparisonofdistanceandtrafficexchangestrength

節(jié)點對距離/km距離因子E流量強度因子γ連邊概率P北京-廣州18860.2280.1900.114北京-武漢10470.4390.0480.157北京-哈爾濱10570.4360.4360.146

可以看出，兩點間的連接概率由距離和互聯(lián)網(wǎng)人數(shù)共同決定，距離較近的城市間E值較大，使得E北京-武漢≈E北京-哈爾濱>E北京-廣州；互聯(lián)網(wǎng)人數(shù)更多的城市間連接強度系數(shù)更大，使得γ北京-廣州>γ北京-武漢>γ北京-哈爾濱。在當前拓撲參數(shù)(α= 0.31，β=0.19，強度系數(shù)ω=0.69)的情況下、節(jié)點間的連接概率中，距離起主要作用，互聯(lián)網(wǎng)人數(shù)起次要作用。相對武漢而言，盡管廣州的互聯(lián)網(wǎng)人數(shù)更多，但是由于北京到廣州距離較長，綜合使得P北京-廣州

通過相關研究比較，選擇了KU-Locgen[13]拓撲生成器的Waxman模型計算其“匹配參數(shù)集”，可以看出本文的拓撲生成算法在平均度指標一樣的情況下，在鏈路長度這個指標上與現(xiàn)實拓撲更為匹配，這是由于考慮了節(jié)點間的聯(lián)系強度對生成邊的影響，而不是簡單地考慮長短邊的比例因素。同時，在網(wǎng)絡效率指標的比較上，本文算法和KU-Locgen[13]算法較為接近，但均略低于真實網(wǎng)絡拓撲的網(wǎng)絡效率，這可能因為真實網(wǎng)絡拓撲往往是經(jīng)過設計部門的反復優(yōu)化后確定的一次具有較高網(wǎng)絡效率的拓撲，而本文算法由于拓撲生成中隨機性因素的作用，取的是在某一匹配參數(shù)集下的網(wǎng)絡效率均值，故該值略低于真實網(wǎng)絡拓撲的網(wǎng)絡效率。

以中國電信骨干網(wǎng)為例，如圖2所示，在可用參數(shù)集α= 0.31，β=0.19的基礎上，由于隨機數(shù)的因素，算法每次都會生成不同的拓撲結(jié)構(gòu)。通過對生成的拓撲集施加不同的約束可篩選得到不同性質(zhì)的網(wǎng)絡拓撲特例，例如，通過施加算法1中的魯棒性約束算法，可得到具備較好魯棒性的拓撲結(jié)構(gòu)(如圖2(b)所示)，該拓撲結(jié)構(gòu)在單個節(jié)點失效的情況下可保證其他任意節(jié)點對之間的連通性；通過加入鏈路總長度約束，可得到具有較高延遲的拓撲結(jié)構(gòu)(如圖2(c)所示)。

2.4費用約束分析

費用是拓撲生成后的定量過濾。根據(jù)式(2)的費用計算方法，設vc為10萬元，可計算得到中國電信和美國ANS骨干網(wǎng)的實際建設費用分別為60億和28.2億元?；贛ATLAB R2009b對拓撲生成算法的參數(shù)空間進行總體建設費用分析，可得到如圖3所示的費用在參數(shù)空間上的分布圖。

(a) 實際拓撲結(jié)構(gòu)(a) Actual Topology

(b) 魯棒性拓撲(生成)(k(vi,vj)≥2)(b) Robustness topology(k(vi,vj)≥2)

(c) 高延遲拓撲(生成)(c) High latency topology圖2　中國電信拓撲結(jié)構(gòu)比較(α= 0.31，β=0.19)Fig.2　Alternative topology for China Telecom(α= 0.31，β=0.19)

(a) 中國電信(a) China Telecom

(b) 美國ANS(b) America ANS圖3　生成算法參數(shù)集費用分布圖Fig.3　Cost distribution for topology parameters

通常，骨干網(wǎng)絡運營商的建設費用是有限的，假設中國電信和美國ANS在現(xiàn)有節(jié)點集基礎上的建設費用約束分別為60億～70億元和25億～30億元，那么滿足上述費用約束的參數(shù)集分布如圖4所示。通過對參數(shù)集進行費用約束分析，可以篩選出符合特定費用約束的參數(shù)集，進而構(gòu)造相應的拓撲結(jié)構(gòu)。

(a) 中國電信(60億～70億元)(a) China Telecom (6 billions to 7 billions)

(b) 美國ANS(25億～30億元)(b) America ANS(2.5 billions to 3 billions)圖4　滿足費用約束的參數(shù)分布Fig.4　Parameters distribution under cost constraint

3結(jié)論

地理位置、節(jié)點間聯(lián)系強度、基礎設施費用和魯棒性是互聯(lián)網(wǎng)骨干網(wǎng)形成的關鍵因素，所提多約束條件下的骨干網(wǎng)路由器級拓撲生成方法，對需要依托路由器級網(wǎng)絡拓撲進行研究的網(wǎng)絡抗毀性分析研究等領域有重要意義。

參考文獻(References)[1]Buldyrev S V, Roni P， Gerald P, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028.

[2]International Cable Protection Committee (ICPC). Submarine cable network security[EB/OL]. (2009-01-01)[2015-06-31]. http://www.iscpc.org/.

[3]李健, 溫柏華. 美軍網(wǎng)絡力量[M]. 沈陽: 遼寧大學出版社, 2013.

LI Jian, WEN Baihua. US network power[M]. Shenyang: Liaoning University Press, 2013. (in Chinese)

[4]Huffaker B, Plummer D, Moore D, et al. Topology discovery by active probing[C]// Proceedings of Symposium on Applications and the Internet (SAINT) Workshops, 2002: 90-96.[5]Shir E, Shavitt Y. DIMES: let the Internet measure itself[J]. Computer Communication Review, 2005, 35(5): 71-74.[6]Liljenstam M, Liu J, Nicol D M. Development of an Internet backbone topology for large-scale network simulations[C]// WSC′03 Proceedings of the 35th Conference on Winter Simulation: Driving Innovation, 2003: 694-702.

[7]Zhou S, Mondragón R J. Accurately modeling the Internet topology[J]. Physical Review E, 2008, 70(6): 066108.

[8]Tian Y, Dey R, Liu Y, et al. China's Internet: topology mapping and geolocating[C]// Proceedings of IEEE INFOCOM, 2012: 2531-2535.

[9]Sally F, Vern P. Difficulties in simulating the Internet[J]. IEEE/ACM Transactions on Networking, 2001, 9(4): 392-403.[10]Li L. A first-principles approach to understanding the Internet’s router-level topology[J]. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2004: 3-14.

[11]Ma X Z, Kim S, Harfoush K. Towards realistic physical topology models for Internet backbone networks[C]//Proceedings of 6th International Symposium on High Capacity Optical Networks and Enabling Technologies, 2009: 36-42.[12]Scholtes I， Botev J, Esch M, et al. TopGen-internet router-level topology generation based on technology constraints[C]// Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, 2008.

[13]Jabbar A, Shi Q, Hameed M, et al. ResiliNets topology modelling[EB/OL]. (2012-05-03)[2015-06-31]. https://wiki.ittc.ku.edu/resilinets/Topology_Modelling.

[14]Albert R, Barabási A. Statistical mechanics of complex networks [J]. Reviews of Modern Physics, 2002, 74: 47-49.[15]Waxman B M. Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622.

[16]Sterbenz J P G, Etinkaya E K, Hameed M A, et al. Evaluation of network resilience, survivability, and disruption tolerance: analysis, topology generation, simulation, and experimentation (invited paper)[J]. Telecommunication Systems, 2011, 52(2): 705-736.

[17]Lakhina A, Byers J W, Crovella M, et al. On the geographic location of Internet resources[J]. IEEE Journal on Selected Areas in Communications, 2003, 21(6): 934-948.

[18]Socioeconomic Data and Applications Center. Gridded population of the world (GPW), V3[EB/OL][2015-06-31].http://sedac.ciesin.columbia.edu/gpw, 2005.

[19]Mahmood A H, Jabbar A, Cetinkaya E K, et al. Deriving network topologies from real world constraints[C]// Proceedings of IEEE in GLOBECOM Workshops (GC Wkshps), 2010: 400-404.

[20]Crain J K. Assessing resilience in the global undersea cable infrastructure[R].DTIC Document, 2012.

[21]Omer M, Nilchiani R, Mostashari A. Measuring the resilience of the global Internet infrastructure system[C]//Proceedings of 3rd Annual IEEE International Systems Conference, 2009:156-162.

[22]Chang H, Roughan M, Uhlig S, et al. The many facets of Internet topology and traffic[J]. Networks and Heterogeneous Media, 2006, 1(4): 569-600.

[23]Bailey D, Wright E. Connecting fibers-practical fiber optics-5[J]. Practical Fiber Optics, 2003: 97-119.

[24]Habibi D, Nguyen H N, Phung Q V, et al. Establishing physical survivability of large networks using properties of two-connected graphs[C]// Proceedings of IEEE Region 10 on TENCON, 2005: 1-5.

[25]Knight S, Nguyen H X, Falkner N, et al. The internet topology zoo[J]//Proceedings of IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1765-1775.

[26]中國互聯(lián)網(wǎng)絡信息中心. 2014年中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告[EB/OL]. (2014-07-01)[2015-06-31]. http://www.cnnic.net.cn/gywm/xwzx/rdxw/2014/201407/W020140721559080702009.pdf.

CNNIC. Statics report for China Internet development in 2014[EB/OL]. (2014-07-01)[2015-06-31]. http://www.cnnic.net.cn/gywm/xwzx/rdxw/2014/201407/W020140721559080702009.pdf. (in Chinese)

[27]Internet World Stats. Internet usage statistics[EB/OL]. (2014-06-02)[2015-06-31]. http://www.internetworldstats.com/am/us.htm, 2015.

[28]Zegura E W, Calvert K L, Acharjee S B. How to model an internetwork[C]//Proceedings of INFOCOM'96 15th Annual Joint Conference of the IEEE Computer Societies, 1996, 2: 594-602.[29]汪小帆， 李翔， 陳關榮. 網(wǎng)絡科學導論[M]. 北京：高等教育出版社， 2012.

WANG Xiaofan，LI Xiang, CHEN Guanrong. Network science: an introduction[M]. Beijing: Higher Education Press， 2012. (in Chinese)

[30]Haddadi H, Rio M, Iannaccone G, et al. Network topologies: inference, modeling, and generation[J]. IEEE Journal on Communications Surveys & Tutorials, 2008, 10(2): 48-69.

Router-level topology generation research for Internet backbone networks under multiple constraints

WU Yuanli1,2,3, SI Guangya1, LUO Pi1

(1.DepartmentofInformationOperation&CommandTraining,NationalDefenseUniversityofChina,Beijing100091,China；2.GraduateSchool,NationalDefenseUniversityofChina,Beijing100091，China;3.The309HospitalofPLA,Beijing100091,China)

Abstract：ThebackbonenetworkisthemainpartoftheInternettraffictransfersystem,andtherouter-leveltopologyofbackbonenetworkisofgreatsignificancefortheresearchonnetworksurvivability.Duetovariousreasons,itisdifficulttogetrealInternetbackbonerouterleveltopology.Byanalyzingtheformingdrivingfactorsofbackbonenetwork,thegeographicalconstraints,theexchangingstrengthofnodes,infrastructurecostandrobustness,etc.werecombined;therouter-leveltopologygenerationmethodforInternetbackbonenetworksundermultipleconstraintswasproposed.Themethodcangeneraterouterleveltopologyfornetworkwhichcannotbeinferredfrompubliclyaccessiblemeasurementdata,andcangeneratetopologysetthatconsistsofrealisticalternativesforabackbonenetwork.Finally,theeffectivenessofthemethodisverifiedbytworealInternetbackbonenetworks.

Keywords：Internet;topologygeneration;networksurvivability

doi:10.11887/j.cn.201603028

收稿日期：2015-04-08

基金項目：國家自然科學基金資助項目(U1435218，61273189，61403401，61174035)

作者簡介：吳元立(1985—)，男，遼寧燈塔人，博士研究生，E-mail：dtnudt@126.com； 司光亞(通信作者)，男，教授，博士，博士生導師，E-mail：sgy863@sina.com

中圖分類號：TP393

文獻標志碼：A

文章編號：1001-2486(2016)03-167-07

http://journal.nudt.edu.cn