一種啟發式Ｉｎｔｅｒｎｅｔ路由器級拓撲建模方法

摘 要:針對Internet網絡拓撲研究現狀，總結了當前Internet所具有的一系列重要屬性特征，并對現有基于度分布的網絡拓撲模型進行了分析，指出了這些模型在表述Internet路由器級網絡時存在的局限性。從實際路由器網絡制約因素出發，引入了構建松散網絡核心的限制條件和保留節點度屬性的重連機制，在增長—優先連接機制的基礎上提出了一種啟發式非線性優先連接(HNLPA)拓撲建模算法。實驗表明，本算法構造的拓撲能夠較好地描述Internet路由器級網絡特征。

關鍵詞:網絡拓撲; 路由器; 啟發式; 拓撲模型

中圖分類號:TP393.2文獻標志碼:A

文章編號:1001-3695(2009)09-3465-03

doi:10.3969/j.issn.1001-3695.2009.09.074

Heuristically modeling method of Internet route-level topology

YANG Guo-zheng， LU Yu-liang， XIA Yang

(Dept. of Network Engineering， Electronic Engineering Institute， Hefei 230037， China)

Abstract:Based on current research on Internet topology， this paper summarized a series of important characters of Internet， analyzed current Internet topology models，and pointed out that these models have some localization in describing Internet rou-ter-level topology. Then， starting from the limit factors in real router-level network， introduced the condition of generating loose network core and rewiring mechanism of preserving the node degree property， proposed a heuristically non-linear preferential attachment (HNLPA) algorithm. The experiment show it works well in modeling characters of Internet router-level topology.

Key words:network topology; router; heuristically; topology model

對Internet網絡拓撲的研究是認識和理解網絡行為和性能的基礎。由于目前的網絡測量技術無法獲得完整而準確的Internet拓撲結構，關于Internet網絡拓撲的建模方法一直都在根據對網絡屬性的認識程度而變化發展。對Internet網絡拓撲建模方法的研究主要經歷了三個階段:最早采用的是隨機圖模型，僅僅能夠根據節點數和節點之間的連接概率構造隨機網絡，缺乏對Internet實際特征的描述;隨后針對Internet網絡的結構出現了一些層次模型，這些模型能夠根據一定的算法構造幾種層次的拓撲結構，但這種層次是定性意義上的，不能對Internet屬性進行定量描述;第三階段是基于Internet冪律分布的建模方法，該方法主要針對Faloutsos等人[1]發現的Internet拓撲結構中存在的冪律特性，能夠進一步針對拓撲的定量屬性特征進行建模。目前，該類方法仍然是主流的Internet建模方法。本文將根據實際網絡在部署過程中遇到的限制因素，在保留度分布具有冪律特性的基礎上，提出一種更能符合實際Internet路由器級網絡的拓撲建模方法。

1 Internet重要拓撲屬性特征分析

由于Internet自身并不存在拓撲測量機制，對Internet網絡拓撲發現的研究都是根據一些相關的網絡協議功能加以改進而實現的。在當前的研究中，比較公認的Internet屬性特征包括以下幾點:

a)節點度分布符合冪律特性。節點度分布用來表示度為k的節點存在的可能性。在文獻[1]于1999年首先發現Internet網絡拓撲中節點度符合冪律特性p(k)∝k-r后，該特性已成為當前拓撲建模方法的主要研究對象。

b)節點具有明顯的層次性。在對Internet自治域級(autonomous system，AS)的網絡拓撲研究中發現[2]，其拓撲節點之間存在明顯的層次性差異。

c)聚類系數較高。聚類系數C(k)是一個衡量網絡中節點平均度為k的節點與其鄰居形成子團容易程度的指標，對于整個網絡的聚類系數C就是指所有節點的聚類系數C(k)的平均值。大量研究表明Internet具有較高的聚類系數，文獻[3]已采用該特性來衡量拓撲生成算法的正確性。

d)相配系數為負值。相配系數是描述節點之間相連是否具有度相關特性的統計量[4]。α>0對應同配網絡，即網絡中節點傾向于與度數相近的節點相連。α<0對應異配網絡，表示高度節點傾向于與低度節點建立連接。文獻[5]在對BGP、Skitter和WHOIS三個來源的Internet拓撲數據研究發現，其相配系數分別為-0.19、-0.24和-0.04，這表明Internet拓撲是一個典型的異配網絡。

e)介數具有冪律特性。介數是一個衡量網絡中心度的參數，網絡拓撲中節點和邊的介數值由任意兩點間經過該節點或邊的最短路徑數來表示。文獻[5]在對Skitter和BGP數據的分析過程中，發現節點的介數與度數關系也存在明顯的冪律特性，其冪律指數分別為1.17和1.35。

