Gnutella環境下資源定位方法的改進

吳明生富美科技有限公司技術研發中心 山東 250306

0 前言

Gnutella網絡目前被廣泛的用來實現文件，特別是視頻及音頻文件的共享，作為無中心非結構化的P2P網絡，其資源定位的查找效率及網絡可擴展性問題一直是針對 Gnutella網絡的研究熱點。本文在已有研究的基礎上提出了一種新的機制，節點在定位資源時僅使用Gnutella網絡的部分通路，把該機制簡稱為基于部分通路的方法。

1 基于部分通路的方法

1.1 基本概念與節點的數據結構

在Gnutella網絡中一個節點的“度”是指到達這個節點的邊的個數，基于部分通路的方法需要在Gnutella網絡上建立一層邏輯結構，把度的概念引入此邏輯結構，節點在此邏輯結構上的“度”稱為邏輯度。為了說明基于部分通路的方法給出以下定義：

定義1：度節點與反度節點

對于一個要加入Gnutella網絡的節點，選出邏輯度較大的幾個鄰居節點，這些鄰居節點的邏輯度之和剛好大于等于一個設定的值 Degreesum，把這些鄰居節點稱為加入節點的度節點。把加入節點稱為這些鄰居節點的反度節點。

定義2：度鏈接

度節點與反度節點間建立的邏輯鏈接稱為度鏈接。

定義3：度生成網絡

Gnutella網絡中所有的度鏈接形成一個網絡，把該網絡稱為度生成網絡。度生成網絡是Gnutella網絡中所有通路的子集所形成的網絡。圖1(b)、(c)中的雙向箭頭鏈接所形成的結構就是度生成網絡。

定義4：邏輯度(Logical Degree)

在度生成網絡上與一個節點相連的度鏈接的個數就是上面所說的邏輯度。例如，在圖 1(b)中，節點 P1、P2加入前，P4的邏輯度為1，P5的邏輯度為2。實際上，邏輯度就是節點在度生成網絡上的度。

例如，假設Degreesum=2，從圖1(a)可知，在P1和P2未加入之前，加入節點P1有2個鄰居節點P3、P4，從圖1(b)可知，P3、P4的邏輯度均為1，這樣在P加入之后，P3、P4成為P1的度節點，P1成為P3、P4的反度節點，在P1與P3間建立的邏輯鏈接稱為度鏈接。P2加入時，因鄰居接點P1、P4和P5的邏輯度均為2，所以僅需選擇通訊延遲較小的P5建立一條度鏈接。

定義5：度廣播搜索

把在度生成網絡上進行的廣播搜索稱為度廣播搜索。在基于部分通路的方法中，規定查詢消息只能在建立了度鏈接的通路上傳輸，在其他通路上不能傳輸。

圖1 節點P1、P2加入Gnutella網絡

在基于部分通路的方法中，一個節點上要維護兩類信息：第一類信息記錄度節點的地址，第二類信息記錄反度節點的地址，如圖2所示。

圖2 節點上創建的數據結構

1.2 相關操作的過程

（1）節點加入

節點加入Gnutella網絡的過程可以分為兩個步驟：①節點通過TTL值為1的傳統廣播，選出邏輯度較大的幾個鄰居節點作為度節點，這些鄰居節點的邏輯度之和剛好大于等于一個設定的值Degreesum。如果因為鄰居節點太少或度太小，所有鄰居節點的邏輯度之和小于 Degreesum，就要選出所有鄰居節點。②建立加入節點的度節點信息，同時度節點把加入節點加為反度節點。

（2）定位資源

假設 TTL=H。節點使用基于部分通路的方法定位資源時，只需進行跳數為 H的度廣播搜索。如果一個節點收到UID相同的Query消息，就把Query消息丟棄，不再轉發；如果一個節點存有所求的資源內容，就停止Query消息的轉發，響應到達的Query請求，回復QueryHit消息，通知請求節點所求資源已經找到，建立HTTP連接進行文件傳輸。

（3）節點離開

