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

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

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

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

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

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

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

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