基于節點有效通信率的Ｐ２Ｐ網絡拓撲優化

（國防科學技術大學 信息系統與管理學院， 長沙 410073）



摘要：

分析了P2P網絡中產生大量冗余通信開銷的原因，根據不同節點對查詢表現出不同的性能，定義了節點有效通信率，讓具有更高有效通信率的節點具有更大的連接度。采用了基于流言的閑談機制來獲取整個網絡的平均有效通信率和平均節點連接度，提出節點度優化模型及連接策略。實驗結果顯示文中的拓撲優化方法大幅提高了資源搜索的整體性能。

關鍵詞：對等網； 拓撲優化； 流言機制

中圖分類號：TP393文獻標志碼：A

文章編號：10013695(2009)03105004



Optimization of topology for P2P networks based onefficient communication ratio of node



DENG Zhanglin， TANG Daquan， ZHANG Weiming

(College of Information System Management， National University of Defense Technology， Changsha 410073， China)



Abstract:

This paper analyzed why there were huge redundant traffics to search in P2P networks. In the searching process， different nodes exhibited different abilities. So efficient communication ratio (ECR) of node was defined as to make the node with higher ECR had bigger degrees. And proposed the model of optimization of node degree in company with the node connection strategy， using the average ERC and average degree of P2P network， which were gained based on gossip mechanism. The experimental results show that the method is effective to improve the performance of resource retrieval in P2P networks.

Key words：peertopeer; topology optimization; gossip



P2P（peertopeer）系統是現今Internet上最流行的應用之一，它是建立在應用層之上的覆蓋網絡[1]。網絡中擁有大量的節點，節點間可以直接建立連接進行文件共享。系統中各節點既是服務器，也是客戶機，避免了C/S模式下網絡依靠中心服務器的限制，因而大量用于文件共享系統，如Gnutella[2]、KazAa[3]、Chord[4]等。當前主要有結構化和非結構化兩種結構的P2P文件共享系統，主要區別在于對節點的組織和資源位置的約束上[5]。結構化的P2P系統通過分布式哈希表(distributed hash table， DHT)嚴格控制網絡拓撲結構和資源的放置位置；而非結構化P2P系統中資源的放置位置與網絡拓撲結構無關，隨機分布在整個系統中，因而節點可以隨意加入或退出網絡，基本無須對網絡進行管理。節點在進行資源查詢時卻往往是盲目的，盡管泛洪(flooding)的查詢方法能通過遍歷系統中的所有節點實現查詢，且對查詢有較好的響應結果，但是會產生大量的冗余查詢消息，帶來巨大的網絡流量開銷，而且搜索效率較低。

改善非結構化P2P系統的搜索性能主要是要減少搜索消息轉發的盲目性和提高查詢消息命中率。針對前者主要是增加節點對網絡拓撲結構和資源位置信息的了解，使查詢消息在進行轉發時具有更多路由信息；提高查詢消息命中率的一種方法是增加網絡中資源的副本數量[6]，通過對網絡中查詢頻率較高的資源進行動態復制來提高資源的查詢命中率。但是在進行數據復制時將增加網絡的流量開銷，特別是P2P網絡中熱點資源多為多媒體文件[7]，對其進行復制會帶來更大的網絡開銷。

本文則從另外的角度出發，通過分析節點對查詢消息的響應率，定義節點的有效通信率，通過節點的有效通信率優化節點的連接度，使具有更高有效通信率的節點具有更高的連接度，使查詢消息更多指向具有高命中率的節點，從而減少整個網絡的通信開銷。

1相關工作

1.1非結構化P2P系統的路由策略

Gnutella是典型的非結構化P2P文件共享系統，最初的Gnutella協議[8]對資源的查詢采用基于flooding的方法。查詢源節點向所有鄰居節點發送查詢消息，如果某鄰居節點含有目標文件，則返回應答消息給源節點；如果沒有，該鄰居節點向自己的鄰居節點轉發搜索消息，直到查詢到目標文件，并通過設置TTL(timetolive)來限制轉發的次數，并防止出現循環。由于這種搜索策略是首先遍歷自己的鄰居節點，然后再向下傳播，又稱為寬度優先搜索方法（breadthfirst search，BFS），查詢通信開銷將隨TTL呈指數規模增長。

