ISSN 1009 3044E-mail: xic@cce.net.cnComputer Knowledge and Technology電腦知識(shí)與技術(shù)htp://ww.nzs.net.nVol.7, No.32, November 2011.Tel:+86- -551- 56909635690964優(yōu)化型Kademlia的設(shè)計(jì)研究王震(遼東學(xué)院信息技術(shù)學(xué)院,遼寧丹東1800)0摘要:通過對(duì)DHT路由算法中的Kademlia技術(shù)的系統(tǒng)分析,提出了一種基于P2P覆蓋網(wǎng)絡(luò)的優(yōu)化Kademlia路由算法的架構(gòu)。針對(duì)于DHT的構(gòu)造和路由方法的改進(jìn),從整體角度出發(fā),提出了優(yōu)化型Kademlia的路由算法,它的實(shí)現(xiàn)是建立在Kademlia核心路由的基礎(chǔ)上。在設(shè)計(jì)中,分別在Planetim、路由層服務(wù)層、應(yīng)用層等不同的網(wǎng)絡(luò)環(huán)境中利用節(jié)點(diǎn)的異構(gòu)性進(jìn)行設(shè)計(jì),采用新的技術(shù)對(duì)路由進(jìn)行改進(jìn),以更好的實(shí)現(xiàn)路由層的負(fù)載均衢以及在很高的網(wǎng)絡(luò)波動(dòng)條件下提高DTH性能。關(guān)鍵詞:DHT;Kademlia;路由算法;節(jié)點(diǎn);P2P中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009 3042011)32-7932-03The Design of Optimized KademliaWANG Zhen(The Information Technology Insticute, Liaodong Universiy, Dandong 118003, China)Abstract: By the Kademlia DHT routing algorithm technology systems analyis, This paper proposes an routing algorithm opimizationfnamework based on Kadenlia P2P overlay network .For improvement in the DHT structure and routing methods , fom the overll per-spective, This paper proposes opimized Kademlia rouing alorithm, is implemcnation is based on the Kademlia routing baced on the core.In the design, respectively, in PlanetSim, routing layer, servicc layer, pplication layer, using dfferent network nodes in heterogeneous envi-ronment of the design, the use of new technologies to improve the rouing. the routing layer to achieve better load balancing and fluctua-tions in conditions of high network performance to improve DTH.Key words: DHT; Kademli; rouing algorithm; node; P2PDHT(分布式哈希表)是- -種分布式存儲(chǔ)方法,在不需要服務(wù)器的情況下.每個(gè)客戶端負(fù)責(zé)-個(gè)小范圍的路由,并負(fù)責(zé)存儲(chǔ)- -小部分?jǐn)?shù)據(jù),從而實(shí)現(xiàn)整個(gè)DHT網(wǎng)絡(luò)的尋址和存儲(chǔ)。Kademlia 是DHT中的主流技術(shù)之- - ,在結(jié)構(gòu)化P2P系統(tǒng)有著廣泛的應(yīng)用。DHT實(shí)際上是- -個(gè)由廣域范圍.大量節(jié)點(diǎn)共同維護(hù)的巨大散列表。散列表被分割成不連續(xù)的塊,每個(gè)節(jié)點(diǎn)被分配給一個(gè)屬于自己的散列塊,并成為這個(gè)散列塊的管理者。DHT的節(jié)點(diǎn)既是動(dòng)態(tài)的，節(jié)點(diǎn)數(shù)量也是巨大的,因此非中心化和自組織成為兩個(gè)設(shè)計(jì)的重要目標(biāo)。由于重疊網(wǎng)絡(luò)采用了確定性拓?fù)浣Y(jié)構(gòu),DHT可以提供精確的發(fā)現(xiàn)。只要目標(biāo)節(jié)點(diǎn)存在于網(wǎng)絡(luò)中,DHT總能發(fā)現(xiàn)它,而且發(fā)現(xiàn)的準(zhǔn)確性得到了保證。DHT的的主流系統(tǒng)有Kademlie Pasty Tapesty、Chord.CAN等。1 DHT算法與Kademlia技術(shù)的分析DHT類結(jié)構(gòu)最大的問題是DHT的維護(hù)機(jī)制較為復(fù)雜.尤其是節(jié)點(diǎn)頰繁加人.退出造成的CHURN會(huì)極大增加DHT的維護(hù)代價(jià)以及不能吻合節(jié)點(diǎn)的異質(zhì)性要求。DHT的主流技術(shù)在路由查找效率、負(fù)載均衡和CHURN這3個(gè)方面也都有不同表現(xiàn)。任何分布式路由算法的目的都是為了能夠得到更快的路由以及在相同時(shí)間內(nèi)更有效的對(duì)未知的P2P網(wǎng)絡(luò)進(jìn)行管理。目前一些較流行的DHT例如Chord.CAN .Pasty .Tapesty和Kademlia以及-些其它的DHT或多或少存在以下一些缺點(diǎn):1)它們都假定P2P網(wǎng)絡(luò)中的所有節(jié)點(diǎn)擁有相同的帶寬和其它的資源,沒有考慮到P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的高度異構(gòu)性這個(gè)性質(zhì)。2)- -些協(xié)議由于在設(shè)計(jì)的時(shí)候就沒有考慮到P2P網(wǎng)絡(luò)中CHURN較差的情況,結(jié)果就是它們不能很好的處理CHURN問題。3)負(fù)載均衡在路由層并沒有被很好的實(shí)現(xiàn)，在改進(jìn)的算法中將通過多種有效的方法解決節(jié)點(diǎn)超載的問題,這些有效的手段包括考慮節(jié)點(diǎn)的異質(zhì)性對(duì)節(jié)點(diǎn)進(jìn)行分類,對(duì)類型不同的節(jié)點(diǎn)分別進(jìn)行節(jié)點(diǎn)ID的均勻分布以及虛擬服務(wù)器技術(shù)。本論文的工作重點(diǎn)就是通過分析上述DHT的構(gòu)造和路由方法以及上述提出的問題來構(gòu)造一-個(gè)新的 DHT路由算法。2優(yōu)化型Kademlia的設(shè)計(jì)為了解決CHURN向題,需要設(shè)計(jì)-個(gè)可以應(yīng)用于任何KBR層路由協(xié)議上的-一個(gè)通用DHT框架解決方案,這就要對(duì)Kadenlia進(jìn)行優(yōu)化設(shè)計(jì),進(jìn)而達(dá)到在CHURN為90%左右的時(shí)候查找成功率將大于95%,查找偏差小于5%。2.2體系架構(gòu)2.2.1 PlanetSim整個(gè)P2P系統(tǒng)的體系架構(gòu)來源于PlanetSim,在PlaneSim中,開發(fā)者可以工作在覆蓋層中進(jìn)行創(chuàng)造和測(cè)試邏輯算法或者創(chuàng)建和測(cè)試新的服務(wù)。PlaneSim 的架構(gòu)為三層的層次結(jié)構(gòu),應(yīng)用層在最上層建立在路由服務(wù)上,該路由服務(wù)由下層的路由層提供,可以在中國(guó)煤化工YHCNMHG收稿日期:2011-09 -27作者簡(jiǎn)介:王震(1972-),男,遼寧人,刪教授,碩士,多年主要從事計(jì)算機(jī)及軟件開發(fā)的教學(xué)、科研工作。7932電 軟件計(jì)計(jì)開資.......本欄目責(zé)任編輯:謝嬡媛第7卷第32期(2011年11月)Computer Knowledge and Technology電腦知識(shí)與技術(shù)應(yīng)用層直接開發(fā)應(yīng)用程序。PlanetSim 的架構(gòu)如圖1所示。Nitra [ [PAST]↑ 的n新算法將在路由層里的覆蓋網(wǎng)(Overlay)中進(jìn)行設(shè)計(jì),最終對(duì)上層提供統(tǒng)一的Comnon API",在服務(wù)層中通過調(diào)用下層提供的DOLRC接口來實(shí)現(xiàn)優(yōu)化的Kademlia路由算法,通過PlaneSim模擬網(wǎng)絡(luò)環(huán)境對(duì)新的算法進(jìn)行測(cè)試。2.2.2路由層NverlayBR層對(duì)所有的結(jié)構(gòu)化網(wǎng)絡(luò)提供相同的基本性能,該層管理仿真蒂ProtooLond Blnmoing麟(EntioeP2P系統(tǒng)中路由所有相關(guān)的功能。該層劃分為兩個(gè)子層,分別是底層網(wǎng)絡(luò)(Network)子層和覆蓋網(wǎng)(Overlay)子層。覆蓋網(wǎng)層有3個(gè)Hotiwork .模塊:圖1 PlanetSim 的體系架構(gòu)1)ID Managemento它負(fù)責(zé)處理節(jié)點(diǎn)ID的分配，它使P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)在ID空間中都能均勻的分布,這有助于KBR層和高層的負(fù)載均衡。2)Routing Protocolo負(fù)責(zé)P2P的路由,優(yōu)化的Kademlia將在這里工作。3)Load Balancing Engine。在查找過程中一些節(jié) 點(diǎn)比其它一些節(jié)點(diǎn)所負(fù)擔(dān)的工作量要多的多,該模塊負(fù)責(zé)對(duì)這些節(jié)點(diǎn)進(jìn)行負(fù)載均衡。2.2.3服務(wù)層.表1 Service 層接口該層處于應(yīng)用和路由層的中間,為不同的應(yīng)用DHTCAST提供可重用的上層服務(wù),例如DHT、DOLR和put(key, data)publishobjectId)join(groupId)CAST。這些服務(wù)使用路由層提供的Common API接口。該層也為上層的應(yīng)用層提供自己的一系列接remove(key)unpubli sh (objeetId)leave(groupId)口,該層的接口"如表1。valuezget (key)sendToObj (msg, objeted, [n]) Mlulti/anyeast (asg, groupId2.2.4應(yīng)用層.該層由-些應(yīng)用組成.例如VoD.CFS、PAST和Scribe等,這些應(yīng)用使用下兩層提供的服務(wù)。大多數(shù)應(yīng)用使用服務(wù)層提供的服務(wù),只有一些很少的系統(tǒng)應(yīng)用直接調(diào)用KBR的服務(wù)。2.3采用的新技術(shù)2.3.1節(jié)點(diǎn)分類在該P(yáng)2P系統(tǒng)中按照節(jié)點(diǎn)的能力將它們劃分為普通對(duì)等節(jié)點(diǎn)和超級(jí)對(duì)等節(jié)點(diǎn)和巨型對(duì)等節(jié)點(diǎn)。通過考慮影響-一個(gè)對(duì)等節(jié)點(diǎn)的各種參數(shù)來計(jì)算該節(jié)點(diǎn)的異構(gòu)因素標(biāo)準(zhǔn)(H1)。用B當(dāng)作節(jié)點(diǎn)的可用帶寬,T為節(jié)點(diǎn)在網(wǎng)絡(luò)中的運(yùn)行時(shí)間比率,C作為CPU的性能,M為節(jié)點(diǎn)內(nèi)存的大小,S為各種路由表儲(chǔ)存容量,那么對(duì)等節(jié)點(diǎn)的HF以參數(shù)B, T, C, M的函數(shù)如下:H, =func(B,T.C,M,S)在公式(1)中,參數(shù)B、T和S在計(jì)算中占有重要的成分,因?yàn)锽是Internet中節(jié)點(diǎn)主要關(guān)心的問題,T則代表了對(duì)等節(jié)點(diǎn)的穩(wěn)定度，S表現(xiàn)一個(gè)節(jié)點(diǎn)的存儲(chǔ)容量。在這里可以忽略參數(shù)C和M帶來的影響,那么公式()可以簡(jiǎn)化為:H, =func(B,T,S)(2)按照公式(2),每個(gè)節(jié)點(diǎn)都要維持不同大小的路由表.其中帶寬.運(yùn)行時(shí)間和存儲(chǔ)容量越大的節(jié)點(diǎn)其路由表的大小也就越大。在計(jì)算HF的時(shí)候,我們將P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)按照普通節(jié)點(diǎn)、超級(jí)節(jié)點(diǎn)和巨型節(jié)點(diǎn)進(jìn)行分別計(jì)算。2.3.2超級(jí)對(duì)等節(jié)點(diǎn)和巨型對(duì)等節(jié)點(diǎn)超級(jí)節(jié)點(diǎn)和巨型節(jié)點(diǎn)就是網(wǎng)絡(luò)中那些可以利用更多資源擁有更強(qiáng)大性能的節(jié)點(diǎn),二者基本的不同點(diǎn)在于巨型節(jié)點(diǎn)由P2P網(wǎng)絡(luò)運(yùn)營(yíng)者或管理者所提供，并且在P2P網(wǎng)絡(luò)中巨型節(jié)點(diǎn)擁有更高的運(yùn)行時(shí)間和性能"。巨型節(jié)點(diǎn)的存儲(chǔ)容量和超級(jí)節(jié)點(diǎn)相似，在當(dāng)前的仿真中利用巨型節(jié)點(diǎn)的主要目的是用來實(shí)現(xiàn)負(fù)載均衡。2.3.3節(jié)點(diǎn)分布通常較多的P2P系統(tǒng)采用根據(jù)節(jié)點(diǎn)的IP地址和端口來產(chǎn)生節(jié)點(diǎn)ID或用隨機(jī)數(shù)來產(chǎn)生”。這就使當(dāng)P2P網(wǎng)絡(luò)中節(jié)點(diǎn)增多的時(shí)候節(jié)點(diǎn)ID分布并不均勻,最終導(dǎo)致某個(gè)ID空間中少數(shù)節(jié)點(diǎn)有很高的負(fù)載(查找熱區(qū)或者查找失敗"?？紤]到這點(diǎn),論文中將采用一一個(gè)較實(shí)用的方法,將節(jié)點(diǎn)的分布分為兩層,超級(jí)節(jié)點(diǎn)層和普通節(jié)點(diǎn)層。每個(gè)節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)首先檢測(cè)自己的性能.根據(jù)該性能來決定加入到哪一-層。 這種ID分配策略可以使ID平均的分布。2.3.4對(duì)路由的改進(jìn)對(duì)原有協(xié)議里的路由機(jī)制進(jìn)行改進(jìn),新的路由機(jī)制將減少節(jié)點(diǎn)對(duì)帶寬的占用并提供較高的CHURN彈性,改進(jìn)包括以下幾點(diǎn):1)并行遞歸查找。2)在查找中學(xué)習(xí),對(duì)查找狀態(tài)進(jìn)行動(dòng)態(tài)的更新。查找狀態(tài)可以從MCNL和RHNL中獲得。3)基于先驗(yàn)式反應(yīng)式移除路由表中失效的表項(xiàng)。4)采用從LPT和BT中選擇親近的節(jié)點(diǎn)的技術(shù)間。(注:LPT和 BT為不同5)對(duì)LPT中XOR距離接近的節(jié)點(diǎn)進(jìn)行相關(guān)的路由維護(hù)。中國(guó)煤化工6)最大化節(jié)點(diǎn)間相互交換維護(hù)信息的容量”。TYRCNMHG2.3.5節(jié)點(diǎn)異構(gòu)性在本系統(tǒng)設(shè)計(jì)中,節(jié)點(diǎn)根據(jù)自己性能的大小來決定可以維護(hù)信息的多少,維護(hù)的信息包括兩個(gè)方面:BT .LPT和PT所占的大小;本欄目責(zé)任編輯:謝媛媛w...:軟件設(shè)計(jì)開發(fā): 7933Computer Knowedge and Technology電脯匆識(shí)與技術(shù)第7卷第32期(2011年 11月)節(jié)點(diǎn)在查找時(shí)如果負(fù)載過大,節(jié)點(diǎn)將丟棄剩余的消息來保證自己的查找性能"。這條因素在模擬器中并沒有考慮,僅停留在理論研究階段。2.3.6 路由層的負(fù)載均衡設(shè)計(jì)該技術(shù)的目的就是避免某個(gè)節(jié)點(diǎn)在它的ID空間中查找工作量超過它所能承受的范圍.如果僅僅采用上節(jié)所采用的一旦超過負(fù)載能力就丟棄消息的做法,那么整個(gè)P2P網(wǎng)絡(luò)的質(zhì)量將會(huì)下降并且查找失敗率將上升。通過實(shí)現(xiàn)KBR層的負(fù)載均衡機(jī)制可以解決這個(gè)問題,該機(jī)制的實(shí)現(xiàn)就是在KBR層通過定位超載節(jié)點(diǎn)并且讓這些超載節(jié)點(diǎn)加入ID空間附近的一些節(jié)點(diǎn)中,這樣就可以實(shí)現(xiàn)局部的負(fù)載平衡。該機(jī)制可以通過共享負(fù)載來減低節(jié)點(diǎn)的負(fù)載,并且可以改善網(wǎng)絡(luò)波動(dòng)下的網(wǎng)絡(luò)性能"。3結(jié)論本論文在分析DHT的構(gòu)造和路由方法基礎(chǔ)上來構(gòu)造- -個(gè)新的DHT路由算法,系統(tǒng)設(shè)計(jì)的目標(biāo)是采用新的技術(shù)對(duì)路由進(jìn)行改進(jìn)實(shí)現(xiàn)路由層的負(fù)載均衡。通過將優(yōu)化的Kademlia網(wǎng)絡(luò)協(xié)議的引人構(gòu)架了通用DHT框架解決方案.就可以得到更快的路由以及在相同時(shí)間內(nèi)更有效的對(duì)未知的P2P網(wǎng)絡(luò)進(jìn)行管理。通常的P2P網(wǎng)絡(luò)在一一個(gè)較穩(wěn)定的網(wǎng)絡(luò)中總能表現(xiàn)出良好的性能,當(dāng)網(wǎng)絡(luò)中CHURN率較高時(shí)這些協(xié)議的性能明顯的降低,如何在高CHURN下設(shè)計(jì)- -個(gè)性能好的DHT算法是個(gè)具有挑戰(zhàn)性的工作。在本論文中主要的工作重點(diǎn)放在如何在CHURN率-一直偏高的情況下,算法仍舊表現(xiàn)出高性能,最終的結(jié)果也基本達(dá)到了預(yù)先的設(shè)想。參考文獻(xiàn):[1] Dabek F.Zhao B,Druschel PetalTowards a common API for structured peer-to peer overaycsC.B.rele.Calfiri.Prc. IPTPS 2003,2003.[2]聶秀英IP網(wǎng)絡(luò)內(nèi)容分發(fā)技術(shù)[.電信科學(xué)20(1):36-38.[3]雷葆華,楊明川.P2P技術(shù)的組網(wǎng)模式與業(yè)務(wù)探討J]電信技術(shù)2011):23 -27.[4] Tian Ruixiong,Xiong Yongqiang,Zhang Qian,et al.Hybrid Overlay Structure Based on Random walks[Z4l.[5] Castro M,Druschel P,Hu Y C,et al.Rowstron.expiting Network Proximity in Peer-to-Peer Overlay Network[R],Camvridge,UKTechnicalReport MSR-TR 2002-82, Microsoft Research,2002[6] Dobuzhskaya M,Liu R,Roewe J,et al,Zebr: Peer To Peer Multicast for live Streaming Video[C].MIT,2004.[7] Portmann M,Ardon S,Senae P,et al.PEOST: A programmable structured peer-to-peer overlay network[CV/Zurich SwitzerLand:Proceed-ings of the Fourth IEEE Intermational Conference on Peer To Peer Computing,2004.[8] Ledlie J.Selzer M.Distributed, Secure Load Balancign with Skew, Heterogeneity, and Churn[R]Harvard Technical Report TR- -31-04,2004.[9] Kenthapadi K,Manku G S.Decentralized algoithms using both local and random probes for P2P load balancing[CV/Proc. 17th ACM Sym-posium on Parallel Algorithms and Architectures(SPAA '05),2005.(上接第7931頁)5自動(dòng)化測(cè)試結(jié)果用Robot工具來錄制和回放測(cè)試用例腳本的執(zhí)行速度至少是人工操作的3倍以上執(zhí)行結(jié)果可以在操作日志中查詢,這樣就能更好的驗(yàn)證整個(gè)用例設(shè)計(jì)的合理性。當(dāng)測(cè)試過程中需要大批量執(zhí)行某些測(cè)試項(xiàng)時(shí),其執(zhí)行速度和效率的優(yōu)勢(shì)更是人工所不能比擬的,充分體現(xiàn)了自動(dòng)化測(cè)試的特點(diǎn)。特別適用于回歸測(cè)試，目前在BSS系統(tǒng)測(cè)試中已得到了初步的應(yīng)用。6需解決的問題在系統(tǒng)不夠穩(wěn)定的情況下,經(jīng)常會(huì)由于一個(gè)未錄制界面的異常出現(xiàn)或-個(gè)已錄制界面的長(zhǎng)期不出現(xiàn).而使整個(gè)BOROT腳本無法運(yùn)行。而且由于現(xiàn)場(chǎng)環(huán)境的復(fù)雜性,有時(shí)無法用設(shè)置Robot驗(yàn)證點(diǎn)的方法來判斷站點(diǎn)初始化或系統(tǒng)運(yùn)行的正確性,而只能用人力來觀察,這樣就使Robot腳本執(zhí)行自動(dòng)化程度大大降低了。7結(jié)束語Rational Robot是伴隨著軟件測(cè)試技術(shù)發(fā)展起來的自動(dòng)化測(cè)試工具,是進(jìn)行現(xiàn)代軟件測(cè)試的有效手段。本文根據(jù)Rationl Robot的特點(diǎn)著重講述了它的測(cè)試過程以及測(cè)試腳本的運(yùn)用,為今后軟件測(cè)試工作提供了更加靈活、充分的方法。[1] 曹薇.軟件測(cè)試M].北京:清華大學(xué)出版社,2008.中國(guó)煤化工[1] Esentials of Functional Testing with Rational Robot User's Manual[Z_2003..MYHCNMHG7934蛹 軟件設(shè)計(jì)開發(fā)=mm==.--本欄目責(zé)任編輯:謝媛媛