Internet拓撲建模與演化綜述?

關曉惠，錢亞冠，周志敏

（1.浙江水利水電專科學校計算機與信息工程系，杭州310018；2.浙江科技學院理學院，杭州310023）

Internet拓撲建模與演化綜述?

關曉惠1，錢亞冠2，周志敏1

（1.浙江水利水電專科學校計算機與信息工程系，杭州310018；2.浙江科技學院理學院，杭州310023）

認識Internet拓撲結構及其演化趨勢對下一代網絡技術的研究至關重要。總結了Internet拓撲研究成果，綜述了Internet靜態拓撲模型和動態演化模型，著重考察了拓撲在節點度和結構兩方面的演化特征，據此提出了今后的研究方向，即運用統計物理的非廣延Tsallis熵理論來研究拓撲特征以及用分層的方式研究Internet拓撲結構，以期取得有效的成果。

下一代網絡；Internet拓撲模型；冪律；演化；節點度；Tsallis熵

1 引言

Internet是復雜網絡的一個典型例子，也可以說是一個龐大的人工生態系統。Internet發展時間盡管不長，但隨著用戶數的不斷增多，其規模變得極其龐大；政治、經濟和技術的變化也影響著拓撲結構的演變。Internet發展到現在，幾乎沒有人能清楚地描述它的真實拓撲結構。研究Internet拓撲演化模型有著重要的意義：深入理解現存路由協議的局限性，正確評估新的協議、體系的設計，預測將來互聯網的發展需求；深入理解網絡技術、拓撲結構和背后的經濟因素之間的相互作用關系；路由協議的模擬與仿真、網絡病毒的傳播等均需要網絡拓撲模型；發現拓撲演變背后的動因、本質規律，對于指導和預測將來Internet上部署各種新技術、新協議和新應用將具有重要指導意義。

對Internet拓撲的研究一般遵循這樣的過程：從真實的Internet環境中提取拓撲數據，通過各種數學方法分析拓撲特征，根據分析得到的拓撲特征建立相應的拓撲模型和生成算法，通過數學分析的方法或實驗的方法來驗證所建立模型的正確性。

對Internet的拓撲研究，前人已經做了很多工作，從最初的隨機圖模型到結構模型，到Faloutsos提出的節點度的分布冪律特征［1］，再到Barabasi等提出的無標度網絡［2］，以及后來Zhou S等提出的rich -club現象［3］、Mahadevan等關于節點度的相關性研究［4］，這些都是基于靜態模型基礎的。目前，動態演化模型的研究越來越受到關注［5-7］。

由于Internet是通過BGP協議將全球AS（自治系統）互聯起來的網絡，其拓撲結構主要由AS之間的互連關系表現出來，因此本文也主要闡述AS級的拓撲模型，即將每個AS看作圖的節點，將AS之間的連接抽象成圖中節點的鄰接關系。

2 拓撲建模存在的困難

2.1 拓撲數據測量的困難

不管是建立還是驗證分析Internet的拓撲模型，都需要可靠和真實的數據。目前獲得Internet拓撲數據的方法主要有：

（1）通過測量技術獲得，常用工具是traceroute，由于Internet的拓撲時刻處于動態變化，因此測量得到的數據具有滯后性；

（2）通過路由器上的BGP表、IRR、RIR獲得，由于測量節點的數量有限，探測的目的節點數量也有限；AS之間存在的路由策略，BGP路由表不一定對外宣告；拓撲結構的高度動態變化等因素；尤其是很難發現冗余鏈接。

出于商業競爭、網絡安全等因素的考慮，對于ISP來說，網絡拓撲、路由策略、對等關系、容錯能力和容量規劃等信息對外界都是不公開的。AS級的營運商會經常變更他們之間的連接和流量交換策略；AS內部也因為經常發生路由設備的失敗、維護和升級等事件，使得路由器級的拓撲結構同樣也是不穩定的。因此，獲取Internet真實的拓撲數據非常困難。

正是由于無法精確了解Internet的真實拓撲結構，也就為正確建立和驗證拓撲模型帶來了很大的困難。CAIDA（The Cooperative Association for Internet Data Analysis）認為目前需要解決的問題有［8］：