2 基于度分布的Internet拓撲模型

對于上述Internet屬性特征，目前還沒有一個很好的構造算法，使得生成的圖符合所有這些特征值。當前基于度分布的拓撲建模方法也主要是對度分布特征進行刻畫。其中最著名的是由Barabasi等人[6]首先提出的網絡增長—優先連接模型——BA模型。Barabasi等人在研究實際網絡中節點和邊的變化時發現，Internet是一個增長型網絡，節點和邊都在不斷增加，且邊的增加傾向于連接到網絡中度數較大的節點上。利用這種增長—優先連接特性，BA模型可以很容易構建具有冪律度分布和小世界特性的網絡。

BA模型是增長—優先連接算法的最初模型，隨后針對Internet中存在大量邊的重新連接問題，出現了AB模型[7];針對Internet拓撲的高聚類特征，出現了DM[8]模型;針對Internet中存在的富人俱樂部現象，又出現了正反饋優先(positive feedback preferential，PFP)模型[9]。與此同時，針對Internet中存在大量的葉子節點和節點優先連接的非線性特征，Sagy等人[10]也提出了TANG模型。TANG模型與PFP模型相類似，都是基于增量加邊和非線性優先連接的思想，但TANG模型的非線性因子更加靈活，可以根據需生成拓撲的冪律指數大小進行調節。文獻[11]在TANG基于模型的非線性優先連接基礎上，根據實際路由器網絡的冪律分布特性，提出了一種動態非線性層次(dynamic non-linear hierarchy，DNLH)模型，進一步對路由器網絡的冪律特性進行了刻畫。

3 一種路由器級網絡拓撲建模方法

上面提到的這些Internet拓撲模型主要是針對網絡中節點度分布符合冪律的屬性特征，部分考慮了少量其他Internet特征現象，產生的拓撲圖無一例外均會出現高度節點互相連接形成網絡核心的結構。這是由于在增長—優先連接算法中，核心節點會首先加入到網絡中，然后不斷與新加入的節點建立連接，最終使得核心節點具有較高的度值。這種結構在對Internet AS拓撲建模時具有一定的適用性，因為AS拓撲是一個邏輯拓撲，其中的節點和邊都不代表實際存在的實體，因而不會有較大限制。然而在對Internet路由器級網絡進行建模時卻存在一個嚴重的問題，即網絡中的節點和邊都是由實際網絡設備和傳輸鏈路構成的，由于受實際網絡構造需求、技術實現條件和運行成本的影響，生成的網絡拓撲中路由器的連通度受技術實現條件的限制不可能很大，兩個相距很遠的節點之間建立直接鏈路的概率不可能很高。因而不會像上述模型那樣節點的連通度和連接只要滿足增長—優先連接規則就可以大量增加。本文將根據實際網絡在部署過程中遇到的限制，提出一種更能符合實際Internet路由器級網絡的拓撲建模方法。

3.1 限制條件

在Internet的發展過程中，路由器技術一直對網絡連通性的設計產生重要影響。當前不論任何廠家生產的路由器在單位時間內都會存在一個處理數據包的上限，這就限制了每臺路由器所能具有的最大鏈路連通數量和最高連通帶寬。在一定范圍內這兩個性能參數還存在一種互相制約的關系，這種制約使得路由器在配置時必須考慮帶寬和連通度指標的均衡性。對于網絡核心路由器，高帶寬是其主要性能指標，因此一般在實際使用時均采用較低的連通度配置方式。同時由于支持高帶寬的鏈路造價昂貴，這種鏈路僅僅會出現在核心骨干路由器之間和與次一級骨干路由器的連接上。而對于網絡邊緣路由器，由于其主要工作目的是以為大量終端客戶提供服務，而對鏈路帶寬的需求不高，連通性是主要性能指標。以思科路由器為例，圖1顯示了思科高性能骨干路由器12800系列的工作區域和配置環境。

思科12800系列路由器是Internet骨干網中廣泛部署的核心路由器之一，包括12810和12816兩種類型，分別具有10和16個插槽，每個插槽的容量可達40 Gpbs。其工作區域如圖1(a)所示，以12816為例，當路由器被配置成少于16個連接時，總帶寬隨著連通數的增加總帶寬也線性增加，且每條帶寬最大值不受影響;當連通度大于16時，路由器總帶寬和單條鏈路帶寬下降隨著連通數的增加而下降，直至達到該路由器的最大可能連通數為止。這類路由器的典型配置環境如圖1(b)所示，除相互之間建立連接外，一般可以與思科12400系列的路由器建立連接。該系列路由器也屬于骨干網路由器，但工作性能低于12800系列。而部署于網絡邊緣地區的路由器，如思科6260，由于需要支持大量終端用戶(DSL、撥號等)以較小的帶寬進行上網的功能，在工作區域內可以具有較大的連通度指標。

