對等網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性分析

《對等網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性分析》由會員分享，可在線閱讀，更多相關(guān)《對等網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性分析（12頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、對等網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性分析 摘 要：網(wǎng)絡(luò)彈性研究的是網(wǎng)絡(luò)在節(jié)點(diǎn)失效或被有意 攻擊下所表現(xiàn)出來的特征。分析Gnutella網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性， 包括對于隨機(jī)攻擊的容錯性和對于選擇性攻擊的抗攻擊性， 并與ER模型和EBA模型進(jìn)行了對比。Gnutella網(wǎng)絡(luò)對于隨機(jī) 攻擊具有很好的容錯性，但是對于選擇性攻擊卻顯得脆弱。 最后對網(wǎng)絡(luò)彈性進(jìn)行了理論分析，給出了網(wǎng)絡(luò)在出現(xiàn)最大集 團(tuán)臨界點(diǎn)之前的平均集團(tuán)大小的公式解。 關(guān)鍵詞：對等網(wǎng)絡(luò)；無標(biāo)度；網(wǎng)絡(luò)彈性；脆弱性 中圖分類號：TP393.02文獻(xiàn)標(biāo)識碼：A 文章編號：1001-9081(2007)04-0784-04 0引言 在過去的40多年里，科學(xué)家習(xí)慣

2、于將所有復(fù)雜網(wǎng)絡(luò)看 作是隨機(jī)網(wǎng)絡(luò)。隨機(jī)網(wǎng)絡(luò)中絕大部分節(jié)點(diǎn)的連結(jié)數(shù)目會大致 相同。1998年開展的一個描繪互聯(lián)網(wǎng)的項(xiàng)目卻揭示了令人驚 詫的事實(shí)：基本上，互聯(lián)網(wǎng)是由少數(shù)高連結(jié)性的頁面串聯(lián)起 來的，80%以上頁面的連結(jié)數(shù)不到4個，而只占節(jié)點(diǎn)總數(shù)不 到萬分之一的極少數(shù)節(jié)點(diǎn)，例如門戶網(wǎng)Yahoo和搜索引擎 Google等類似網(wǎng)站，卻高達(dá)上百萬乃至幾十億個鏈接。研究 者把包含這種重要集散節(jié)點(diǎn)的網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò)［1］。 具有集散節(jié)點(diǎn)和集群結(jié)構(gòu)的無標(biāo)度網(wǎng)絡(luò)，對意外故障具 有極強(qiáng)的承受能力，但面對蓄意的攻擊和破壞卻不堪一擊［2］。 在隨機(jī)網(wǎng)絡(luò)中，如果大部分節(jié)點(diǎn)發(fā)生癱瘓，將不可避免地導(dǎo) 致網(wǎng)絡(luò)的分裂。無標(biāo)度網(wǎng)

3、絡(luò)的模擬結(jié)果則展現(xiàn)了全然不同的 情況，隨意選擇高達(dá)80%的節(jié)點(diǎn)使之失效，剩余的網(wǎng)絡(luò)還可 能組成一個完整的集群并保持任意兩點(diǎn)間的連接，但是只要 5%-10%的集散節(jié)點(diǎn)同時失效，就可導(dǎo)致互聯(lián)網(wǎng)潰散成孤立 無援的小群路由器。 許多復(fù)雜網(wǎng)絡(luò)系統(tǒng)顯示出驚人的容錯特性，例如復(fù)雜通 信網(wǎng)絡(luò)也常常顯示出很強(qiáng)的健壯性，一些關(guān)鍵單元的局部失 效很少會導(dǎo)致全局信息傳送的損失。但并不是所有的網(wǎng)絡(luò)都 具有這樣的容錯特性，只有那些異構(gòu)連接的網(wǎng)絡(luò)，即無標(biāo)度 網(wǎng)絡(luò)才有這種特性，這樣的網(wǎng)絡(luò)包括WWW、因特網(wǎng)、社會 網(wǎng)絡(luò)等。雖然無標(biāo)度網(wǎng)絡(luò)具有很強(qiáng)的容錯性，但是對于那些 有意攻擊，無標(biāo)度網(wǎng)絡(luò)卻非常脆弱。容錯性和抗攻擊性是通 信網(wǎng)