當一個節點Pleave要離開Gnutella網絡時，在真正切斷它之前，要通知與其聯系的節點，以便這些節點可對Pleave的離開做出相應處理。Pleave的度節點收到Pleave的離開通知時，把Pleave從其反度節點表中刪除。Pleave的反度節點收到Pleave的離開通知時，把Pleave從其度節點表中刪除，然后執行加入操作。

（4）維護

執行維護操作時，各節點需要檢查其度節點和反度節點的活性，并刪除或更換無效的信息。在具體實現維護操作時，基于部分通路的方法借助 Gnutella協議的消息傳播規則：QueryHit消息總是沿著Query消息轉發的路徑逆向傳輸。遵循此規則，節點 P對與自己建立聯系的每個節點 Pi發出Query消息，在Pi不失效的情況下，P將收到 Pi發回來的QueryHit消息。如果在一定的時間內未收到來自Pi的回復消息，就可以認為節點 Pi已經失效，就要刪除或更換有關 Pi的信息。

2 仿真及其結果分析

2.1 仿真設置及性能指標

在 Red Hat9.0下運用 Gnutella仿真軟件 Packet-level Gnutellasim進行實驗。仿真時節點數目在1000到3000之間變化。仿真中產生10000個文件作為網絡內容，根據記錄文件“ClarkNet-HTTP”把它們分到不同節點上，各節點也根據此記錄文件發起資源查詢請求，查詢請求的個數設為2000。TTL值設為 6，鄰居節點的邏輯度之和要達到的值Degreesum設為2。每個網絡大小使用三個不同的由GT-ITM產生的網絡拓撲模擬三次，所列仿真結果是重復實驗后計算的平均值。

一般使用以下指標來評估資源定位方法的性能：

（1）詢問消息數：用來定位網絡中資源的詢問消息個數。這里用兩種方式統計這個量：①只統計一次資源搜索過程所引起的詢問消息個數；②統計所有節點進行資源定位及維護操作所引起的總詢問消息個數。

（2）范圍：一次搜索過程所訪問的節點個數。

在相同搜索范圍下，訪問消息少的資源定位方法較好，或者說產生相同詢問消息數時，搜索范圍大的資源定位方法較好。

2.2 對比結果

2.2.1 詢問消息數

從圖3可以看出，完成一次資源搜索平均所引起的消息個數有如下特點：①使用基于部分通路的方法一次資源搜索過程所引起的消息個數遠小于使用傳統廣播搜索法所引起的消息個數；②當節點個數增加時，兩種方法所引起的消息個數都增加。

圖3 一次資源搜索過程所引起的消息數

每個節點要定期檢查與其建立聯系的節點是否存在，每100個節點加入網絡后要利用維護消息更新路由信息。從圖4可以看出，在節點進行資源定位及維護操作時，使用基于部分通路的方法所引起的通訊負載遠小于使用傳統廣播搜索法所引起的通訊負載；并且當節點個數增加時，兩種方法所引起的通訊負載都增加。

圖4 資源定位及維護操作所引起的通訊負載

2.2.2 范圍

從圖5可以看出，使用基于部分通路的方法時查詢請求的平均搜索范圍低于使用傳統廣播搜索法時查詢請求的平均搜索范圍。

圖5 查詢請求的平均搜索范圍

3 結論

為了減少Gnutella網絡中資源定位時的冗余消息，提高Gnutella網絡的可擴展性，本文提出了基于部分通路的資源定位方法。運用此方法所構建的邏輯結構不但使網絡的“冪規律”特征更加突出，而且還減少了網絡中的回路。仿真實驗的結果顯示出，在相同搜索范圍下，基于部分通路的方法所引起的通訊負載小于傳統廣播搜索法所引起的通訊負載，這些對于未來智能網絡打印機的研發具有深遠意義。

[1]The Gnutella protocol specification v0. 4. http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf.

[2]Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology [J].ACM SIGCOMM Computer Communication Review.1999.

[3]黃道穎,劉剛,張堯.利用Gnutella網絡的拓撲特性改進其可擴展性[J].計算機工程與應用.2003.

[4]ClarkNet-HTTP.http://ita.ee.lbl.gov/html/contrib/ClarkNet-HTTP.html.

[5]Zegura E W, Calvert K L, Bhattacharjee S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM’96, San Francisco.CA: IEEE Computer Press.1996.