結(jié)構(gòu)化p2p網(wǎng)絡(luò)性能分析與搜索算法研究.pdf

1、近年來,對等網(wǎng)絡(luò)(P2P)日益成為Internet上的一個重要應(yīng)用。P2P網(wǎng)絡(luò)中的每個節(jié)點既是內(nèi)容提供者,又是內(nèi)容消費者。結(jié)構(gòu)化對等網(wǎng)絡(luò)是擴展性高、容錯性好的P2P網(wǎng)絡(luò),是當(dāng)前的研究熱點?；诜植际焦１淼慕Y(jié)構(gòu)化P2P網(wǎng)絡(luò)利用DHT進行資源定位,它將網(wǎng)絡(luò)中每個資源和節(jié)點哈希到同一個值空間,每個共享資源被發(fā)布到和自己資源標(biāo)識符最接近的節(jié)點上。這種定位機制雖然有效地解決了非結(jié)構(gòu)化對等網(wǎng)絡(luò)中洪泛機制所帶來的不可擴展問題,卻不可避免地帶來了另外

2、的一些問題。這些問題主要是:(1)由于節(jié)點的頻繁加入和離開所引起的路由表更新代價非常大;(2)哈希過程丟失了節(jié)點的物理位置信息,使得重疊網(wǎng)絡(luò)中的鄰居物理上可能相距很遠(yuǎn),從而使得結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的查找延遲增大;(3)在抖動率很高時,某些結(jié)構(gòu)化P2P網(wǎng)絡(luò)隨著網(wǎng)絡(luò)規(guī)模的擴大而性能急劇下降;(4)只支持從key到value的精確匹配,不支持多關(guān)鍵字搜索,搜索效率不高。
　　當(dāng)前,結(jié)構(gòu)化P2P網(wǎng)絡(luò)的研究主要集中在對現(xiàn)有的DHT協(xié)議的直接改

3、進上,很少通過對網(wǎng)絡(luò)的性能進行分析而提出改進方案。這種方法存在著兩個缺點,一是這種改進只針對某種DHT協(xié)議,如Tapestry,沒有普遍意義;二是容易造成顧此失彼,如常量度數(shù)的DHT算法雖然降低了查詢跳數(shù),但對于節(jié)點的異常離開的處理能力較差,容錯性能大大降低。為了更有效解決上述問題,有必要從路由表更新代價、查找延遲和抖動環(huán)境下的可擴展性等網(wǎng)絡(luò)性能指標(biāo)對典型結(jié)構(gòu)化P2P網(wǎng)絡(luò)的性能進行整體分析,進而提出改進算法和方案。從而提高結(jié)構(gòu)化P2P網(wǎng)

4、絡(luò)的整體性能。
　　為了找出影響網(wǎng)絡(luò)抖動的關(guān)鍵因素,首次提出了反向鄰居節(jié)點的概念,即把自己作為鄰居節(jié)點的節(jié)點,在此基礎(chǔ)上,計算了六種DHT網(wǎng)絡(luò)的反向鄰居節(jié)點數(shù)。分析了影響抖動的路由方式、鄰居選擇、節(jié)點加入和節(jié)點離開以及并行查找等策略因素。發(fā)現(xiàn)對任意兩種DHT網(wǎng)絡(luò),它們分別采用的五種策略都至少有兩種不同,于是,對兩種DHT網(wǎng)絡(luò)直接進行比較就很難確定哪些策略能更有效地降低抖動。因此,提出在同一網(wǎng)絡(luò)內(nèi),用不同的單個策略對網(wǎng)絡(luò)抖動進行比較

5、和分析的方法,稱之為CSP。對現(xiàn)有的Pastry算法進行改進,構(gòu)造了使用快速加入策略的F_Pastry算法和周期性恢復(fù)策略的P_Pastry算法。并分別把F_Pastry、P_Pastry和原有版本的慢速加入、反應(yīng)性恢復(fù)算法進行了比較。還把使用迭代路由的Chord協(xié)議和使用遞歸路由的Chord協(xié)議進行了比較,得出以下結(jié)論:迭代路由、快速加入和周期性恢復(fù)策略和有效的鄰居選擇算法能更有效地降低網(wǎng)絡(luò)的抖動。
　　研究發(fā)現(xiàn),數(shù)據(jù)存放機制、

6、路由方式、鄰居選擇和服務(wù)選擇方式等,是影響結(jié)構(gòu)化P2P網(wǎng)絡(luò)查找延遲的關(guān)鍵因素。通過對一些典型結(jié)構(gòu)化P2P網(wǎng)絡(luò)查找延遲的比較和分析,提出了降低內(nèi)容尋址網(wǎng)絡(luò)節(jié)點間延遲的DCAN算法。該算法將內(nèi)容尋址網(wǎng)絡(luò)中的節(jié)點抽象成一個無向帶權(quán)圖,在此基礎(chǔ)上,把Dijkstra算法求得的源節(jié)點到目的節(jié)點的最短路徑作為路由。仿真實驗表明,和路由過程中每次選擇最小的下一跳的算法相比,DCAN算法能更有效地降低從源節(jié)點到目的節(jié)點的總延遲。
　　為了研究抖動

7、環(huán)境下各種結(jié)構(gòu)化P2P網(wǎng)絡(luò)的可擴展性,提出了LBE評價方法。該方法把成功查找的時間延遲和查找失敗率隨網(wǎng)絡(luò)規(guī)模的變化作為衡量可擴展性好壞的標(biāo)準(zhǔn)。隨機改變DHT的各種參數(shù),得到一系列查找延遲時間,把它們形成的最低線作為網(wǎng)絡(luò)的整體性能指標(biāo)。固定某一參數(shù),但隨機改變其它參數(shù)再進行仿真,從而得到最佳網(wǎng)絡(luò)整體性能條件下的參數(shù)值。用上述方法對三種DHT協(xié)議的可擴展性進行了綜合分析,并得出了相應(yīng)的結(jié)論。
　　通過分析現(xiàn)有多關(guān)鍵字搜索算法的缺點,提

8、出了ICCCS搜索算法,該算法在DHT協(xié)議層之上建立邏輯的關(guān)鍵字搜索層,搜索層采用改進的超立方體互聯(lián)圈(Improved Cube-Connected Cycle)結(jié)構(gòu)。通過向量空間模型選擇每個對象的重要關(guān)鍵字,并將其映射到ICCC節(jié)點的環(huán)號,然后將描述對象的整個關(guān)鍵字集映射到ICCC節(jié)點的立方體標(biāo)號。基于反向文檔索引技術(shù)建立了索引算法,并使用生成樹建立了搜索算法。實驗結(jié)果表明,該算法對于關(guān)鍵字較少的查詢有較高的查找精度和較低的查找延遲