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

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

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

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

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

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

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

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