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

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

2、存在用戶的計(jì)算機(jī)中(我們稱之為對(duì)等結(jié)點(diǎn)，Peer)，而不像以往的客戶/服務(wù)器模式那樣把數(shù)據(jù)存放在集中的服務(wù)器上。這種運(yùn)行于多個(gè)對(duì)等結(jié)點(diǎn)(Peer)之上的網(wǎng)絡(luò)被稱為對(duì)等網(wǎng)絡(luò)(P2P)。今天，P2P應(yīng)用的帶寬已經(jīng)超過萬維網(wǎng)，成為占用互聯(lián)網(wǎng)帶寬最多的部分。 在對(duì)等網(wǎng)絡(luò)中，數(shù)據(jù)在對(duì)等結(jié)點(diǎn)之間直接傳遞。隨著對(duì)等網(wǎng)絡(luò)規(guī)模的增長(zhǎng)，數(shù)據(jù)的存儲(chǔ)和搜索成為迫切需要解決的問題，也成為了研究的熱點(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ò)展性和容錯(cuò)能力等方面的優(yōu)勢(shì)。 目前，許多實(shí)際運(yùn)用的P2P搜索機(jī)制都提供與本地存儲(chǔ)無關(guān)的路由基礎(chǔ)結(jié)構(gòu)。其中幾種基于分布式哈希表的P2P機(jī)制已有較為廣泛的應(yīng)用。它們?cè)诰哂性S多優(yōu)點(diǎn)的同時(shí)，依然存在幾個(gè)重大問題，影響了實(shí)際使用效果。 首

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

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

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

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

8、稱時(shí)形成一個(gè)路由更正機(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ā)布者對(duì)文件的控制能力。在P2P網(wǎng)絡(luò)中，由于文件經(jīng)哈希函數(shù)處理后被隨機(jī)分散到不同位置，文件的所有者難以對(duì)文件的使用和傳播進(jìn)行控制。文件的發(fā)布者或所有者不能決定哪些節(jié)點(diǎn)存儲(chǔ)哪

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