盡管當前的Internet包含多種不同的路由器模型，但是每種路由器均采用不同的技術并工作在各自的工作區域內。在路由器總帶寬的限制下，Internet路由器級網絡應該具有類似這樣的結構:Internet網絡核心部分由松散網狀的高速鏈路組成，低連通度的核心路由器能夠在高帶寬鏈路上傳遞大量數據流。同時在網絡邊緣位置，區域相近的路由器節點更容易相互連接形成子團，在與其他區域網絡交換流量時會先匯聚到一些度數較大的網關路由器上整合流量，然后再通過網絡核心區的高帶寬鏈路傳送流量。新加入的路由器或網絡終端受區域位置的影響，會傾向于選擇距離當前節點較近且度數較大的路由器進行連接，以期獲得較高的網絡性能。

3.2 啟發式非線性優先拓撲構造算法

受實際Internet中路由器技術條件和網絡部署位置限制的啟發，本文在基于增長—優先連接機制的基礎上，引入了啟發式條件和度屬性保留重連機制，從而提出了一種啟發式非線性優先連接(heuristically non-linear preferential attachment，HNLPA)算法，用于對Internet路由器級網絡進行建模。具體算法如下:

a)根據待建模實際網絡中核心節點數目，確定模型的初始節點數m0，同時根據網絡中存在的最高路由器性能，確定核心節點的最大連接度值k′max，然后循環執行b)和c)，直至達到需要的網絡規模為止。

b)每一步新增加一個新節點和m條邊。其中一條外部邊將新節點與已存在節點相連，已存在節點選擇概率為Π(ki)=(ki+1)1+ε/∑j(ki+1)1+ε，ε>0是一個非線性因子;其他m-1條邊在網絡內部產生，每條邊的產生方式如下:按照統一的概率隨機選擇一個節點i，另一個節點j的選擇首先以概率Π(kj)=(kj+1)1+ε/∑i(ki+1)1+ε確定選擇節點的度值kj，然后選擇度值為kj且距離節點i最近的節點與i相連，兩點間的距離根據最短路徑之間的跳數確定。

c)檢查網絡中的核心節點度值k是否超過了k′max，如果某一核心節點v的度值k>k′max，則需要重新連接b)中加入與節點v相關的連接。為了保留度分布屬性，重連操作保持原先與節點v相連的節點不變，邊的另一個節點則需要隨機選擇一個度為k-1的節點。

d)去除網絡中節點間出現重復邊的現象，得到一個簡單的連通圖。

算法首先根據實際限制確定生成網絡的初始條件。b)是產生Internet冪律度分布特征的重要保證，由于線性優先連接得到的度分布冪律指數大于實際Internet路由器級網絡度分布的冪律指數，本文采用非線性因子ε來降低模型中的冪律指數值。文獻[10]通過實驗得出當ε=0.2時生成的拓撲圖能夠較好地擬合實際Internet的冪律特性。同時為了保證實際網絡中節點連接的本地特性，在隨機加邊過程中引入了一些限制，使得距離相近的節點之間更容易形成連接。c)是為了實現符合Internet的松散核心結構而進行保留度分布屬性的隨機重連。最后，針對網絡中可能出現的重復鏈路現象進行去除，得到一個符合Internet路由器網絡結構的拓撲。

3.3 拓撲比較

由于本文并不比較生成拓撲在冪律特性上與實際路由器網絡的相符程度，并不采用對路由器網絡冪律特性擬合程度較高但算法較為復雜的DNLH模型算法，而是采用復雜度較低但具有代表性的模型算法與HNLPA算法進行比較。實驗中采用MATLAB進行兩種算法的模型構造，用最短路徑算法模擬網絡中任意兩點之間的路由路徑。根據CAIDA skitter數據的分析，度分布冪指數取r值2.2。為了使產生的結果具有直觀性，令網絡節點數N=1 000，TANG模型算法和HNLPA算法中的初始節點數m0=20，每次增加的邊數m=3，HNLPA算法中的k′max=10，得到的實際冪律分布和拓撲結果如圖2、3所示。

圖3中，節點的布局按照從網絡核心到邊緣的順序由內向外地分層隨機分布，最核心節點用“*”表示，其他節點用“#8226;”表示。淺灰線表示非核心節點之間的相互連接，黑線表示與核心節點相關的連接。從圖中可以看出，TANG模型法生成的拓撲中網絡核心是由高連通度的節點組成，這邊節點不僅相互之間存在復雜的連接，而且與網絡邊緣位置的節點也存在大量連接。在實際網絡中這種既具有高連通度，又需要有高帶寬性能的核心節點是不可能存在的。而在HNLPA算法構造的拓撲中，其核心節點除互相連接外，只與次一級的骨干節點建立連接，從而形成一種松散結構，有利于骨干鏈路高帶寬的實現。同時這些非核心的骨干節點由于無須具有較高帶寬的限制，因而能夠產生較大的連通度，有利于整合來自更低級節點的流量。