（1）所有的測量都受到實驗條件和觀測條件的限制，如觀測點的地理分布范圍、數量，被探測節點的數量等，使得數據不可避免的帶有局限性；

（2）數據的不完整導致我們將一些合成的拓撲模型當作真實的Internet拓撲，已經證明像E-R隨機圖這樣一類特殊的圖不能代表真實的Internet拓撲；

（3）應該將測量的目標放到具體的地理區域，通過比較不同的地理區域和社會經濟環境下的數據去區分Internet在全局核心和局部區域的不同特征。

在CAIDA發起的WIT（the Workshop on Internet Topology）上，所有與會的網絡研究組織一致認為高質量的測量數據對于拓撲建模研究非常重要。目前可供給研究者使用的拓撲數據源有RouteViews、RIPE、Skitter、DIMES、iPlane等。

2.2 生成機理與演化規律

目前，我們只是對Internet的靜態拓撲統計特性有所了解，如節點度分布的冪律特征、rich-club特征等，但Internet拓撲如何演變，以及模擬演變過程，即找到合適的拓撲生成算法，使之在演變過程中始終保持這些特征是一個困難的問題。我們發現的這些統計特征只是一個靜態的、表層的、描述性的（de

scriptive），要解決這個難題必須找到形成這些統計特征背后的生長機理和各種促進因素，包括技術的、經濟的和社會的，必須是解析性的（explanatory）。文獻［9］指出，即使兩個拓撲具有相同的統計度量，它們之間也可能具有不同的拓撲結構，如二維格子和三叉樹，均具有相同的節點度分布。Internet拓撲的形成沒有事先設計規劃，各個ISP只在自己的AS域內進行優化規劃，但Internet拓撲卻很好地表現出“小世界”特征，使得路由非常高效，是什么原因使得局部最優同時也能全局最優，尋找這些背后的生成機理對于下一代網絡的研究具有重要意義。

2.3 模型驗證的困難

由于缺乏對真實Internet拓撲的了解，以及測量方法的局限和拓撲的動態變化，使得拓撲模型的驗證也存在極大的困難。文獻［10］指出了目前拓撲模型驗證的困難在于以下幾方面。

（1）拓撲生成器旨在產生一類拓撲圖，它們反映Internet某些拓撲特征。區分這些拓撲圖的類型依賴于哪些拓撲特征需要表達，以及這些特征如何表達。如何確定這些分類在真實性和典型性之間的界限是目前還無法解決的問題。

（2）目前對Internet的拓撲特征還沒有被充分的研究。由于路由選擇的復雜性，通過traceroute工具和BGP數據進行逆向工程方式分析，得出的拓撲特征存在不合理的地方。

（3）目前已經存在很多拓撲度量，但并不是每個都與Internet的拓撲相關，選擇哪些拓撲度量去驗證模型是一個目前還沒解決的問題。

3 拓撲演化

拓撲模型可分為靜態模型和動態模型［11］。靜態模型是指從可獲得的實際拓撲數據中生成能夠反映實際網絡拓撲特性的靜態網絡拓撲圖，可以稱為是一個拓撲快照（Topology Snapshot）；動態模型是指根據某種或某幾種拓撲特性而研究網絡的生長／演化過程，反映拓撲特性生成機理，因此也把動態模型稱為演化模型。動態演化的不僅包括節點和邊在數量上的增長，也包含數量的減少和節點之間連接的改變等。

對于動態模型，我們又將它們分為基與節點度的演化和基于結構的演化兩類。

3.1 基于節點度的演化模型

3.1.1 BA模型

BA模型是Barabasi和Albert于1999年提出，大型網絡能自組織成無標度（Scale-free）狀態，主要是因為：增長（Growth）特性，即網絡的規模是不斷擴大的；優先連接（preferential-attachment）特性，即新的節點加入網絡，總是傾向于與較高連接度的“大”節點連接。

BA模型就是基于上述兩個特征構造的具有度分布呈冪律特征的無標度網絡。構造算法如下：

（1）增長：從一個具有m0個節點的網絡開始，每次加入一個新的節點，并連接到m個已存在的節點上，m≤m0；

（2）優先連接：新加入的節點以概率∏（ki）=與節點i連接，ki是節點i的度。

