大規(guī)模網(wǎng)絡(luò)拓?fù)錅y(cè)量與分析研究.pdf

1、Internet，意為“網(wǎng)絡(luò)的網(wǎng)絡(luò)”，由上萬(wàn)個(gè)被稱為自治系統(tǒng)（Autonomous system, AS）的網(wǎng)絡(luò)互聯(lián)而成，每個(gè)AS又由一組路由器互聯(lián)而成。這兩個(gè)層次的互聯(lián)結(jié)構(gòu)分別稱為網(wǎng)絡(luò)的AS級(jí)拓?fù)浜虸P級(jí)拓?fù)?。大?guī)模網(wǎng)絡(luò)拓?fù)涞臏y(cè)量與分析已經(jīng)受到來(lái)自計(jì)算機(jī)科學(xué)、物理學(xué)、數(shù)學(xué)領(lǐng)域的廣泛關(guān)注，因?yàn)槿藗兿嘈?，認(rèn)識(shí)網(wǎng)絡(luò)拓?fù)涞谋举|(zhì)不僅是開發(fā)高效、魯棒、可擴(kuò)展互聯(lián)網(wǎng)絡(luò)的基礎(chǔ)，更是尋找復(fù)雜系統(tǒng)中普適定律的一條關(guān)鍵途徑。然而，當(dāng)前有三個(gè)問(wèn)題亟待解決：(

2、1)缺乏完整、準(zhǔn)確的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)；(2)大規(guī)模網(wǎng)絡(luò)特征化框架尚未建立；(3)網(wǎng)絡(luò)拓?fù)涞钠鹪春脱莼瘷C(jī)理尚未明確。
　　為此，本文以準(zhǔn)確描述網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)性質(zhì)和演化趨勢(shì)為目標(biāo)。首先，完整地測(cè)量大規(guī)模網(wǎng)絡(luò)IP級(jí)拓?fù)?；然后，比較不同完整性的IP級(jí)拓?fù)渲g的特征差異；接著，測(cè)量AS級(jí)拓?fù)洳⒎治鯝S級(jí)拓?fù)涮卣鞑町?；最后，分析AS級(jí)拓?fù)溲莼瘹v史。
　　鑒于IP級(jí)拓?fù)錅y(cè)量實(shí)踐中目標(biāo)采樣的不充分以及測(cè)量模型中存在的失真，實(shí)施了蠻力測(cè)量實(shí)驗(yàn)，發(fā)

3、現(xiàn)通常的低密度隨機(jī)采樣丟失了大量信息。通過(guò)分析路由行為，發(fā)現(xiàn)信息丟失的主要原因在于子網(wǎng)結(jié)構(gòu)多樣性，次要原因在于路徑多樣性；同時(shí)證明一種優(yōu)化采樣方法適用于長(zhǎng)期測(cè)量實(shí)踐。開發(fā)了一個(gè)測(cè)量工具fastrace，其中所采用的新技術(shù)可在保證完整性的同時(shí)將探測(cè)負(fù)載降低一半。2004年底對(duì)中國(guó)IP級(jí)拓?fù)涞臏y(cè)量發(fā)現(xiàn)了約8萬(wàn)個(gè)節(jié)點(diǎn)，這是CAIDA skitter所測(cè)得拓?fù)湟?guī)模的四倍?；谶@一結(jié)果，考察了地區(qū)網(wǎng)絡(luò)規(guī)模與其經(jīng)濟(jì)情況之間的相關(guān)性。
　　為考

4、察不同完整性IP級(jí)拓?fù)鋽?shù)據(jù)在特征上的共性與差異，首先，給出了拓?fù)涮卣骰亩攘苛斜?，并分析了度量間相關(guān)性。然后，基于可視化技術(shù)，觀察了拓?fù)溟g的直觀差異。接著，提出了子圖覆蓋模式的概念，來(lái)描述子圖對(duì)全圖中不同重要性部分的覆蓋程度。使用子圖覆蓋模式發(fā)現(xiàn)，中國(guó)網(wǎng)絡(luò)處于Internet的邊緣，表現(xiàn)為離心性；而skitter和fastrace測(cè)得的中國(guó)拓?fù)湓诤喜⑼負(fù)渲蟹謩e表現(xiàn)為向心性和離心性。最后，將子圖覆蓋模式應(yīng)用于特征差異分類，發(fā)現(xiàn)多數(shù)冪律指數(shù)

5、是魯棒的，而其他度量對(duì)圖規(guī)?；蚋采w模式是敏感的。
　　為了解AS級(jí)拓?fù)錅y(cè)量數(shù)據(jù)的多樣性，運(yùn)用綜合集成的思想來(lái)廣泛收集拓?fù)鋽?shù)據(jù)并比較其間差異。采用基于BGP（Border Gateway Protocol）、基于traceroute和基于IRR（Internet Routing Registry）的方法從不同數(shù)據(jù)源獲取了多幅拓?fù)淇煺?。其間，提出了基于更新時(shí)間的IRR信息過(guò)濾法，以及一種基于層次的互連關(guān)系推斷法。基于集合運(yùn)算對(duì)快照進(jìn)行

6、了分組比較，發(fā)現(xiàn)基于BGP更新消息的數(shù)據(jù)具有較好完整性和一致性，而基于traceroute的數(shù)據(jù)一致性較差。進(jìn)而得到了一幅較完整可信的中國(guó)AS圖，比通常采用的RouteViews路由表多出近65％的鏈接。通過(guò)對(duì)典型拓?fù)鋽?shù)據(jù)的特征進(jìn)行比較后發(fā)現(xiàn)：在定量上，平均度是主導(dǎo)差異的主特征；在定性上，多數(shù)特征本身相同，但其統(tǒng)計(jì)顯著性不同；基于BGP測(cè)量和基于traceroute測(cè)量分別低估和高估了連通性。對(duì)全球AS級(jí)拓?fù)涮卣鞯谋容^印證了上述發(fā)現(xiàn)，為

7、最近關(guān)于Rich-club現(xiàn)象的爭(zhēng)論提供了一條新的解決途徑。
　　為了解AS級(jí)拓?fù)溲莼厔?shì)與機(jī)理，對(duì)AS級(jí)拓?fù)錃v史進(jìn)行了全面觀測(cè)。首先，提出了拓?fù)渖L(zhǎng)方式和優(yōu)先附著函數(shù)的測(cè)量方法。接著，對(duì)中國(guó)AS級(jí)拓?fù)錃v史進(jìn)行觀察，發(fā)現(xiàn)具有非交互性的拓?fù)錅邕^(guò)程，以及平均度增長(zhǎng)、特征顯著性累積現(xiàn)象。然后，通過(guò)觀察全球AS級(jí)拓?fù)錃v史，發(fā)現(xiàn)最大度增長(zhǎng)受抑制現(xiàn)象，提出了無(wú)尺度是一個(gè)階段性特征的假設(shè)；發(fā)現(xiàn)非相配性減弱現(xiàn)象，提出了度相關(guān)性將向中立性轉(zhuǎn)變的假設(shè)