4、絡(luò)的基本屬性，可以用這兩種屬性來概括網(wǎng)絡(luò)彈性。 對等網(wǎng)絡(luò)技術(shù)和復(fù)雜網(wǎng)絡(luò)理論的進(jìn)展促使對現(xiàn)有對等 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行深入分析。對網(wǎng)絡(luò)彈性的認(rèn)識可以使從 網(wǎng)絡(luò)拓?fù)涞慕嵌攘私饩W(wǎng)絡(luò)的脆弱點(diǎn)，以及如何設(shè)計(jì)有效的策 略保護(hù)、減小攻擊帶來的危害。本文研究Gnutella網(wǎng)絡(luò)的網(wǎng) 絡(luò)彈性，并與ER模型和EBA模型進(jìn)行了比較，對比不同類 型的復(fù)雜網(wǎng)絡(luò)在攻擊中的網(wǎng)絡(luò)彈性。當(dāng)網(wǎng)絡(luò)受到攻擊達(dá)到某 一個臨界值時，網(wǎng)絡(luò)中已不存在最大集團(tuán)了，節(jié)點(diǎn)分散于許 多相互獨(dú)立的小集團(tuán)里，分析了這些小集團(tuán)大小的分布及平 均大小，并對于攻擊對網(wǎng)絡(luò)造成的損害進(jìn)行了定量的理論分 析。 1網(wǎng)絡(luò)的容錯性和抗攻擊性 對一般網(wǎng)絡(luò)的攻擊方式可以

5、選擇去點(diǎn)與去邊兩種方式， 從選擇的方式上分為隨機(jī)攻擊和選擇性攻擊兩種類型［3］，抵 抗這兩種攻擊的能力分別稱為網(wǎng)絡(luò)的容錯能力與抗攻擊能 力。 隨機(jī)攻擊，顧名思義就是在一個網(wǎng)絡(luò)中隨機(jī)選擇一些節(jié) 點(diǎn)，并去掉這些節(jié)點(diǎn)，攻擊者不知道這些節(jié)點(diǎn)在整個網(wǎng)絡(luò)拓 撲結(jié)構(gòu)中的位置。選擇性攻擊才可以理解為真正意義的對網(wǎng) 絡(luò)的攻擊，比如計(jì)算機(jī)網(wǎng)絡(luò)中的黑客攻擊。對網(wǎng)絡(luò)攻擊脆弱 性的研究表明，攻擊者為了最大化攻擊效果，往往想挑選那 些網(wǎng)絡(luò)中最重要的節(jié)點(diǎn)進(jìn)行攻擊，這需要事先知道整個網(wǎng)絡(luò) 的拓?fù)浣Y(jié)構(gòu)，但這在真實(shí)網(wǎng)絡(luò)環(huán)境下是不太可能的。然而， 為了深入了解不同攻擊行為對網(wǎng)絡(luò)造成的影響，往往是在知 道網(wǎng)絡(luò)的全局拓?fù)涞那闆r下對各

6、種攻擊行為進(jìn)行分析。選擇 性攻擊使用兩種不同方式：第一種攻擊使用基于節(jié)點(diǎn)度的策 略，即按順序去掉網(wǎng)絡(luò)中那些節(jié)點(diǎn)度高的節(jié)點(diǎn)；第二種攻擊 使用基于節(jié)點(diǎn)介數(shù)的策略，即去掉網(wǎng)絡(luò)中那些介數(shù)比較大的 節(jié)點(diǎn)。 研究表明［2,3］，無標(biāo)度網(wǎng)絡(luò)具有很強(qiáng)的容錯性，但是對 于基于頂點(diǎn)的度值或介數(shù)的選擇性攻擊抗攻擊能力較差，對 于基于邊的介數(shù)的攻擊也非常敏感。文獻(xiàn)［2］不僅討論了網(wǎng)絡(luò) 的最短距離等幾何性質(zhì)在去邊去點(diǎn)攻擊下的改變，還討論了 節(jié)點(diǎn)度與介數(shù)等幾何量的相關(guān)性。一些文獻(xiàn)對代謝網(wǎng)絡(luò)、食 物鏈網(wǎng)絡(luò)、Email網(wǎng)絡(luò)［4］和Internet［5,6］等網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性進(jìn) 行了深入討論。 1.1 Gnutella網(wǎng)絡(luò)的

