Ｉｎｔｅｒｎｅｔ網絡拓撲建模方法綜述

（電子工程學院 a.網絡系; b.訓練部 合肥 230037）

摘 要：針對Internet網絡拓撲的重要屬性特征，對當前基于度分布的網絡拓撲建模方法進行了綜述，指出了不同建模方法存在的局限性，并分析了當前網絡模型在表述Internet網絡時面臨的問題，最后給出了進一步的研究方向。

關鍵詞：網絡拓撲； 網絡建模； 冪律； 度分布

中圖分類號：TP393.3文獻標志碼：A

文章編號：1001-3695(2009)05-1625-03

Survey on Internet topology modeling method

YANG Guozheng LU Yuliang ZHU Fengb

（a.Dept. of Network Engineering b.Dept. of Training Electronic Engineering Institute Hefei 230037 China）

Abstract:Based on important Internet topology properties this paper analysed current Internet topology modeling methods pointed out some limitations of each method and proposed the problems when using currunt models to describe the Internet. At last put forward some suggestions for future research work.

Key words：network topology; topology modeling; powerlaw; degree distribution

如今Internet網絡已成為人們日常工作生活中的重要組成部分。然而由于Internet網絡規模巨大、結構復雜和管理分散等特性，以及缺乏準確有效的網絡拓撲探測技術，當前對Internet網絡拓撲的認識仍然存在很大的局限性。關于Internet網絡拓撲的建模方法一直都在根據對網絡屬性認識的深入而變化發展。最早用于網絡建模的是隨機圖模型，如Waxman模型^[1]，該模型能夠根據節點數與節點之間的連接概率構造一個給定大小的隨機網絡，使該網絡具有較短的平均路徑長度。隨后針對Internet網絡的結構特征出現了一些層次模型，如等級模型^[2]和TransitStub模型^[3]，這些模型能夠根據一定的算法構造幾種層次的拓撲結構。但是文獻[4]指出這種層次屬性不是Internet的本質屬性，用這種屬性建立的網絡模型具有較大的主觀性。第三階段是基于Internet冪律分布的建模方法，該方法受啟發于Faloutsos等人^[5]發現的Internet拓撲結構中存在的冪律特性，進一步針對拓撲的定量屬性特征進行建模。目前，該類方法仍然是主流的Internet網絡建模方法。

1 用于建模的Internet拓撲屬性

Internet是一個典型的大規模復雜網絡，由于缺乏完整的Internet網絡拓撲圖，對Internet建模主要是針對Internet網絡的屬性特征。并不是所有的特征屬性都適用于模型的構造^[6]，因此，在模型構造中主要采用下面四個屬性：

a)網絡平均路徑長度。它表示網絡中任意兩點之間距離的平均值。雖然Internet規模巨大，但通過Internet和BGP數據的分析可以發現，Internet的平均最短路徑長度很小，而且隨Internet網絡的演化而逐漸降低。

b)節點度分布。它用來表示網絡中度為k的節點的存在可能性。文獻[5]在1999年首先發現Internet網絡拓撲中節點度符合冪律特性，即p(k)∝k-r。此后，該特性已成為Internet網絡建模研究中的重要內容之一。當前所有基于度的拓撲建模方法也是針對該屬性設計的。目前Internet網絡的冪律指數r被認為是在2~3。

c)聚類特性。它用于描述網絡中相鄰節點之間建立連接的難易程度，可以用聚類系數C（k）來表示。聚類系數是一個衡量網絡中節點平均度為k的節點與其鄰居形成子團容易程度的指標。大量研究表明Internet網絡具有較高的聚類系數，文獻[7]指出現行的路由策略是使Internet網絡產生高聚類現象的原因。

d)節點聯合度分布。它用于表示具有度值k與k′的節點之間產生連接的概率分布情況，可以反映網絡中的節點是傾向于與度數相近的節點相連，還是傾向于與度數相差很遠的節點相連。盡管在對Internet自治域級網絡研究中發現“富人俱樂部”^[8]現象，但通過BGP、Skitter和WHOIS三個來源的Internet拓撲數據研究發現，Internet是一個典型的異配網絡，即節點傾向于與度數相差很遠的節點相連。

2 Internet拓撲建模方法

目前，Internet網絡拓撲的建模方法都是以隨機連接為主要實施步驟，以節點度分布為主要建模目標，部分考慮了網絡的聚類特性和聯合度分布屬性。這些方法主要包括隨機圖法、配置法、馬爾可夫鏈蒙特卡洛法、目標屬性隨機重連法和增長—優先連接法。

2.1 隨機圖法

