大型互聯(lián)網(wǎng)絡(luò)實現(xiàn)拓?fù)浞抡嫒绾纬闃?.0

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

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

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

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

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

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

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

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

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

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

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

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

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