BFS查詢方法造成冗余網絡通信開銷的原因主要在于鄰居節點范圍寬度的選擇和TTL值深度的設置[9]。針對這兩個問題出現了幾種對BFS方法的改進。Iterative Deepening[10]是通過最初設置一個較小的TTL值進行寬度優先搜索，然后等待搜索是否成功。如果成功，則停止搜索；否則增加TTL值再進行廣度優先搜索。重復此過程直到文件找到或者TTL到達設置最大值。在Directed BFS[10]方法中，查詢源節點不是向所有的鄰居節點發送查詢消息，而是選擇鄰居節點的一個子集以減少查詢消息量。RandomWalks[11]中查詢源節點生成k個查詢消息，隨機選擇k個鄰居節點進行消息的轉發，k根據網絡通信消耗和搜索成功率的要求選定。

以上對BFS方法的改進僅從算法本身入手，往往是以犧牲查詢響應時間、搜索成功率等性能為代價來獲取較少的網絡流量開銷。網絡拓撲的優化可建立在原有P2P系統路由算法的基礎上，既保持了原有路由算法的優點，又使網絡從拓撲結構上更利于對資源的查詢，從而進一步提高資源查詢的整體性能。

1.2網絡拓撲優化的特點

從對P2P系統的拓撲結構分析可知，造成產生冗余通信的原因主要有兩類：a）邏輯拓撲網絡與物理網絡之間的不匹配，使相同的物理連接上可能會多次傳遞同樣的查詢消息；b）節點缺乏對網絡拓撲結構的掌握，很多路徑的查詢消息是無效的，沒有應答消息返回。

針對以上兩個方面的原因，對P2P網絡拓撲的優化主要有兩種：一種是通過優化邏輯拓撲連接與物理連接之間的不匹配，使查詢消息在轉發過程中，減少在同一物理路徑上傳遞的次數，如LTM[12]，將物理上鄰近的節點選做鄰居節點，既保持了搜索范圍，又減少了查詢的響應時間；另外一種是不考慮底層物理網絡，而是優化節點間的邏輯連接，以提高查詢的發現效率，減少網絡的通信開銷。例如將提供相似資源或具有相似興趣的節點進行聚類[13，14]，使節點在進行資源查詢時，查詢消息發送給更可能具有目標文件的節點，從而提高搜索性能。

文獻[15]基于數據訪問頻率提出節點度優化模型，但它對網絡模型作出很多假設，如節點資源確定，并服從Uniform分布，節點存儲資源的訪問頻率已知等。但往往節點內容并不確定，時常發生變化，且網絡資源及資源的訪問頻率服從Zipf分布[7]。本文不對網絡模型作過多假設，通過分析產生冗余通信的原因，定義了網絡及節點的有效通信率，通過優化節點連接度來實現網絡拓撲的優化。

2覆蓋網絡的拓撲結構優化

非結構化的P2P系統是建立在物理網絡之上的邏輯網絡，節點通過維護與鄰居節點間的連接關系，實現與網絡間其他節點的通信。當一個節點想獲取某個資源時，生成對該資源的查詢消息并發送給它的鄰居節點。當鄰居節點收到查詢消息時，首先進行本地檢索，如果本地擁有與查詢消息相匹配的資源，返回應答消息給查詢源節點；如果本地沒有與查詢相匹配的資源時，然后將查詢消息轉發至它的鄰居節點。各鄰居節點對查詢消息主要有兩類結果，即返回應答消息和轉發查詢消息。鄰居節點對查詢消息的轉發等同于新產生一個查詢消息，轉發消息次數越多產生的查詢消息就越多。一個節點返回的應答消息越多，轉發的查詢消息越少，體現了節點在整個網絡中對查詢消息具有更強的響應能力。在查詢消息量一定的情況下，使這類節點接收更多的查詢消息，有利于減少整個網絡的通信開銷。