隨機圖法是最早用于網絡建模的方法。根據設定的網絡包含的節點數n與任意兩個節點之間的連接概率p就可以構造出最簡單的網絡模型。為了描述Internet網絡中節點度分布的冪律特性，文獻[9]將這種隨機構造算法進行了擴展：首先根據期望的度分布p(k)將所有節點i以其期望的度ki進行標注；然后將每個節點對（i，j）以概率p(ki，kj)=kikj/(nk)相連，從而構造具有期望度分布的網絡圖。然而，該方法在實際實現中的性能較差，因為這種概率特性來源于大規模的統計數值，將其運用到具體實現中時存在很高的變化性。例如，在構造結果中一些細小的連接部分，許多節點度期望值為1的節點最后都變成了孤立的節點。所以在實際構造中需要增加一些額外的策略來處理這些孤立的節點。

2.2 配置法

配置法是一種廣泛采用的生成圖算法，又稱廣義隨機圖法。其具體算法如下：給定一系列節點，度為k的節點數為n(k)，總節點數n=∑k max1n(k)。首先將每個度為k的節點復制成k個備份點（k=1，…，k max）；然后隨機選擇所有節點（包括復制點）對進行隨機連接；再將原來復制的節點還原成最初的節點，但此時構造結果并不是一個簡單圖，而是會出現自環路或兩個節點之間出現多條連接的情況。為此必須將所有出現自環路或兩個節點之間出現的多余連接去除，再從中解析出最大的一個連通子圖，即得到生成圖。只要期望度分布序列能夠在實際中存在，則該算法是能夠成功實現這樣的圖。

針對該算法中出現自環路或兩個節點之間出現多條連接的情況，還可以在構造過程中加以改進，即在隨機重連時一旦檢測到出現自環路與節點間存在多條連接的情況，就跳過該次連接。該方法可以直接構造出一個簡單的最大連通子圖。但不幸的是，避免環路的策略會使算法在執行過程中出現多種死鎖的現象，這是由于當前狀態下除了產生回路連接而沒有其他合適的連接可以產生的原因造成的。這就需要引入其他一些限制條件來保證算法的可執行性。

2.3 馬爾可夫鏈蒙特卡洛算法

由于配置法得到的結果僅僅是一個最大連通子圖，得到的度分布應該是原先的度分布乘上一個比例系數。盡管這種度分布與期望的度分布大致相符，但對于生成圖其他屬性的影響由于了解很少而經常被忽視。為了得到一個具有給定期望度的完整簡單連通圖，出現了馬爾可夫鏈蒙特卡洛算法^[10]。該算法被認為是當前構造全局簡單連通圖最有效的算法。它由三個主要步驟組成：

a)實例化度分布序列。采用上面介紹的配置法生成一個符合度序列的簡單圖。

b)在沒有改變節點度的前提下連通該圖。由于步驟a)生成的圖不能保證圖的連通性，需要加入邊的重連策略，使得所有的連通子圖合并成一個單一的連通圖。對于任意兩個非連通子圖Gx和Gy，從Gx中選擇一條邊（a-b），滿足當這條邊刪除時不會影響Gx本身的連通性，再從Gy中選擇一條滿足同樣條件的邊（c-d），然后執行邊交換（a-b），（c-d）→（a-d），（b-c）可以得到一個簡單的連通圖，而且由于Gx和Gy本身不連通，不會生成多條重復邊。圖1顯示了一個類似這樣的操作。通過對該操作的重復執行便可以得到一個單一的連通圖。

c)在保持連通性和簡單性的前提下打亂邊的連接使其隨機化。該步驟是為了對生成圖中的其他屬性保持無偏性，因此可以通過邊的隨機交換來完成。給定某時刻t時的圖Gt，隨機選取兩條邊進行交換，得到具有相同度分布的另一個圖Gt′。如果Gt′是簡單連通的，則認為該次交換有效，即Gt+1=Gt′；否則拒絕交換，Gt+1=Gt。循環執行這個步驟，直到在某一步驟后進行的交換對生成圖的性質具有一致性為止。目前仍然不清楚這種趨于一致性的收斂速度，但該過程是一個不可還原的、均衡的和非周期性的馬爾可夫鏈。馬爾可夫鏈在其空間的每一個狀態都會形成一個統一的分布。文獻[11]從實驗上證明它需要經過O（m）次邊交換才能收斂。

2.4 目標屬性隨機重連法

