Gnutella環(huán)境下資源定位方法的改進(jìn)

吳明生富美科技有限公司技術(shù)研發(fā)中心 山東 250306

0 前言

Gnutella網(wǎng)絡(luò)目前被廣泛的用來(lái)實(shí)現(xiàn)文件，特別是視頻及音頻文件的共享，作為無(wú)中心非結(jié)構(gòu)化的P2P網(wǎng)絡(luò)，其資源定位的查找效率及網(wǎng)絡(luò)可擴(kuò)展性問(wèn)題一直是針對(duì) Gnutella網(wǎng)絡(luò)的研究熱點(diǎn)。本文在已有研究的基礎(chǔ)上提出了一種新的機(jī)制，節(jié)點(diǎn)在定位資源時(shí)僅使用Gnutella網(wǎng)絡(luò)的部分通路，把該機(jī)制簡(jiǎn)稱(chēng)為基于部分通路的方法。

1 基于部分通路的方法

1.1 基本概念與節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

在Gnutella網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的“度”是指到達(dá)這個(gè)節(jié)點(diǎn)的邊的個(gè)數(shù)，基于部分通路的方法需要在Gnutella網(wǎng)絡(luò)上建立一層邏輯結(jié)構(gòu)，把度的概念引入此邏輯結(jié)構(gòu)，節(jié)點(diǎn)在此邏輯結(jié)構(gòu)上的“度”稱(chēng)為邏輯度。為了說(shuō)明基于部分通路的方法給出以下定義：

定義1：度節(jié)點(diǎn)與反度節(jié)點(diǎn)

對(duì)于一個(gè)要加入Gnutella網(wǎng)絡(luò)的節(jié)點(diǎn)，選出邏輯度較大的幾個(gè)鄰居節(jié)點(diǎn)，這些鄰居節(jié)點(diǎn)的邏輯度之和剛好大于等于一個(gè)設(shè)定的值 Degreesum，把這些鄰居節(jié)點(diǎn)稱(chēng)為加入節(jié)點(diǎn)的度節(jié)點(diǎn)。把加入節(jié)點(diǎn)稱(chēng)為這些鄰居節(jié)點(diǎn)的反度節(jié)點(diǎn)。

定義2：度鏈接

度節(jié)點(diǎn)與反度節(jié)點(diǎn)間建立的邏輯鏈接稱(chēng)為度鏈接。

定義3：度生成網(wǎng)絡(luò)

Gnutella網(wǎng)絡(luò)中所有的度鏈接形成一個(gè)網(wǎng)絡(luò)，把該網(wǎng)絡(luò)稱(chēng)為度生成網(wǎng)絡(luò)。度生成網(wǎng)絡(luò)是Gnutella網(wǎng)絡(luò)中所有通路的子集所形成的網(wǎng)絡(luò)。圖1(b)、(c)中的雙向箭頭鏈接所形成的結(jié)構(gòu)就是度生成網(wǎng)絡(luò)。

定義4：邏輯度(Logical Degree)

在度生成網(wǎng)絡(luò)上與一個(gè)節(jié)點(diǎn)相連的度鏈接的個(gè)數(shù)就是上面所說(shuō)的邏輯度。例如，在圖 1(b)中，節(jié)點(diǎn) P1、P2加入前，P4的邏輯度為1，P5的邏輯度為2。實(shí)際上，邏輯度就是節(jié)點(diǎn)在度生成網(wǎng)絡(luò)上的度。

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

定義5：度廣播搜索

把在度生成網(wǎng)絡(luò)上進(jìn)行的廣播搜索稱(chēng)為度廣播搜索。在基于部分通路的方法中，規(guī)定查詢(xún)消息只能在建立了度鏈接的通路上傳輸，在其他通路上不能傳輸。

圖1 節(jié)點(diǎn)P1、P2加入Gnutella網(wǎng)絡(luò)

在基于部分通路的方法中，一個(gè)節(jié)點(diǎn)上要維護(hù)兩類(lèi)信息：第一類(lèi)信息記錄度節(jié)點(diǎn)的地址，第二類(lèi)信息記錄反度節(jié)點(diǎn)的地址，如圖2所示。

圖2 節(jié)點(diǎn)上創(chuàng)建的數(shù)據(jù)結(jié)構(gòu)

