基于復雜網絡理論的P2P覆蓋網拓撲結構研究

鄭力明,李嘵冬,孫偉東

（1.國防科技大學 計算機學院 并行與分布處理國家重點實驗室，湖南 長沙 410073；2.武警成都指揮學院 信息技術教研室，四川 成都 610213；3.武警成都指揮學院 科研科，四川 成都 610213）

隨著網絡技術的發展，計算機網絡的規模越來越龐大，基于網絡的應用中節點的規模也越來越龐大，傳統的集中式客戶端/服務器C/S（Client/Server）模式的應用模式因為存在可擴展性低、抗毀性差以及存在單點瓶頸等問題，逐步被分布式的對等端到端P2P（Peer-to-Peer）模式的應用所替代，因此，傳統的隨機網絡模型已很難對其拓撲特性做出客觀的描述。復雜網絡理論以規模的網絡系統為研究對象，其不斷發展的理論和取得的成果為計算機網絡拓撲的研究提供一個新的視野和思路。這里研究基于復雜網絡理論的P2P覆蓋網拓撲結構。

1 P2P覆蓋網簡介

P2P的本質思想在于打破傳統的C/S模式，讓一切網絡成員享有自由、平等、互聯的功能，不再有客戶、服務器之分，任何兩個網絡節點之間都能共享資源、傳遞消息。在對等網絡中，每個網絡節點在行為上是自由的，在功能上是平等的，在連接上是互聯的，因此，它能夠極大程度地提高網絡效率，充分利用網絡帶寬，開發每個網絡節點的潛力。圖1表示C/S模式與P2P模式的區別。

圖1 C/S模式與P2P模式的區別

覆蓋網（overlay）是在物理網絡上構建的連接網絡所有節點的邏輯拓撲結構，是P2P網絡的核心機制。覆蓋網的結構往往和應用相關，對應用系統的性能和效率具有決定性的作用。圖2表示物理網絡和覆蓋網的關系。

2 復雜網絡理論

2.1 網絡定義

圖2 P2P覆蓋網示意圖

網絡是由許多節點與連接兩個節點的一些邊組成的，其中節點代表系統中不同的個體，邊則表示個體間的關系。兩個節點之間具有特定的關系則連接一條邊，有邊相連的兩個節點被看作是相鄰的。計算機網絡可看作是自主工作的計算機通過各種物理介質與通信協議相互連接所得到的網絡。

2.2 網絡的統計參數

2.2.1 度和度分布

一個節點與其他節點相連的邊數稱為該節點的度，度是描述網絡局部特性的基本參數。節點的度分布是指網絡中度為k的節點的概率p（k）隨節點度k的變化規律。節點的度分布函數反映網絡系統的宏觀統計特征，理論上利用度的分布可計算出其他表征全局特征參數的量化行為。

2.2.2 網絡的平均距離L

在具有N個節點的網絡中，兩點i和j的距離定義為所有連通i到j的通路中，所經過的其他頂點最少的一條或幾條路徑的長度。網絡的平均距離L定義為平均距離描述節點對時間的平均分離。

2.2.3 聚集系數C

在具有N個節點的網絡中，若第i個節點的度為Ki，在由這ki個鄰居節點構成的子網中，實際存在的邊ei與這ki個節點所構成的完全圖的總邊數（ki（ki-1））/2的比值C（i）=2ei/（ki·（ki-1）），稱為第i個節點的聚集系數。整個網絡的聚集系數C定義為所有節點聚集系數的平均值，即集系數反映網絡的聚集程度，聚集程度的意義是指網絡集團化的程度，即網絡的內聚傾向。

2.3 復雜網絡的統計特征

復雜網絡的主要統計特征是小世界效應（small-world effect），無標度性（scale free property），并且節點度服從冪律分布(power-law distribution)。研究表明，規則網絡具有大的簇系數和大的平均距離，隨機網絡具有小的簇系數和小的平均距離。Watts和Strogatz通過以某個很小的概率p切斷規則網絡中原始的邊，并隨機選擇新的端點重新連接，構造出一種介于規則網絡和隨機網絡之間的網絡（WS網絡）。WS網絡同時具有大的簇集系數和小的平均距離，因此既不是規則網絡也不是隨機網絡[1]。隨后，Newman和Watts給出一種新的網絡構造方法，在他們的網絡（NW網絡）中，原有的連接邊并不會被破壞，平均距離的縮短源于以一個很小的概率在原來的規則網絡上添加新的連接邊[2]。大的簇系數和小的平均距離兩個統計特征被合稱為小世界效應[3]，具有這種效應的網絡就是小世界網絡（small world networks）。圖3是小世界網絡的演化過程。