3.1.2 AB模型

AB模型是Albert和Barabasi于2000年提出的［12］，是對BA模型的擴展。AB模型的拓撲演化來自于新節點的加入、新邊的加入和邊的重新連接。具體算法是從m0個孤立的節點開始，每一步執行下面3個步驟中的一個：

（1）以概率p加入m（m≤m0）條新邊，這些邊連接已存在的節點：隨機選擇一個節點作為新邊的起始點，再以概率

選擇另一端的節點；此過程重復m次；

（2）以概率q重連m條邊：隨機取節點i和它的一條邊lij，刪除這條邊并重新以概率∏ab（kj）選擇一個節點j作新的連接；此過程重復m次；

（3）以概率1-p-q增加一個新節點，以概率∏ab（kj）與網絡中已存在的m個節點連接。

上述概率p、q滿足0≤p＜1，0≤q＜1-p。

3.1.3 GLP模型

GLP模型［13］稱廣義線性優先（Generalized Linear Preference）模型，由Tian Bu和Don Towsley于2002年提出。該模型不僅體現了度分布的冪律特征，還表達了兩個“小世界”模型的聚簇特性和特征路徑長度。經過觀察，發現Internet節點比BA模型線性優先連接更傾向于連接到連接度高的節點上，因此提出了廣義線性優先的方法。另外，文獻［14］的研究表明，Internet在AS級很少發生重連（rewiring）操作。GLP模型去除了AB模型的重連操作，算法與AB模型相似，是從一個有m0個節點、m0-1條邊連接的網絡開始，首先以概率p增加m≤m0條新邊，新邊兩端的每個節點以概率

在網絡中已存在的節點中選擇。β∈（-∞，1）是一個可調節參數，β值越小，表明對高連接度節點的偏好性越小。其次，以概率1-p增加一個新節點，新節點以概率∏（di）連接m個節點。Tian Bu從數學上證明了廣義線性優先模型具有冪律特征的度分布。

3.1.4 GNG模型

GNG（Generalized Network Growth）模型［15］與GLP模型相似，由Caldarelli于2003年提出。基本思路是除了允許同時以概率p加入節點和以概率（1-p）加入連接，還采用了一種新的偏好方案：即要么加入一個新節點，以概率

與節點i連接；要么以概率

在節點i、j之間加入一條新邊。GNG模型生成的網絡具有無標度特征，在節點度的分布、介數的分布和聚簇系數等方面與Internet拓撲測量吻合，但動態增長特征與測量結果不符合。

3.1.5 IG模型

IG（Interactive Growth）模型［16］由S.Zhou于2003年提出。IG模型仍然采用BA模型的兩個基本操作：新節點和新邊的加入，連接概率也采用BA模型的線性偏好連接∏（ki），但BA、AB、GLP模型的新節點和新邊的加入是相互獨立的，IG模型提出新節點和新邊聯合增長模式。聯合增長模型基于如下發現：新加入的節點連接到它的宿主節點（host），會給宿主節點增加流量，同時也帶來宿主節點周圍節點的流量模式變化，從而需要增加從宿主節點到它對等方（peer）的新連接，以便均衡流量和優化網絡性能。實驗表明，與AB、GLP模型相比，IG模型在節點度的分布和rich-club特性上更接近于真實的Internet拓撲。

具體算法是從一個小的隨機網絡開始，反復執行如下操作：

（1）以概率p∈（0，1），加入一個新節點，并以概率∏（ki）與網絡中已有節點（稱宿主節點）連接，如圖1中新節點A-接入節點連接，再在宿主節點與其它網內節點之間添加兩條內部連接，如圖中的伙伴節點-接入節點-伴節點連接；

（2）以概率1-p，加入一個新節點，并以概率∏（ki）與網絡中已有的兩個宿主節點連接，再在其中一個宿主節點和網內其它節點之間添加一條內部連接。

3.1.6 PFP模型

PFP模型［17］是由S.Zhou于2008年在IG模型的基礎上提出，稱為正向反饋優先模型。Internet在AS級拓撲中的節點最大度kmax約等于節點總數的1／4，而IG和BA模型在節點最大度這個指標上遠遠超過了這個值。根據Internet歷史數據，Pastor-

