結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中路由負(fù)載均衡問題的研究.pdf

1、P2P網(wǎng)絡(luò)已經(jīng)成為Internet中最重要的應(yīng)用系統(tǒng)之一?；贒HT的結(jié)構(gòu)化P2P網(wǎng)絡(luò)能夠高效地完成對(duì)象查詢和定位工作,并具有良好的可擴(kuò)展性、健壯性、自組織和自適應(yīng)能力等優(yōu)點(diǎn),因此成為P2P網(wǎng)絡(luò)的一個(gè)主流研究方向。然而,DHT網(wǎng)絡(luò)自身存在的負(fù)載不均衡因子、節(jié)點(diǎn)處理能力的異構(gòu)性、用戶查詢分布的不均勻性以及網(wǎng)絡(luò)中存在的動(dòng)態(tài)性都會(huì)造成負(fù)載分布不均衡,降低整個(gè)系統(tǒng)的服務(wù)質(zhì)量和可用性。
　　 在DHT網(wǎng)絡(luò)中,節(jié)點(diǎn)的負(fù)載主要由兩部分組成:一

2、部分是由節(jié)點(diǎn)所維護(hù)的對(duì)象帶來的負(fù)載,稱為對(duì)象負(fù)載(Obiect Load)；另一部分是節(jié)點(diǎn)根據(jù)路由算法轉(zhuǎn)發(fā)其他用戶查詢消息時(shí)產(chǎn)生的路由負(fù)載(Routing Load)?，F(xiàn)有負(fù)載均衡問題的研究主要針對(duì)對(duì)象負(fù)載而忽略了路由負(fù)載,會(huì)導(dǎo)致節(jié)點(diǎn)因?yàn)檗D(zhuǎn)發(fā)大量查詢消息而產(chǎn)生過載,影響用戶查詢的成功率及響應(yīng)時(shí)間。針對(duì)這一問題,本文圍繞基于DHT的結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的路由負(fù)載均衡問題展開了深入研究,主要工作包括以下幾個(gè)方面:
　　 (1)入度調(diào)整

3、機(jī)制是目前解決路由負(fù)載均衡問題的一種有效手段。針對(duì)入度調(diào)整機(jī)制在DHT網(wǎng)絡(luò)中存在的不足,本文提出了一種使用公平指數(shù)和負(fù)載分層方法的路由負(fù)載均衡算法FLLB。該算法利用公平指數(shù)發(fā)現(xiàn)局部范圍內(nèi)負(fù)載分布的不均衡,利用入度調(diào)整機(jī)制對(duì)輕節(jié)點(diǎn)和重節(jié)點(diǎn)分別進(jìn)行有針對(duì)性的負(fù)載調(diào)整。該算法將節(jié)點(diǎn)的入連接和需要處理的路由負(fù)載劃分為多個(gè)子層,允許節(jié)點(diǎn)通過調(diào)整特定子層的入度數(shù)量來單獨(dú)調(diào)整該子層負(fù)載的大小,提高了調(diào)整的針對(duì)性,細(xì)化了調(diào)整的粒度。模擬結(jié)果表明FLL

4、B算法能夠提高負(fù)載分配的公平性,以較低的開銷取得較好的調(diào)整效果。
　　 (2)針對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)中由于查詢熱點(diǎn)所導(dǎo)致的節(jié)點(diǎn)擁塞問題,本文提出了一種基于入度調(diào)整機(jī)制的路由負(fù)載擁塞控制算法HGCG。該算法能夠動(dòng)態(tài)判定出可能存在的查詢熱點(diǎn),并將熱點(diǎn)周圍的節(jié)點(diǎn)組織起來建立熱點(diǎn)組,通過在熱點(diǎn)組內(nèi)各節(jié)點(diǎn)之間轉(zhuǎn)移入連接來實(shí)現(xiàn)負(fù)載的最優(yōu)分配。同時(shí),HGCG算法還充分考慮了節(jié)點(diǎn)處理能力的異構(gòu)性,將熱點(diǎn)組中的節(jié)點(diǎn)進(jìn)一步劃分為多個(gè)能力組,并在能力組

5、內(nèi)和組間分別進(jìn)行調(diào)整。為了預(yù)防節(jié)點(diǎn)擁塞,算法還將每條入連接的平均剩余處理能力作為指導(dǎo)負(fù)載調(diào)整的標(biāo)準(zhǔn)之一。模擬結(jié)果表明,與其他同類算法相比,HGCG算法可以有效地減少負(fù)載增加過程中查詢失敗的數(shù)量,降低擁塞帶來的影響。
　　 (3)針對(duì)在DHT網(wǎng)絡(luò)中,入度調(diào)整機(jī)制的負(fù)載調(diào)整范圍存在局限性,無法進(jìn)行全局范圍負(fù)載調(diào)整的問題,本文提出了一種基于虛擬服務(wù)器機(jī)制和入度調(diào)整機(jī)制相結(jié)合的路由負(fù)載均衡算法VSG。該算法選取系統(tǒng)中處理能力較強(qiáng)的節(jié)點(diǎn)組

6、成VSG組,并允許在該組成員上創(chuàng)建虛擬服務(wù)器。熱點(diǎn)區(qū)域可以通過在VSG組中創(chuàng)建虛擬服務(wù)器來實(shí)現(xiàn)系統(tǒng)全局范圍內(nèi)的負(fù)載轉(zhuǎn)移；熱點(diǎn)區(qū)域內(nèi)的節(jié)點(diǎn)和虛擬服務(wù)器通過入度調(diào)整來進(jìn)行局部范圍的負(fù)載細(xì)分。同時(shí),VSG算法通過縮小虛擬服務(wù)器路由表的規(guī)模、禁止虛擬服務(wù)器維護(hù)數(shù)據(jù)對(duì)象等措施降低了虛擬服務(wù)器的資源消耗,并考慮了節(jié)點(diǎn)同時(shí)使用多個(gè)標(biāo)識(shí)符時(shí)的安全性問題。模擬結(jié)果表明VSG算法兼具了虛擬服務(wù)器機(jī)制和入度調(diào)整機(jī)制的優(yōu)點(diǎn),能夠有效地處理DHT網(wǎng)絡(luò)中的路由負(fù)載

7、不均衡問題。
　　 (4)為了降低查詢分布不均勻?qū)β酚韶?fù)載均衡的影響,本文提出了一種路由負(fù)載分散機(jī)制RLD,通過將集中的查詢分散化來避免產(chǎn)生查詢熱點(diǎn)。RLD機(jī)制允許同一個(gè)對(duì)象的查詢從多條查詢路徑到達(dá)目標(biāo),讓網(wǎng)絡(luò)中更多的節(jié)點(diǎn)參與查詢消息的路由過程,共同分擔(dān)路由負(fù)載,解決了單一查詢路徑條件下的負(fù)載匯聚問題,提高了路由負(fù)載的均衡程度。通過對(duì)現(xiàn)有DHT路由方法進(jìn)行簡(jiǎn)單擴(kuò)展,RLD機(jī)制能夠以很高的概率保證查詢消息在相同的跳步數(shù)內(nèi)到達(dá)目標(biāo)節(jié)