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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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