大規(guī)模網(wǎng)絡(luò)拓撲測量與分析研究.pdf

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

2、1)缺乏完整、準(zhǔn)確的網(wǎng)絡(luò)拓撲數(shù)據(jù)；(2)大規(guī)模網(wǎng)絡(luò)特征化框架尚未建立；(3)網(wǎng)絡(luò)拓撲的起源和演化機理尚未明確。
　　為此，本文以準(zhǔn)確描述網(wǎng)絡(luò)拓撲的結(jié)構(gòu)性質(zhì)和演化趨勢為目標(biāo)。首先，完整地測量大規(guī)模網(wǎng)絡(luò)IP級拓撲；然后，比較不同完整性的IP級拓撲之間的特征差異；接著，測量AS級拓撲并分析AS級拓撲特征差異；最后，分析AS級拓撲演化歷史。
　　鑒于IP級拓撲測量實踐中目標(biāo)采樣的不充分以及測量模型中存在的失真，實施了蠻力測量實驗，發(fā)

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

4、察不同完整性IP級拓撲數(shù)據(jù)在特征上的共性與差異，首先，給出了拓撲特征化的度量列表，并分析了度量間相關(guān)性。然后，基于可視化技術(shù)，觀察了拓撲間的直觀差異。接著，提出了子圖覆蓋模式的概念，來描述子圖對全圖中不同重要性部分的覆蓋程度。使用子圖覆蓋模式發(fā)現(xiàn)，中國網(wǎng)絡(luò)處于Internet的邊緣，表現(xiàn)為離心性；而skitter和fastrace測得的中國拓撲在合并拓撲中分別表現(xiàn)為向心性和離心性。最后，將子圖覆蓋模式應(yīng)用于特征差異分類，發(fā)現(xiàn)多數(shù)冪律指數(shù)

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

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

7、最近關(guān)于Rich-club現(xiàn)象的爭論提供了一條新的解決途徑。
　　為了解AS級拓撲演化趨勢與機理，對AS級拓撲歷史進行了全面觀測。首先，提出了拓撲生長方式和優(yōu)先附著函數(shù)的測量方法。接著，對中國AS級拓撲歷史進行觀察，發(fā)現(xiàn)具有非交互性的拓撲滅過程，以及平均度增長、特征顯著性累積現(xiàn)象。然后，通過觀察全球AS級拓撲歷史，發(fā)現(xiàn)最大度增長受抑制現(xiàn)象，提出了無尺度是一個階段性特征的假設(shè)；發(fā)現(xiàn)非相配性減弱現(xiàn)象，提出了度相關(guān)性將向中立性轉(zhuǎn)變的假設(shè)