對等網(wǎng)絡(luò)路由算法研究.pdf

1、客戶/服務(wù)器計算模型(Client/Server：C/S)是現(xiàn)代互聯(lián)網(wǎng)的核心。結(jié)構(gòu)的簡練和高效使其成為Internet的主流，現(xiàn)有應(yīng)用也多以此為基礎(chǔ)。但在高速的下一代Internet平臺上，該模型面臨諸多問題與挑戰(zhàn)。其中，服務(wù)瓶頸問題尤為突出。分布式計算是有望解決服務(wù)瓶頸問題的候選技術(shù)之一。 在過去的幾年里，Napster和Gnutella這樣的文件共享軟件在Internet上迅速傳播，用戶數(shù)量急劇增長。在這樣的系統(tǒng)中，數(shù)據(jù)被保

2、存在用戶的計算機(jī)中(我們稱之為對等結(jié)點(diǎn)，Peer)，而不像以往的客戶/服務(wù)器模式那樣把數(shù)據(jù)存放在集中的服務(wù)器上。這種運(yùn)行于多個對等結(jié)點(diǎn)(Peer)之上的網(wǎng)絡(luò)被稱為對等網(wǎng)絡(luò)(P2P)。今天，P2P應(yīng)用的帶寬已經(jīng)超過萬維網(wǎng)，成為占用互聯(lián)網(wǎng)帶寬最多的部分。 在對等網(wǎng)絡(luò)中，數(shù)據(jù)在對等結(jié)點(diǎn)之間直接傳遞。隨著對等網(wǎng)絡(luò)規(guī)模的增長，數(shù)據(jù)的存儲和搜索成為迫切需要解決的問題，也成為了研究的熱點(diǎn)。從2001年開始，有關(guān)P2P的研究主要集中在結(jié)構(gòu)化覆蓋

3、網(wǎng)及分布式哈希表(DistributedHash Table，DHT)的理論研究。目前，單純的理論研究熱潮正漸漸轉(zhuǎn)向如何將這些P2P理論結(jié)合起來并應(yīng)用于實(shí)際系統(tǒng)當(dāng)中。其目標(biāo)是體現(xiàn)出P2P系統(tǒng)在可擴(kuò)展性和容錯能力等方面的優(yōu)勢。 目前，許多實(shí)際運(yùn)用的P2P搜索機(jī)制都提供與本地存儲無關(guān)的路由基礎(chǔ)結(jié)構(gòu)。其中幾種基于分布式哈希表的P2P機(jī)制已有較為廣泛的應(yīng)用。它們在具有許多優(yōu)點(diǎn)的同時，依然存在幾個重大問題，影響了實(shí)際使用效果。 首

4、先，P2P查找經(jīng)常受到覆蓋擴(kuò)張(overlay dilation)的影響。覆蓋擴(kuò)張是指與底層網(wǎng)絡(luò)最佳路由相關(guān)的，無必要的路徑長度的增加。忽略交換時間，這種反應(yīng)時間上的延遲與路徑長度的增加大致成比例。第二個與DHT相關(guān)的問題是，由于文件經(jīng)哈希函數(shù)處理后被隨機(jī)分散到不同位置，文件的所有者對文件的控制能力實(shí)際上是很弱的。文件的發(fā)布者或所有者不能決定哪些節(jié)點(diǎn)存儲哪些文件。DHT的另外一個問題是它難于處理復(fù)制(replica)問題。盡管現(xiàn)在提出了

5、幾種處理復(fù)制問題的方法，但都有其不足點(diǎn)。這種情況下，發(fā)布者實(shí)際上缺乏對文件的控制能力。 在P2P的發(fā)展過程中，文件共享系統(tǒng)始終是P2P研究的動力之源。這也促使我們盡量發(fā)掘更適合文件共享的數(shù)據(jù)結(jié)構(gòu)。Bloom filter對數(shù)據(jù)集合采用一個位串表示并能有效支持集合元素的哈希查找操作。早期用于數(shù)據(jù)庫，現(xiàn)在則更多的用于網(wǎng)絡(luò)應(yīng)用中。在路由和資源發(fā)現(xiàn)方面，基于Bloom filter的方法可以顯著地減少查找臨近文件的覆蓋延遲，但對較遠(yuǎn)的文

6、件影響較小。 本文描述了Bloom filter用于路由的基本思想；并提出了引入距離概念的改進(jìn)距離加權(quán)Bloom filter路由算法。該算法可以較為顯著地改善普通Bloom filter路由中路由失敗率較高、對不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)適應(yīng)性差的問題。 本文以分布式計算為理論基礎(chǔ)，以對等計算環(huán)境中的分布式路由算法為主攻對象，開展了基于距離加權(quán)Bloom filter的分布式路由算法的研究，內(nèi)容主要涉及基于距離加權(quán)Bloom fi

7、lter的分布式路由算法、該算法的數(shù)學(xué)分析，以及實(shí)驗(yàn)?zāi)Ｐ秃蜏y試手段等。研究工作取得了以下進(jìn)展： ●把距離的概念整合進(jìn)Bloom filter中，讓Bloom filter中的比特位表示距離以產(chǎn)生距離向量。一個距離加權(quán)Bloom filter(distance-weighted Bloom Filter,dwBF)是一串整數(shù)而不是標(biāo)準(zhǔn)Bloom filter里的一串比特位。采用距離加權(quán)Bloom filter路由方式?？梢栽诎l(fā)生誤

8、稱時形成一個路由更正機(jī)制，大大降低路由失敗率。 ●通過設(shè)置dwBF,解決了普通Bloom filter只能用于樹型拓?fù)渚W(wǎng)絡(luò)的問題。使得具有良好數(shù)據(jù)性能的Bloom filter能夠直接應(yīng)用于各種實(shí)際網(wǎng)絡(luò)而不是僅能依靠覆蓋網(wǎng)技術(shù)來進(jìn)行路由。 ●增強(qiáng)了文件發(fā)布者對文件的控制能力。在P2P網(wǎng)絡(luò)中，由于文件經(jīng)哈希函數(shù)處理后被隨機(jī)分散到不同位置，文件的所有者難以對文件的使用和傳播進(jìn)行控制。文件的發(fā)布者或所有者不能決定哪些節(jié)點(diǎn)存儲哪

9、些文件。我們通過在數(shù)據(jù)結(jié)構(gòu)里增加一些附加位，用以控制訪問權(quán)限。這樣，可以加強(qiáng)發(fā)布者對資源的控制。在處理侵權(quán)等方面非常有效。 ●解決了現(xiàn)有P2P系統(tǒng)難于處理復(fù)制(replica)的問題。目前，雖然有學(xué)者通過在指針節(jié)點(diǎn)增加多個指向復(fù)制服務(wù)器的指針的形式來解決復(fù)制問題，但是這需要一種在多個復(fù)制之間進(jìn)行選擇的機(jī)制。而且，尤為嚴(yán)重的是，指針節(jié)點(diǎn)有可能成為單點(diǎn)錯誤。通過dwBF算法獨(dú)立地設(shè)置每個復(fù)制的dwBF。路由過程能以較高概率選擇一個較