Satorras［18］和V′azquez［19］發現新節點與低連接度節點的連接傾向遵循線性優先概率∏（i）=ki／∑jkj，

而Chen［20］發現高連接度節點的“吸引力”遠高于低連接度節點。PFP模型在偏好連接概率上進行了改進：由原來的線性優先改為非線性優先，

∏（i）=k1+δlgki／∑jk1+δlgkj，δ∈0，[] 1以提高連接度高的節點的“吸引力”。

算法與IG模型相似，是從一個小的隨機網絡開始，反復執行如下操作：

（1）以概率p∈（0，1），加入一個新節點，并以概率∏（i）與網絡中已有節點（稱宿主節點）連接，再在宿主節點與其它網內節點之間添加一條內部連接；

（2）以概率q∈（0，1-p），加入一個新節點，并以概率∏（i）與網絡中已有節點（稱宿主節點）連接，再在宿主節點與其它網內節點之間添加兩條內部連接；

（3）以概率1-p-q，加入一個新節點，并以概率∏（i）與網絡中已有的兩個宿主節點連接，再在其中一個宿主節點和網內其它節點之間添加一條內部連接。當p=0.3、q=0.1時，PFP模型生成的拓撲接近真實的AS拓撲。

3.1.7 MPA模型

MPA（Multiclass Preferential Attachment）模型［21］是由加州大學的Srinivas Shakkottai等在2010年提出。MPA模型仍然基于連接偏好的原理，其所有參數都可從測量數據中獲取，這一點為模型的客觀性和驗證上帶來了優勢。與以往模型的不同，該模型的一個顯著改進是注意區分節點的類型，分為ISP和非ISP節點，因此稱為多類偏好連接。但這種區分仍然顯得過于粗略，與我們在結構演化中的討論存在差距。最后，作者基于對實際測量數據的分析，進一步肯定連接偏好性是Internet演變的驅動力。

3.1.8 HOT模型

前面介紹的各種演化模型，其生長機理都是基于偏好連接，而且只有新節點和新連接的加入，沒有節點和邊的減少、連接的重新調整，這是不符合In

ternet的實際運行情況的。基于節點度的模型都可以很好地吻合冪律分布這個特性，但它們的缺陷是，除MPA模型外，都忽視了AS之間連接建立的內在因素，即商業關系。基于度的模型盡管也有演化能力，但這種演化方式很大程度上是帶主觀的假設，其目的就是符合冪律，因此缺乏充分的解析能力。

Chang等［22］將HOT（Highly Optimized Tolerance）模型應用到AS級的拓撲建上。純粹的HOT模型是一種多目標的優化方式：當一個新節點加入網絡，它基于兩種目標來選擇它要連接的節點（稱父節點），分別是最后距離（Last Mile）的連接成本和父節點核心度（node centrality）成本。前者以新節點和父節點之間的歐氏距離來計算，后者以父節點到其它節點的平均距離來計算。文中指出，provider-customer關系在拓撲的節點度分布特征中占主導地位，peer -peer關系可以忽略。另外，多穴（Multi-Homing）連接對于節點度分布也沒有影響。基于這個分析，文中的建模主要針對provider-customer連接的。Internet的發展不是隨意的，而是在收益、資源成本和對風險的承受這三者之間的一種平衡，是一種高度優化設計的結果。

3.2 基于結構的演化模型

自從1999年Faloutsos提出Internet節點度的分布也服從冪律后，基于節點度的拓撲模型的研究迅速發展起來。Internet拓撲結構主要由自治系統（AS）之間的連接關系來體現，這里AS被看成是節點。因此拓撲結構的演化要反映AS數量的增減、AS之間的連接關系的增減（或重連），以及不同類型的AS分布情況。圖2為Internet典型的傳統分層拓撲結構。

3.2.1 AS之間的關系分類

AS之間的關系可分為c2p（customer-provider）、p2p（peer-peer）、s2s（sibling-sibling）3類。在c2p關系中，customer AS需要向provider AS繳納它們之間發生的流量費用；在p2p關系中，兩個AS自身或它們的customer之間的流量可以在它們之間免費傳輸，但不能傳輸它們的provider及peer之間的流量；屬于s2s關系的AS往往屬于同一個管理組織，它們之間或它們的provider、customer之間的流量都可以在這些AS之間免費傳輸。s2s這種關系是隨著Internet規模的擴大，一個大公司可以同時擁有多個AS時出現，它們之間的關系一般并不體現商業利益關系。正是由于提供商之間這種復雜的利益關系，最終體現在Internet拓撲的高度動態變化中。

