Internet路由級宏拓撲結(jié)構(gòu)的TL模型.pdf

1、Internet作為一個典型的復雜網(wǎng)絡實例，對其宏觀拓撲結(jié)構(gòu)的特征分析及建模研究是目前研究的熱點問題，受到學術界廣泛關注。近年來人們在該領域的研究取得了長足的進展，尤其是在Internet拓撲結(jié)構(gòu)的分析中發(fā)現(xiàn)了冪律分布規(guī)律之后，提出了許多遵循冪律特征的拓撲生成算法以及拓撲模型，完成了從早期純粹的經(jīng)驗假設到客觀數(shù)據(jù)分析，從單純的計算機網(wǎng)絡研究到復雜系統(tǒng)特征化研究的建模過程的飛躍。但這些提出的模型大多為自治系統(tǒng)層面(autonomous s

2、ystem，AS-level)的Internet拓撲模型，而在相對更細粒度的，更能表現(xiàn)：Intemet本質(zhì)特征的路由器層面(router-level)Internet拓撲建模，由于規(guī)模巨大，以及獲取完整的路由級拓撲方面的困難，目前研究還較少。揭示路由級Internet宏觀拓撲結(jié)構(gòu)的特征規(guī)律并建模，是幫助人們用其來對Internet進行分析、預報、決策或控制的需要，也是進行Internet相關的研究的基礎，因此必然具有重要的意義。

3、 Internet拓撲研究與復雜網(wǎng)絡學術界將Internet拓撲建模研究的內(nèi)容大致歸結(jié)為三個問題：(1)如何獲得一份完整而準確的Internet拓撲數(shù)據(jù)；(2)如何對Internet網(wǎng)絡拓撲特征進行分析并建立模型；(3)如何使用模型構(gòu)造一幅類似于Internet的拓撲圖。這三個問題分別對應于三個研究方向，即拓撲結(jié)構(gòu)測量、拓撲特征發(fā)現(xiàn)與建模以及可視化拓撲生成器開發(fā)。其中拓撲特征發(fā)現(xiàn)與建模是重點，拓撲特征發(fā)現(xiàn)指針對Internet測量拓撲結(jié)

4、構(gòu)的特征分析與特征參量提取，建立模型指根據(jù)特征參量建立拓撲模型，即本文提出的TL模型，這是本文研究的核心內(nèi)容；拓撲結(jié)構(gòu)測量作為拓撲特征分析與建模的基礎與前提，也是本文中比較重要的部分；而拓撲結(jié)構(gòu)的可視化問題由于涉及范圍較廣，可單獨做為研究課題，因此不在本文中做為重點研究內(nèi)容。 本文首先針對分布在世界范圍內(nèi)的21個CAIDA監(jiān)測點通過主動探測方法得到的路由級Internet拓撲測量結(jié)果，分別進行同名IP解析與單點測量導致的采樣偏見

5、問題分析。在使用CAIDA iffinder同名IP測量結(jié)果集對多組Internet測量數(shù)據(jù)解析時，發(fā)現(xiàn)每組中合并的路由數(shù)占總路由數(shù)的3％～8％，邊數(shù)則從7％～30％不等。合并路由數(shù)增長比較平緩，說明測量結(jié)果集數(shù)量龐大，基本上已經(jīng)完全覆蓋了iffinder提供了同名解析空間。在單點測量問題分析中發(fā)現(xiàn)，隨著測量點數(shù)的增加，新測量到的路由增量呈y=88782.0-18993×ln(x)的對數(shù)曲線分布形式。進一步分析表明，以目前CAIDA監(jiān)測

6、點的分布情況，只有當測量點數(shù)達到至少107個時才可能完全解決采樣偏見問題，即沒有路由器在測量中遺失。而本文測量結(jié)果集中CAIDA監(jiān)測點數(shù)為21，因此需要在未來工作中對拓撲測量問題做進一步研究。其次，本文對Internet拓撲結(jié)構(gòu)特征進行了不同層面的分析與研究。首先論述了Internet測量拓撲的冪律分布特征，包括frequency-degree冪律分布、degree-rank冪律分布與CCDF(d)-degree冪律分布等，發(fā)現(xiàn)Inte

7、rnet測量拓撲具有非常明顯的frequency-degree冪律分布與degree-rank冪律分布規(guī)律。其中。frequency-degree冪律分布符合冪律指數(shù)為2.1406的分布規(guī)律，而degree-rank冪律分布則分為兩部分，主體節(jié)點服從冪律指數(shù)為0.84639的分布，而度值最大的部分節(jié)點卻符合冪律指數(shù)為0.29981的分布規(guī)律。在CCDF(d)-degree冪律分布研究中發(fā)現(xiàn)，Weibull分布要比冪律分布擬合效果更好，也

8、就是說，對于本文Internet拓撲來說，其節(jié)點度的CCDF不一定符合冪律分布。其次研究了Internet平均度值分布情況，并統(tǒng)計得出葉子路由在Internet測量路由總數(shù)所占比重平穩(wěn)地保持在17％附近的結(jié)論，說明Internet拓撲結(jié)構(gòu)中，葉子路由的分布具有一定規(guī)律性；之后研究了Internet拓撲結(jié)構(gòu)的譜密度分布與無符號拉普拉斯譜(SLS)分布結(jié)果，通過對拓撲結(jié)構(gòu)各異的五種采樣拓撲圖，分別進行譜密度．特征值分布分析，發(fā)現(xiàn)五組分析結(jié)果

9、表現(xiàn)出高度的一致性，證明了Internet拓撲結(jié)構(gòu)的自相似性。而通過四組3000點采樣拓撲進行SLS分布分析，發(fā)現(xiàn)盡管四組3000點采樣路由與連接互不相同，但SLS譜分布卻非常相似，四組采樣拓撲在特征值λ=1處重數(shù)均較高，重數(shù)次高的特征值都群聚在λ=2處。在特征值從2～10<'3>變化過程中表現(xiàn)出較明顯的冪律分布特性，其冪指數(shù)值保持在3.2813至3.8013之間，特征指數(shù)接近。這同樣從另一個角度證明了Internet拓撲結(jié)構(gòu)的自相似性

10、。 之后，本文根據(jù)Internet拓撲特征分析結(jié)果(特征參量)提出了一個基于三層(ThreeLevel)路由節(jié)點的TL模型。針對部分源于Internet拓撲統(tǒng)計分析的模型特征參數(shù)，進行了以無符號拉普拉斯譜密度(SLS)分布結(jié)果的為校驗值(評估函數(shù))的遺傳優(yōu)化。對優(yōu)化后模型，本文從定性分析、定量分析與可視化結(jié)果的直觀視覺角度予以了分析與評價。定性分析結(jié)果表明，TL模型兼具純靜態(tài)與純動態(tài)模型的優(yōu)點，即避免了純靜態(tài)模型下過多的人為干預