Chord算法改進現(xiàn)狀研究

胡秀源

摘要：P2P網(wǎng)絡中，chord搜索算法是一個研究熱點。對于經(jīng)典chord算法，研究者已經(jīng)從各自角度進行了改進，形成了多種改進chord算法，比如，MR-chord算法、nrtochord算法、多環(huán)的chord算法。該文從多個角度對改進chord算法進行匯總研究，期望能明確chord算法的各個改進方向。

關(guān)鍵詞：P2P；chord；對比分析

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）02-0325-02

1 chord算法概述

2001年，MIT提出了Chord算法，其核心思想就是要解決在P2P應用中遇到的基本問題——P2P網(wǎng)絡中的資源定位問題。該算法使用一致性哈希作為哈希算法。在一致性哈希協(xié)議中并沒有定義具體的算法，在Chord協(xié)議中將其規(guī)定為SHA-1。

2 現(xiàn)有chord改進算法簡介

經(jīng)典chord算法固然以實現(xiàn)簡便的優(yōu)勢，促進了當時的P2P網(wǎng)絡技術(shù)的發(fā)展。隨著P2P網(wǎng)絡進一步的發(fā)展，經(jīng)典chord算法也暴露出了一些不足。開發(fā)者從不同角度對經(jīng)典chord算法提出了改進。近期的chord算法改進文獻如下：

《基于DHT的Chord路由算法的研究與改進》[文獻1]首先介紹了chord算法的路由過程，并且闡述了該算法在新節(jié)點加入操作時帶來的查詢效率問題：新節(jié)點加入后比加入前，查詢多了一跳。這種情況在p2p網(wǎng)絡動態(tài)性極強的情況下，對效率的影響尤為突出。因此，文章提出對新加入節(jié)點的直接前驅(qū)節(jié)點的指取表進行部分擴充的辦法。

《一種改進的CHORD搜索算法》[文獻2]在原有chord算法路由表不變的基礎上，節(jié)點又增加了最近訪問節(jié)點表和鄰居節(jié)點表，每個節(jié)點都要維護三個表，增加了維護成本，但是，它卻讓資源搜索初，算法先在節(jié)點內(nèi)部的最近訪問節(jié)點表和鄰居節(jié)點表中搜索，以提高搜索效率，提供了客觀基礎。

《P2P網(wǎng)絡中Chord搜索算法的改進研究》[文獻3]提出根據(jù)信息相關(guān)度將網(wǎng)絡節(jié)點進行分組，形成多個二級環(huán)，并從中選出一個節(jié)點作為超級節(jié)點，每個二級環(huán)可以在本組內(nèi)自治。而把所有二級環(huán)的超級節(jié)點相互連接，形成一個超級組。當一個節(jié)點發(fā)出資源搜索請求時，算法先在節(jié)點所在環(huán)內(nèi)進行搜索。若找到相關(guān)節(jié)點，算法就此返回結(jié)果，并且停止；否則，算法向超級組內(nèi)發(fā)出資源搜索請求，繼續(xù)查找。

《基于多環(huán)的Chord改進算法》[文獻4]提出MR-chord算法，該算法提出多環(huán)和組相結(jié)合的結(jié)構(gòu)，組內(nèi)節(jié)點有本組其它節(jié)點的相關(guān)信息，組間通過遞歸算法連接成環(huán)。申請搜索資源的節(jié)點先在本組內(nèi)搜索（由于該節(jié)點有組內(nèi)所有其它節(jié)點的相關(guān)信息，因此，該搜索過程的時間復雜度為O（1）），當算法找不到所需資源時，將請求轉(zhuǎn)發(fā)出去。因此，該算法冗余較少。

《一種改進的Chord網(wǎng)絡模型》[文獻5]針對經(jīng)典chord模型中，節(jié)點路由表存在一定的信息冗余和所有節(jié)點周期性執(zhí)行stablize操作，印發(fā)大量消息轉(zhuǎn)發(fā)兩個缺陷，做了以下改進：采用動態(tài)雙向路由表；路由選擇方面，算法充分利用雙向路由表加速定位過程；節(jié)點加入和退出方面，算法充分利用雙向路由表，盡可能低免除周期性fix操作。通過算法改進，算法有效的減少了消息轉(zhuǎn)發(fā)次數(shù)，提高了路由效率。

《改進的chord加入算法》[文獻6]在chordfingerpns加入算法的基礎上，提出改進的chord加入算法：spjoin算法。該算法通過使用加入節(jié)點的后繼結(jié)點和后繼結(jié)點的前驅(qū)節(jié)點的信息，減少加入節(jié)點時構(gòu)造finger表需要查詢的跳數(shù)，已達到減少加入算法總開銷的效果。

《一種基于鄰居路由表的Chord改進算法》[文獻7]提出nrtochord算法，該算法中，每個節(jié)點不僅要維護一個本地的指針表，還要維護一張感知表，該表是節(jié)點通過信息互換機制，感知后繼結(jié)點的指針表得來的。加入節(jié)點時，新加入節(jié)點通過遠程過程調(diào)用其他節(jié)點的更新函數(shù)，更新其他節(jié)點的指針表，并從后繼結(jié)點獲取關(guān)鍵詞標示符。該算法要求每個節(jié)點的后繼節(jié)點信息都要有即時性。即保證后繼結(jié)點的真實、可靠性。

3 現(xiàn)有chord改進算法的分析研究

