多約束條件下互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓?fù)渖煞椒?

吳元立，司光亞，羅　批

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

?

多約束條件下互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓?fù)渖煞椒?

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

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

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

關(guān)鍵詞：互聯(lián)網(wǎng)；拓?fù)渖?；網(wǎng)絡(luò)抗毀性

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

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

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

綜合文獻(xiàn)[11]和文獻(xiàn)[13]的思想，在Waxman模型的基礎(chǔ)上考慮地理限制、基礎(chǔ)設(shè)施費用、魯棒性等因素，并引入節(jié)點間聯(lián)系強度作為拓?fù)渖蓞?shù)，本文研究提出一種多約束條件下的互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓?fù)渖煞椒ā?/p>

1拓?fù)渖煞椒?/p>

1.1Waxman模型

不同于數(shù)萬個節(jié)點的自治系統(tǒng)級拓?fù)渌鶎?yīng)的BA[14]生成模型，擁有數(shù)十個節(jié)點的大型互聯(lián)網(wǎng)骨干網(wǎng)路由器級拓?fù)渫cWaxman模型更為匹配[15-16]。Waxman模型是隨機圖拓?fù)渖傻拇?，類似于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)算法是針對邏輯拓?fù)渖傻?，沒有考慮網(wǎng)絡(luò)拓?fù)涔?jié)點的地理位置限制。對大型網(wǎng)絡(luò)而言，核心路由器或接入點(PointofPresence,PoP)節(jié)點的位置受到多種經(jīng)濟和政策因素制約，通常部署在多個網(wǎng)絡(luò)光纖交匯的人口密集處，而不是如Waxman模型中節(jié)點的隨機分布。本算法面向大尺度的骨干網(wǎng)，用經(jīng)緯度坐標(biāo)表示節(jié)點的位置。一方面，在生成已有骨干網(wǎng)的不同特性的替身拓?fù)鋾r，可直接使用其公開的路由器節(jié)點的地理位置。另一方面，對于難以獲取拓?fù)涞乩砦恢玫墓歉删W(wǎng)可通過人口密度數(shù)據(jù)集來估算骨干網(wǎng)路由器節(jié)點可能的地理位置[17]，而地理位置的粒度取決于骨干網(wǎng)的規(guī)模和人口密度數(shù)據(jù)集的精度。例如，國際地球科學(xué)信息網(wǎng)絡(luò)中心(CenterforInternationalEarthScienceInformationNetwork,CIESIN)[18]提供了多種分辨率的全球人口密度數(shù)據(jù)集，在粒度選擇上可根據(jù)骨干網(wǎng)規(guī)模靈活選擇相應(yīng)的分辨度，以國家級的骨干網(wǎng)絡(luò)為例，可基于1km2分辨率的人口密度數(shù)據(jù)集并指定相應(yīng)的路由器節(jié)點數(shù)量，采用k-means聚簇算法推算路由器節(jié)點的經(jīng)緯度坐標(biāo)。k-means算法是基于相似度的聚簇方法，目標(biāo)是通過迭代計算，使得所有數(shù)據(jù)點與聚簇中心距離的距離總和最小化，此方法常被用來根據(jù)人口密度數(shù)據(jù)集和給定的聚簇中心數(shù)量(路由器節(jié)點數(shù)量)推測可能的聚簇中心點位置[16,19]，這些聚簇中心代表著人口密度的極值點，可用作估算路由器節(jié)點的地理位置。

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

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

(2)

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

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

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

(3)

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

算法1　魯棒性約束

1.3拓?fù)渖煞椒?/p>

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

(4)

(5)

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

2拓?fù)渖煞椒ㄔu估

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

選擇中國電信和美國高級網(wǎng)絡(luò)服務(wù)(AdvancedNetworkService,ANS)兩大互聯(lián)網(wǎng)骨干網(wǎng)作為算法評估的樣本(如圖1所示)，其拓?fù)鋽?shù)據(jù)集來自TopologyZoo項目[25]，該項目認(rèn)為網(wǎng)絡(luò)測量方法無法獲得準(zhǔn)確、全面的網(wǎng)絡(luò)拓?fù)浜屯負(fù)湓畔?，而網(wǎng)絡(luò)服務(wù)提供商公布的網(wǎng)絡(luò)結(jié)構(gòu)往往較準(zhǔn)確，且包含了節(jié)點和鏈路等多種元信息，通過圖形處理手段將全球近百個網(wǎng)絡(luò)服務(wù)提供商發(fā)布的骨干網(wǎng)絡(luò)拓?fù)鋱D轉(zhuǎn)換成統(tǒng)一的拓?fù)鋽?shù)據(jù)表達(dá)。拓?fù)渖伤褂玫牡乩砦恢弥苯邮褂迷撏負(fù)鋽?shù)據(jù)中節(jié)點的經(jīng)緯度坐標(biāo)，例如位于北京的核心路由器節(jié)點的坐標(biāo)為(東經(jīng)116.397，北緯39.908)，基于經(jīng)緯度坐標(biāo)就可以計算得到城市間的距離。

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