為了進一步定量分析這兩種方法產生的拓撲屬性，本文分別對網絡的平均路徑長度〈l〉、聚類系數C-和相配系數α進行了計算，采用十次計算取平均值的方式，結果如表1所示。

HNLPA算法的網絡平均長度值高于TANG模型，這是由于HNLPA中核心節點的連通度較小，且僅和次一級的流量整合節點建立連接，大量邊緣節點之間的最短路徑通常需要通過各自的上級流量整合節點，再經過核心節點才能建立，而不像TANG模型中存在高連通度的核心節點，邊緣節點可以通過這些核心節點直接相連，因而HNLPA算法更符合實際路由器網絡的特征。雖然HNLPA網絡具有松散核心結構，但其網絡聚類系數值卻大于TANG模型，而且其聚類特征表現在網絡靠近邊緣的各個區域，這也反映出實際Internet路由器網絡的局域世界特性。對于相配系數，HNLPA算法的值略低于TANG模型，這是因為HNLPA網絡中無法出現類似TANG模型中那種全局核心節點與大量邊緣節點相連的情況。

實驗中，本文還計算了兩種拓撲的介數分布，由于計算能力限制，拓撲節點數僅為1 000，而介數值的變化范圍巨大(從0到最大介數值73 384)，因而兩種介數分布圖的前端分布都比較分散，但末端都出現明顯的重尾現象。同時，盡管HNLPA算法限制了核心節點的連通度，但計算得到的介數值與TANG模型核心節點的介數值卻保持在同一個數量級上。這里限于篇幅，不再給出具體的介數分布圖和介數值。

4 結束語

盡管當前對Internet的全局網絡仍然無法獲得完整的拓撲結構，但通過一些技術手段的測量，對Internet拓撲結構屬性的認識正在逐步發展。本文首先總結了當前Internet所具有的一些重要屬性，然后針對當前網絡模型在表述Internet路由器級網絡時存在的局限性，從實際路由器網絡制約條件出發，引入一些網絡建模中合理的制約因素，在增長—優先連接機制的基礎上構造一種HNLPA拓撲建模算法，實驗說明本算法能夠較好地符合Internet路由器級網絡的特征。

當然，目前已知的這些屬性特征僅僅是描述了Internet網絡拓撲性質的幾個方面，并不能完全概括全部Internet網絡拓撲的屬性。拓撲建模方法也在隨著人們對網絡屬性的深入認識而不斷改進。如果出現一種新的特征參數，使得原先算法的生成圖與實際圖不相符，則必然會產生新的網絡建模方法來適應新的網絡特征。

參考文獻:

[1]FALOUTSOS M， FALOUTSOS P， FALOUTSOS C. On power-law relationships of the Internet topology[C]//Proc of ACM SIGCOMM Computer Communication Review. New York:ACM Press，1999:251-262.

[2]SUBRAMANIAN L， AGARWAL S， REXFORD J， et al. Characterizing the Internet hierarchy from multiple vantage points[C]// Proc of IEEE INFOCOM. New York: IEEE Press， 2002: 618-627.

[3]SOFFER S N， VAZQUEZ A. Network clustering coefficient without degree correlation biases[J]. Phys Rev E， 2005， 71:057101.

[4]ZHOU S， MONDRAGON R J. Structural constraints in complex networks [J]. New Journal of Phys， 2007， 9(172):1-11.

[5]MAHADEVAN P，KRIOUKOV D，FOMENKOV M， et al. Lessons from three views of the Internet topology， CAIDA-TR-2005-02[R]. 2005.

[6]BARABASI A， ALBERT R. Emergence of scaling in random networks[J].Science， 1999， 286 (5439):509-512.

[7]ALBERT R，BARABASI A L.Topology of evolving networks:local events and universality[J].Phys Rev Lett，2000， 85(24):5234-5237.

[8]DOROGOVTSEV S N， MENDES J F F. Evolution of networks[J]. Adv Phys ， 2002， 51:1079-1187.

[9]ZHOU Shi. Understanding the evolution dynamics of Internet topology[J]. Phys Rev E， 2006， 74(1): 016124.

[10]SAGY B，MIRA G，AVISHAI W.An incremental super-linear preferential Internet topology model[C]// Proc of the 5th Annual Passive and Active Measurement Workshop.2004:53-62.

[11]張昕， 趙海，李超. 一種基于多項復雜特征的Internet路由器拓撲建模方法[J].電子學報，2008，36(1):57-63.