一種新的基于Ｆｌｏｏｄｉｎｇ的資源發(fā)現(xiàn)機(jī)制

摘要：洪泛機(jī)制(Flooding)由于其簡(jiǎn)單性而被廣泛應(yīng)用于目前的非結(jié)構(gòu)化P2P文件共享系統(tǒng)中，盡管它在內(nèi)容搜索方面有很高的效率，但同時(shí)產(chǎn)生了大量的冗余消息，嚴(yán)重制約了網(wǎng)絡(luò)的可擴(kuò)展性。本文提出一種新的基于Flooding的資源發(fā)現(xiàn)機(jī)制，通過(guò)在本地結(jié)點(diǎn)維護(hù)興趣簇、簇內(nèi)結(jié)點(diǎn)索引等信息列表來(lái)改善Flooding機(jī)制的缺點(diǎn)。

關(guān)鍵詞：Flooding；資源發(fā)現(xiàn)；興趣簇

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)11-20243-02

1 引言

在全分布拓?fù)涞膶?duì)等網(wǎng)模型[1]中，結(jié)點(diǎn)的路由只是通過(guò)網(wǎng)絡(luò)廣播的方式進(jìn)行，結(jié)點(diǎn)之間的通信使用Flooding方法[2，3]實(shí)現(xiàn)資源的查找和定位，盡管它在內(nèi)容搜索方面有很高的效率，但同時(shí)產(chǎn)生了大量的冗余消息，嚴(yán)重制約了網(wǎng)絡(luò)的可擴(kuò)展性，現(xiàn)有的改進(jìn)搜索策略雖然減少了冗余消息的數(shù)量，但也明顯降低了消息的覆蓋范圍，這是因?yàn)镕looding方式?jīng)]有考慮查詢(xún)歷史記錄和結(jié)點(diǎn)興趣度等有助于降低消息冗余和查詢(xún)效率的信息。而在實(shí)際的資源發(fā)現(xiàn)[4，5]過(guò)程中，部分用戶(hù)可能之間的興趣偏好和行為相似度可能非常接近，如果把這些用戶(hù)劃分在一起形成對(duì)某類(lèi)資源感興趣的簇[6]，則其他用戶(hù)向該簇查詢(xún)這類(lèi)資源時(shí)，查詢(xún)請(qǐng)求將有更大的概率得到滿(mǎn)足。同時(shí)簇內(nèi)用戶(hù)之間由于具有相似的興趣度，則大部分查詢(xún)請(qǐng)求可以在簇內(nèi)得到滿(mǎn)足，這將大大減少Flooding方式所產(chǎn)生的消息風(fēng)暴，而且查詢(xún)成功率也大大增加。本文就是通過(guò)此種方法來(lái)改善Flooding機(jī)制的缺點(diǎn)。

2 洪泛機(jī)制(Flooding)

2.1 洪泛機(jī)制(Flooding)的主要特點(diǎn)

Flooding機(jī)制的特點(diǎn)，主要有：

(1)簡(jiǎn)單健壯，無(wú)需維護(hù)狀態(tài)。

(2)容錯(cuò)性高，局部結(jié)點(diǎn)失效不影響整個(gè)系統(tǒng)性能；

(3)以擴(kuò)散方式發(fā)送搜索信息會(huì)產(chǎn)生大量冗余，造成網(wǎng)絡(luò)擁塞，擴(kuò)展性差；

(4)資源發(fā)現(xiàn)效率不高和準(zhǔn)確性不高。

2.2 Flooding機(jī)制

Gnutella的資源發(fā)現(xiàn)采用基于Flooding的消息擴(kuò)散方式進(jìn)行。發(fā)起查詢(xún)時(shí)給消息賦予一個(gè)TTL值表示消息能傳播的最大跳數(shù)，擴(kuò)散策略是當(dāng)一個(gè)結(jié)點(diǎn)收到資源查詢(xún)請(qǐng)求時(shí)，若不滿(mǎn)足，則將TTL減1并把查詢(xún)消息向其鄰居結(jié)點(diǎn)擴(kuò)散，重復(fù)上述過(guò)程直到TTL減為0或查詢(xún)得到滿(mǎn)足，F(xiàn)looding過(guò)程如圖1所示。理論上，通過(guò)Flooding方式的消息廣播，消息最后可以到達(dá)網(wǎng)絡(luò)中的所有結(jié)點(diǎn)。如圖1所示，搜索的節(jié)點(diǎn)一開(kāi)始TTL=3，它每傳播一次TTL減1，如果TTL減到0還沒(méi)有搜索到資源，則停止。如果搜索到資源則返回目標(biāo)機(jī)器的信息以用來(lái)建立連接。在搜索過(guò)程中可能出現(xiàn)循環(huán)，但是由于有TTL控制，所以這個(gè)循環(huán)不會(huì)永遠(yuǎn)進(jìn)行下去，當(dāng)TTL=0的時(shí)候自然結(jié)束。

