DHT覆蓋網(wǎng)若干基礎(chǔ)性問題研究.pdf

1、分布式哈希表(DHT)是一種新的P2P網(wǎng)絡(luò)組網(wǎng)方式，具有高效、易擴(kuò)展、低成本等優(yōu)點(diǎn)，廣泛應(yīng)用于各種大規(guī)模分布式系統(tǒng)，如文件共享、內(nèi)容分發(fā)、流媒體、VoIP等。在這些系統(tǒng)中，由DHT形成的覆蓋網(wǎng)扮演著重要角色，支撐著上層各種應(yīng)用。因此，它引起了研究人員的廣泛關(guān)注，已成為當(dāng)前的研究熱點(diǎn)。 論文對DHT覆蓋網(wǎng)在應(yīng)用中亟待解決的一些基礎(chǔ)性問題進(jìn)行了深入的研究，從分析DHT網(wǎng)絡(luò)的基本模型入手，研究了DHT網(wǎng)絡(luò)的管理范圍(Zone)均衡問題

2、，深入探討了如何在DHT網(wǎng)絡(luò)中防御Sybil攻擊，并對網(wǎng)絡(luò)規(guī)模估計(jì)問題進(jìn)行了建模分析，提出了高效的隨機(jī)節(jié)點(diǎn)選擇算法。 論文的創(chuàng)新點(diǎn)及其貢獻(xiàn)在于： 1．研究了線段隨機(jī)分割問題，得出兩個基本結(jié)論：在Chord網(wǎng)絡(luò)中，節(jié)點(diǎn)間距近似服從指數(shù)分布，一段地址空間上出現(xiàn)的節(jié)點(diǎn)個數(shù)近似服從泊松分布。理論分析和仿真數(shù)據(jù)表明，這兩個結(jié)論的近似程度非常高，誤差很小。這兩個結(jié)論不僅適用于Chord網(wǎng)絡(luò)，還適用于所有滿足節(jié)點(diǎn)ID在網(wǎng)絡(luò)中均勻分布假

3、設(shè)的DHT網(wǎng)絡(luò)。它們是全文分析與建模工作的基礎(chǔ)。 2．提出基于靜態(tài)副本Zone均衡策略，推導(dǎo)出Chord和Pastry網(wǎng)絡(luò)、虛擬服務(wù)器(VS)和基于靜態(tài)副本的Zone均衡策略下節(jié)點(diǎn)的負(fù)載分布。分析表明：Chord、Pastry和VS的Zone負(fù)載分布服從參數(shù)形式相似的伽馬分布；在Chord網(wǎng)絡(luò)中k個后繼節(jié)點(diǎn)上放置副本，節(jié)點(diǎn)Zone負(fù)載服從參數(shù)為(k，n)的伽馬分布。與VS和基于平衡樹的Zone均衡策略相比，基于靜態(tài)副本的均衡策略

4、除了使節(jié)點(diǎn)Zone負(fù)載均衡外，還具有使系統(tǒng)更魯棒的優(yōu)勢。 3．提出一種ID自檢驗(yàn)的安全框架(ISV)，并結(jié)合洗牌策略高效抵御Sybil攻擊(ICS)。ISV引入顯式證書分發(fā)服務(wù)器(CD)對ID申請進(jìn)行審計(jì)，分發(fā)節(jié)點(diǎn)簽名；而身份驗(yàn)證工作由節(jié)點(diǎn)根據(jù)簽名自行完成；有效降低了CD服務(wù)器的開銷。ICS利用CD簽發(fā)的票據(jù)記錄節(jié)點(diǎn)加入過程，保證三輪替換規(guī)則強(qiáng)制實(shí)施；利用票據(jù)的替換區(qū)間和發(fā)布時戳來判定ID是否過期，防止敵手積累ID。論文對節(jié)點(diǎn)需

5、要保存的票據(jù)數(shù)量進(jìn)行了定量分析，得出問題的近似閉合解；理論分析表明平均每個節(jié)點(diǎn)上保存的票據(jù)數(shù)是O(log2，n)；仿真數(shù)據(jù)表明，該近似解具有很高的精度，說明了理論分析的正確性。 4．指出在DHT網(wǎng)絡(luò)中估計(jì)網(wǎng)絡(luò)規(guī)模等同于指數(shù)分布或泊松分布的參數(shù)估計(jì)問題，提出基于平均間距(AIE)和基于節(jié)點(diǎn)密度(NDE)兩種網(wǎng)絡(luò)規(guī)模估計(jì)算法。論文推導(dǎo)出AIE和NDE算法中網(wǎng)絡(luò)規(guī)模估計(jì)值的概率分布，討論了如何選擇NDE測量范圍和測量位置等問題。分析表

6、明：AIE的測量精度只與測量間距個數(shù)相關(guān)，與網(wǎng)絡(luò)規(guī)模本身無關(guān)，具有自適應(yīng)網(wǎng)絡(luò)規(guī)模變化的特點(diǎn)。仿真實(shí)驗(yàn)證明AIE算法的測量誤差完全符合理論分析結(jié)果。 5．提出一種基于取舍原則的DHT網(wǎng)絡(luò)隨機(jī)節(jié)點(diǎn)抽樣算法(RPS)，分析了單點(diǎn)啟發(fā)式算法(HUR)和多點(diǎn)啟發(fā)式算法(HURk)的抽樣概率以及抽樣間距的概率分布，構(gòu)造了一種服從倒數(shù)分布的取舍算法(RDRP)。分析表明：RPS以等概率抽樣在線節(jié)點(diǎn)，抽樣間距服從指數(shù)分布；RPS的時間復(fù)雜度與網(wǎng)