結構化對等網(wǎng)絡的搜索機制研究.pdf

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

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

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

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