7、彈性分析 Gnutella是一份用于文件共享的內(nèi)容分發(fā)和分布式檢索 的協(xié)議。雖然該協(xié)議也支持傳統(tǒng)的客戶端/中心服務(wù)器的檢索 規(guī)范，但它更主要是支持點(diǎn)對點(diǎn)的，沒有中心的檢索。 根據(jù)Gnutella的協(xié)議規(guī)范，在Gnutella網(wǎng)絡(luò)中為了找到 需要的信息，一個節(jié)點(diǎn)將請求消息發(fā)送給其鄰節(jié)點(diǎn)，鄰節(jié)點(diǎn) 首先查找自己是否有與請求消息匹配的信息。如果存在匹配 信息則發(fā)送響應(yīng)消息，然后檢查請求消息中的TTL (Time — To- Live)是否小于零；如果沒有超過則繼續(xù)轉(zhuǎn)發(fā)請求消息， 否則停止轉(zhuǎn)發(fā)。 接下來介紹怎樣通過PING、PONG命令和TTL值來探測 Gnutella網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。當(dāng)探測節(jié)點(diǎn)發(fā)

8、送一個TTL值為2 的PING命令給其鄰節(jié)點(diǎn)時，鄰節(jié)點(diǎn)收到PING命令后將TTL 字段值減1,此時TTL值為1,鄰節(jié)點(diǎn)再將PING命令轉(zhuǎn)發(fā)至 下一層鄰節(jié)點(diǎn)，下一層鄰節(jié)點(diǎn)收到PING命令后同樣將TTL 值減1,此時TTL值為0，因此不再轉(zhuǎn)發(fā)PING命令，而只將 PONG命令返回給探測節(jié)點(diǎn)。這樣探測節(jié)點(diǎn)可以收集到與它 相鄰的第二層鄰節(jié)點(diǎn)的IP地址信息，然后探測節(jié)點(diǎn)又發(fā)送 TTL值為2的PING命令至第二層鄰節(jié)點(diǎn)，這樣又可以得到第 三層鄰節(jié)點(diǎn)的信息，按照這種廣度優(yōu)先的搜索方式，最后就 可以得到整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。通過分析Gnutella網(wǎng)絡(luò)的拓 撲結(jié)構(gòu)來考察網(wǎng)絡(luò)彈性。隨機(jī)性攻擊的情況比較簡單，這里

9、使用隨機(jī)選擇去掉某些節(jié)點(diǎn)來模擬真實(shí)網(wǎng)絡(luò)環(huán)境中節(jié)點(diǎn)失 效的情況。 任何一個網(wǎng)絡(luò)的互聯(lián)性從本質(zhì)上可以由它的網(wǎng)絡(luò)直徑 和平均最短路徑長度來描述。網(wǎng)絡(luò)直徑描述了網(wǎng)絡(luò)中兩個節(jié) 點(diǎn)相互通信的能力：直徑越小那么兩點(diǎn)間期望的通信長度就 越短。一個網(wǎng)絡(luò)就算擁有大量的節(jié)點(diǎn)也可能具有很小的網(wǎng)絡(luò) 直徑，比如擁有80億個節(jié)點(diǎn)的WWW網(wǎng)絡(luò)，它的網(wǎng)絡(luò)直徑 大約為19。 設(shè)想當(dāng)一個完整的網(wǎng)絡(luò)（即所有節(jié)點(diǎn)都是連通的）在受到 攻擊后，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)勢必會受到很大的影響，以至網(wǎng)絡(luò) 中的某些邊也會消失，從而導(dǎo)致整個網(wǎng)絡(luò)分裂成很多相互獨(dú) 立的子圖，這些子圖之間沒有連接。反映到真實(shí)網(wǎng)絡(luò)情況就 是說某些節(jié)點(diǎn)之間的通信無法進(jìn)行，從而使網(wǎng)