由于隨機重連可以使圖的屬性保持無偏性，那么考慮該算法的逆向過程，同樣可以為達到某一屬性特征而進行逆向隨機重連過程，即以特定屬性為目標的隨機重連法^[12]。該算法主要思想是在保留當前特征屬性的前提下，為實現某種其他屬性而對可行的邊進行隨機重連。保留當前特征屬性是指在隨機重連時不會對已有屬性造成影響。例如，隨機選取兩條邊，將這兩條邊其中的一個端點互換即可以保留圖中節點度分布P(k)屬性不變。如果這兩條邊中有一對端點的度數相同且出現在不同的邊上，則進行互換時節點之間的聯合度分布P(k，k′)屬性也會保持不變，如圖2所示。

算法中每一步只接受隨機重連結果更接近目標屬性特征的連接，在實際操作中可以用一些距離參數來量化重連前后兩個圖的差異。以目標屬性是聚類系數Ctarget為例，可用當前圖中的聚類系數值Ccurrent與目標屬性Ctarget之間的差的絕對值ΔD=｜Ccurrent-Ctarget｜來描述這種差異。在每一步重連時，只接受使該差異值減少的重連。由于ΔD值是一個非負值，只有當ΔD=0時才表明已達到目標聚類系數的值。

這種隨機化重連方法存在一個最重要的問題是需要獲得初始圖作為輸入才能構造其目標屬性隨機圖的版本，因此需要首先使用前面的方法構造一個初始圖才能執行。此外，這種保留當前屬性的目標屬性重連法還存在一個潛在的問題，它可能是非各態歷經的，即有可能不存在一系列的重連過程，使得該算法可以從初始圖轉換成具有目標屬性的圖。為了解決這個問題，可以使算法接受使ΔD＜0的重連，但同時也以概率e-ΔD/T接受ΔD≥0的情況。其中T>0表示溫度參數。這是根據模擬退火算法的參數命名的。

2.5 增長—優先連接算法

上述幾種方法都是直接針對從實際Internet網絡中觀察到的屬性構建模型，屬于靜態建模方法。Barabasi等人^[13]在研究實際網絡中節點和邊的變化時發現，Internet網絡是一個增長型網絡，節點和邊都在不斷增加，且邊的增加傾向于與網絡中度數較大的節點相連。因此，他們利用網絡變化特征提出了一個動態演化建模算法。這種算法主要基于兩種機制：a)增長，從一個具有m0個節點的網絡開始，每次引入一個新的節點，并連接到m個已存在的節點上，m≤m0；b)優先連接，一個新節點與一個已經存在的節點i相連的概率為Πi與節點i的度ki、節點j的度kj滿足關系Πi=ki/∑jkj。

BA模型是增長—優先連接算法的最初模型，隨后針對Internet中存在大量邊的重新連接問題，出現了AB模型^[14]；針對Internet拓撲的高聚類特征，出現了DM^[15]模型；針對Internet中存在的“富人俱樂部”現象，又出現了正反饋優先（positive feedback preferential，PFP）模型^[8，16]，文獻[17]在對中國AS網絡的測量時發現PFP模型在對區域自治域網絡的建模上也具有一定的適用性。與此同時，針對Internet中存在大量的葉子節點和節點優先連接的非線性特征，Sagy等人^[18]也提出了TANG模型。該模型與PFP模型相類似，都是基于增量加邊和非線性優先連接的思想，但TANG模型的非線性因子更加靈活，可以根據需要生成拓撲的冪律指數大小進行調節。文獻[19]在基于TANG模型的非線性優先連接基礎上，根據實際路由器網絡的冪律分布特性，提出了一種動態非線性層次（dynamic nonlinear hierarchy，DNLH）模型，進一步對路由器網絡的冪律特性進行刻畫。這些模型都是基于增長—優先連接機制，針對Internet網絡拓撲中存在的一些特征現象，在算法實現上進行了改進。

3 面臨的問題和進一步的研究方向

盡管當前網絡拓撲模型能夠很好地刻畫平均路徑長度、節點度分布和聚類特性等屬性，但這僅僅代表了Internet拓撲特征的幾個方面，對Internet拓撲結構的研究仍然存在一些問題：

a）目前關于Internet拓撲屬性的研究是不充分的。通過對類似traceroute和BGP數據分析得到的抽樣網絡拓撲并不能掌握到所有的拓撲屬性特征。文獻[20]指出traceroute和BGP數據會丟失實際網絡中大量的對等連接信息，而這些信息會對網絡的連通性和聚類方式產生重要的影響。

b）當前網絡建模中，不管是靜態還是動態方法，針對的目標都是構造一個靜態的Internet網絡拓撲圖，無法反映出隨時間的演化特性。由于實際網絡中一直存在路由器和鏈路的增加與刪除、路由策略的失敗和重定向、網絡地址的通告和撤銷等事件，使得無論是邏輯層的自治域級拓撲，還是由物理實體構造的路由器級拓撲一直處于動態變化中^[21]。如何在網絡建模中引入這些網絡隨機事件，構造一個隨時間變化的動態拓撲，將比構造靜態的拓撲圖更加有意義。

