一種異構(gòu)網(wǎng)絡(luò)中的高效路由P2P覆蓋網(wǎng)的設(shè)計(jì)

程志強(qiáng)

(武漢船舶職業(yè)技術(shù)學(xué)院實(shí)訓(xùn)中心,湖北武漢 430050)

目前的P2P覆蓋網(wǎng)設(shè)計(jì)需要著力解決如下的問(wèn)題,如節(jié)點(diǎn)加入、退出造成網(wǎng)絡(luò)不穩(wěn)定,節(jié)點(diǎn)負(fù)載不均衡造成網(wǎng)絡(luò)運(yùn)行效率低下,覆蓋網(wǎng)與物理網(wǎng)拓?fù)洳黄ヅ涠a(chǎn)生冗余消息流量。針對(duì)這些問(wèn)題,P2P覆蓋網(wǎng)設(shè)計(jì)廣泛采用了層次化方法,從眾多節(jié)點(diǎn)中選擇若干能力較強(qiáng)的超級(jí)節(jié)點(diǎn)(SP),負(fù)責(zé)服務(wù)索引維護(hù)和路由,以提高查詢(xún)效率。在SP節(jié)點(diǎn)的選擇策略上,有基于網(wǎng)絡(luò)拓?fù)鋄1,2]、基于節(jié)點(diǎn)興趣[3]、基于節(jié)點(diǎn)能力[4,5]、及基于網(wǎng)絡(luò)運(yùn)行代價(jià)[6]的多種策略;在SP數(shù)目的選擇上,分別有基于節(jié)點(diǎn)能力[7]和基于節(jié)點(diǎn)負(fù)載[8]的選取策略。以上提出的層次化覆蓋網(wǎng)能顯著改善系統(tǒng)的服務(wù)性能,但不足之處在于其中SP的負(fù)載均衡程度不一[8],容易產(chǎn)生系統(tǒng)的性能“瓶頸”,難以同時(shí)承擔(dān)服務(wù)索引維護(hù)與消息路由的繁重任務(wù),且在層次化結(jié)構(gòu)設(shè)計(jì)過(guò)程中未考慮底層物理拓?fù)涫欠衲芎透采w網(wǎng)的查詢(xún)路徑盡可能一致,一條查詢(xún)消息可能通過(guò)一條鏈路或一個(gè)節(jié)點(diǎn)多次,造成不必要的開(kāi)銷(xiāo)。本文針對(duì)節(jié)點(diǎn)度數(shù)冪率分布的異構(gòu)網(wǎng)絡(luò)中的SP負(fù)載不均衡與網(wǎng)絡(luò)拓?fù)洳黄ヅ溥@兩個(gè)問(wèn)題,在不同的SP上分離了路由和服務(wù)索引維護(hù)功能,實(shí)現(xiàn)了覆蓋網(wǎng)結(jié)構(gòu)與查詢(xún)消息路由的優(yōu)化。

1 系統(tǒng)的體系結(jié)構(gòu)

1.1 覆蓋網(wǎng)層次化設(shè)計(jì)

覆蓋網(wǎng)包括三層:路由層、服務(wù)層、節(jié)點(diǎn)層,如圖1所示。頂層為路由層,由穩(wěn)定、高性能的節(jié)點(diǎn)(記為SuSP)構(gòu)成,占節(jié)點(diǎn)總數(shù)的比例很小,形成一個(gè)很穩(wěn)定的Chord環(huán),起路由樞紐作用,每個(gè)SuSP負(fù)責(zé)維護(hù)一個(gè)由鄰近的普通節(jié)點(diǎn)構(gòu)成的簇(Cluster),并針對(duì)路由層建立路由表,不維護(hù)服務(wù)索引。中間層為服務(wù)層,由較穩(wěn)定、性能較強(qiáng)的節(jié)點(diǎn)(記為OrSP)構(gòu)成,每個(gè)OrSP選擇并被綁定到最近的一個(gè)SuSP,負(fù)責(zé)維護(hù)一定數(shù)目的服務(wù)索引,及一個(gè)由鄰近的普通節(jié)點(diǎn)構(gòu)成的簇,每個(gè)SuSP綁定多個(gè)物理鄰近的OrSP,每個(gè)OrSP從其綁定的SuSP中獲取路由表,并維護(hù)記錄著1跳距離內(nèi)的所有SuSP信息的表(SuSPList),用以不經(jīng)過(guò)路由層的Chord快速找到目標(biāo)SuSP。底層為節(jié)點(diǎn)層,由普通節(jié)點(diǎn)構(gòu)成,記為CP,每個(gè)CP連接到一個(gè)鄰近的作為其簇首的SuSP或Or-SP,借助其進(jìn)行快速的服務(wù)查詢(xún)。

