DHT分布式搜索中Chord算法研究.pdf

1、P2P網絡因其突顯的非中心化、可擴展性、健壯性、高性價比、負載均衡、隱私保護等特點和其特殊的體系結構得以迅速發(fā)展和應用。結構化網絡采用分布式哈希表(DHT)技術，由查詢關鍵字key直接定位其在分布式系統(tǒng)中的儲存的節(jié)點位置，主要的應用有CAN、Tapestry、Pastry、Chord等，本文其中本文重點研究Chord算法。Chord是一種結構化搜索方式，通過分布式哈希表(DHT)技術，將查詢的關鍵字Key與節(jié)點標識(id)使用相容哈希[

2、1]散列在同一地址空間中。同時，Chord采用了路由(finger)表的查詢方式，使得每個節(jié)點在只需維護少量的節(jié)點信息的同時可以進行高效的查詢。Chord路由算法具有負載平衡、健壯性、可擴展性、可用性、命名的靈活性等五個方面的優(yōu)點，但其相應也存在節(jié)點的異構性導致的性能瓶頸、節(jié)點加入和離開帶來的低效、模糊查詢技術很難應用等缺點。
　　 Chord查詢算法的改進一般是通過改進路由表結構或改變路由查詢的方法，即是通過改善其路由表結構或

3、者修改其查詢算法。至目前，較為典型的對Chord協議的改進方法有F-Chord算法、PNS算法(Proximity neighborselection)、Vivaldi定位算法等。由于修改路由表結構的方法在降低平均查詢跳數與時間的同時通常增加了路由表長度，使得Chord在維護時占用更多的帶寬且改善效果并不理想。本文通過分析Chord在查詢過程中的路由特點，提出一種基于節(jié)點信息復制和查詢熱點的改進算法CH-Chord，即如果將節(jié)點的復制信

4、息儲存在其后繼節(jié)點的方法變?yōu)閮Υ嬖诠?jié)點的前驅節(jié)點中，在進行Chord查詢時，查詢仍然按照原本的方法進行，但只需查詢找到擁有查詢key對應的信息或復制信息的節(jié)點便完成查詢，同時再加入對查詢熱點的復制，并與并行查詢的方式相結合。通過這樣的改進，降低了查詢跳數與路由時間，減少了查詢失敗且沒有增加帶寬消耗的效果。
　　 論文最后使用仿真工具P2PSim對改進算法CH-Chord進行仿真實驗，并與傳統(tǒng)的Chord算法和改進路由表的F-Ch