3.2.2 AS的類型

在基于節點度的拓撲模型中，并不區分節點的類型，而實際的AS節點并不是等同的。AS節點的類型也決定了它在整個拓撲結構中的位置，如核心層、邊緣層等。根據業務類型可分為5類。

（1）企業客戶（EC）：處于網絡邊緣的組織、大學和公司，它們代表了大多數的用戶，不會再有自己的客戶AS。

（2）小型傳輸業務提供商（STP）：通常是區域ISP（包括國家傳輸網、科研網），提供Internet的接入服務和傳輸業務，目的是建立本地區域的客戶群。這些ISP之間通過優化的對等連接，可以減少客戶的上行鏈路的傳輸成本。

（3）大型傳輸服務提供商（LTP）：具有極大的地域分布的國際級ISP。它們與其它ISP的對等連接僅為了可達性的需要，因此對等連接采取限制性策略。

（4）接入／托管服務提供商（AHP）：提供Internet接入（如DSL、撥號連接、租用線路等）、服務器托管業務的ISP。它們的客戶主要是沒有AS號的本地用戶和企業。

（5）內容提供商（CP）：以提供付費內容為業務的供應商，它們的目的是為了降低傳輸成本，所以采用開放的對等連接策略。

k-核的分解［23］是一種提取大規模網絡核心區域的新方法。Guo-Qing Zhang等利用k-核分解的方法研究了Internet的演化趨勢，發現：AS級的Internet規模增長很快，遵循摩爾定律，即N（t）～100.0283t～e0.0652t；與整個Internet拓撲規模的指數級增大相比，k值越大的k-核，其規模隨時間變化得更穩定；2003年后，與配置模型的預測相比，最大核數kmax非常穩定；與主流Internet模型的預測相比，最大節點連接度相對穩定；與隨機模型相比，Internet仍然屬于松散連接結構；與隨機網絡相比，不管Internet整體上還是它的核心都呈現異配性。

最近由Hamed Haddadi等提出用帶權譜分布（Weighted Spectral Distribution，WSD）這個度量來分析Internet拓撲結構。研究表明：WSD可以很好地區分Internet的核心層和邊緣層；核心層與邊緣層的界限隨著Internet進化，開始變得模糊；從圖3中可以看出，隨著核數的增加，高連接度的節點數2008年比2004增加，這意味著Internet中的對等連接增加，也反映出Internet的層次結構的模糊化。

文獻［5］在對BGP數據的測量分析基礎上，對Internet拓撲的演化規律進行了有益的探索。作者提出兩個概念，通過測量發現的拓撲（ObservedTopology，OT）和真實的網絡拓撲（Real Topology，RT）。發現了一個重要的演化規律：臨時性的路由動態變化對OT的影響隨著時間的推移呈指數遞減，而RT中的拓撲變化包含了恒速出生和恒速消亡兩種過程。同時又發現Internet規模的擴大主要由處于AS拓撲邊緣的用戶網絡節點的出生和消亡引起，邊緣網絡和核心網絡存在不同的增長模式。核心網絡節點的增長速度緩慢，但相互間的連接變化卻非常頻繁，這種變化主要來自AS之間的peer-to-peer鏈路連接的重新調整。因此，研究AS的出生率、死亡率和增長率以及路由器和鏈路的失效模型，有利于建立真實的拓撲發生器，用于有效地模擬Internet的端到端行為。

隨著網絡新應用的不斷涌現，文獻［24，25］通過對BGP路由和流量的測量，發現Internet結構出現新的變化趨勢。文獻［24］發現40%～80%的BGP路徑經過tier-2 ISP，從而認為tier-2 ISP在拓撲連接性上開始扮演重要角色，區別于以往傳統上認為樹型分層拓撲結構（見圖4）。文獻［25］對域間流量的分析也得出相似的結論，流量從核心層向外層轉移，也反映出拓撲結構的非樹形變化。