1.2 超級(jí)節(jié)點(diǎn)的選擇

假設(shè)節(jié)點(diǎn)的能力強(qiáng)弱、穩(wěn)定性高低與度數(shù)大小是一致的,設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù) N,SP包括SuSP和 OrSP,數(shù)目為 NSP,占總節(jié)點(diǎn)比例設(shè)為 αSP,αSP=NSP/N,SP最低度數(shù)Ksv也為OrSP的最低度數(shù),基于復(fù)雜網(wǎng)絡(luò)理論,節(jié)點(diǎn)的度分布可以表述為累積分布函數(shù)[9]:P(K)=CK1-γ,且在連通圖中所有節(jié)點(diǎn)的度都不小于1:P(1)=1,因此可以認(rèn)為 C=1,有 αSP=P(Ksv)=Ksv1-γ,規(guī)定 γ為常數(shù),得 Ksv表示為

圖1 覆蓋網(wǎng)體系結(jié)構(gòu)

設(shè)SuSP總數(shù)為Nrt,占總節(jié)點(diǎn)比例設(shè)為αrt,且αr t=αSP/Div,其中Div大于1,SuSP最低度數(shù)為Krt,基于度冪率分布累積概率公式

αrt=P(Krt)=Krt1-γ,得 Krt表示為

1.3 節(jié)點(diǎn)和服務(wù)的地址分配

采用二維編址方法,一維用于路由層,另一維用于服務(wù)層,采用2個(gè)不同的Hash函數(shù)計(jì)算節(jié)點(diǎn)或服務(wù)在兩層對(duì)應(yīng)的地址,分別得到路由層的UPID和服務(wù)層的DOWNID。路由層節(jié)點(diǎn)SuSPi的ID表示為UPIDi:00…00,其DOWNID永遠(yuǎn)為0;服務(wù)層節(jié)點(diǎn)OrSPj(假設(shè)綁定到SuSPi)的ID表示為UPIDi:DOWNIDj。在路由層各SuSP按UPID排列在Chord環(huán)上,設(shè)服務(wù)層最大地址值為V,綁定到SuSPi的m個(gè)OrSP將依照各自DOWNID的大小排列,并平均劃分DOWNID地址空間,依次為:{V/m,2V/m,…,(m-1)V/m,V}。如圖 2所示,縱軸代表 UPID,橫軸代表DOWNID,DOWNID空間被綁定到同一個(gè)SuSP的各OrSP均分,如三個(gè)OrSP(a1-a3)綁定到UPIDi所對(duì)應(yīng)的SuSP上,可將對(duì)應(yīng)的ID空間(DOWNID∈[0,V],UPID∈(UPIDi-1,UPIDi])平分成三個(gè)矩形,各自對(duì)應(yīng)一個(gè)OrSP。

服務(wù)的ID編址空間與以上相同,用 2個(gè)hash函數(shù)分別計(jì)算得到服務(wù)的UPID和DOWNID,該服務(wù)應(yīng)被放置到的節(jié)點(diǎn)的ID應(yīng)滿(mǎn)足:節(jié)點(diǎn)UPID最小但不小于服務(wù)UPID,且DOWNID最小但不小于服務(wù)DOWNID。如果服務(wù)(UPIDs:DOWNIDt)對(duì)應(yīng)的坐標(biāo)(DOWNIDt,UPIDs)落在一個(gè)矩形內(nèi),則該服務(wù)應(yīng)發(fā)布在此矩形對(duì)應(yīng)的OrSP上,如圖2中服務(wù)索引A、B置于a1上,C置于a2上。

圖2 節(jié)點(diǎn)和服務(wù)索引的2維地址空間

2 系統(tǒng)性能分析