(b) 美國ANS(b) America ANS圖1　骨干網(wǎng)拓?fù)浣Y(jié)構(gòu)Fig.1　Backbone network topology

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

2.2拓?fù)湓u估指標(biāo)

由于每個骨干網(wǎng)拓?fù)湓谠O(shè)計上各有其特點，評估生成的拓?fù)浣Y(jié)構(gòu)是否與現(xiàn)實拓?fù)湎嗥ヅ渫ǔＭㄟ^一些特定的、可量化的拓?fù)渲笜?biāo)來計算[28]。選取以下三種拓?fù)鋮?shù)作為評估指標(biāo)：

1)節(jié)點度分布：節(jié)點度分布指網(wǎng)絡(luò)中隨機選擇的節(jié)點度為k的概率[29]，是比較網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的重要指標(biāo)。

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

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

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

(6)

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

(7)

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

2.3評估方法

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

表1　拓?fù)渲笜?biāo)對比(μ/σ)

注：①匹配參數(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ù)更大，使得γ北京-廣州>γ北京-武漢>γ北京-哈爾濱。在當(dāng)前拓?fù)鋮?shù)(α= 0.31，β=0.19，強度系數(shù)ω=0.69)的情況下、節(jié)點間的連接概率中，距離起主要作用，互聯(lián)網(wǎng)人數(shù)起次要作用。相對武漢而言，盡管廣州的互聯(lián)網(wǎng)人數(shù)更多，但是由于北京到廣州距離較長，綜合使得P北京-廣州

通過相關(guān)研究比較，選擇了KU-Locgen[13]拓?fù)渖善鞯腤axman模型計算其“匹配參數(shù)集”，可以看出本文的拓?fù)渖伤惴ㄔ谄骄戎笜?biāo)一樣的情況下，在鏈路長度這個指標(biāo)上與現(xiàn)實拓?fù)涓鼮槠ヅ?，這是由于考慮了節(jié)點間的聯(lián)系強度對生成邊的影響，而不是簡單地考慮長短邊的比例因素。同時，在網(wǎng)絡(luò)效率指標(biāo)的比較上，本文算法和KU-Locgen[13]算法較為接近，但均略低于真實網(wǎng)絡(luò)拓?fù)涞木W(wǎng)絡(luò)效率，這可能因為真實網(wǎng)絡(luò)拓?fù)渫墙?jīng)過設(shè)計部門的反復(fù)優(yōu)化后確定的一次具有較高網(wǎng)絡(luò)效率的拓?fù)洌疚乃惴ㄓ捎谕負(fù)渖芍须S機性因素的作用，取的是在某一匹配參數(shù)集下的網(wǎng)絡(luò)效率均值，故該值略低于真實網(wǎng)絡(luò)拓?fù)涞木W(wǎng)絡(luò)效率。

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

2.4費用約束分析

費用是拓?fù)渖珊蟮亩窟^濾。根據(jù)式(2)的費用計算方法，設(shè)vc為10萬元，可計算得到中國電信和美國ANS骨干網(wǎng)的實際建設(shè)費用分別為60億和28.2億元?；贛ATLAB R2009b對拓?fù)渖伤惴ǖ膮?shù)空間進(jìn)行總體建設(shè)費用分析，可得到如圖3所示的費用在參數(shù)空間上的分布圖。

(a) 實際拓?fù)浣Y(jié)構(gòu)(a) Actual Topology

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

(c) 高延遲拓?fù)?生成)(c) High latency topology圖2　中國電信拓?fù)浣Y(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)絡(luò)運營商的建設(shè)費用是有限的，假設(shè)中國電信和美國ANS在現(xiàn)有節(jié)點集基礎(chǔ)上的建設(shè)費用約束分別為60億～70億元和25億～30億元，那么滿足上述費用約束的參數(shù)集分布如圖4所示。通過對參數(shù)集進(jìn)行費用約束分析，可以篩選出符合特定費用約束的參數(shù)集，進(jìn)而構(gòu)造相應(yīng)的拓?fù)浣Y(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)系強度、基礎(chǔ)設(shè)施費用和魯棒性是互聯(lián)網(wǎng)骨干網(wǎng)形成的關(guān)鍵因素，所提多約束條件下的骨干網(wǎng)路由器級拓?fù)渖煞椒ǎ瑢π枰劳新酚善骷壘W(wǎng)絡(luò)拓?fù)溥M(jìn)行研究的網(wǎng)絡(luò)抗毀性分析研究等領(lǐng)域有重要意義。

參考文獻(xiàn)(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)絡(luò)力量[M]. 沈陽: 遼寧大學(xué)出版社, 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)絡(luò)信息中心. 2014年中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(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]汪小帆， 李翔， 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[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

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

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

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：A

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

http://journal.nudt.edu.cn