大型互聯(lián)網(wǎng)絡實現(xiàn)拓撲仿真如何抽樣3.0

1、大型互聯(lián)網(wǎng)絡實現(xiàn)拓撲仿真如何抽樣大型互聯(lián)網(wǎng)絡實現(xiàn)拓撲仿真如何抽樣摘要：在本文中，我們闡述了一種如何從大型互聯(lián)網(wǎng)絡中抽取小樣本的方法，盡管最近的研究活動表明：用現(xiàn)實圖形模擬和仿真大型互聯(lián)網(wǎng)絡任然是一個沒有解決的問題。所以先前試圖產(chǎn)生這種圖類的工作都是從零開始。我們致力于完善已存在的拓撲網(wǎng)絡結(jié)構(gòu)的簡化工作，具體說，這項工作分為三個部分。首先我們提出了一系列的簡單方法，可以歸納為3類：（a）刪除方法（b）收縮的方法（c）勘探方法。我們驗證了這

2、些方法中的一些保持了原始圖的一些關鍵特性。通過執(zhí)行我們的方法證明了當有效的減少網(wǎng)絡70%的節(jié)點時，網(wǎng)絡任然能夠保持其特性。第二，驗證了我們的方法能夠很好的應對基本構(gòu)造發(fā)生器。最后，我們成功的驗證了我們的方法在實際有效評價多播路由中的研究，除了其實際應用，圖的采樣來自于網(wǎng)絡的某個單獨特性。1、導言各種網(wǎng)絡互聯(lián)協(xié)議要求能夠在從大型互聯(lián)網(wǎng)絡中抽取的小樣本上執(zhí)行。實時圖應能實現(xiàn)大范圍的模擬，特別是非常細節(jié)性的例如包一級的模擬。為了驗證抽樣的有效

3、性，在給定節(jié)點數(shù)的圖上做實驗并取實驗結(jié)果的平均值。做實驗時允許實驗人員所測節(jié)點數(shù)在允許范圍之外。特別的它證實了這種方法能夠適應不同層的網(wǎng)絡協(xié)議隨機網(wǎng)絡規(guī)模的增加，從而能夠?qū)ξ磥淼幕ヂ?lián)網(wǎng)做出更準確的預測。目前，所有一直的仿真模型產(chǎn)生的圖都是來自網(wǎng)絡的某個特定屬性。我們的工作正好采用相反的途徑：我們希望要求降級大型網(wǎng)絡互聯(lián)距離來產(chǎn)生小樣本拓撲結(jié)構(gòu)。這個想法可被認為是一個采樣圖，并引起了其他方面的注意。有趣的是，在現(xiàn)有的互聯(lián)網(wǎng)絡拓撲發(fā)生器中，

4、還沒有一個足夠精確得以被廣泛接受的發(fā)生器這些發(fā)生器產(chǎn)生了經(jīng)過實驗論證的仿真圖，但是沒有必要和互聯(lián)網(wǎng)絡上所有已知的拓撲特性相匹配。近年來在應用層的大多數(shù)圖發(fā)生器產(chǎn)生的圖可以增長，這是一個具有建設性的方法這是此領域自互聯(lián)網(wǎng)絡上范縣傾斜度分布的空前運動。產(chǎn)生器使用有“偏向性的”或“優(yōu)生的”增長政策來生成冪律度分布這些有建設性的方法通過集中度分布與真實網(wǎng)絡中的距離相匹配產(chǎn)生的合成圖。但通常不能兼顧到拓撲結(jié)構(gòu)其它方法來寫入文檔。本文中，我們闡述了

5、下列問題：如何從真實網(wǎng)絡拓撲中抽樣或得一個小的仿真圖。像我們隨后解釋的那樣，我們在域內(nèi)和自治系統(tǒng)一級檢查網(wǎng)絡的拓撲結(jié)構(gòu)。我們這種方法的總體目標是非常明確的：無論是從大的抽樣圖還是小的抽樣圖上都能夠得出同樣的結(jié)論。雖然相關工作已在其他領域中存在，但是在網(wǎng)絡仿真領域這是一個全新的問題。我們稱這種抽樣方法為還原圖。非常非正式地，直覺告訴我們這種方法應保證不破壞網(wǎng)絡已存在的一些特性，期望這種方法能從適應性和統(tǒng)計特性上完成此任務是合理的。相反，這

6、種方法受到了首先確認某功能然后正確產(chǎn)生其他性能的方法的挑戰(zhàn)。我們?nèi)绾卧u價我們方法的成功之處呢？建立真實產(chǎn)生圖的標準是一個開放無終止的問題，在圖的抽樣中，這個問題變的更棘手：例如怎樣的互聯(lián)網(wǎng)絡距離能減少圖的匹配問題如何區(qū)分兩個實體如何匹配網(wǎng)絡的特性等問題。如果這種特性不隨著尺寸的改變而改變，那么這個目標就是相等的。然而，似乎沒有脫離時間的獨立拓撲存在。研究表明：即使每個網(wǎng)絡互聯(lián)距離在AS層都存在冪率特性，但他們的斜率都是不同的。這樣，我們