文獻(xiàn)[4,5,8]提出了傳統(tǒng)的層次化覆蓋網(wǎng)設(shè)計(jì)思想,是以Chord為頂層的2層覆蓋網(wǎng),在結(jié)構(gòu)上等同于本文提出的覆蓋網(wǎng)中α rt=0、地址一維分布的情況。本文選定平均查詢(xún)路徑長(zhǎng)度(QPL)、簇大小分布均勻度、節(jié)點(diǎn)負(fù)載均衡程度和查詢(xún)成功率(QSR)這幾個(gè)指標(biāo),以Div和α rt作為變參,展開(kāi)性能分析和比較。其中QSR表示為成功查詢(xún)的總數(shù)與查詢(xún)總數(shù)之比。引入隨機(jī)節(jié)點(diǎn)失效模型來(lái)描述節(jié)點(diǎn)動(dòng)態(tài)加入、退出行為對(duì)網(wǎng)絡(luò)的影響,其中節(jié)點(diǎn)失效的概率反比于其度數(shù)。

2.1 查詢(xún)路徑長(zhǎng)度分析

在2層覆蓋網(wǎng)中,發(fā)自CP的查詢(xún)的QPL為CP到其簇首SP的跳數(shù)(為h=1)加Chord上的跳數(shù),發(fā)自SP的查詢(xún)的QPL為Chord上的跳數(shù),故總的QPL表示為

在本文的覆蓋網(wǎng)中,發(fā)自CP的查詢(xún)的QPL為:CP到其SP的跳數(shù)(為h=1),加Chord上的跳數(shù),加目的SuSP到目的OrSP的跳數(shù)(為1),發(fā)自SP的查詢(xún)的QPL為:Chord上的跳數(shù),加目的SuSP到目的OrSP的跳數(shù),故總QPL為

在理論上,2層覆蓋網(wǎng)中Chord上的節(jié)點(diǎn)數(shù)是本文的覆蓋網(wǎng)的Div倍,當(dāng) Div＞2時(shí),有QPL3＜QPL2,此時(shí)本文的覆蓋網(wǎng)的查詢(xún)性能超過(guò)2層覆蓋網(wǎng)。

2.2 負(fù)載均衡程度分析

假設(shè)各節(jié)點(diǎn)的服務(wù)請(qǐng)求特性是一致的,理想的負(fù)載平衡應(yīng)實(shí)現(xiàn)節(jié)點(diǎn)的負(fù)載正比與其能力,可通過(guò)簇中的CP數(shù)目的分布程度來(lái)衡量,體現(xiàn)服務(wù)請(qǐng)求的平衡程度。求各SP的簇大小與其度數(shù)的比值,定義為 Rclsi=Nclsi/ki,其中Nclsi為該SP的簇的大小,ki為該 SP的度,記平均值為,用歸一化標(biāo)準(zhǔn)差表示的平衡程度如(5),其值越小,表明簇大小及查詢(xún)請(qǐng)求的分布越合理。

3 仿 真

3.1 仿真設(shè)置

在Windows環(huán)境下基于C++開(kāi)發(fā)仿真程序,實(shí)現(xiàn)成簇、覆蓋網(wǎng)構(gòu)建、服務(wù)發(fā)布、失效節(jié)點(diǎn)隨機(jī)選擇、查詢(xún)事件生成、查詢(xún)執(zhí)行等過(guò)程。在6000個(gè)節(jié)點(diǎn)構(gòu)成的節(jié)點(diǎn)度數(shù)冪率分布的網(wǎng)絡(luò)拓?fù)湎?設(shè)原先每個(gè)節(jié)點(diǎn)平均提供6個(gè)服務(wù),生成5000個(gè)隨機(jī)查詢(xún)事件并執(zhí)行查詢(xún),記錄各指標(biāo)在不同參數(shù)下的平均值,這些參數(shù)規(guī)定為:αSP分別取值0.01,0.02,0.03,0.04,0.05,Div分別取值4,12,20,探索各性能指標(biāo)隨參數(shù)變化的規(guī)律。

3.2 仿真分析

依據(jù)(1)和(2),獲得不同參數(shù)下SuSP和Or-SP節(jié)點(diǎn)數(shù)目,結(jié)果顯示在表1的二元組中?？梢钥闯?3層覆蓋網(wǎng)的路由層節(jié)點(diǎn)數(shù)僅為幾十到上百,且它們之間彼此直接連通或距離很近,能形成穩(wěn)定高效的路由層。獲取不同參數(shù)下的QSR如圖3,在2層覆蓋網(wǎng)中由于Chord上失效節(jié)點(diǎn)多,該指標(biāo)隨α SP增大而顯著降低,而本文覆蓋網(wǎng)中該指標(biāo)隨α SP增大僅略有下降,但均保持在90%以上。值得注意的是,QSR與前述幾個(gè)指標(biāo)在α SP的選擇上存在性能折中。