10、絡(luò)的通信受到 影響。因此，下面將基于最大集團(tuán)，網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直 徑三個拓?fù)鋵傩詠矸治鯣nutella網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性。最大集團(tuán) 指的是相對大小，即最大集團(tuán)中的節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)中所有節(jié)點(diǎn) 數(shù)的比值。緊中心性定義為：d(x,y)，這里d(x,y)表示節(jié)點(diǎn)x 和y之間的最短路徑長度，U是所有節(jié)點(diǎn)的集合。 在試驗(yàn)時，為了觀察隨機(jī)失效給網(wǎng)絡(luò)帶來的影響，這里 隨機(jī)選擇去掉網(wǎng)絡(luò)中的一小部分節(jié)點(diǎn)，用百分比f表示。同 樣對于模擬選擇性攻擊，首先去掉網(wǎng)絡(luò)中節(jié)點(diǎn)度最高的節(jié)點(diǎn)， 然后按照節(jié)點(diǎn)度降序的規(guī)則選擇被去掉的節(jié)點(diǎn)。圖1一圖3 描述了最大集團(tuán)相對大小、網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直徑在隨機(jī) 攻擊(Failure)、基于度的

11、攻擊(DAttack)和基于介數(shù)的攻擊 (BAttack)三種情況下的變化過程。在對Gnutella網(wǎng)絡(luò)拓?fù)溥M(jìn) 行探測時，經(jīng)過大量的數(shù)據(jù)分析發(fā)現(xiàn)，在Gnutella網(wǎng)絡(luò)中超 級節(jié)點(diǎn)所占的比例大約是3.3%，這種節(jié)點(diǎn)是使用基于度的攻 擊方法時的目標(biāo)節(jié)點(diǎn)，因此上述三個圖中x軸的變化范圍限 定在［0,0.05］。 如圖1一圖3所示，Gnutella網(wǎng)絡(luò)對于隨機(jī)攻擊顯示 出很好的容錯性：最大集團(tuán)的相對大小變化非常緩慢，到去 掉4%左右的節(jié)點(diǎn)時，S大小仍然在0.85左右，見圖1；網(wǎng) 絡(luò)的緊中心性在整個過程基本上保持不變，只有微小的波動， 見圖2；網(wǎng)絡(luò)直徑的變化也不明顯，在區(qū)間［0, 0.04］內(nèi)保持不

12、 變，到Uf為5%時才增加1，見圖3。然而，Gnutella網(wǎng)絡(luò)在 基于度的攻擊和基于介數(shù)的攻擊時卻顯得非常脆弱。 如圖1所示，對于基于度的攻擊(DAttack)，當(dāng)f趨于2% 時，最大集團(tuán)相對大小S趨向于0,這說明這時網(wǎng)絡(luò)中已經(jīng) 不存在最大子圖，大部分節(jié)點(diǎn)都分散在很多小的子圖里，或 者某些節(jié)點(diǎn)已經(jīng)成為孤立的節(jié)點(diǎn)；基于介數(shù)的攻擊(BAttack) 時，情況要比DAttack時好一些，當(dāng)f趨于3.3%左右時S才 趨于0，這說明在Gnutella網(wǎng)絡(luò)中，基于度的攻擊比基于介數(shù) 的攻擊對于網(wǎng)絡(luò)的危害更大一些。 如圖2所示，對于基于度的攻擊(DAttack)，f趨于1%時 網(wǎng)絡(luò)的緊中心性達(dá)到最小