設(shè)網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)的平均度數(shù)為ave_dgr，則一個(gè)Query消息在網(wǎng)絡(luò)中訪問(wèn)到的結(jié)點(diǎn)數(shù)N最多為N=(ave_dgr)TTL，假設(shè)一個(gè)網(wǎng)絡(luò)中的結(jié)點(diǎn)平均度數(shù)為5，Query消息的TTL=6，則消息能夠訪問(wèn)到15625個(gè)結(jié)點(diǎn)，如果每個(gè)消息都產(chǎn)生如此巨大的消息副本，網(wǎng)絡(luò)帶寬將會(huì)很快被消耗完畢。圖1是Flooding方式。

2.3 TTL的意義

消息生存時(shí)間(TTL)：消息生存時(shí)間主要是控制消息在網(wǎng)絡(luò)中傳播時(shí)能夠生存的時(shí)間。它是包含在消息頭中的一個(gè)字段，在消息生成時(shí)被賦予一個(gè)初始值。當(dāng)消息被發(fā)送出去，其他主機(jī)結(jié)點(diǎn)接收到該消息時(shí)，首先檢查它的消息頭中的TTL 值，如果為零，則將該消息丟棄掉。否則，將該消息的TTL 值減1，然后再發(fā)給它的鄰居結(jié)點(diǎn)。TTL值越大，消息能傳播的距離就越遠(yuǎn)，反之就越近。

2.4 TTL控制機(jī)制分析

Flooding方法的最大優(yōu)點(diǎn)是簡(jiǎn)單，易維護(hù)。但這種方法的缺點(diǎn)也很明顯，TTL值的設(shè)定將直接影響到查詢(xún)結(jié)果，如果TTL初始值設(shè)置較高，則搜索需要經(jīng)過(guò)整個(gè)網(wǎng)絡(luò)或至少一個(gè)限定的范圍才能得到結(jié)果，這需要占用很多帶寬，查詢(xún)開(kāi)銷(xiāo)過(guò)大。而如果TTL設(shè)置的值低，則可能查詢(xún)很快就結(jié)束，找不到所需要的資源（即使在網(wǎng)絡(luò)中的某個(gè)結(jié)點(diǎn)上存在該資源）。在結(jié)點(diǎn)平均度數(shù)為n的Gnutella網(wǎng)絡(luò)中，一條消息最多可以產(chǎn)生P2n-(n-1)個(gè)冗余消息。這些冗余消息將消耗大量的處理時(shí)間和網(wǎng)絡(luò)帶寬，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，網(wǎng)絡(luò)中的消息呈指數(shù)增長(zhǎng)，很容易造成系統(tǒng)過(guò)載和擁塞。

3 一種新的基于Flooding的資源發(fā)現(xiàn)機(jī)制

此機(jī)制分3個(gè)階段：Cluster形成、Cluster維護(hù)和搜索算法。

3.1 Cluster形成

Cluster的形成不需要外部檢測(cè)和控制，結(jié)點(diǎn)通過(guò)局部知識(shí)得到與其興趣度相似的其他結(jié)點(diǎn)，并保留其所在簇內(nèi)其他結(jié)點(diǎn)信息。為了實(shí)現(xiàn)高效的協(xié)同工作和資源共享，最好讓每個(gè)結(jié)點(diǎn)盡量了解其他具有相似特征的結(jié)點(diǎn)信息（研究發(fā)現(xiàn)具有相同或相似特征的對(duì)等體之間，具有較高的可能性進(jìn)行合作和信息交換），不再為確定合作結(jié)點(diǎn)定位和路由付出額外的通信開(kāi)銷(xiāo)。在全分布的網(wǎng)絡(luò)中，沒(méi)有集中控制器來(lái)負(fù)責(zé)組成興趣簇，為了獲得興趣簇信息，本文設(shè)計(jì)了協(xié)作學(xué)習(xí)方法：假設(shè)網(wǎng)絡(luò)中某個(gè)簇中的相似結(jié)點(diǎn)組成一個(gè)連通圖G=(V，E)，∣E∣=n，簇內(nèi)結(jié)點(diǎn)通過(guò)不斷與鄰接的相似結(jié)點(diǎn)進(jìn)行信息交換來(lái)發(fā)現(xiàn)新的結(jié)點(diǎn)，使得結(jié)點(diǎn)本地相似集合S(vi)不斷擴(kuò)大，在經(jīng)過(guò)有限次的信息交換后，最終可以獲取整個(gè)連通的具有相似興趣度結(jié)點(diǎn)的興趣簇C。