從傳統意義上的樹型分層拓撲結構向非樹型結構的演變，主要原因來自新應用、新的互聯網盈利模式的出現。繼web應用之后，最近社會網絡和視頻內容逐漸在Internet流量中居主導地位。經濟因素的變化，包括IP地址租用費用的連續下降，以廣告為支撐的信息量的增長，極大地改變了許多提供商的互連策略。新互聯網經濟的出現，大的內容提供商開始構建自己的全球骨干網，并直接與自己的客戶網絡連接，轉移了超過5%的域間流量。由此可見，Internet的拓撲結構的演變，新應用和經濟因素起到非常重要的作用。

4 拓撲模型的驗證

在本文的第2節中提到了驗證模型的正確性是其中的一大困難。通過比較不同模型生成的拓撲的統計特性，不一定能反映出模型的正確性。已有研究表明，相同的統計度量下，也可能存在不同的拓撲結構。同時，測量取得拓撲數據存在很多虛假信息，如節點和邊的消失與出現不一定與實際拓撲結構變化相符合。Ricardo Oliveira提出了一種與真實Inter

net比較節點／邊的生滅過程來驗證模型的思路。理論模型的節點／邊的加入是由連接偏好來決定的，那么真實Internet是怎么樣呢？Ricardo Oliveira提出拓撲活性（liveness）的概念來說明該問題。我們將真實的Internet拓撲用Greal來表示，通過測量等手段提取出來的拓撲稱為Gobsv。Gobsv對于我們是可見的，而Greal則是不可見的。如圖5所示，箭頭表示BGP路徑或trace route探測方向。

由圖5發現，Greal和Gobsv是不一致的，即使在同一個Gobsv中，t0到t1和t2到t3也是不一致的。其中t0到t1的不一致是由動態路由引起的，而t2到t3的不一致是由Greal拓撲結構發生變化引起的。同時又可觀察到B-C這條邊在Gobsv中，從t0到t3的過程中經歷了消失-出現-消失的過程，而實際上它一直存在。因此我們希望能區分出這些邊或接點在Gobsv的出現／消失是由于動態路由還是真實的拓撲改變引起的，這個問題就是拓撲活性問題。為了區分這兩種不同，將Greal中的拓撲元素（節點／邊）的加入／移除稱為出生（birth）／死亡（death），而將Gobsv中的元素加入／移除稱為出現（appearance）／消失（disappearance）。研究發現，Greal拓撲元素的出生／死亡和Gobsv中的元素出現／消失并不對應。因此我們要去發現真正由于元素“死亡”而“消失”、“出生”而“出現”的情況，篩除因動態路由等原因造成的同一個元素在不同時刻反復消失又出現的干擾情況（實際在Greal中一直存在）。通過觀察Gobsv發現Greal中的節點／邊的“死亡”和“出生”規律來驗證理論上的拓撲模型的生長過程，才能取得合理的結論。

Srinivas Shakkottai等提出一個可以驗證的模型應該符合如下的條件：模型盡可能簡單，參數盡可能少；所有的參數必須是可測量的，排除主觀假設；易用分析手段來處理。因此，作為拓撲建模者，在建模過程中始終能考慮這些最優階段的驗證要求，無疑對模型的有效性、真實性、合理性是有積極意義的。

5 存在的問題和發展趨勢

Internet拓撲建模從最初的隨機模型到結構模型，隨著復雜網絡的無標度性質的發現，基于度的模型應運而生。研究表明，基于度的模型不但很好地反映出了局部特征，同時也符合Internet的結構特征，但反之不成立。盡管有研究表明，網絡的核心層與邊緣層在結構上有模糊的傾向，但仍然不能忽視Internet整體上仍然是一個等級網絡的事實。因此，一個好的拓撲生成器，不僅要考慮局部特征，也要兼顧整體的結構特征。

Internet拓撲在結構上的演變對我們以往的一些靜態統計度量，如聚簇系數、平均距離等，也提出了挑戰：這些統計度量是否還存在？在數值上又有哪些變化？這些都要求我們不斷地去更新拓撲測量方法，獲取更新的認識。對Internet拓撲研究的最終目的是能夠預測未來，但這恰恰也是最難的。Internet拓撲對于網絡領域的其它研究起著關鍵性的基礎作用，可應用于網絡模擬、研究網絡病毒傳播機理、網絡協議性能等。