13、值0.145，對于基于介數(shù)的攻擊 (BAttack)，f趨于3%時網(wǎng)絡(luò)緊中心性達(dá)到最小值0.145,這里 的情況跟選擇性攻擊對最大集團(tuán)的影響相似，基于度的攻擊 比基于介數(shù)的攻擊危害性要大一些。 圖2中另外一個有趣的現(xiàn)象是，當(dāng)緊中心性達(dá)到最小值 后，在兩種攻擊情況下，緊中心性又開始逐漸增大。這是因 為網(wǎng)絡(luò)緊中心性是針對網(wǎng)絡(luò)中的最大集團(tuán)來計(jì)算的，攻擊剛 開始時，網(wǎng)絡(luò)中的最大集團(tuán)大小相比整個網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目來說 較大，攻擊發(fā)生后去掉了一些關(guān)鍵節(jié)點(diǎn)導(dǎo)致某些關(guān)鍵路徑也 從網(wǎng)絡(luò)中去掉，影響了節(jié)點(diǎn)間通信的平均最短路徑，確切地 說是增大了平均最短路徑，從而導(dǎo)致緊中心性的減??；然而 隨著攻擊的增加，網(wǎng)絡(luò)中的最大集

14、團(tuán)大小越來越小，即網(wǎng)絡(luò) 被分成了許多獨(dú)立的小的子圖，而這時最大集團(tuán)中的平均最 短路徑也會變小，集團(tuán)中的節(jié)點(diǎn)間通信平均來說會更快，相 應(yīng)地緊中心性會增大。 圖3給出了攻擊對網(wǎng)絡(luò)直徑的影響，在大圖的坐標(biāo)范圍 內(nèi)無法看到網(wǎng)絡(luò)直徑的變化過程，所以放大了區(qū)間［0, 001］， 如小圖所示。圖3表明兩種攻擊對網(wǎng)絡(luò)直徑的影響很大，與 前面兩種情況類似，基于度的攻擊對網(wǎng)絡(luò)直徑的影響比基于 介數(shù)的攻擊要大。 綜上所述，Gnutella網(wǎng)絡(luò)對于隨機(jī)攻擊具有很強(qiáng)的容錯 性，而對選擇性攻擊卻顯得比較脆弱；在遭受攻擊時測量網(wǎng) 絡(luò)得到的相關(guān)參數(shù)表明，基于度的攻擊均比基于介數(shù)的攻擊 對網(wǎng)絡(luò)造成的危害性更大。 1.2

15、ER模型和EBA模型的網(wǎng)絡(luò)彈性分析 復(fù)雜網(wǎng)絡(luò)的理論研究始于20世紀(jì)60年代，著名數(shù)學(xué)家 Erdfis和Renyi提出了 ER模型，一個由n個節(jié)點(diǎn)組成的隨機(jī) 圖中，每兩個節(jié)點(diǎn)被一條邊連接起來的概率為p。鑒于實(shí)際 網(wǎng)絡(luò)的情況，Barabasi和Albert的第二個關(guān)于無標(biāo)度網(wǎng)絡(luò)的 機(jī)制模型考慮了加點(diǎn)、加邊和重連三種事件，擴(kuò)充了原有的 BA模型，即EBA（Extended日入）模型。下面通過ER模型和 EBA模型來比較與Gnutella網(wǎng)絡(luò)彈性的異同。圖4一圖6分 別描述了在ER模型中隨機(jī)攻擊和兩種選擇性攻擊對最大集 團(tuán)大小、網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直徑的影響。與Gnutella網(wǎng)絡(luò) 不同，對于ER模型

16、，隨機(jī)攻擊和選擇性攻擊對于網(wǎng)絡(luò)的影 響基本上是相同的，正如圖中所繪的曲線基本是重疊的。 如圖4,對于基于介數(shù)的攻擊，當(dāng)f趨于32%時，S趨于 0;而對于基于度的攻擊和隨機(jī)攻擊，當(dāng)f趨于38%時，S趨 于0，這說明基于介數(shù)的攻擊危害性要大一些。如圖5，對 于基于介數(shù)的攻擊，當(dāng)f趨于15%時，CC趨于最小值；對于 基于度的攻擊和隨機(jī)攻擊，當(dāng)f分別趨于17%和18%時，CC 趨于最小值。基于介數(shù)的攻擊使網(wǎng)絡(luò)緊中心性下降得更快， 比其他兩種攻擊更加具有危害性。如圖6，這幾種攻擊對于 網(wǎng)絡(luò)直徑的影響也跟上面的情況類似，影響由大到小的順序 是：基于介數(shù)的攻擊，基于度的攻擊，隨機(jī)攻擊。 圖7一圖9分別

