結(jié)構(gòu)化對等網(wǎng)絡(luò)的搜索機(jī)制研究.pdf

1、對等網(wǎng)絡(luò)(PeertoPeer,P2P)的出現(xiàn)是對傳統(tǒng)C/S網(wǎng)絡(luò)架構(gòu)的一次進(jìn)化。由于P2P中的每個節(jié)點(diǎn)都能存儲和共享數(shù)據(jù),隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)展,基于P2P架構(gòu)的系統(tǒng)所擁有的數(shù)據(jù)量迅速擴(kuò)大,信息資源非常豐富。因此,如何有效地獲取有用信息,即如何有效地進(jìn)行路由資源搜索,成為P2P系統(tǒng)能否大規(guī)模應(yīng)用的關(guān)鍵問題之一。所以,P2P資源搜索定位機(jī)制成為目前的研究熱點(diǎn),當(dāng)前的研究主要集中在如何提高查詢效率、負(fù)載平衡及可擴(kuò)展性等方面。
　　 除了

2、采用中央目錄服務(wù)器的集中式對等網(wǎng)絡(luò)外,從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上看,對等網(wǎng)絡(luò)大致可分為無結(jié)構(gòu)對等網(wǎng)絡(luò)和基于分布式哈希表(DHT)的結(jié)構(gòu)化對等網(wǎng)絡(luò)。無結(jié)構(gòu)對等網(wǎng)絡(luò)采用類似Flooding的盲目搜索機(jī)制,以Gnutella為代表,雖然可以支持靈活查詢,但搜索效率及可擴(kuò)展性都比較低,DHT方法的可擴(kuò)展性和查詢效率都比較高。利用DHT實(shí)現(xiàn)的算法比較多,比較知名的包括最早的Plaxton算法及其變種Tapestry,微軟提出的Pastry,伯克立等提出的C

3、AN,MIT提出的Chord等等。Chord是一種環(huán)形拓?fù)涞慕Y(jié)構(gòu)化對等網(wǎng)絡(luò)結(jié)構(gòu),因其結(jié)構(gòu)簡潔,具有可擴(kuò)展性而被廣泛應(yīng)用。
　　 本文在對經(jīng)典的Chord算法深入分析的基礎(chǔ)上,通過擴(kuò)展Chord的路由表,提出了四階雙向Chord算法,此算法主要在以下兩個方面對Chord進(jìn)行改進(jìn):
　　 (1)增加Chord原路由表的指針密度,即把Chord的Finger表由2階變?yōu)?階,這樣增加了每個節(jié)點(diǎn)維護(hù)的路由表的長度,使得每個節(jié)點(diǎn)指

4、向的后繼節(jié)點(diǎn)個數(shù)增加,增大了找到目標(biāo)節(jié)點(diǎn)的概率。
　　 (2)變Chord的單向查找為雙向查找,即在Finger表的基礎(chǔ)上增加一個R_Finger表,R_Finger表實(shí)際上是Finger表的一個反轉(zhuǎn),是一個逆向的路由表,這樣Chord在選擇下一跳的節(jié)點(diǎn)的時候就有順時針和逆時針兩個方向,使得查找能更快地接近目標(biāo)節(jié)點(diǎn)。
　　 此算法結(jié)合了四階Chord和雙向Chord的優(yōu)點(diǎn),使得系統(tǒng)的查找策略可以根據(jù)關(guān)鍵字在Chord環(huán)上