現(xiàn)有chord改進算法從不同角度對經(jīng)典chord算法進行改進。以實現(xiàn)chord算法在效率方面、信息維護方面更進一步。通過對現(xiàn)有chor改進算法進行比對分析，該文將現(xiàn)有chord算法進行如下分類：

1）類1：通過對維護信息的改進，提高chord算法在節(jié)點加入、退出方面的效率。

P2P網(wǎng)絡的動態(tài)性，導致了P2P網(wǎng)絡節(jié)點的在線時間的不固定性和節(jié)點加入的即時性。這種情況要求算法要盡可能的將新加入節(jié)點的信息加入到相關(guān)節(jié)點的finger table中去，將已經(jīng)離線節(jié)點的信息及時告知相關(guān)節(jié)點。這兩種操作都會引起chord算法效率下降，特別是大規(guī)模P2P網(wǎng)絡，這種情況更為嚴重。基于此，該分類以對維護信息的調(diào)整為契機，期望在節(jié)點加入、退出時，盡可能減少相應成本。該分類的文檔有：《基于DHT的Chord路由算法的研究與改進》、《一種基于鄰居路由表的Chord改進算法》和《改進的chord加入算法》。

2）類2：通過對維護信息的改進，提高chord算法在資源搜索方面的效率。

P2P網(wǎng)絡的規(guī)模具有可擴展性，其節(jié)點眾多，信息資源更是數(shù)不勝數(shù)。如何讓P2P網(wǎng)絡中的資源有序化，讓算法減少跳數(shù)。是該種分類的改進思路。比如，《一種改進的CHORD搜索算法》提出在節(jié)點原有finger table不變的基礎上，每個節(jié)點再增加兩張表：最近訪問節(jié)點表和鄰居節(jié)點表。資源搜索時，算法先從最近訪問節(jié)點表和鄰居節(jié)點表中進行搜索，搜索不到時，節(jié)點再進行資源搜索消息轉(zhuǎn)發(fā)。

該分類的文檔有：《一種改進的CHORD搜索算法》、《P2P網(wǎng)絡中Chord搜索算法的改進研究》、《基于多環(huán)的Chord改進算法》

3）類3：通過網(wǎng)絡模型的改進，提高消息轉(zhuǎn)發(fā)性能，減少查詢跳數(shù)，進而提高算法效率。

任何一個算法都以一定的網(wǎng)絡模型為基礎，網(wǎng)絡模型的優(yōu)化程度，直接影響到算法的效率。盡管經(jīng)典chord算法的網(wǎng)絡模型具有簡便和易于實現(xiàn)兩種特性。但是，該算法的模型仍有可進一步優(yōu)化的空間。于是，該分類從此下手，減少消息拒絕轉(zhuǎn)發(fā)次數(shù)，提高消轉(zhuǎn)發(fā)有效轉(zhuǎn)發(fā)次數(shù)。減少查詢跳數(shù)。以達到提高算法效率的目的。

該分類的文檔有：《一種改進的Chord網(wǎng)絡模型》、《G-Chord：一種基于Chord的路由改進算法》、《DM-Chord：基于Chord的路由改進算法》、《動態(tài)多路由Chord路由算法的研究與實現(xiàn)》、《基于Chord的結(jié)構(gòu)化P2P路由改進算法》

4 結(jié)束語

Chord算法是P2P網(wǎng)絡研究的一個核心問題。各種改進方法層出不窮。由于論文發(fā)表的滯后性、所掌握資料的局部性和研究人員的個人原因（比如，研究方法），chord算法改進現(xiàn)狀分類有一定的局限性。研究人員希望拋磚引玉，與大家交流彼此的認識。同時，研究人員也希望通過該文章，為以后的chord算法改進工作明確方向添一份力。

參考文獻：

[1] 張鐵強，舒小潤.基于DHT的Chord路由算法的研究與改進[J].電腦知識與技術(shù)，2009（29）：8153-8154.

[2] 李士寧，夏貽勇，倪紅波，等.一種改進的CHORD搜索算法[J].計算機工程與應用，2008（22）：139-142.

[3] 曹磊，張玉梅，吳曉軍，等.P2P網(wǎng)絡中Chord搜索算法的改進研究[J].計算機應用研究，2014.

[4] 李建軍，熊選東，譚曉貞.基于多環(huán)的Chord改進算法[J].計算機工程，2010（2）：116-118.

[5] 鄧杰文.一種改進的Chord網(wǎng)絡模型[J].計算機應用與軟件，2010（2）：247-248，260.

[6] 任小金，古志民.改進的Chord加入算法[J].計算機工程，2007（17）：123-124，130.

[7] 戴彬，王芙蓉，劉見.一種基于鄰居路由表的Chord改進算法[J].華中科技大學學報：自然科學版，2009（2）：49-52.

[8] 成培，胡峰松，粟智.基于Chord的結(jié)構(gòu)化P2P路由改進算法[J].計算機工程與設計，2009（1）：63-65.

[9] 郝黎明，陸松年，楊樹堂等.DM-Chord：基于Chord的路由改進算法[J].計算機工程，2009（1）：4-6.

[10] 何可佳.動態(tài)多路由Chord路由算法的研究與實現(xiàn)[J].微計算機信息，2009（30）：192-193，201.

[11] 陳剛，吳國新，楊望.G-Chord：一種基于Chord的路由改進算法[J].東南大學學報：自然科學版，2007（1）：9-12.