圖3 小世界網絡的演化過程

大量實驗研究表明，真實網絡幾乎都具有小世界效應[4]，真實網絡的節點度服從冪律分布[5-6]。冪函數曲線是一條下降相對緩慢的曲線，這使得度很大的節點可以在網絡中存在。對于隨機網絡和規則網絡，度分布區間非常狹窄，幾乎找不到偏離節點度均值較大的點，故其平均度可被看作是其節點度的一個特征標度。則可把節點度服從冪律分布的網絡叫做無標度網絡（scale free networks），并稱這種節點度的冪律分布為網絡的無標度特性。Barabási和Albert把真實系統通過自組織生成無標度的網絡歸為兩個主要因素：生長和優先連接，他們模擬這兩個關鍵機制設計出構造無標度網絡的演化模型（BA 網絡）[7-8]。

3 P2P覆蓋網拓撲結構

覆蓋網是構建在一個或多個網絡上的邏輯網絡拓撲，它通過虛擬鏈路或邏輯鏈路連接網絡節點，為應用提供與底層網絡透明的網絡訪問接口。按照節點間的耦合度，現有覆蓋網拓撲結構可分成結構化和非結構化兩種。結構化拓撲通常以嚴格的規則確定節點之間的鄰居關系和數據的放置位置，因此路由效率較高、開銷較小，但維護開銷較大，對網絡的動態性支持不夠；非結構化拓撲以一種松散的、隨意的方式組織節點，因此構建簡單，易于擴展，而且具有很好的魯棒性，但是路由的效率較低、開銷較大。

3.1 非結構化拓撲

在非結構化拓撲中，節點間的邏輯拓撲關系通常較為松散，具有較大的隨意性。“非結構化”指覆蓋網沒有固定、嚴格的拓撲結構，是一張隨機生成、松散組織的普通圖或隨機圖，但理論上隨機圖可以是任何形狀的。經典的非結構化網絡有Genutella[9]和FreeNet[10]。非結構化拓撲的構建和維護相對簡單，易于擴展并具有較強的魯棒性。但由于其拓撲結構組織較為松散，節點及數據定位較為困難，通常采用泛洪搜索、隨機搜索和選擇性轉發等方法，其效率和準確率難以保證，且冗余消息較多，網絡開銷也較大。

3.2 結構化拓撲

在結構化拓撲網絡中，節點間的鄰居關系通常由確定性的算法嚴格控制，資源(或資源的元信息)的放置也是由確定性的算法精確發布到特定的節點上。結構化拓撲通常采用分布式哈希表技術DHT（Distributed Hash Table）構建。典型的結構化覆蓋網有 Chord[11]、Pastry[12]、CAN[13]等。常度數 P2P 網絡是一種新型結構化覆蓋網，其路由、定位、自組織方式與傳統的模型區別并不大，但每個節點的“度”（即連接數）是固定的，不隨網絡規模改變，從而在保證數據查詢效率的同時減少網絡的自適應開銷。常度數覆蓋網有Viceroy[14]、Koorde[15]、Cycloid[16]等。

3.3 基于復雜網絡理論的拓撲結構

傳統的覆蓋網構建主要研究資源的查詢、定位、分發效率等問題，很少從網絡的本質屬性出發研究覆蓋網的特征。隨著復雜網絡理論研究的逐步成熟，基于復雜網絡理論的拓撲研究逐漸成為覆蓋網拓撲結構研究的熱點。網絡是一個不斷變化的動態系統，因此掌握網絡拓撲行為的演化規律是網絡動態覆蓋網構建的基礎。傳統方法大都采用結構相對簡單的隨機網絡[17-18]描述真實的計算機網絡拓撲。在規模不大、業務種類比較單一的網絡初步階段，隨機網絡模型在一定程度上能客觀反映計算機網絡拓撲演化規律。