2.1概念定義

定義1網絡有效通信率。整個P2P網絡中對查詢消息的響應量與產生的總查詢消息量之比定義為網絡有效通信率，記網絡有效通信率為EC，則EC∈[0，1]。一段時間內整個網絡對查詢消息的響應量記做Me，冗余通信量記做Mr，總查詢消息量記做M，則有M+Me+Mr。整個網絡的有效通信率為

EC=Me/M（1）

類似網絡有效通信率，對于任意節點i，節點有效通信率是節點對查詢消息的響應量與節點收到的總查詢消息量之比，記節點i的有效通信率為ECi，節點的查詢消息響應量、冗余通信量和查詢總消息量分別由Mei、Mri和Mi 表示，則

ECi=Mei/Mi（2）

對于具有N個節點的P2P網絡，所有節點有效通信率的平均值記做EC，則

EC=(∑Ni=1ECi）/N（3）

2.2網絡優化模型

P2P網絡節點的連接度往往還受到節點自身性能的影響，如節點處理能力、帶寬等。在本文中假設所有節點具有同樣的性能，僅從節點有效通信率出發來優化節點連接度。假設一個具有N個節點的P2P網絡，網絡中任意節點P2P的連接度用di表示，網絡中所有節點連接度之和為D，則有D=∑Ni=1di，平均連接度記做d。假設每個節點發起查詢的概率相同，向任意節點轉發的概率相同，任意節點i收到的查詢消息量Mi與其連接度di成正比[14]：

Mi=M×（di/D）（4）

節點i的冗余通信量為

Mri=Mi-Mei=Mi-Mi×ECi=Mi×(1-ECi)（5）

由式（4）（5）可得整個P2P網絡的冗余查詢通信量Mr為

Mr=∑Ni=1Mri=∑Ni=1Mi×(1-ECi)=∑Ni=1M×（di/D)×(1-ECi)=M×(∑Ni=1di/D-∑Ni=1di/D×ECi)=M×(1-1/D×∑Ni=1ECi×di)（6）

式（6）表明網絡的冗余通信量與所有節點有效通信率和連接度的乘積之和呈現出線性關系。令 Γ=∑Ni=1ECi×di，則當Γ增加時，Mr減小；當Γ減小時，Mr增加。對于網絡中任意兩節點i、j，當節點有效通信率存在ECi＞ECj時，將節點i的連接度增加Δd，節點 j的連接度減少Δd，其余節點連接度不變，則Γ值的變化量為

ΔΓ=(ECi×(di+Δd)+ECj×(dj-Δd))-(ECi×di+ECj×dj)=(ECi-ECj)×Δd＞0

因此，在網絡中當有效通信率越高的節點具有越高的節點連接度時， Γ值將越大，網絡冗余通信量將越小。極端情況是當節點i的有效通信率ECi=ECmax時，如果有 di=D/2，即網絡呈現出星型結構，節點i是中心節點，與其他剩余節點相連，而其他節點相互沒有連接，其他所有節點的連接度均為1。

但是P2P網絡中當某些節點連接度過大，解決網絡的負載均衡成為網絡維護的額外負擔，且容易使網絡產生單點失效問題。節點對查詢消息的響應即節點所擁有資源的對查詢的匹配程度，因此節點有效通信率與其共享資源的分布一致。根據已有研究結果，資源的流行度及數量分布均呈冪率特性（Zipf分布）[7]，因此節點有效通信率也應該具有相似性質。P2P網絡的節點連接度也服從冪率分布[16]，表現出無標度特性，具有無標度特性的網絡具有很好的魯棒性[17]。在本文中節點連接度與節點有效通信率的關系由式（7）表示，節點的連接度能夠較好地滿足冪率分布。所有節點的平均有效通信率和平均連接度是優化標準，兩者的值均基于流言的傳播機制來獲取，將在2.3節討論。

di=(ECi/EC)α×d（7）

由于D=∑Ni=1di，則

∑Ni=1di=∑Ni=1(ECi/EC)α×d=d/(EC)α×∑Ni=1ECαi=N×d