將統計物理的熵概念引入對Internet拓撲結構的統計特性研究，將是我們下階段需要研究的方向。尤其是非廣延量Tsallis熵［26］對于研究Internet這樣具有明顯異配性、冪律特征的系統，是一個非常合適的統計量。

最后，我們發現目前大量的工作集中在對物理拓撲結構的研究，這樣的工作吸引了大量的數學、物理等學科的學者參與。從計算機網絡學科看，Internet是由多層協議構成的異質網絡，僅對物理連接性的研究是不夠的，在不同的協議層需要的拓撲信息其實是不一致的。因此我們提出分層拓撲建模的思路，分別在物理層（物理介質連接性）、網絡層（路由路徑構成）、應用層（P2P、覆蓋網、虛擬網路由路徑構成）測量、分析和研究構建各種邏輯拓撲的方法，這樣的研究成果會對網絡研究界更具實用意義。我們希望這些研究成果可應用于下階段關于大規模虛擬網模擬的研究。

6 結論

本文詳細介紹了Internet的靜態拓撲模型和動態拓撲模型，并對拓撲模型在節點度和結構方面的演化進行了詳細的討論，最后分析了存在的問題并提出了以后的發展方向，希望為Internet拓撲建模提供一定的參考。

［1］FaloutsosM，Faloutsos P，Faloutsos C.On power-law relationships of the internet topology［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，1999：251-262.

［2］Barab′asi A，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［3］Zhou S，Mondragon R J.The rich-club phenomenon in the Internet topology［J］.IEEECommunication Letters，2004，8（3）：180-182.

［4］Mahadevan P，Krioukov D，Fall K，etal.Systematic topology analysis and generation using degree correlations［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication. New York：ACM，2006：135-146.

［5］Oliveira R，Zhang B，Zhang L.Observing the evolution of Internet AS topology［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，2007：313-324.

［6］Shakkottai S，Fomenkov M，Koga R，et al.Evolution of the Internet AS-Level Ecosystem［J］.European Physical JournalB，2010，74（2）：271-278.

［7］Zhang GQ，Yang Q F，Cheng SQ，et al.Evolution of the Internet and its cores［J］.New Journal of Physics，2008，10（12）：123027.

［8］Krioukov D，Chung F，Claffy K，et al.2007 The workshop on Internet topology（WIT）report［J］.ACM SIGCOMM Computer Communication Review，2007，37（1）：69-73.

［9］Li L，Alderson D，WillingerW，etal.A first-principlesapproach to understanding the Internet′s router-level topology［J］.ACM SIGCOMM Computer Communication Review，2004，34（4）：3-14.

［10］Haddadi H，Uhlig S，Moore A，et al.Modeling internet topology dynamics［J］.Computer Communication Review，2008，38（2）：65-68.

［11］MahadeVan P，Krioukov D，Fall K.Systematic topology analysisand generation using degree correlations［J］.SIGCOMM，2006，36（4）：135-146.

［12］Réka Albert，Albert-LászlóBarabási.Topology of Evolving Networks：Local Events and Universality［J］.Physical Review Letters，2000，85（24）：5234-5237.

［13］Tian Bu，Don Towsley.On Distinguishing between Internet Power Law Topology Generators［C］／／Proceedings of the Twenty First Annual Joint Conference of the IEEEComputer and Communications Societies.New York：IEEE，2002：638-647.

［14］Chen Q，Chang H，Govindan R，etal.The Origin of Power Laws in Internet Topologies Revisited［C］／／Proceedings of the Twenty First Annual Joint Conference of the IEEE Computer and Communications Societies.New York：IEEE，2002：608-617.

［15］BianconiG，CaldarelliG，Capocci A.Number of h-cycles in the Internet at the autonomous system level［EB／OL］. 2003-10-15［2003-10-16］.http：arxiv.org／condmat／0310339.

［16］Zhou S，Mondragon R J.Towards modeling the Internet topology：the interactive growth model［J］.Teletraffic Science and Engineering，2003（5）：121-130.