3.2 Cluster維護(hù)

簇(Cluster)的形成是通過(guò)結(jié)點(diǎn)之間的交互形成的，在動(dòng)態(tài)網(wǎng)絡(luò)中，Cluster的維護(hù)和更新需要考慮結(jié)點(diǎn)的加入、離開(kāi)、失效和行為變化等問(wèn)題，本文對(duì)這四種情況做了分析和處理：

(1)結(jié)點(diǎn)加入

結(jié)點(diǎn)vii在初始加入網(wǎng)絡(luò)時(shí)，沒(méi)有網(wǎng)絡(luò)中其他結(jié)點(diǎn)的任何信息。vi采用廣播的方式向其鄰居

結(jié)點(diǎn)nbr(vi)交換信息來(lái)發(fā)現(xiàn)已有興趣簇。vi與所有的ni∈nbr(vi)結(jié)點(diǎn)比較結(jié)點(diǎn)相似度s(vi，ni)，當(dāng)s高于相似度闋值t時(shí)則該鄰居結(jié)點(diǎn)為vi的鄰接相似結(jié)點(diǎn)，此時(shí)ni再將vi加入的消息按照興趣相似鏈向興趣簇內(nèi)其他結(jié)點(diǎn)傳播，同時(shí)ni將自己保存的興趣簇結(jié)點(diǎn)信息告知vi。

(2)結(jié)點(diǎn)離開(kāi)

結(jié)點(diǎn)離開(kāi)的處理比較簡(jiǎn)單，只要向該結(jié)點(diǎn)相似鄰接點(diǎn)發(fā)送離開(kāi)消息即可，在由相似鄰接點(diǎn)負(fù)責(zé)將此消息按照興趣相似鏈發(fā)送給簇內(nèi)其他結(jié)點(diǎn)。

(3)結(jié)點(diǎn)失效

在結(jié)點(diǎn)失效的情況下，該結(jié)點(diǎn)不能通過(guò)向相似鄰接點(diǎn)發(fā)送離開(kāi)消息來(lái)通知其他結(jié)點(diǎn)，為獲取結(jié)點(diǎn)失效情況，簇內(nèi)結(jié)點(diǎn)定期向相似鄰接點(diǎn)詢(xún)問(wèn)，如果結(jié)點(diǎn)在一定時(shí)間內(nèi)沒(méi)有答復(fù)，則認(rèn)為該結(jié)點(diǎn)失效，并將消息按照興趣相似鏈通告簇內(nèi)其他結(jié)點(diǎn)。

(4)結(jié)點(diǎn)行為改變

結(jié)點(diǎn)行為的改變主要指結(jié)點(diǎn)興趣度的改變。結(jié)點(diǎn)在初始加入時(shí)通過(guò)廣播向鄰居確認(rèn)相似度，根據(jù)鄰居結(jié)點(diǎn)返回的信息選擇一個(gè)或多個(gè)興趣簇加入。結(jié)點(diǎn)在以后的查詢(xún)過(guò)程中，可以根據(jù)查詢(xún)歷史記錄來(lái)決定加入與其興趣度更相似的興趣簇。如果要改變興趣簇，重復(fù)結(jié)點(diǎn)加入過(guò)程所做工作即可。

3.3 搜索算法

網(wǎng)絡(luò)內(nèi)任一結(jié)點(diǎn)在發(fā)起資源查詢(xún)請(qǐng)求時(shí)，首先查看結(jié)點(diǎn)所在簇內(nèi)其他結(jié)點(diǎn)是否能滿(mǎn)足查詢(xún)請(qǐng)求。簇內(nèi)查詢(xún)得不到滿(mǎn)足時(shí)，結(jié)點(diǎn)通過(guò)轉(zhuǎn)發(fā)結(jié)點(diǎn)向簇外結(jié)點(diǎn)發(fā)送資源請(qǐng)求消息。

(1)簇內(nèi)消息發(fā)送

