鄭力明,李嘵冬,孫偉東

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

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

1 P2P覆蓋網(wǎng)簡介

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

圖1 C/S模式與P2P模式的區(qū)別

覆蓋網(wǎng)（overlay）是在物理網(wǎng)絡上構(gòu)建的連接網(wǎng)絡所有節(jié)點的邏輯拓撲結(jié)構(gòu)，是P2P網(wǎng)絡的核心機制。覆蓋網(wǎng)的結(jié)構(gòu)往往和應用相關(guān)，對應用系統(tǒng)的性能和效率具有決定性的作用。圖2表示物理網(wǎng)絡和覆蓋網(wǎng)的關(guān)系。

2 復雜網(wǎng)絡理論

2.1 網(wǎng)絡定義

圖2 P2P覆蓋網(wǎng)示意圖

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

2.2 網(wǎng)絡的統(tǒng)計參數(shù)

2.2.1 度和度分布

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

2.2.2 網(wǎng)絡的平均距離L

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

2.2.3 聚集系數(shù)C

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

2.3 復雜網(wǎng)絡的統(tǒng)計特征

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

圖3 小世界網(wǎng)絡的演化過程

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

3 P2P覆蓋網(wǎng)拓撲結(jié)構(gòu)

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

3.1 非結(jié)構(gòu)化拓撲

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

3.2 結(jié)構(gòu)化拓撲

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

3.3 基于復雜網(wǎng)絡理論的拓撲結(jié)構(gòu)

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

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

3.4 計算機網(wǎng)絡拓撲行為的演化模型

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

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

4 結(jié)束語

計算機網(wǎng)絡龐大的規(guī)模、異質(zhì)而復雜的體系結(jié)構(gòu)和豐富的動態(tài)特性，使傳統(tǒng)的隨機網(wǎng)絡模型難以對其拓撲行為特征做出系統(tǒng)、客觀的描述，強調(diào)系統(tǒng)整體性的復雜網(wǎng)絡理論為網(wǎng)絡行為的研究提供了新方法，成為解決網(wǎng)絡行為基礎(chǔ)理論研究的有力工具，為網(wǎng)絡的基礎(chǔ)理論研究帶來重大突破。任何復雜網(wǎng)絡理論研究的新成果都有可能被運用到計算機網(wǎng)絡行為特性的研究中，結(jié)合計算機網(wǎng)絡的特點，應用復雜性理論研究計算機網(wǎng)絡的拓撲行為，有可能發(fā)現(xiàn)其拓撲行為演化規(guī)律，從而根據(jù)實際需要，設計出性能較優(yōu)越的計算機網(wǎng)絡。 以下是基于復雜網(wǎng)絡理論的計算機網(wǎng)絡拓撲行為以及相關(guān)技術(shù)可以研究的方向和實現(xiàn)的目標：

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

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

3）基于復雜網(wǎng)絡理論的路由機制及其算法的研究，以及如何通過適當?shù)穆酚蓹C制提高網(wǎng)絡的信息傳輸量。

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

5）在復雜網(wǎng)絡理論中引入節(jié)點帶寬、網(wǎng)絡延遲等物理網(wǎng)絡特性，優(yōu)化拓撲結(jié)構(gòu)。

[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.