［17］Zhou S，Mondragon R J.Accurately modeling the Internet topology［J］.Physical Review E，2004，70（6）：106-108.

［18］Pastor-Satorras R，V′azquez A，Vespignani A.Dynamical and Correlation Properties of the Internet［J］.Physical Review Letters，2001，87（25）：1-4.

［19］V′azquez A，Pastor-Satorras R，Vespignani A.Largescale topological and dynamical properties of Internet［J］. Physical Review E，2001，65（6）：1-13.

［20］Chen Q，Chang H，Govindan R，etal.The origin of power laws in internet topologies revisited［C］／／Proceedings of the Twenty-First Annual JointConference of the IEEEComputer and Communications.［S.l.］：IEEE，2002：608-617.

［21］Shakkottai S，Fomenkov M，Koga R，etal.Evolution of the Internet AS-Level Ecosystem［J］.European Physical Journal B，2010，74（2）：271-278.

［22］Chang H，Jamin S，WillingerW.Internet connectivity at the AS-level：An optimization-driven modeling approach［C］／／Proceedings of the ACM SIGCOMM 2003Workshops. Karlsruhe，Germany：ACM，2003：33-46.

［23］Pittel B，Spencer J，Wormald N.Sudden emergence of a giant k-core in a random graph［J］.Journal of Combinatorial Theory B，1996，67（1）：111-151.

［24］Hiroshi Fujinoki，Andrew Hauck.Analysis on the Trend of Recent Changes in the Internet Structure：Departing from the Long-Assumed Tree-Structure Model［C］／／Proceedings of the 8th International Conference on Computing，Communication and Control Technology.Orland，Florida，USA：［s.n.］，2010.

［25］Craig Labovitz，Scott Iekel-Johnson，Danny McPherson，et al.Internet Inter-Domain Traffic［C］／／Proceedings of the ACM SIGCOMM 2010 Conference on SIGCOMM.New York：ACM，2010：75-86.

［26］Tsallis C.Introduction to nonextensive statisticalmechanics—approaching a complex world［M］.New York：Springer，2009.

GUANXiao-huiwas born in Luohe，Henan Province，in 1977. She received the M.S.degree from Zhejiang University in 2005.She is now a lecturer.Her research direction is networkmultimedia.

Email：guanxh＠zjwchc.com

錢亞冠（1976—），男，浙江嵊州人，2005年于浙江大學計算機學院獲碩士學位，現為講師，主要從事計算機網絡建模方面的研究；

QIAN Ya-guan was born in Shengzhou，Zhejiang Province，in 1976.He received the M.S.degree from Zhejiang University in 2005.He is now a lecturer.His research concerns computer networkmodeling.

周志敏（1966—），女，河北保定人，碩士，副教授，主要從事計算機硬件的研究和開發。

ZHOU Zhi-min was born in Baoding，Hebei Province，in 1966.She is now an associate professor with the M.S.degree.Her research concerns R＆D of computer hardware.

A Survey of Internet Topology Modeling and Evolution

GUAN Xiao-hui1，QIAN Ya-guan2，ZHOU Zhi-min1
（1.Department of Computer and Information Enginering，ZhejiangWater Conservancy and Hydropower College，Hangzhou 310018，China；2.Science College，Zhejiang University of Science and Technology，Hangzhou 310023，China）

It iswell known that clearly learning the realistic Internet topology and its evolution trend will play an important role in the research of next generation network and the operatingmanagement.This papermakes a comprehensive survey of the topology evolution based on node degree and structure，and reviews static topology models and dynamic topology models.Finally，it proposes the future research directions，that are using Tsallis entropy to explore the topology statistics and using layered fashion to study the topology structure.

next generation network；Internet topologymodel；power-law；evolution；node degree；Tsallis entropy

Scientific Research Foundation of Zhejiang Educational Committee（Y201017457）

TP393.02

A

10.3969／j.issn.1001-893x.2011.11.025

關曉惠（1977—），女，河南漯河人，2005年于浙江大學計算機學院獲碩士學位，現為講師，主要研究方向為網絡多媒體；

1001-893X（2011）11-0121-08

2011-07-11；

2011-08-15

浙江省教育廳科研項目資助（Y201017457）