∑Ni=1ECαi=[(∑Ni=1ECi)α/N]×N

∑Ni=1ECαi/(∑Ni=1ECi)α=N1-α（8）

由式（8）可知參數α的取值與網絡中節點有效通信率和網絡節點規模有關，在實際中可以根據需要選取適當的值。在本仿真實驗中選取α=1.5。

2.3流言傳播機制及算法

流言能被廣泛傳播，在節點間實現簡單。推拉（pushpull）式[18]的流言機制中每個節點執行兩個線程，即主動流言傳播和被動流言傳播線程。主動流言傳播進程中，節點隨機選擇一個鄰居節點，將本地狀態信息發送給該鄰居節點，并等待該鄰居節點返回它的狀態信息。被動流言傳播線程中節點等待其鄰居節點發送遠程狀態信息給它，然后返回本地狀態信息給該鄰居節點。推拉是成對出現的，當節點發送了本地狀態信息，就必能收到鄰居節點的遠程狀態信息；當節點收到鄰居節點的遠程狀態信息后，也必將發送本地狀態信息給鄰居節點。基于推拉流言機制的聚合算法具有很好的收斂性，能夠快速降低網絡中各節點的值與整個網絡平均值的差異[18]。

本文采用這種推拉式的傳播機制設計P2P系統中平均有效通信率和平均連接度獲取算法。任意節點i通過式（2）計算自己的有效通信率ECi，并以ECi、di分別記錄網絡的平均有效通信率和平均連接度。節點主動流言傳播算法中節點i初始化網絡的平均有效通信率和平均連接度為節點自身的有效通信率和連接度，在每個σ周期上，節點 i通過GetNeighbor()方法隨機獲取一個鄰居節點j，將本地存儲網絡平均有效通信率和節點連接度發送給它，并由Receive()方法得到節點j上存儲的這兩個值，最后通過AVG()方法計算兩節點的平均值。通過設置n的值，可以控制平均值收斂的精度，實驗顯示當n=30時，能夠達到良好的效果。節點被動流言傳播算法是指節點被動接收到鄰居節點向其發送的網絡平均有效通信率和平均連接度，在接收后將本地存儲的值返回給該請求節點，并計算兩節點平均值。具體算法如算法1和2所示。

算法1節點主動流言傳播進程

Initially:ECi=ECi，di=d，T=0

Every σ time do:

j←GetNeighbor(*);

send ECi， di to j;

ECj←Receive(j)#8226;ECj，dj，←Receive(j)#8226;dj;

ECjAVG(ECi，ECj)，di=AVG(di，dj);

T=T+1;

if T=n

di=(ECi/EC)α×di;

ECi=ECI，di=d，T=0;

算法2節點被動流言傳播進程

ECj，dj←Receive();

send ECidi to sender(ECj，dj);

ECi=AVG(ECi，ECj)，di=AVG(di，dj);

2.4節點連接度優化方法

節點連接度優化時應考慮給網絡帶來的開銷，但節點連接策略不是本文研究重點。本文中，增加節點連接度采取基于Randomwalks的方式[10]，通過鄰居節點轉發增加連接度的消息；減少連接度則直接與鄰居節點通信，與有效通信率低的節點斷開連接。設網絡中任意節點i的現有連接度由d′i表示，優化后的連接度由di表示，通過式（7）計算節點連接度優化的變化量為 Δd=di-d′i。當 Δd＞0時表示節點連接度增加；當Δd＜0時表示節點連接度減少；當Δd=0時節點連接度不變。在節點度變化過程中，用Δ表示節點度變化計數器，初值為Δ=Δd。

節點連接度增加步驟如下：

a)節點度增加源節點生成Δd個節點度增加消息，隨機選擇Δd個節點發送此消息，消息生命周期由TTL控制。

b)接收到節點度增加消息的節點檢查自身是否也需要增加節點連接度，如果是，則發起與源節點之間的新連接請求；否則按同樣的方法轉發消息。