1.2 相關(guān)操作的過(guò)程

（1）節(jié)點(diǎn)加入

節(jié)點(diǎn)加入Gnutella網(wǎng)絡(luò)的過(guò)程可以分為兩個(gè)步驟：①節(jié)點(diǎn)通過(guò)TTL值為1的傳統(tǒng)廣播，選出邏輯度較大的幾個(gè)鄰居節(jié)點(diǎn)作為度節(jié)點(diǎn)，這些鄰居節(jié)點(diǎn)的邏輯度之和剛好大于等于一個(gè)設(shè)定的值Degreesum。如果因?yàn)猷従庸?jié)點(diǎn)太少或度太小，所有鄰居節(jié)點(diǎn)的邏輯度之和小于 Degreesum，就要選出所有鄰居節(jié)點(diǎn)。②建立加入節(jié)點(diǎn)的度節(jié)點(diǎn)信息，同時(shí)度節(jié)點(diǎn)把加入節(jié)點(diǎn)加為反度節(jié)點(diǎn)。

（2）定位資源

假設(shè) TTL=H。節(jié)點(diǎn)使用基于部分通路的方法定位資源時(shí)，只需進(jìn)行跳數(shù)為 H的度廣播搜索。如果一個(gè)節(jié)點(diǎn)收到UID相同的Query消息，就把Query消息丟棄，不再轉(zhuǎn)發(fā)；如果一個(gè)節(jié)點(diǎn)存有所求的資源內(nèi)容，就停止Query消息的轉(zhuǎn)發(fā)，響應(yīng)到達(dá)的Query請(qǐng)求，回復(fù)QueryHit消息，通知請(qǐng)求節(jié)點(diǎn)所求資源已經(jīng)找到，建立HTTP連接進(jìn)行文件傳輸。

（3）節(jié)點(diǎn)離開(kāi)

當(dāng)一個(gè)節(jié)點(diǎn)Pleave要離開(kāi)Gnutella網(wǎng)絡(luò)時(shí)，在真正切斷它之前，要通知與其聯(lián)系的節(jié)點(diǎn)，以便這些節(jié)點(diǎn)可對(duì)Pleave的離開(kāi)做出相應(yīng)處理。Pleave的度節(jié)點(diǎn)收到Pleave的離開(kāi)通知時(shí)，把Pleave從其反度節(jié)點(diǎn)表中刪除。Pleave的反度節(jié)點(diǎn)收到Pleave的離開(kāi)通知時(shí)，把Pleave從其度節(jié)點(diǎn)表中刪除，然后執(zhí)行加入操作。

（4）維護(hù)

執(zhí)行維護(hù)操作時(shí)，各節(jié)點(diǎn)需要檢查其度節(jié)點(diǎn)和反度節(jié)點(diǎn)的活性，并刪除或更換無(wú)效的信息。在具體實(shí)現(xiàn)維護(hù)操作時(shí)，基于部分通路的方法借助 Gnutella協(xié)議的消息傳播規(guī)則：QueryHit消息總是沿著Query消息轉(zhuǎn)發(fā)的路徑逆向傳輸。遵循此規(guī)則，節(jié)點(diǎn) P對(duì)與自己建立聯(lián)系的每個(gè)節(jié)點(diǎn) Pi發(fā)出Query消息，在Pi不失效的情況下，P將收到 Pi發(fā)回來(lái)的QueryHit消息。如果在一定的時(shí)間內(nèi)未收到來(lái)自Pi的回復(fù)消息，就可以認(rèn)為節(jié)點(diǎn) Pi已經(jīng)失效，就要?jiǎng)h除或更換有關(guān) Pi的信息。

2 仿真及其結(jié)果分析

2.1 仿真設(shè)置及性能指標(biāo)

在 Red Hat9.0下運(yùn)用 Gnutella仿真軟件 Packet-level Gnutellasim進(jìn)行實(shí)驗(yàn)。仿真時(shí)節(jié)點(diǎn)數(shù)目在1000到3000之間變化。仿真中產(chǎn)生10000個(gè)文件作為網(wǎng)絡(luò)內(nèi)容，根據(jù)記錄文件“ClarkNet-HTTP”把它們分到不同節(jié)點(diǎn)上，各節(jié)點(diǎn)也根據(jù)此記錄文件發(fā)起資源查詢(xún)請(qǐng)求，查詢(xún)請(qǐng)求的個(gè)數(shù)設(shè)為2000。TTL值設(shè)為 6，鄰居節(jié)點(diǎn)的邏輯度之和要達(dá)到的值Degreesum設(shè)為2。每個(gè)網(wǎng)絡(luò)大小使用三個(gè)不同的由GT-ITM產(chǎn)生的網(wǎng)絡(luò)拓?fù)淠M三次，所列仿真結(jié)果是重復(fù)實(shí)驗(yàn)后計(jì)算的平均值。