網(wǎng)絡(luò)內(nèi)任一結(jié)點(diǎn)在發(fā)起資源查詢(xún)請(qǐng)求時(shí)，首先在結(jié)點(diǎn)所在簇內(nèi)進(jìn)行查找。雖然簇內(nèi)每個(gè)結(jié)點(diǎn)都有該簇的全局信息，但為了避免簇內(nèi)網(wǎng)絡(luò)帶寬消耗過(guò)大，本文采用從簇內(nèi)結(jié)點(diǎn)索引表中選擇與本結(jié)點(diǎn)相似度較高的前k個(gè)結(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，且初始查詢(xún)賦予的TTL值較小，這種方式可以有效避免簇內(nèi)消息數(shù)量。簇內(nèi)其他結(jié)點(diǎn)在收到查詢(xún)消息后，只轉(zhuǎn)發(fā)給本簇內(nèi)其他結(jié)點(diǎn)。

結(jié)點(diǎn)Node開(kāi)始查詢(xún)，所在簇B為內(nèi)找到資源的查找描述為

初始化Node.TTL

Query_In_Cluster(Node，Key，TTL)

Begin

If TTL<0 Then Return(沒(méi)有找到)

Else

If 在前k個(gè)相似度較高的結(jié)點(diǎn)集合SimK(Node)中找到資源 Then

Return(查找成功)

Else For each Nodei In SimK(Node) Do

Query_In_Cluster(Nodei，Key，TTL-1)

End

(2)簇間消息路由

如果資源查詢(xún)請(qǐng)求沒(méi)有在簇內(nèi)得到滿(mǎn)足，查詢(xún)消息就需要發(fā)送到簇外結(jié)點(diǎn)。簇間結(jié)點(diǎn)的消息路由可以看做是一個(gè)動(dòng)態(tài)環(huán)境下的目標(biāo)決策算法，目的是為了實(shí)現(xiàn)經(jīng)過(guò)最少的跳數(shù)實(shí)現(xiàn)消息從本簇到資源所在簇的路由。

在結(jié)點(diǎn)Node所在簇B內(nèi)沒(méi)有找到資源，開(kāi)始簇間資源查找的描述為：

初始化Node.TTL

Query_Between_Cluster(Node，Key，TTL)

Begin

If TTL<0 Then

Return(沒(méi)有找到)

Else

if在前k個(gè)相似度較高的結(jié)點(diǎn)集合SimK(Node)中找到資源Then

Return(查找成功)

Else if 所有鄰居都已訪問(wèn)過(guò) Then

SimK={隨機(jī)選擇的k個(gè)鄰居結(jié)點(diǎn)}

Else For each Nodei In SimK(Node) Do

Query_ Between_Cluster(Nodei，Key，TTL-1)

End

4 結(jié)論

由于網(wǎng)絡(luò)中的所有結(jié)點(diǎn)都具有一定的相似愛(ài)好和行為目的，如果兩個(gè)結(jié)點(diǎn)具有相似的興趣愛(ài)好，則他們之間有著很大的可能存在互連和資源交換。又由于網(wǎng)絡(luò)中度數(shù)較大的結(jié)點(diǎn)認(rèn)識(shí)更多的鄰居結(jié)點(diǎn)，所以它們具有比其他結(jié)點(diǎn)更高的概率連接到目標(biāo)結(jié)點(diǎn)。將網(wǎng)絡(luò)按照結(jié)點(diǎn)興趣度的不同劃分為不同的“簇”（Cluster），有相似興趣度的結(jié)點(diǎn)聚集在一起，形成興趣簇，結(jié)點(diǎn)的資源查找首先在簇內(nèi)進(jìn)行，由于簇內(nèi)結(jié)點(diǎn)的興趣度相似，資源發(fā)現(xiàn)的成功率將會(huì)大大增加，這種新的基于Flooding的資源發(fā)現(xiàn)機(jī)制，有效地減少了查詢(xún)消息的冗余發(fā)送，提高了資源發(fā)現(xiàn)的效率和成功率。

參考文獻(xiàn)：

[1] Manoj P，Anjana S，P2P Networking: An Information Sharing Alternative.IEEE Computing Practices， 2001，34(7):31-38.

[2] LV Q.Cao P.Cohen E.Search and replication in unstructured peer-to-peer networks.In:Proc. Of the 16th ACM Int'1 Conf. on Supercomputing(ICS 2002).2002.254-261.

[3] Adar E，Huberman B.Free Riding on Gnutella[J].First Monday，2000，5(10): 53-56.

[4] A Chander， S Dawson， P Lincoln， et al. NEVRLATE: Scalable resource discovery. In: Proc of the 2nd IEEE/ACM Int'l Symp on Cluster Computing and the Grid (CCGrid 2002).Los Alamitos，CA:IEEE Computer Society Press，2002.382-388.

[5] Chen Hao，Jin Hai，Sun Jianhua，et al.Analysis of larkge-scale topological properties for peer-to-peer networks.In: Pan Yi， ed. Proc of 4th IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGrid'04)[C].Los Angeles: IEEE Press，2004，27-34.

[6] JON K leinberg.The Small-World phenomenon: An algorithmic perspective. ACM Symp on Theory of Computing， 2000，28(4).820-828.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文