c)當源節點收到新連接請求消息后，判斷節點Δ值是否為0，如果是，則不建立連接；如果Δ＞0，則向新連接請求節點發送應答消息，建立新連接。兩個節點的連接度變化計數器Δ=Δ-1。

連接度增加源節點本身也可能會接收到其他節點發送的節點度增加消息。連接過程如圖1所示。

減少節點連接度時節點分為主動和被動節點兩類。主動節點是操作的發起節點，其節點度減少量為Δd，向所有鄰居節點發送節點度減少消息，鄰居節點向其返回自身的連接度變化量。操作步驟如下：

a)如果鄰居節點中，當Δd＜0的節點數m＜Δ時，則主動節點直接發送與這些節點斷開連接的消息，接收到斷開連接消息的鄰居節點被動斷開連接，主動節點Δ=Δ+m，被動節點Δ=Δ+1；從剩余鄰居節點中按Δd從小到大的原則選擇Δ-m個節點進行斷開連接，方式與上相同。

b)當鄰居節點中Δd＜0的節點數m＞Δ時，主動節點按Δd從小到大的原則選擇Δ個此類節點進行斷開連接操作，斷開連接操作相同。

在上述增加和減少節點連接度的方法中，可能會出現兩個節點相互收到對方的增加或減少連接度消息，此時按先到先處理的原則進行。例如增加連接度消息，當兩個操作是建立同一條連接，則后一次連接無效。此方法的優勢是節點通過相當于一次查詢的通信開銷即實現了對節點連接度的優化，實現了對網絡整體查詢消息的優化，給網絡帶來的額外網絡流量很小。但方法并不保證節點度優化成功率，結合實驗結果，在以后的研究中將進一步對此進行深入研究。

3實驗仿真

為了驗證網絡拓撲優化對資源搜索性能的改善，本文采用Brite[19]拓撲產生器生成P2P網絡，在Peersim[20]仿真平臺上對拓撲優化模型進行了性能評估。本文選取具有冪率特性的BA模型[21]作為優化前的P2P網絡，并從不同的TTL值及不同的網絡規模對優化前后BFS查詢方法的性能進行了測試。所有實驗在一臺PC機上實現。網絡中擁有1 000個相異的資源，資源的數量服從Zipf分布。發起查詢的節點在網絡中隨機分布，對數據的查詢頻率也服從Zipf分布。資源數量與數據查詢頻率的 Zipf分布中，Zipf指數均取1。以10 000次查詢為時間片，在查詢中節點計算自身有效通信率，在時間片截止時根據2.3節中的流言機制對網絡平均有效通信率、平均節點連接度進行計算，并優化節點連接度。以10 000次同樣的數據查詢頻率分布對優化后的網絡搜索性能進行測試分析。文中選取1 000個節點規模的P2P網絡對不同TTL值對資源搜索性能的影響進行測試，選取2 000、4 000、6 000、8 000、10 000個節點等不同規模的網絡對資源搜索性能的影響進行測試。

3.1TTL值對搜索性能的影響

圖2~4分別為10 000次查詢中，搜索成功率、平均響應時間和網絡通信開銷與TTL值之間的關系。圖2顯示了對于1 000個節點的網絡，搜索成功率隨TTL值的增長而提高，當TTL=6時，搜索成功率接近100%，在TTL<5時優化模型較優化前有明顯提高。響應時間由TTL值來表征，即TTL值越小，響應時間越小。拓撲優化后查詢的平均響應時間和網絡通信開銷均較優化前有明顯改善。

3.2優化模型對網絡規模的擴展性

圖5~7分別為10 000次查詢中，TTL=6時，搜索成功率、平均響應時間和網絡通信開銷與網絡節點數目之間的關系。如圖5所示，優化后不同規模的網絡搜索成功率基本沒有降低。圖6結果顯示，拓撲優化后響應時間均較優化前有明顯縮短。拓撲優化后的網絡通信開銷與優化前相比，有大幅減少。如圖7所示，最大降幅接近70%。

4結束語

