Internet路由級(jí)宏拓?fù)浣Y(jié)構(gòu)的TL模型.pdf

1、Internet作為一個(gè)典型的復(fù)雜網(wǎng)絡(luò)實(shí)例，對(duì)其宏觀拓?fù)浣Y(jié)構(gòu)的特征分析及建模研究是目前研究的熱點(diǎn)問(wèn)題，受到學(xué)術(shù)界廣泛關(guān)注。近年來(lái)人們?cè)谠擃I(lǐng)域的研究取得了長(zhǎng)足的進(jìn)展，尤其是在Internet拓?fù)浣Y(jié)構(gòu)的分析中發(fā)現(xiàn)了冪律分布規(guī)律之后，提出了許多遵循冪律特征的拓?fù)渖伤惴ㄒ约巴負(fù)淠Ｐ停瓿闪藦脑缙诩兇獾慕?jīng)驗(yàn)假設(shè)到客觀數(shù)據(jù)分析，從單純的計(jì)算機(jī)網(wǎng)絡(luò)研究到復(fù)雜系統(tǒng)特征化研究的建模過(guò)程的飛躍。但這些提出的模型大多為自治系統(tǒng)層面(autonomous s

2、ystem，AS-level)的Internet拓?fù)淠Ｐ?，而在相?duì)更細(xì)粒度的，更能表現(xiàn)：Intemet本質(zhì)特征的路由器層面(router-level)Internet拓?fù)浣?，由于?guī)模巨大，以及獲取完整的路由級(jí)拓?fù)浞矫娴睦щy，目前研究還較少。揭示路由級(jí)Internet宏觀拓?fù)浣Y(jié)構(gòu)的特征規(guī)律并建模，是幫助人們用其來(lái)對(duì)Internet進(jìn)行分析、預(yù)報(bào)、決策或控制的需要，也是進(jìn)行Internet相關(guān)的研究的基礎(chǔ)，因此必然具有重要的意義。

3、 Internet拓?fù)溲芯颗c復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)界將Internet拓?fù)浣Ｑ芯康膬?nèi)容大致歸結(jié)為三個(gè)問(wèn)題：(1)如何獲得一份完整而準(zhǔn)確的Internet拓?fù)鋽?shù)據(jù)；(2)如何對(duì)Internet網(wǎng)絡(luò)拓?fù)涮卣鬟M(jìn)行分析并建立模型；(3)如何使用模型構(gòu)造一幅類似于Internet的拓?fù)鋱D。這三個(gè)問(wèn)題分別對(duì)應(yīng)于三個(gè)研究方向，即拓?fù)浣Y(jié)構(gòu)測(cè)量、拓?fù)涮卣靼l(fā)現(xiàn)與建模以及可視化拓?fù)渖善鏖_(kāi)發(fā)。其中拓?fù)涮卣靼l(fā)現(xiàn)與建模是重點(diǎn)，拓?fù)涮卣靼l(fā)現(xiàn)指針對(duì)Internet測(cè)量拓?fù)浣Y(jié)

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

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

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

7、rnet測(cè)量拓?fù)渚哂蟹浅Ｃ黠@的frequency-degree冪律分布與degree-rank冪律分布規(guī)律。其中。frequency-degree冪律分布符合冪律指數(shù)為2.1406的分布規(guī)律，而degree-rank冪律分布則分為兩部分，主體節(jié)點(diǎn)服從冪律指數(shù)為0.84639的分布，而度值最大的部分節(jié)點(diǎn)卻符合冪律指數(shù)為0.29981的分布規(guī)律。在CCDF(d)-degree冪律分布研究中發(fā)現(xiàn)，Weibull分布要比冪律分布擬合效果更好，也

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

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

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