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

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

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

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

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

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

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］，無(wú)標(biāo)度網(wǎng)絡(luò)具有很強(qiáng)的容錯(cuò)性，但是對(duì) 于基于頂點(diǎn)的度值或介數(shù)的選擇性攻擊抗攻擊能力較差，對(duì) 于基于邊的介數(shù)的攻擊也非常敏感。文獻(xiàn)［2］不僅討論了網(wǎng)絡(luò) 的最短距離等幾何性質(zhì)在去邊去點(diǎn)攻擊下的改變，還討論了 節(jié)點(diǎn)度與介數(shù)等幾何量的相關(guān)性。一些文獻(xiàn)對(duì)代謝網(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)的客戶(hù)端/中心服務(wù)器的檢索 規(guī)范，但它更主要是支持點(diǎn)對(duì)點(diǎn)的，沒(méi)有中心的檢索。 根據(jù)Gnutella的協(xié)議規(guī)范，在Gnutella網(wǎng)絡(luò)中為了找到 需要的信息，一個(gè)節(jié)點(diǎn)將請(qǐng)求消息發(fā)送給其鄰節(jié)點(diǎn)，鄰節(jié)點(diǎn) 首先查找自己是否有與請(qǐng)求消息匹配的信息。如果存在匹配 信息則發(fā)送響應(yīng)消息，然后檢查請(qǐng)求消息中的TTL (Time — To- Live)是否小于零；如果沒(méi)有超過(guò)則繼續(xù)轉(zhuǎn)發(fā)請(qǐng)求消息， 否則停止轉(zhuǎn)發(fā)。 接下來(lái)介紹怎樣通過(guò)PING、PONG命令和TTL值來(lái)探測(cè) Gnutella網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。當(dāng)探測(cè)節(jié)點(diǎn)發(fā)

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

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

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

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

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

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

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

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

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

17、描述了在EBA模型中隨機(jī)攻擊和兩種選 擇性攻擊對(duì)最大集團(tuán)大小、網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直徑的影響。 從圖中曲線的變化可以看出，EBA模型與Gnutella網(wǎng)絡(luò)具有 比較大的相似性。 如圖7,對(duì)于基于介數(shù)的攻擊，當(dāng)f趨于22%時(shí)，S趨于 0；而對(duì)于基于度的攻擊和隨機(jī)攻擊，當(dāng)f趨于24%時(shí)，S趨 于0。 如圖8,對(duì)于基于介數(shù)的攻擊，當(dāng)f趨于9%時(shí)，CC趨于 最小值；對(duì)于基于度的攻擊，當(dāng)f趨于11%時(shí)，CC趨于最小 值。EBA模型與ER模型的一個(gè)相似之處是它們對(duì)于兩種不同 的選擇性攻擊具有相同的反映，從圖中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)）非 常依賴(lài)于大度節(jié)點(diǎn)，通常小度節(jié)點(diǎn)只與三個(gè)左右的ultrapeer 相連，小度節(jié)點(diǎn)之間基本上沒(méi)有連接，這樣就使得網(wǎng)絡(luò)在受 到基于度的攻擊時(shí)，會(huì)比受到基于介數(shù)的攻擊更加脆弱。 2網(wǎng)絡(luò)彈性的理論模型 通過(guò)試驗(yàn)分析了 Gnutella網(wǎng)絡(luò)在隨機(jī)攻擊和選擇性攻擊 發(fā)生時(shí)，網(wǎng)絡(luò)的三種拓?fù)鋵傩缘淖兓闆r，并ER模型和EBA 模型做了對(duì)比。最大集團(tuán)大小，網(wǎng)絡(luò)緊中心性和網(wǎng)絡(luò)直徑這 三種拓?fù)鋵傩援?dāng)中，對(duì)于實(shí)際系統(tǒng)最有意義最直

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

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

21、的一個(gè)節(jié)點(diǎn)，每條邊又 連接其他的集團(tuán)，這些集團(tuán)的大小分布也是由H1(x)生成。通 過(guò)一條邊訪問(wèn)某個(gè)節(jié)點(diǎn)時(shí)，與這個(gè)節(jié)點(diǎn)相連的其他邊的數(shù)目 (不包含訪問(wèn)次節(jié)點(diǎn)所用到的那條邊)的分布生成函數(shù)可以由 下式來(lái)表示： 從上面的分析看出，要求得所有階的集團(tuán)大小的概率分 布(Ps)的公式解是非常困難的，但是可以計(jì)算集團(tuán)大小概率 分布的期望值。最簡(jiǎn)單的是一階期望值，即平均集團(tuán)大小。 平均集團(tuán)大小可對(duì)生成函數(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é)語(yǔ) 本文對(duì)Gnutella網(wǎng)絡(luò)的網(wǎng)絡(luò)彈性，即對(duì)于隨機(jī)攻擊的容 錯(cuò)性和對(duì)于選擇性攻擊抗攻擊性進(jìn)行了詳細(xì)的分析，并且與 ER模型和EBA模型進(jìn)行了對(duì)比。發(fā)現(xiàn)Gnutella網(wǎng)絡(luò)與EBA 模型在很多方面表現(xiàn)出相似性，它們對(duì)于隨機(jī)攻擊具有很好 的容錯(cuò)性，但是對(duì)于選擇性攻擊卻顯得非常脆弱。另外 Guntella網(wǎng)絡(luò)與EBA模型的一個(gè)重要不同點(diǎn)是，它們對(duì)于基 于節(jié)點(diǎn)度的攻擊和基于節(jié)點(diǎn)介數(shù)的攻擊具有不同的表現(xiàn)， Gnutella網(wǎng)絡(luò)中基于節(jié)點(diǎn)度的攻擊更具破壞性，而EBA模型 中卻恰好相反。最后對(duì)網(wǎng)絡(luò)彈性進(jìn)行了理論分析，并給出了 網(wǎng)絡(luò)在出現(xiàn)最大集團(tuán)臨界點(diǎn)之前(等價(jià)于網(wǎng)絡(luò)受到攻擊的最 大集團(tuán)消失臨界點(diǎn))的平均集團(tuán)大小的公式解。未來(lái)的工作 是針對(duì)網(wǎng)絡(luò)在不同攻擊下的特征，提出網(wǎng)絡(luò)自修復(fù)機(jī)制和策 略，增強(qiáng)網(wǎng)絡(luò)的抗攻擊性能。 本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格 式閱讀原文。