多約束條件下互聯網骨干網路由器級拓撲生成方法*

吳元立，司光亞，羅　批

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

?

多約束條件下互聯網骨干網路由器級拓撲生成方法*

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

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

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

關鍵詞：互聯網；拓撲生成；網絡抗毀性

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

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

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

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

1拓撲生成方法

1.1Waxman模型

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

(1)

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

1.2骨干網形成因素分析

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

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

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

(2)

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

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

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

(3)

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

算法1　魯棒性約束

1.3拓撲生成方法

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

(4)

(5)

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

2拓撲生成方法評估

2.1數據集

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

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

(b) 美國ANS(b) America ANS圖1　骨干網拓撲結構Fig.1　Backbone network topology

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

2.2拓撲評估指標

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

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

2)最短路徑跳數：指任意兩個節點之間的最短路徑跳數[30]，代表了數據包通過路由器轉發的次數，可用來衡量網絡效率。

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

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

(6)

其中，di,j是節點i到j的最短路徑跳數，網絡效率為：

(7)

其中N為網絡節點總數。

2.3評估方法

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

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

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

②匹配參數集為α= 0.14，β=0.66；

③匹配參數集為α= 0.38，β=0.15；

④匹配參數集為α= 0.27，β=0.49。

表2距離和流量聯系強度影響對比

Tab.2Comparisonofdistanceandtrafficexchangestrength

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

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

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

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

2.4費用約束分析

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

(a) 實際拓撲結構(a) Actual Topology

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

(c) 高延遲拓撲(生成)(c) High latency topology圖2　中國電信拓撲結構比較(α= 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　生成算法參數集費用分布圖Fig.3　Cost distribution for topology parameters

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

(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　滿足費用約束的參數分布Fig.4　Parameters distribution under cost constraint

3結論

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

參考文獻(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]李健, 溫柏華. 美軍網絡力量[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]中國互聯網絡信息中心. 2014年中國互聯網絡發展狀況統計報告[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]汪小帆， 李翔， 陳關榮. 網絡科學導論[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