高階Chord：一種新型P2P查找策略.pdf

1、P2P提供無(wú)窮的存儲(chǔ)空間以及不受限制的傳輸容量，這是傳統(tǒng)中央服務(wù)器所無(wú)可企及的。P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)既是服務(wù)使用者，也是服務(wù)提供者。整個(gè)網(wǎng)絡(luò)應(yīng)用的核心從中央服務(wù)器向網(wǎng)絡(luò)邊緣的終端設(shè)備擴(kuò)散。目前因特網(wǎng)以網(wǎng)站為中心的狀態(tài)終將徹底改變，人們將會(huì)以更主動(dòng)的方式參與到網(wǎng)絡(luò)活動(dòng)中去。從C/S模式到P2P模式的發(fā)展，Internet上的共享行為被提升到了一個(gè)更高的層次。　　所有這些P2P應(yīng)用面臨的最核心問(wèn)題就是如何在沒(méi)有中心節(jié)點(diǎn)的情況下完成資源的查找

2、，并且能保證查找過(guò)程的高效性、可靠性、可伸縮性。目前很多研究都集中在基于DHT的方法上。利用DHT實(shí)現(xiàn)的查找算法比較多，比較知名的包括最早的Plaxton算法及其變種Tapstry，微軟提出的Pastry，伯克立和AT&T提出的CAN等等。特別是MIT提出的Chord算法在網(wǎng)絡(luò)節(jié)點(diǎn)變化劇烈的環(huán)境中仍然具有較好的性能。這一點(diǎn)非常重要，因?yàn)楝F(xiàn)實(shí)中P2P網(wǎng)絡(luò)的節(jié)點(diǎn)自治性必然導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)頻繁變動(dòng)。在這些惡劣條件下能保持較高的查詢(xún)效率才是最重要的

3、。　　本文在此基礎(chǔ)上提出Chord中“階”的概念。指出經(jīng)典Chord算法相當(dāng)于2階的Chord，并討論了一種更為一般化的資源查找策略：高階Chord。根據(jù)高階Chord的結(jié)構(gòu)我們可以構(gòu)造出階數(shù)大于2的任何階Chord。高階Chord將會(huì)使查詢(xún)請(qǐng)求更快地轉(zhuǎn)發(fā)到目標(biāo)節(jié)點(diǎn)。但是為此節(jié)點(diǎn)必須維護(hù)更大的路由表?？梢灶A(yù)見(jiàn)相比于減少轉(zhuǎn)發(fā)次數(shù)帶來(lái)的收益，維護(hù)路由表的代價(jià)是比較低的。因此可以通過(guò)高階Chord的算法為P2P網(wǎng)絡(luò)提供一種更為有效的查詢(xún)策略