通過分析節點的有效通信率，指出產生大量網絡通信開銷的原因，根據節點有效通信率提出了節點連接度優化模型。文中采用了基于流言的閑談機制來獲取整個網絡的平均有效通信率和平均節點連接度，并提出節點度優化連接策略。實驗中，資源及查詢均采用與實際P2P網絡相符的Zipf分布，結果顯示，文中的優化方法在沒有降低搜索成功率的基礎上，縮短了查詢響應時間，大幅降低了網絡通信開銷，并對網絡規模具有很好的擴展性。

參考文獻：

[1] WANG Chonggang， LI Bo. Peertopeer overlay network: a survey[R].Hongkong:HKUST， 2003.

[2]Gnutella[EB/OL].http//:www.gnutella.com.

[3]KaZaA[EB/OL].http//:www.kazaa.com.

[4]STOICA I，MORRIS R，KARGER D， et al. Chord: a scalable peertopeer lookup service for Internet applications[C]//Proc ofSIGCOMM Conference. 2001:149160.

[5]QIAO Yi， BUSTAMANTE F E. Structured and unstructured overlays under the microscope[C]//Proc of Annual Conference on USENIX’06 Annual Technical Conference. Berkeley:USENIX Association， 2006:31.

[6]COHEN E， SHENKER S. Replication strategies in unstructured peertopeer networks[C]//Proc of Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications. New York:ACM Press， 2002:177190.

[7]ZHAO Shanyu， STUTZBACH D， REJAIE R. Characterizing files in the modern Gnutella network:a measurement study[J]. Proceedings of SPIE，2006，6071:239251.

[8]The Gnutella protocol specification v0.4[EB/OL]. [2008].http://www9. limewire.com/developer/gnutella_protocol_0.4.pdf.

[9]LUO Jiaqing， ZHOU Shijie， WU Chunjiang， et al. Adaptive flooding routing algorithm in unstructured P2P[C]//Proc of International Conference on Communications， Circuits and Systems.[S.l.]:IEEE， 2006:15571561.

[10]YANG B， GARCIA M H. Improving search in peertopeer networks.[C]//Proc of the 22nd IEEE International Conference on Distributed Computing. Washington DC:IEEE Computer Society， 2002:110.

[11]LV Qin， CAO Pei ， COHEN E， et al. Search and replication in unstructured peertopeer network[C]//Proc of the 16th ACM International Conference onSupercomputing. New York:ACM Press， 2002:8495.

[12]LIU Yunhao， XIAO Li， LIU Xiaomei， et al. Location awareness in unstructured peertopeer systems[J]. IEEE Trans on Parallel and Distributed Systems， 2005，16(2):163174.

[13]SAKARYAN G， UNGER H. Contentoriented selforganization in unstructured P2P data sharing systems:an approach to improve resource discovery[C]//Proc of the 5th International Workshop. Berlin: Springer，2005.

[14]CARCHIOLO V， MALGERI M， MANGIONI G， et al. Social behaviours applied to P2P systems:an efficient algorithm for resources organization[EB/OL].(2007).http://arxiv.org/abs/cs.DC/0702 085v1.

[15]馮國富，張金城，姜玉泉，等.無結構P2P覆蓋網絡的拓撲優化[J].軟件學報，2007，18(11):2819 2829.

[16]RIPEANU M， FOSTER I. Mapping the Gnutella network: macroscopic properties of largescale P2P systems[C]//Proc of the 1st International Workshop on P2P Systems. London:SpringerVerlag， 2002:8593.

[17]BARABASI A L， BONABEAU E.Scalefree networks[J]. Scientific American，2003，288:6069.

[18]JELASITY M， MONTRESOR A，BABAOGLU O.Gossipbased aggregation in large dynamics networks[C]//Proc of ACM Transactions on Computer Systems. New York:ACM Press， 2005:219252.

[19]BRITE[EB/OL]. http://www.cs.bu.edu/brite.

[20]Peersim[EB/OL]. http://peersim.sourceforge.net.

[21]BARABASI A L， ALBERT R. Emergence of scaling in random networks[J]. Science，1999，286:509512.