7、選擇上面的第一種方法來把簡化圖和其等價的網(wǎng)絡互聯(lián)距離進行比較。我們使用兩種類型的測量來比較圖。第一類包括各種圖的不變量，例如平均度。第二種類型的測量是基于在兩幅圖中多播路由協(xié)議在其上的比較。事實證明，這些方法在大的互聯(lián)網(wǎng)絡上的測量結(jié)果和小的網(wǎng)絡上的測量結(jié)果是相似的。這就簡單的通過比較得出結(jié)論:這種測試方法在簡化圖上得到的結(jié)果與大的互聯(lián)網(wǎng)絡得到的結(jié)果是一致的。請注意我們的測量方法是參閱了一些廣泛應用于復雜網(wǎng)絡測量的文獻[816351244

8、23439]研究者拿來在此領域做研究，并且這是記錄了近五年來唯一存在的一份檔案數(shù)據(jù)應為我們的研究需要很大范圍的數(shù)據(jù)，所以這份數(shù)據(jù)使我們特地選作我們研究的數(shù)據(jù)。用IYYMMPD的形式標記網(wǎng)絡實例，這種標注形式用最后的兩個數(shù)字來標注年月日。例如：2001年5月7日收集的數(shù)據(jù)標注為I010507，在我們實驗中我們使用從1997年11月到2003年3月的數(shù)據(jù)。請注意，在我們的研究中我們使用從1997年到2003年跨越6年的網(wǎng)絡拓撲數(shù)據(jù)。由于這點

9、，我們確信我們的結(jié)果與網(wǎng)絡拓撲的演化是極其相似的。這是我們主要用19972001年數(shù)據(jù)進行仿真，但是我們也用了2003年收集的數(shù)據(jù)仿真。22圖的性質(zhì)存在幾個圖的特性來獲得真實網(wǎng)絡的本領。我們便用幾乎所有機制來比較簡化圖的真實性。這些特性被認為是必需的，但不是以保證構(gòu)造圖的真實性。221平均程度及其標準偏差圖的平局度定義為2mn，m是邊數(shù)，n是節(jié)點時。我們使用這個測量機制來比較簡化圖與真實網(wǎng)絡拓撲的密集性。人們注意到了平均度隨時間的增長，

10、隨著互聯(lián)網(wǎng)規(guī)模的增加，自1997年的3.42到1999年11月的3.93，同時，互聯(lián)網(wǎng)絡尺寸大約增長了一倍，為了測量度分布如何分布在平均值附近，我們同樣測量標準偏差。222度分布冪率分布使用了近似的斜率分布，這是由經(jīng)驗觀察得來的。這里，我們重點關注冪率分布1的度分布指數(shù)和冪率分布2的度分布指數(shù)。節(jié)點的度分布指數(shù)是按照節(jié)點的指數(shù)斜率分布的，即第K節(jié)點的度的大小排在第K位。度分布曲線是節(jié)點度分布的指數(shù)曲線，值得注意的是，如果節(jié)點分布極具冪率

11、性，這兩種冪率分布在理論程度上是相等的。事實上，它們所提出的度分布特點是大致相同的。在這種測量機制中，驗證了度分布的存在性并且比較了冪率分布的指數(shù)值，通過對關系系數(shù)的量化發(fā)現(xiàn)米律分布是很相似的。關系系數(shù)對相似精確的一個測量，超過97%的系數(shù)被認為都是合理的近似。223光譜分析網(wǎng)絡拓撲結(jié)構(gòu)光譜分析采用鄰接矩陣圖分析網(wǎng)絡的聚簇性和空間特性、光譜分析在拓撲結(jié)構(gòu)的聚簇特性中獲得了顯著的信息。它包含了以前使用過的聚簇系數(shù)統(tǒng)計法。具體點：光譜分析測

12、量的是整個網(wǎng)絡拓撲結(jié)構(gòu)的逆置鄰接矩陣的特征向量。仿真圖描述了一系列與特征向量有關的特征值。結(jié)果表明：網(wǎng)絡的聚簇性并沒有隨著網(wǎng)絡尺寸的增大而改變。224同邊函數(shù)與節(jié)點跳周邊函數(shù)定義為大多數(shù)節(jié)點之間的跳數(shù)，周邊函數(shù)是對圖的輸出的一個測量。距離分布和節(jié)點跳并沒有隨時間而改變，這是一個很好的度量比較指標。這是我們繪出了在節(jié)點跳內(nèi)節(jié)點能否互相到達的百分率。值得注意的是，近來其他測量方法已經(jīng)被提出來作為圖的測量比較方法。一個基于鄰接節(jié)點度的概性方法

13、已經(jīng)被提出來了。23圖產(chǎn)生器早期的圖產(chǎn)生器對圖的傾斜度分布的匹配是失敗的，在思想上，近來的圖產(chǎn)生器用冪率分布產(chǎn)生拓撲結(jié)構(gòu)。早期的BarabasiAlbert模型通過偏好連接產(chǎn)生圖：在新的節(jié)點連接已經(jīng)存在的節(jié)點時，它趨向于連接度數(shù)大的幾點。Mitzammacher概括了近來產(chǎn)生器冪率分布的方法。為了闡述我們方法的優(yōu)越性，用簡化法簡化AS層的拓撲結(jié)構(gòu)得到的相似圖與GLP比較拓撲機構(gòu)的特性。值得注意的是：其他產(chǎn)生器和研究集中在網(wǎng)絡路由層的拓撲