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

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

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

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

4、息儲(chǔ)存在其后繼節(jié)點(diǎn)的方法變?yōu)閮?chǔ)存在節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)中，在進(jìn)行Chord查詢時(shí)，查詢?nèi)匀话凑赵镜姆椒ㄟM(jìn)行，但只需查詢找到擁有查詢key對(duì)應(yīng)的信息或復(fù)制信息的節(jié)點(diǎn)便完成查詢，同時(shí)再加入對(duì)查詢熱點(diǎn)的復(fù)制，并與并行查詢的方式相結(jié)合。通過(guò)這樣的改進(jìn)，降低了查詢跳數(shù)與路由時(shí)間，減少了查詢失敗且沒(méi)有增加帶寬消耗的效果。
　　 論文最后使用仿真工具P2PSim對(duì)改進(jìn)算法CH-Chord進(jìn)行仿真實(shí)驗(yàn)，并與傳統(tǒng)的Chord算法和改進(jìn)路由表的F-Ch