c）上述這些建模方法主要用于Internet 自治域級網絡拓撲構造中，缺乏對路由器級網絡拓撲的模型構造。這主要局限于兩個方面：一方面路由器網絡結構比AS拓撲更加復雜，目前仍然缺乏有效的探測數據來源，從而使得對路由器網絡屬性的認識仍然存在很大的局限；另一方面自治域拓撲是一種邏輯上的粗粒度拓撲，在建模時無須考慮到一些實際條件的限制，而路由器級拓撲是一個客觀存在的實體，對其建模僅僅是從個別屬性特征考慮是遠遠不夠的，還需要研究實際網絡在構造時存在的技術條件、地理環境和經濟實力等因素。

對Internet網絡拓撲的建模方法還需要從以下三個方面進行深入研究：a）研究新的拓撲數據收集技術來發現網絡拓撲中存在的一些新屬性特征；b）研究什么樣的動態機制能夠加入到Internet網絡模型中去；c)針對路由器級網絡的屬性特征和限制條件，構造符合Internet路由器級網絡的拓撲模型。

參考文獻：

［1］WAXMAN B M. Routing of multipoint connections[J].IEEE JSAC 1988，6(9):1617-1622.

[2]DOAR M B. A better model for generating test networks[C]//Proc of the GLOBECOM’96. London: IEEE Press 1996:86-93.

[3]ZEGURA E W CALVERT K L DONAHOO M J. A quantitative comparison of graphbased models for Internet topology[J]. IEEE/ACM Trans on Networking 1997，5(6):770-783.

[4]TANGMUNARUNKIT H COVINDAN R. Network topology generators:degreebased vs structural[C]//Proc of ACM SIGCOMM 2002. Pittsburgh:[s.n.] 2002:147-159.

[5]FALOUTSOS M FALOUTSOS P FALOUTSOS C. On powerlaw relationships of the Internet topology[J]. ACM SIGCOMM Computer Communication Review 1999，29(4):251-262.

[6]ANGELES S M，BOGUNA M. Tuning clustering in random networks with arbitrary degree distributions[J].Physical Review E，2005，72(3):036133.

[7]FRAIGNIAUD P. Greedy routing in treedecomposed graphs[C]//Proc of the 13th Europ Symp on Algo. Berlin: Springer，2005:791-802.

[8]ZHOU Shi. Characterising and modelling the Internet topology: the richclub phenomenon and the PFP model[J]. BT Technology Journal 2006，24(33):108-115.

[9]MARIAN B ROMUALDO P S. Class of correlated random networkswith hidden variables[J]. Physical Review E 2002，68(2):036112.1-036112.13.

[10]GKANTSIDIS C，MIHAIL M，ZEGURA E.The Markov chain simulation method for generating connected powerlaw random graphs[C]//Proc of ALENEX’03. 2003:16-25.

[11]VIGER F LATAPY M. Efficient and simple generation of random simple connected graphs with prescribed degree sequence[C]//Proc of COCOON. 2005:440-449.

[12]MAHADEVAN P KRIOUKOV D FALL K，et al. Systematic topology analysis and generation using degree correlations[C]//Proc of ACM SIGCOMM 2006. Pisa:[s.n.] 2006:135-146.

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

[14]ALBERT R BARABASI A L. Topology of evolving networks:local events and universality[J]. Physical Review Letters，2000，85(24):5234-5237.

[15]DOROGOVTSEV S N MENDES J F F. Evolution of network:from biological nets to the Internet and WWW[M].London:Oxford University Press，2003.

[16]ZHOU Shi. Understanding the evolution dynamics of Internet topology[J]. Physical Review E 2006，74(1): 016124.

[17]張國強，張國清，范晶. 中國大陸AS級拓撲的測量與分析[J]. 通信學報 2007，28(10):92-101.

[18]SAGY B MIRA G AVISHAI W. An incremental superlinear preferential Internet topology model[C]//Proc ofthe 5th Annual Passive and Active Measurement Workshop. 2004:53-62.

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

[20]OLIVERIRA R V PEI Dan WILLINGER W et al. In search of the elusive ground truth: the Internet’s ASlevel connectivity structure[C]//Proc ofACM SIGMETRICS. Annapolis:[s.n.] 2008:217-228.

[21]HADDADI H IANNACCONE G. Network topologies: inference modelling and generation[J]. IEEE Communications Surveys and Tutorials 2008，2(10):48-69.