17、描述了在EBA模型中隨機(jī)攻擊和兩種選 擇性攻擊對最大集團(tuán)大小、網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直徑的影響。 從圖中曲線的變化可以看出，EBA模型與Gnutella網(wǎng)絡(luò)具有 比較大的相似性。 如圖7,對于基于介數(shù)的攻擊，當(dāng)f趨于22%時，S趨于 0；而對于基于度的攻擊和隨機(jī)攻擊，當(dāng)f趨于24%時，S趨 于0。 如圖8,對于基于介數(shù)的攻擊，當(dāng)f趨于9%時，CC趨于 最小值；對于基于度的攻擊，當(dāng)f趨于11%時，CC趨于最小 值。EBA模型與ER模型的一個相似之處是它們對于兩種不同 的選擇性攻擊具有相同的反映，從圖中BAttack和DAttack的 變化快慢可知，基于介數(shù)的攻擊比基于度的攻擊危害更大， 這剛好

18、跟Gnutella網(wǎng)絡(luò)中的情況相反。因?yàn)閺膄變化范圍可 以看出，Gnutella網(wǎng)絡(luò)中大度節(jié)點(diǎn)（ultrapeer）所占比例要小于 EBA模型中大度節(jié)點(diǎn)所占比例，并且小度節(jié)點(diǎn)（葉子節(jié)點(diǎn)）非 常依賴于大度節(jié)點(diǎn)，通常小度節(jié)點(diǎn)只與三個左右的ultrapeer 相連，小度節(jié)點(diǎn)之間基本上沒有連接，這樣就使得網(wǎng)絡(luò)在受 到基于度的攻擊時，會比受到基于介數(shù)的攻擊更加脆弱。 2網(wǎng)絡(luò)彈性的理論模型 通過試驗(yàn)分析了 Gnutella網(wǎng)絡(luò)在隨機(jī)攻擊和選擇性攻擊 發(fā)生時，網(wǎng)絡(luò)的三種拓?fù)鋵傩缘淖兓闆r，并ER模型和EBA 模型做了對比。最大集團(tuán)大小，網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直徑這 三種拓?fù)鋵傩援?dāng)中，對于實(shí)際系統(tǒng)最有意義最直

19、觀的就是最 大集團(tuán)大小。當(dāng)網(wǎng)絡(luò)受到攻擊后，一般最關(guān)心的是這個網(wǎng)絡(luò) 最大范圍內(nèi)有多少節(jié)點(diǎn)仍然可以相互通信。從另一個方面考 慮，當(dāng)網(wǎng)絡(luò)受到攻擊達(dá)到某一個臨界值（f趨于某個值），整個 網(wǎng)絡(luò)已經(jīng)不存在最大集團(tuán)了，網(wǎng)絡(luò)節(jié)點(diǎn)都分散于許多相互獨(dú) 立的小集團(tuán)里，那么這些小集團(tuán)大小的分布情況及平均大小 是多少？這些對于攻擊對網(wǎng)絡(luò)造成損害的定量分析非常重 要，下面將進(jìn)行理論分析。 在分析攻擊臨界點(diǎn)發(fā)生后集團(tuán)大小的分布和集團(tuán)平均 大小時，為了便于理論分析，可以按如下思路來考慮。在攻 擊臨界點(diǎn)發(fā)生后，網(wǎng)絡(luò)被分散成許多獨(dú)立的小集團(tuán)，由于攻 擊的方法是去掉網(wǎng)絡(luò)中的某些節(jié)點(diǎn)，那可以反過來思考網(wǎng)絡(luò) 的形成過程。開始時網(wǎng)絡(luò)由