一般使用以下指標(biāo)來(lái)評(píng)估資源定位方法的性能：

（1）詢(xún)問(wèn)消息數(shù)：用來(lái)定位網(wǎng)絡(luò)中資源的詢(xún)問(wèn)消息個(gè)數(shù)。這里用兩種方式統(tǒng)計(jì)這個(gè)量：①只統(tǒng)計(jì)一次資源搜索過(guò)程所引起的詢(xún)問(wèn)消息個(gè)數(shù)；②統(tǒng)計(jì)所有節(jié)點(diǎn)進(jìn)行資源定位及維護(hù)操作所引起的總詢(xún)問(wèn)消息個(gè)數(shù)。

（2）范圍：一次搜索過(guò)程所訪問(wèn)的節(jié)點(diǎn)個(gè)數(shù)。

在相同搜索范圍下，訪問(wèn)消息少的資源定位方法較好，或者說(shuō)產(chǎn)生相同詢(xún)問(wèn)消息數(shù)時(shí)，搜索范圍大的資源定位方法較好。

2.2 對(duì)比結(jié)果

2.2.1 詢(xún)問(wèn)消息數(shù)

從圖3可以看出，完成一次資源搜索平均所引起的消息個(gè)數(shù)有如下特點(diǎn)：①使用基于部分通路的方法一次資源搜索過(guò)程所引起的消息個(gè)數(shù)遠(yuǎn)小于使用傳統(tǒng)廣播搜索法所引起的消息個(gè)數(shù)；②當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，兩種方法所引起的消息個(gè)數(shù)都增加。

圖3 一次資源搜索過(guò)程所引起的消息數(shù)

每個(gè)節(jié)點(diǎn)要定期檢查與其建立聯(lián)系的節(jié)點(diǎn)是否存在，每100個(gè)節(jié)點(diǎn)加入網(wǎng)絡(luò)后要利用維護(hù)消息更新路由信息。從圖4可以看出，在節(jié)點(diǎn)進(jìn)行資源定位及維護(hù)操作時(shí)，使用基于部分通路的方法所引起的通訊負(fù)載遠(yuǎn)小于使用傳統(tǒng)廣播搜索法所引起的通訊負(fù)載；并且當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，兩種方法所引起的通訊負(fù)載都增加。

圖4 資源定位及維護(hù)操作所引起的通訊負(fù)載

2.2.2 范圍

從圖5可以看出，使用基于部分通路的方法時(shí)查詢(xún)請(qǐng)求的平均搜索范圍低于使用傳統(tǒng)廣播搜索法時(shí)查詢(xún)請(qǐng)求的平均搜索范圍。

圖5 查詢(xún)請(qǐng)求的平均搜索范圍

3 結(jié)論

為了減少Gnutella網(wǎng)絡(luò)中資源定位時(shí)的冗余消息，提高Gnutella網(wǎng)絡(luò)的可擴(kuò)展性，本文提出了基于部分通路的資源定位方法。運(yùn)用此方法所構(gòu)建的邏輯結(jié)構(gòu)不但使網(wǎng)絡(luò)的“冪規(guī)律”特征更加突出，而且還減少了網(wǎng)絡(luò)中的回路。仿真實(shí)驗(yàn)的結(jié)果顯示出，在相同搜索范圍下，基于部分通路的方法所引起的通訊負(fù)載小于傳統(tǒng)廣播搜索法所引起的通訊負(fù)載，這些對(duì)于未來(lái)智能網(wǎng)絡(luò)打印機(jī)的研發(fā)具有深遠(yuǎn)意義。

[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網(wǎng)絡(luò)的拓?fù)涮匦愿倪M(jìn)其可擴(kuò)展性[J].計(jì)算機(jī)工程與應(yīng)用.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.