優(yōu)化型Kademlia的設計研究

ISSN 1009 3044E-mail: xic@cce.net.cnComputer Knowledge and Technology電腦知識與技術(shù)htp://ww.nzs.net.nVol.7, No.32, November 2011.Tel:+86- -551- 56909635690964優(yōu)化型Kademlia的設計研究王震(遼東學(xué)院信息技術(shù)學(xué)院,遼寧丹東1800)0摘要:通過(guò)對DHT路由算法中的Kademlia技術(shù)的系統分析,提出了一種基于P2P覆蓋網(wǎng)絡(luò )的優(yōu)化Kademlia路由算法的架構。針對于DHT的構造和路由方法的改進(jìn),從整體角度出發(fā),提出了優(yōu)化型Kademlia的路由算法,它的實(shí)現是建立在Kademlia核心路由的基礎上。在設計中,分別在Planetim、路由層服務(wù)層、應用層等不同的網(wǎng)絡(luò )環(huán)境中利用節點(diǎn)的異構性進(jìn)行設計,采用新的技術(shù)對路由進(jìn)行改進(jìn),以更好的實(shí)現路由層的負載均衢以及在很高的網(wǎng)絡(luò )波動(dòng)條件下提高DTH性能。關(guān)鍵詞:DHT;Kademlia;路由算法;節點(diǎn);P2P中圖分類(lèi)號:TP311文獻標識碼:A 文章編號: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(分布式哈希表)是- -種分布式存儲方法,在不需要服務(wù)器的情況下.每個(gè)客戶(hù)端負責-個(gè)小范圍的路由,并負責存儲- -小部分數據,從而實(shí)現整個(gè)DHT網(wǎng)絡(luò )的尋址和存儲。Kademlia 是DHT中的主流技術(shù)之- - ,在結構化P2P系統有著(zhù)廣泛的應用。DHT實(shí)際上是- -個(gè)由廣域范圍.大量節點(diǎn)共同維護的巨大散列表。散列表被分割成不連續的塊,每個(gè)節點(diǎn)被分配給一個(gè)屬于自己的散列塊,并成為這個(gè)散列塊的管理者。DHT的節點(diǎn)既是動(dòng)態(tài)的，節點(diǎn)數量也是巨大的,因此非中心化和自組織成為兩個(gè)設計的重要目標。由于重疊網(wǎng)絡(luò )采用了確定性拓撲結構,DHT可以提供精確的發(fā)現。只要目標節點(diǎn)存在于網(wǎng)絡(luò )中,DHT總能發(fā)現它,而且發(fā)現的準確性得到了保證。DHT的的主流系統有Kademlie Pasty Tapesty、Chord.CAN等。1 DHT算法與Kademlia技術(shù)的分析DHT類(lèi)結構最大的問(wèn)題是DHT的維護機制較為復雜.尤其是節點(diǎn)頰繁加人.退出造成的CHURN會(huì )極大增加DHT的維護代價(jià)以及不能吻合節點(diǎn)的異質(zhì)性要求。DHT的主流技術(shù)在路由查找效率、負載均衡和CHURN這3個(gè)方面也都有不同表現。任何分布式路由算法的目的都是為了能夠得到更快的路由以及在相同時(shí)間內更有效的對未知的P2P網(wǎng)絡(luò )進(jìn)行管理。目前一些較流行的DHT例如Chord.CAN .Pasty .Tapesty和Kademlia以及-些其它的DHT或多或少存在以下一些缺點(diǎn):1)它們都假定P2P網(wǎng)絡(luò )中的所有節點(diǎn)擁有相同的帶寬和其它的資源,沒(méi)有考慮到P2P網(wǎng)絡(luò )中節點(diǎn)的高度異構性這個(gè)性質(zhì)。2)- -些協(xié)議由于在設計的時(shí)候就沒(méi)有考慮到P2P網(wǎng)絡(luò )中CHURN較差的情況,結果就是它們不能很好的處理CHURN問(wèn)題。3)負載均衡在路由層并沒(méi)有被很好的實(shí)現，在改進(jìn)的算法中將通過(guò)多種有效的方法解決節點(diǎn)超載的問(wèn)題,這些有效的手段包括考慮節點(diǎn)的異質(zhì)性對節點(diǎn)進(jìn)行分類(lèi),對類(lèi)型不同的節點(diǎn)分別進(jìn)行節點(diǎn)ID的均勻分布以及虛擬服務(wù)器技術(shù)。本論文的工作重點(diǎn)就是通過(guò)分析上述DHT的構造和路由方法以及上述提出的問(wèn)題來(lái)構造一-個(gè)新的 DHT路由算法。2優(yōu)化型Kademlia的設計為了解決CHURN向題,需要設計-個(gè)可以應用于任何KBR層路由協(xié)議上的-一個(gè)通用DHT框架解決方案,這就要對Kadenlia進(jìn)行優(yōu)化設計,進(jìn)而達到在CHURN為90%左右的時(shí)候查找成功率將大于95%,查找偏差小于5%。2.2體系架構2.2.1 PlanetSim整個(gè)P2P系統的體系架構來(lái)源于PlanetSim,在PlaneSim中,開(kāi)發(fā)者可以工作在覆蓋層中進(jìn)行創(chuàng )造和測試邏輯算法或者創(chuàng )建和測試新的服務(wù)。PlaneSim 的架構為三層的層次結構,應用層在最上層建立在路由服務(wù)上,該路由服務(wù)由下層的路由層提供,可以在中國煤化工YHCNMHG收稿日期:2011-09 -27作者簡(jiǎn)介:王震(1972-),男,遼寧人,刪教授,碩士,多年主要從事計算機及軟件開(kāi)發(fā)的教學(xué)、科研工作。7932電 軟件計計開(kāi)資.......本欄目責任編輯:謝嬡媛第7卷第32期(2011年11月)Computer Knowledge and Technology電腦知識與技術(shù)應用層直接開(kāi)發(fā)應用程序。PlanetSim 的架構如圖1所示。Nitra [ [PAST]↑ 的n新算法將在路由層里的覆蓋網(wǎng)(Overlay)中進(jìn)行設計,最終對上層提供統一的Comnon API",在服務(wù)層中通過(guò)調用下層提供的DOLRC接口來(lái)實(shí)現優(yōu)化的Kademlia路由算法,通過(guò)PlaneSim模擬網(wǎng)絡(luò )環(huán)境對新的算法進(jìn)行測試。2.2.2路由層NverlayBR層對所有的結構化網(wǎng)絡(luò )提供相同的基本性能,該層管理仿真蒂ProtooLond Blnmoing麟(EntioeP2P系統中路由所有相關(guān)的功能。該層劃分為兩個(gè)子層,分別是底層網(wǎng)絡(luò )(Network)子層和覆蓋網(wǎng)(Overlay)子層。覆蓋網(wǎng)層有3個(gè)Hotiwork .模塊:圖1 PlanetSim 的體系架構1)ID Managemento它負責處理節點(diǎn)ID的分配，它使P2P網(wǎng)絡(luò )中的節點(diǎn)在ID空間中都能均勻的分布,這有助于KBR層和高層的負載均衡。2)Routing Protocolo負責P2P的路由,優(yōu)化的Kademlia將在這里工作。3)Load Balancing Engine。在查找過(guò)程中一些節 點(diǎn)比其它一些節點(diǎn)所負擔的工作量要多的多,該模塊負責對這些節點(diǎn)進(jìn)行負載均衡。2.2.3服務(wù)層.表1 Service 層接口該層處于應用和路由層的中間,為不同的應用DHTCAST提供可重用的上層服務(wù),例如DHT、DOLR和put(key, data)publishobjectId)join(groupId)CAST。這些服務(wù)使用路由層提供的Common API接口。該層也為上層的應用層提供自己的一系列接remove(key)unpubli sh (objeetId)leave(groupId)口,該層的接口"如表1。valuezget (key)sendToObj (msg, objeted, [n]) Mlulti/anyeast (asg, groupId2.2.4應用層.該層由-些應用組成.例如VoD.CFS、PAST和Scribe等,這些應用使用下兩層提供的服務(wù)。大多數應用使用服務(wù)層提供的服務(wù),只有一些很少的系統應用直接調用KBR的服務(wù)。2.3采用的新技術(shù)2.3.1節點(diǎn)分類(lèi)在該P2P系統中按照節點(diǎn)的能力將它們劃分為普通對等節點(diǎn)和超級對等節點(diǎn)和巨型對等節點(diǎn)。通過(guò)考慮影響-一個(gè)對等節點(diǎn)的各種參數來(lái)計算該節點(diǎn)的異構因素標準(H1)。用B當作節點(diǎn)的可用帶寬,T為節點(diǎn)在網(wǎng)絡(luò )中的運行時(shí)間比率,C作為CPU的性能,M為節點(diǎn)內存的大小,S為各種路由表儲存容量,那么對等節點(diǎn)的HF以參數B, T, C, M的函數如下:H, =func(B,T.C,M,S)在公式(1)中,參數B、T和S在計算中占有重要的成分,因為B是Internet中節點(diǎn)主要關(guān)心的問(wèn)題,T則代表了對等節點(diǎn)的穩定度，S表現一個(gè)節點(diǎn)的存儲容量。在這里可以忽略參數C和M帶來(lái)的影響,那么公式()可以簡(jiǎn)化為:H, =func(B,T,S)(2)按照公式(2),每個(gè)節點(diǎn)都要維持不同大小的路由表.其中帶寬.運行時(shí)間和存儲容量越大的節點(diǎn)其路由表的大小也就越大。在計算HF的時(shí)候,我們將P2P網(wǎng)絡(luò )中的節點(diǎn)按照普通節點(diǎn)、超級節點(diǎn)和巨型節點(diǎn)進(jìn)行分別計算。2.3.2超級對等節點(diǎn)和巨型對等節點(diǎn)超級節點(diǎn)和巨型節點(diǎn)就是網(wǎng)絡(luò )中那些可以利用更多資源擁有更強大性能的節點(diǎn),二者基本的不同點(diǎn)在于巨型節點(diǎn)由P2P網(wǎng)絡(luò )運營(yíng)者或管理者所提供，并且在P2P網(wǎng)絡(luò )中巨型節點(diǎn)擁有更高的運行時(shí)間和性能"。巨型節點(diǎn)的存儲容量和超級節點(diǎn)相似，在當前的仿真中利用巨型節點(diǎn)的主要目的是用來(lái)實(shí)現負載均衡。2.3.3節點(diǎn)分布通常較多的P2P系統采用根據節點(diǎn)的IP地址和端口來(lái)產(chǎn)生節點(diǎn)ID或用隨機數來(lái)產(chǎn)生”。這就使當P2P網(wǎng)絡(luò )中節點(diǎn)增多的時(shí)候節點(diǎn)ID分布并不均勻,最終導致某個(gè)ID空間中少數節點(diǎn)有很高的負載(查找熱區或者查找失敗"?？紤]到這點(diǎn),論文中將采用一一個(gè)較實(shí)用的方法,將節點(diǎn)的分布分為兩層,超級節點(diǎn)層和普通節點(diǎn)層。每個(gè)節點(diǎn)加入網(wǎng)絡(luò )時(shí)首先檢測自己的性能.根據該性能來(lái)決定加入到哪一-層。 這種ID分配策略可以使ID平均的分布。2.3.4對路由的改進(jìn)對原有協(xié)議里的路由機制進(jìn)行改進(jìn),新的路由機制將減少節點(diǎn)對帶寬的占用并提供較高的CHURN彈性,改進(jìn)包括以下幾點(diǎn):1)并行遞歸查找。2)在查找中學(xué)習,對查找狀態(tài)進(jìn)行動(dòng)態(tài)的更新。查找狀態(tài)可以從MCNL和RHNL中獲得。3)基于先驗式反應式移除路由表中失效的表項。4)采用從LPT和BT中選擇親近的節點(diǎn)的技術(shù)間。(注:LPT和 BT為不同5)對LPT中XOR距離接近的節點(diǎn)進(jìn)行相關(guān)的路由維護。中國煤化工6)最大化節點(diǎn)間相互交換維護信息的容量”。TYRCNMHG2.3.5節點(diǎn)異構性在本系統設計中,節點(diǎn)根據自己性能的大小來(lái)決定可以維護信息的多少,維護的信息包括兩個(gè)方面:BT .LPT和PT所占的大小;本欄目責任編輯:謝媛媛w...:軟件設計開(kāi)發(fā): 7933Computer Knowedge and Technology電脯匆識與技術(shù)第7卷第32期(2011年 11月)節點(diǎn)在查找時(shí)如果負載過(guò)大,節點(diǎn)將丟棄剩余的消息來(lái)保證自己的查找性能"。這條因素在模擬器中并沒(méi)有考慮,僅停留在理論研究階段。2.3.6 路由層的負載均衡設計該技術(shù)的目的就是避免某個(gè)節點(diǎn)在它的ID空間中查找工作量超過(guò)它所能承受的范圍.如果僅僅采用上節所采用的一旦超過(guò)負載能力就丟棄消息的做法,那么整個(gè)P2P網(wǎng)絡(luò )的質(zhì)量將會(huì )下降并且查找失敗率將上升。通過(guò)實(shí)現KBR層的負載均衡機制可以解決這個(gè)問(wèn)題,該機制的實(shí)現就是在KBR層通過(guò)定位超載節點(diǎn)并且讓這些超載節點(diǎn)加入ID空間附近的一些節點(diǎn)中,這樣就可以實(shí)現局部的負載平衡。該機制可以通過(guò)共享負載來(lái)減低節點(diǎn)的負載,并且可以改善網(wǎng)絡(luò )波動(dòng)下的網(wǎng)絡(luò )性能"。3結論本論文在分析DHT的構造和路由方法基礎上來(lái)構造- -個(gè)新的DHT路由算法,系統設計的目標是采用新的技術(shù)對路由進(jìn)行改進(jìn)實(shí)現路由層的負載均衡。通過(guò)將優(yōu)化的Kademlia網(wǎng)絡(luò )協(xié)議的引人構架了通用DHT框架解決方案.就可以得到更快的路由以及在相同時(shí)間內更有效的對未知的P2P網(wǎng)絡(luò )進(jìn)行管理。通常的P2P網(wǎng)絡(luò )在一一個(gè)較穩定的網(wǎng)絡(luò )中總能表現出良好的性能,當網(wǎng)絡(luò )中CHURN率較高時(shí)這些協(xié)議的性能明顯的降低,如何在高CHURN下設計- -個(gè)性能好的DHT算法是個(gè)具有挑戰性的工作。在本論文中主要的工作重點(diǎn)放在如何在CHURN率-一直偏高的情況下,算法仍舊表現出高性能,最終的結果也基本達到了預先的設想。參考文獻:[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ò )內容分發(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頁(yè))5自動(dòng)化測試結果用Robot工具來(lái)錄制和回放測試用例腳本的執行速度至少是人工操作的3倍以上執行結果可以在操作日志中查詢(xún),這樣就能更好的驗證整個(gè)用例設計的合理性。當測試過(guò)程中需要大批量執行某些測試項時(shí),其執行速度和效率的優(yōu)勢更是人工所不能比擬的,充分體現了自動(dòng)化測試的特點(diǎn)。特別適用于回歸測試，目前在BSS系統測試中已得到了初步的應用。6需解決的問(wèn)題在系統不夠穩定的情況下,經(jīng)常會(huì )由于一個(gè)未錄制界面的異常出現或-個(gè)已錄制界面的長(cháng)期不出現.而使整個(gè)BOROT腳本無(wú)法運行。而且由于現場(chǎng)環(huán)境的復雜性,有時(shí)無(wú)法用設置Robot驗證點(diǎn)的方法來(lái)判斷站點(diǎn)初始化或系統運行的正確性,而只能用人力來(lái)觀(guān)察,這樣就使Robot腳本執行自動(dòng)化程度大大降低了。7結束語(yǔ)Rational Robot是伴隨著(zhù)軟件測試技術(shù)發(fā)展起來(lái)的自動(dòng)化測試工具,是進(jìn)行現代軟件測試的有效手段。本文根據Rationl Robot的特點(diǎn)著(zhù)重講述了它的測試過(guò)程以及測試腳本的運用,為今后軟件測試工作提供了更加靈活、充分的方法。[1] 曹薇.軟件測試M].北京:清華大學(xué)出版社,2008.中國煤化工[1] Esentials of Functional Testing with Rational Robot User's Manual[Z_2003..MYHCNMHG7934蛹 軟件設計開(kāi)發(fā)=mm==.--本欄目責任編輯:謝媛媛