隨著計算機網絡規模和用戶數量巨大且不斷增長，各種異構的網絡需要融合發展、共享資源；網絡協議體系龐雜，垂直方向呈現出多樣化的層次結構，而水平方向上又以地域和功能為標準進一步形成分布且多級的架構；網絡節點間、節點與數據分組間由于協議而產生的非線性作用、用戶之間的合作與競爭，這些情況使計算機網絡日益復雜。強調系統整體性的復雜網絡理論提供了計算機網絡拓撲研究的新思路。利用復雜網絡理論研究計算機復雜的網絡行為，從多個視角、不同抽象角度分析網絡系統，研究各個單元之間相互連接、相互作用而導致網絡系統表現出的行為規律和本質。例如流量行為特性分析、網絡拓撲的生成機理和動力學行為、流量行為和拓撲行為的相互作用、網絡同步行為的研究等。

3.4 計算機網絡拓撲行為的演化模型

針對計算網絡拓撲，主要是基于復雜網絡演化模型（BA模型）及其改進型的局部演化模型，從路由器和自治域兩種不同層次描述計算機網絡的拓撲結構[19-21]。從路由器層次看，路由器相當于網絡節點，路由器之間的物理連接相當于邊；而從自治域看，如果兩個自治域之間存在基于邊界網關協議（BGP）的對等連接，則表示這兩個節點之間有一條邊相連。研究表明，計算機網絡的增長遵循BA模型的“偏好連接”法則，演化的結果會導致“富者更富”的現象，即新加入的用戶總是更傾向于優先考慮連接到那些知名度高、服務質量好、連接數多的服務器或網絡服務商。但這個模型明顯的不足之處是，其中的“偏好連接”是基于整個網絡的“偏好連接”，這點與實際情況不符，現實中網絡路由一般優先考慮連接到本地區的路由器或服務器，即使該地區以外的其他路由器或服務器的連接數可能要高于當地路由器的連接數。針對這種情況，Wang等人所提出的局部演化模型的“偏好連接”的傾向性[22]是基于局部而非全局的信息，在一定程度上改進該模型的缺陷。

現有的模型還不能很好地解釋計算機網絡拓撲演化規律。無論是BA模型、局部演化模型還是其他演化模型，都是在一些理想化的簡單假定下解釋計算機網絡復雜的拓撲演化規律的，對于在一些復雜情況下（諸如信息傳輸中的延遲、時變、節點動態加入和退出、不同節點不同動力學的差異等）網絡拓撲行為特性的研究較少，所以現有的模型還不能很好地描述網絡拓撲對網絡動力學的影響以及網絡單節點的行為與網絡整體行為特性的關系等問題。而能更加真實的細致和全面的刻畫計算機網絡拓撲結構的動力學演化特性的模型還有待研究[23]。

4 結束語

計算機網絡龐大的規模、異質而復雜的體系結構和豐富的動態特性，使傳統的隨機網絡模型難以對其拓撲行為特征做出系統、客觀的描述，強調系統整體性的復雜網絡理論為網絡行為的研究提供了新方法，成為解決網絡行為基礎理論研究的有力工具，為網絡的基礎理論研究帶來重大突破。任何復雜網絡理論研究的新成果都有可能被運用到計算機網絡行為特性的研究中，結合計算機網絡的特點，應用復雜性理論研究計算機網絡的拓撲行為，有可能發現其拓撲行為演化規律，從而根據實際需要，設計出性能較優越的計算機網絡。 以下是基于復雜網絡理論的計算機網絡拓撲行為以及相關技術可以研究的方向和實現的目標：

1）從理論上定義和建立計算機網絡的復雜網絡理論。包括描述計算機網絡拓撲基本性質的特征量，定量與定性分析方法；研究計算機網絡的拓撲演化機制，不同節點對于整個網絡拓撲演化行為的影響程度，以及彼此間的相互作用；尋求能夠真實反映其拓撲結構的復雜網絡的構造機制，并建立網絡拓撲以及其動力學演化行為的模型，基于該模型討論網絡結構的統計平均性質，如類似節點度的分布特征、小世界性質、無標度特性以及動力學過程中混沌、分形等復雜行為；構造網絡拓撲模型的各種算法以及模型的性能評價。