表1 不同參數(shù)下SuSP和OrSP節(jié)點(diǎn)數(shù)目

圖3 不同參數(shù)下查詢(xún)成功率

平均QPL如圖4,可以發(fā)現(xiàn),本文的覆蓋網(wǎng)的平均QPL絕大部分在4跳以?xún)?nèi),而2層覆蓋網(wǎng)的平均QPL都在5跳以上。

圖4 不同參數(shù)下的平均查詢(xún)路徑長(zhǎng)度

在仿真中記錄每個(gè)簇的大小,依(5)得到不同參數(shù)下的σ cls,結(jié)果如圖5。從中看出本文的覆蓋網(wǎng)各Div參數(shù)下的σ cls值要顯著小于2層覆蓋網(wǎng)的,故本文的覆蓋網(wǎng)的簇大小與SP能力對(duì)應(yīng)分布較均勻。且隨著α SP減小,σ cls值將不斷增大,簇大小的分布變得更不均衡。

圖5 簇大小比值分布

4 結(jié) 語(yǔ)

本文提出了體現(xiàn)拓?fù)湟庾R(shí)、運(yùn)行穩(wěn)定的覆蓋網(wǎng)體系、地址分配方案,針對(duì)P2P覆蓋網(wǎng)的負(fù)載均衡與拓?fù)淦ヅ鋯?wèn)題進(jìn)行了專(zhuān)門(mén)優(yōu)化,仿真結(jié)果證明了本文提出的方法的優(yōu)越性。未來(lái)的工作包括設(shè)計(jì)動(dòng)態(tài)控制節(jié)點(diǎn)負(fù)載的算法,基于節(jié)點(diǎn)行為特征和服務(wù)內(nèi)容設(shè)計(jì)內(nèi)容復(fù)制方法,以改進(jìn)另一個(gè)體現(xiàn)負(fù)載均衡的指標(biāo),即超級(jí)節(jié)點(diǎn)上的服務(wù)分布平衡程度。

1 樂(lè)光學(xué),李仁發(fā),周祖德.基于Region多層結(jié)構(gòu)P2P計(jì)算網(wǎng)絡(luò)模型[J].軟件學(xué)報(bào),2005,6(6):1140～1150.

2 JESI G P,MON TRESOR A,BABAOGLU O.Proximity-aware superpeer overlay topologies[J].IEEE T ransactions on Network and Service Management,2007,4(2):74～83.

3 ZOELS S,EICHHORN M,TA RLANO A,etc.Contentbased hierarchies in DHT-based peer-to-peer sy stems[C]//IEEE Computer Society.Proceedings of 2006 Symposium on Applications and the Internet Workshops,Phoenix.Arizona.USA,2006:105～108.

4 夏啟志,謝高崗,閔應(yīng)驊,等.IS-P2P:一種基于索引的結(jié)構(gòu)化P2P網(wǎng)絡(luò)模型[J],計(jì)算機(jī)學(xué)報(bào),2006,29(4):602～610.

5 M IN S H,HOLLIDA Y J,CHO D S.Optimal super-peer selection for large-scale P2P system[C]//Proceedings of 2006 International Conference on Hybrid Information Technology,Jeju Island.Korea,2006:588～593.

6 WAT ANABE K,HAYASHIBARA N,T AKIZAWA M.A superpeer-based two-layer P2P overlay network with the CBF strategy[C]//IEEE Computer Society.First International Conference on Complex,Intelligent and Software Intensive Systems,Vienna.Austria,2007:111～118.

7 HAN S Y,PARK S Y.Adapting superpeer size using particle swam optimization for self-organizing superpeer ring with loosely-consistent DHT[C]//Proceeding of 7th IEEE International Conference on Computer and Information Technology,Fukushima.Japan,2007:463～468.

8 XIAO Li,ZHUANG Zhen-yun,LIU Yun-hao.Dynamic layer management in superpeerarchitectures[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(11):1078～1091.

9 FALO UTSOS M,FALO UTSO P,FALO UTSO C.On Power-Law Relationships of the Internet T opology[C]//Proceedings of ACM SIGCOM M,Cambridge.Massachusetts.USA,1999:251～262.