20、一些單個節(jié)點(diǎn)組成，隨著其他節(jié) 點(diǎn)的加入和邊的形成，網(wǎng)絡(luò)會逐漸演化生長，到某一個臨界 點(diǎn)時網(wǎng)絡(luò)中的最大集團(tuán)開始形成，這里的臨界點(diǎn)與攻擊使得 最大集團(tuán)消失的臨界點(diǎn)是相同的，只是它們的表述方式不同 而已。因此可以用這種方法來分析最大集團(tuán)形成前(即臨界點(diǎn) 之前)網(wǎng)絡(luò)中集團(tuán)的大小分布和集團(tuán)的平均大小。 在一個網(wǎng)絡(luò)圖中隨機(jī)選擇一條邊，設(shè)想沿著這條邊指向 它的一個端點(diǎn)并且通過這個端點(diǎn)可以到達(dá)其他節(jié)點(diǎn)，就稱通 過這條隨機(jī)選擇的邊的一端可達(dá)的節(jié)點(diǎn)集合為一個集團(tuán)。令 H1(x)為這些集團(tuán)大小分布的生成函數(shù)。沿著一條隨機(jī)選擇的 邊，與它相連的可能只是一個單一的節(jié)點(diǎn)，沒有其他邊與這 個節(jié)點(diǎn)相連；也可能是有多條邊連接

21、的一個節(jié)點(diǎn)，每條邊又 連接其他的集團(tuán)，這些集團(tuán)的大小分布也是由H1(x)生成。通 過一條邊訪問某個節(jié)點(diǎn)時，與這個節(jié)點(diǎn)相連的其他邊的數(shù)目 (不包含訪問次節(jié)點(diǎn)所用到的那條邊)的分布生成函數(shù)可以由 下式來表示： 從上面的分析看出，要求得所有階的集團(tuán)大小的概率分 布(Ps)的公式解是非常困難的，但是可以計(jì)算集團(tuán)大小概率 分布的期望值。最簡單的是一階期望值，即平均集團(tuán)大小。 平均集團(tuán)大小可對生成函數(shù)求導(dǎo)數(shù)得到： 計(jì)算集團(tuán)大小的概率分布(Ps)的公式解比較困難，可以 計(jì)算集團(tuán)大小概率分布的一階期望值，即平均集團(tuán)大小，式 (11)給出了攻擊臨界點(diǎn)發(fā)生后或者網(wǎng)絡(luò)在出現(xiàn)最大集團(tuán)臨界 點(diǎn)之前的平均集團(tuán)大小的公

22、式解。 3結(jié)語 本文對Gnutella網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性，即對于隨機(jī)攻擊的容 錯性和對于選擇性攻擊抗攻擊性進(jìn)行了詳細(xì)的分析，并且與 ER模型和EBA模型進(jìn)行了對比。發(fā)現(xiàn)Gnutella網(wǎng)絡(luò)與EBA 模型在很多方面表現(xiàn)出相似性，它們對于隨機(jī)攻擊具有很好 的容錯性，但是對于選擇性攻擊卻顯得非常脆弱。另外 Guntella網(wǎng)絡(luò)與EBA模型的一個重要不同點(diǎn)是，它們對于基 于節(jié)點(diǎn)度的攻擊和基于節(jié)點(diǎn)介數(shù)的攻擊具有不同的表現(xiàn)， Gnutella網(wǎng)絡(luò)中基于節(jié)點(diǎn)度的攻擊更具破壞性，而EBA模型 中卻恰好相反。最后對網(wǎng)絡(luò)彈性進(jìn)行了理論分析，并給出了 網(wǎng)絡(luò)在出現(xiàn)最大集團(tuán)臨界點(diǎn)之前(等價于網(wǎng)絡(luò)受到攻擊的最 大集團(tuán)消失臨界點(diǎn))的平均集團(tuán)大小的公式解。未來的工作 是針對網(wǎng)絡(luò)在不同攻擊下的特征，提出網(wǎng)絡(luò)自修復(fù)機(jī)制和策 略，增強(qiáng)網(wǎng)絡(luò)的抗攻擊性能。 本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格 式閱讀原文。