2）基于復雜網絡的某些統計特性，研究計算機網絡拓撲的構建、拓撲發現、用戶的動態更新、資源管理、服務發現、服務部署等問題；針對某種具體網絡體系結構服務或應用，構造其相應的性能高、可擴展性好、有利于管理的具有小世界或無標度特性的網絡結構，如具有小世界特性或無標度的主動網絡、主動Overlay網絡、Web服務Overlay網絡、P2P網絡、組播Overlay網絡。

3）基于復雜網絡理論的路由機制及其算法的研究，以及如何通過適當的路由機制提高網絡的信息傳輸量。

4）基于復雜網絡理論探討了計算機網絡的可靠性、抗毀性，提出一個能夠真實描述計算機網絡魯棒同時脆弱的動力學模型。

5）在復雜網絡理論中引入節點帶寬、網絡延遲等物理網絡特性，優化拓撲結構。

[1]Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998（393）：440-448.

[2]Newman M E J.Models of the small world[J].Phys.Rev,1999（60）：7332-7336.

[3]Watts D J.Networks,dynamics,and the small world phenomenon[J].Amer.Sociol,1999:493-499.

[4]Sen P,Chakrabarti B K.Mall-world phenomena and the statistics of linear polymers[J].Phys，2001:7749-7753.

[5]Faloutsos M,Faloutsos P,et al.On power-law relationships of the internet topology[J].Computer Communications Rev,1999（29）：251-255.

[6]Ebel H,Mielsch L I.Scale-ree topology of e-mail networks[J].Phys.Rev,2002（26）：035103-035110.

[7]Barabási A-L,Albert R.Emergence of scaling in random networks[J].Science,1999（286）：509-513.

[8]Barabási A-L,Albert R,etal.Mean-field theory for scale free random networks[J].Physica A,1999（272）：173-179.

[9]Gnutella protocol specification[EB/OL].2001.version 0.4Http://www.clip2.com/GnutellaProtocol04.pdf.

[10]Clarke I,Sandberg O,Wiley B,et al.Freenet.A distributed anonymous information storage and retrieval system[C]//InPr oc.of ICSI Workshop on Design Issues in Anonymity and Un observability.Berkeley,2000.

[11]Stoica I,Morris R,Liben-nowell D,et al.A scalable Peer-topeer lookup protocol for internet applications[J].IEEE/ACM Transactions on Networking,2003（11）：17-25.

[12]Rowstron A,Druschel P.Pastry.Scalable,distributed object location and routing for large-scale Peer-to-Peer systems[C].In Proc.of IFIP/ACM Middleware,2001.

[13]Ratnasamy S,Francis P,Handley M,et al.A Scalable content-addressable network[C]//In Proc.of ACM SIGCOMM,2001.

[14]Malkhi D,Naor M，Ratajczak D.A scalable and dynamic look up network[C]//In 21st ACM Symposium on Principles of Distributed Computing （PODC）.Monterey,CA,USA,2002.

[15]Kaashoek F,Karger D R.A simple degree-optimal hash table[C]//In 2nd international workshop on peer-to-Peer systems（IPTPS）.Berkeley,CA,USA,2003.

[16]Shen H，Xu C,Chen G.A constant-degree and lookup-efficient P2P overlay network[C]//In IPDPS,2004.

[17]Erd＂os P，R′enyi A.On random graphs[J].Publ.Math.Debrecen,1959（6）：290-295.

[18]Erd＂os P，R′enyi.A On the evolution of random graphs[J].Magyar Tud.Akad.Mat.Kutat′oInt.K′ozl,1960（5）：17-23.

[19]Vázquez A,Pastor-Satorras R,et al.Large-scale topological and dynamical properties of the Internet[J].Phys Rev E,2002（65）：066130-066135.

[20]Wang X，Chen G.Complex networks.small-world,scale-free,and beyond[J].IEEE Circuits and Systems Magazine,2003,3（2）：6-12.

[21]Chen G,Fan Z,Li Xiang.Modeling the complex Internet topology[C]//Complex Dynamics in Communication Networks.Springer Publisher,2004.

[22]Wang X,Chen G.Synchronization in scale-free dynamical networks:robustness and fragility[J].IEEE Transactions on Circuits and Systems,Part I:Regular Paper,2002,49（1）：54-61.

[23]Li Xiang,Chen Guan-rong.A local-world evolving network model[J].Physical A,2003,328（1/2）：274-279.