基于P2P系統(tǒng)的分布式查詢算法的研究.pdf

1、對(duì)等網(wǎng)絡(luò)是一種資源分布利用與共享的網(wǎng)絡(luò)體系架構(gòu)，與目前網(wǎng)絡(luò)中占據(jù)主導(dǎo)地位的客戶機(jī)/服務(wù)器體系架構(gòu)相對(duì)應(yīng)?；赪eb應(yīng)用，使C/S結(jié)構(gòu)獲得巨大成功。但在這種體系架構(gòu)下，網(wǎng)絡(luò)的能力和資源全部集中在中央Server，它們成為網(wǎng)絡(luò)開放和能力擴(kuò)展的瓶頸。與C/S網(wǎng)絡(luò)架構(gòu)相反，P2P的網(wǎng)絡(luò)架構(gòu)在進(jìn)行媒體通信時(shí)不存在中心節(jié)點(diǎn)，節(jié)點(diǎn)之間是對(duì)等的，即每一個(gè)節(jié)點(diǎn)可以進(jìn)行對(duì)等的通信，各節(jié)點(diǎn)同時(shí)具有媒體內(nèi)容的接收、存儲(chǔ)、發(fā)送和集成及其對(duì)媒體元數(shù)據(jù)（Metada

2、ta）的搜索和被搜索功能等。這種網(wǎng)絡(luò)架構(gòu)所帶來的優(yōu)點(diǎn)使P2P網(wǎng)絡(luò)各節(jié)點(diǎn)的能力和資源可以共享；理論上說，網(wǎng)絡(luò)的能力和資源是P2P各節(jié)點(diǎn)的總和。在P2P體系架構(gòu)中，內(nèi)容不再集中在網(wǎng)絡(luò)的中央Server，而是分布在靠近用戶的網(wǎng)絡(luò)邊緣的各P2P節(jié)點(diǎn)上。P2P技術(shù)的應(yīng)用使得業(yè)務(wù)系統(tǒng)從集中向分布演化，特別是服務(wù)器的分布化，克服了業(yè)務(wù)節(jié)點(diǎn)集中造成的瓶頸，大大降低系統(tǒng)的建設(shè)和使用成本，提高網(wǎng)絡(luò)及系統(tǒng)設(shè)備的利用率。在典型的P2P網(wǎng)絡(luò)中，數(shù)據(jù)資源分布在各個(gè)

3、獨(dú)立的節(jié)點(diǎn)上，如何高效地索引、查找、定位以及訪問這些數(shù)據(jù)信息資源是一個(gè)重要問題。最新的成果都是基于DHT（Distributed Hash Table）的分布式查找和路由算法，DHT在應(yīng)用層上把所有的P2P節(jié)點(diǎn)組織成一個(gè)結(jié)構(gòu)化的重疊網(wǎng)絡(luò)，文件索引分布其中，查詢報(bào)文將通過這個(gè)重疊網(wǎng)絡(luò)路由。DHT通過分布式哈希函數(shù)，將輸入的關(guān)鍵字唯一映射到重疊網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)上，然后通過某些路由算法同該節(jié)點(diǎn)建立連接。典型的這一類P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型有CA

4、N、Chord、Pastry、Tapestry等。本文結(jié)合P2P網(wǎng)絡(luò)的新特點(diǎn)和資源定位的特點(diǎn)，圍繞DHT尋路效率的改善，提出了優(yōu)化的方案，并對(duì)該方案進(jìn)行了性能分析。通過分析闡明了這些方案能有效地改善現(xiàn)有DHT尋路效率。主要研究工作如下： ⑴提出雙向路由結(jié)構(gòu)的Chord環(huán)。在基于DHT的Chord的路由表中，只存在順時(shí)針的路由信息，尋路只能沿順時(shí)針進(jìn)行，但當(dāng)目的節(jié)點(diǎn)落在從當(dāng)前節(jié)點(diǎn)開始的沿順時(shí)針方向的后半環(huán)時(shí)，逆時(shí)針查找所經(jīng)過的跳數(shù)

5、可能會(huì)比順時(shí)針查找的跳數(shù)少，尋路時(shí)延也會(huì)降低。為此提出在節(jié)點(diǎn)的路由表中增加逆時(shí)針路由，使查找可以在兩個(gè)方向上選擇一個(gè)相對(duì)好的路由跳轉(zhuǎn)，即跳到離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)，這樣可以減少查找的邏輯跳數(shù)，縮短尋路時(shí)間，提高查詢效率。 ⑵提出基于B+樹的分布式哈希表路由結(jié)構(gòu)。B+樹結(jié)構(gòu)是一種有序的平衡的多叉樹，可以通過B+樹為P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)標(biāo)識(shí)符建立樹型索引，以實(shí)現(xiàn)范圍查找。這種結(jié)構(gòu)組織的節(jié)點(diǎn)標(biāo)識(shí)符索引在進(jìn)行關(guān)鍵字查找時(shí)，通過索引可以將查找

6、范圍縮小到很小的區(qū)域，使得查找更為快速有效，查詢的跳數(shù)減少，并能夠使查找長(zhǎng)度控制在B+樹的高度內(nèi)。 ⑶提出基于IPv6的層次化路由結(jié)構(gòu)。由于IPv6地址的結(jié)構(gòu)具有層次性和聚集性，可以利用IPv6的層次化地址分配來做到路由聚集，以解決基于DHT的P2P系統(tǒng)中重疊網(wǎng)絡(luò)和物理網(wǎng)絡(luò)脫節(jié)的問題。網(wǎng)絡(luò)中的尋路時(shí)延主要是域間的時(shí)延，而域內(nèi)的時(shí)延相對(duì)較小，因此若想減少查詢時(shí)間，就必須減少域間的跳數(shù)。網(wǎng)絡(luò)中的節(jié)點(diǎn)使用IPv6地址，通過對(duì)IP地址的

7、不同部分分別進(jìn)行哈希函數(shù)運(yùn)算，構(gòu)造分層次的節(jié)點(diǎn)標(biāo)識(shí)符，使得處于相同子域內(nèi)或互為近鄰的節(jié)點(diǎn)在重疊網(wǎng)絡(luò)中也能夠彼此鄰近，這樣邏輯網(wǎng)絡(luò)與物理網(wǎng)絡(luò)更加匹配，域間跳數(shù)減少，查詢效率提高。 ⑷提出一種基于Chord的P2P數(shù)據(jù)庫模型。通過以上對(duì)DHT的三點(diǎn)改進(jìn)，在基于Chord的重疊網(wǎng)絡(luò)上構(gòu)建了一種P2P系統(tǒng)的數(shù)據(jù)庫模型--本地關(guān)系數(shù)據(jù)庫模型LRM，旨在解決客戶機(jī)/服務(wù)器方式的分布式數(shù)據(jù)庫系統(tǒng)存在的瓶頸節(jié)點(diǎn)，以及為保持節(jié)點(diǎn)間的數(shù)據(jù)一致性而增