動(dòng)態(tài)結(jié)構(gòu)化P2P網(wǎng)絡(luò)的負(fù)載均衡方案*

彭利民 肖文俊

(1.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006;2.華南理工大學(xué)軟件學(xué)院，廣東廣州510006)

基于分布式散列表(DHT)的P2P網(wǎng)絡(luò)，通過(guò)采用統(tǒng)一的Hash函數(shù)將網(wǎng)絡(luò)中的對(duì)象和節(jié)點(diǎn)映射到一個(gè)鍵值空間，然后將資源按照鍵值存儲(chǔ)在鍵值相等或相近的節(jié)點(diǎn)上.由于Hash函數(shù)的隨機(jī)性，每個(gè)鍵值空間中的節(jié)點(diǎn)和對(duì)象分布也存在隨機(jī)性，因此，每個(gè)節(jié)點(diǎn)負(fù)責(zé)的對(duì)象個(gè)數(shù)也可能不同，文獻(xiàn)［1］中已證明:結(jié)構(gòu)化P2P網(wǎng)絡(luò)中某些節(jié)點(diǎn)負(fù)責(zé)的標(biāo)識(shí)符空間可能是其它節(jié)點(diǎn)的O(log2N)倍，N為P2P網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù).另外，P2P網(wǎng)絡(luò)中所有節(jié)點(diǎn)在分配存儲(chǔ)對(duì)象或負(fù)載時(shí)，不論其處理能力是否相同，都承擔(dān)著同樣的功能角色.現(xiàn)有研究表明:P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的處理能力(包括存儲(chǔ)空間、帶寬及CPU性能等)具有很大的差異性［2］，容易出現(xiàn)某些處理能力較弱的節(jié)點(diǎn)承擔(dān)較高的負(fù)載，而處理能力較強(qiáng)的節(jié)點(diǎn)承擔(dān)較低的負(fù)載，使P2P網(wǎng)絡(luò)呈現(xiàn)負(fù)載不均衡問(wèn)題.

負(fù)載均衡是一個(gè)經(jīng)典且被廣泛研究的課題，文獻(xiàn)［3］中針對(duì)并行處理系統(tǒng)提出的負(fù)載均衡算法，有效地將單個(gè)處理任務(wù)有機(jī)地分配到多個(gè)處理器上，減少多處理器系統(tǒng)中單任務(wù)的執(zhí)行時(shí)間.為實(shí)現(xiàn)分布式系統(tǒng)的動(dòng)態(tài)負(fù)載平衡，文獻(xiàn)［4］中基于Multi-Agent提出了一種新的分布式系統(tǒng)動(dòng)態(tài)負(fù)載平衡算法.根據(jù)節(jié)點(diǎn)間轉(zhuǎn)移虛擬服務(wù)器的思想，文獻(xiàn)［5］中針對(duì)P2P網(wǎng)絡(luò)的負(fù)載不均衡問(wèn)題，提出了一對(duì)一、一對(duì)多和多對(duì)多負(fù)載均衡算法.文獻(xiàn)［6］中擴(kuò)展了文獻(xiàn)［5］的一對(duì)多和多對(duì)多負(fù)載均衡算法，使其適應(yīng)動(dòng)態(tài)P2P系統(tǒng).但文獻(xiàn)［5-6］中的負(fù)載均衡算法依賴(lài)系統(tǒng)中指定的d個(gè)目錄服務(wù)節(jié)點(diǎn)來(lái)收集負(fù)載信息和生成轉(zhuǎn)移策略，這種類(lèi)似于集中式處理方式容易引起單點(diǎn)失效問(wèn)題;而且在轉(zhuǎn)移負(fù)載時(shí)，由于沒(méi)有考慮節(jié)點(diǎn)間的物理位置關(guān)系，使負(fù)載均衡開(kāi)銷(xiāo)增大，延緩了負(fù)載均衡操作的收斂時(shí)間.文獻(xiàn)［7］中通過(guò)在Chord系統(tǒng)上嵌入K-ary樹(shù)模型，并采用界標(biāo)簇算法來(lái)收集網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，使負(fù)載轉(zhuǎn)移盡量在物理位置較近的節(jié)點(diǎn)之間進(jìn)行，從而減少轉(zhuǎn)移負(fù)載的物理跳數(shù)，節(jié)省系統(tǒng)資源.但K-ary樹(shù)的根節(jié)點(diǎn)需要定期收集所有節(jié)點(diǎn)的負(fù)載信息，并在將收到的信息分發(fā)給K-ary樹(shù)中各個(gè)節(jié)點(diǎn)后，模型中的節(jié)點(diǎn)才能確定自身的負(fù)載狀態(tài).因此，在K-ary樹(shù)中某個(gè)父節(jié)點(diǎn)失效到其恢復(fù)前，其孩子節(jié)點(diǎn)所在子樹(shù)中的負(fù)載不均衡問(wèn)題無(wú)法解決，并且每次負(fù)載轉(zhuǎn)移后，K-ary樹(shù)需要重新構(gòu)造，使得構(gòu)造和維護(hù)K-ary樹(shù)的開(kāi)銷(xiāo)較大，P2P系統(tǒng)不便于擴(kuò)展.在文獻(xiàn)［8］中，每個(gè)節(jié)點(diǎn)周期性地收集鄰近區(qū)域內(nèi)其它節(jié)點(diǎn)的負(fù)載信息，并選擇鏈路延遲較小的節(jié)點(diǎn)轉(zhuǎn)移負(fù)載，但該方法只能保證局部的負(fù)載均衡，很難較快地使整個(gè)P2P系統(tǒng)達(dá)到負(fù)載均衡.

文中在超立方體P2P覆蓋網(wǎng)絡(luò)上構(gòu)建一個(gè)基于二叉樹(shù)的負(fù)載均衡模型，根據(jù)節(jié)點(diǎn)的承載容量分配相應(yīng)的負(fù)載，以減少負(fù)載均衡過(guò)程中的通信冗余和負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)等.首先，將P2P系統(tǒng)中的節(jié)點(diǎn)組織成一個(gè)層次化的二叉樹(shù)型結(jié)構(gòu)，負(fù)責(zé)收集與分發(fā)節(jié)點(diǎn)的負(fù)載信息，以減少負(fù)載均衡代價(jià)，并便于P2P系統(tǒng)的擴(kuò)展.同時(shí)，通過(guò)引入均衡域概念，將P2P系統(tǒng)中的節(jié)點(diǎn)劃分到各個(gè)均衡域中，使負(fù)載均衡操作可以在整個(gè)系統(tǒng)或各均衡域中完成，有利于將整個(gè)P2P系統(tǒng)的負(fù)載均衡任務(wù)按照并行與分布式處理，降低負(fù)載均衡算法的時(shí)間復(fù)雜度，使負(fù)載均衡模型具有很好的適應(yīng)性.

1 系統(tǒng)模型

1.1 相關(guān)概念和定義

(1)虛擬服務(wù)器.虛擬服務(wù)器是Chord系統(tǒng)中為改善節(jié)點(diǎn)負(fù)載量而提出的一個(gè)概念［9］，也是文中負(fù)載均衡處理的基本單位.虛擬服務(wù)器類(lèi)似于P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)，一個(gè)虛擬服務(wù)器負(fù)責(zé)相應(yīng)的鍵值空間，而每個(gè)物理節(jié)點(diǎn)可擁有多個(gè)虛擬服務(wù)器.從負(fù)載均衡的觀點(diǎn)，虛擬服務(wù)器可以表示確定的負(fù)載量.當(dāng)物理節(jié)點(diǎn)過(guò)載時(shí)，可以在其擁有的虛擬服務(wù)器中選擇一個(gè)或多個(gè)虛擬服務(wù)器轉(zhuǎn)移到其它非過(guò)載節(jié)點(diǎn)上.

(2)均衡域.均衡域是并行計(jì)算機(jī)系統(tǒng)中的一個(gè)概念［3］，通過(guò)將系統(tǒng)劃分為多個(gè)獨(dú)立的處理器集合(稱(chēng)為均衡域)，可以將單個(gè)處理任務(wù)分配到多個(gè)處理器上，減少多處理器系統(tǒng)中單任務(wù)的執(zhí)行時(shí)間.在圖2中，均衡域是指位于同一棵子樹(shù)中的節(jié)點(diǎn)集合，如節(jié)點(diǎn)000和001屬于同一個(gè)均衡域，節(jié)點(diǎn)000、001、010和011屬于同一個(gè)均衡域.均衡域的規(guī)?？梢詮膸讉€(gè)節(jié)點(diǎn)到整個(gè)系統(tǒng)，負(fù)載均衡決策唯一依賴(lài)于每個(gè)均衡域的負(fù)載狀態(tài)，各個(gè)均衡域可以并行地進(jìn)行負(fù)載均衡操作，以減少整個(gè)系統(tǒng)負(fù)載均衡操作的收斂時(shí)間，降低負(fù)載均衡算法的時(shí)間復(fù)雜度.

(3)節(jié)點(diǎn)利用率.節(jié)點(diǎn)利用率是指節(jié)點(diǎn)的負(fù)載與承載能力的比值.節(jié)點(diǎn)的承載能力(綜合處理能力)可以是節(jié)點(diǎn)的CPU處理能力，也可以是節(jié)點(diǎn)的存儲(chǔ)空間大小.不失一般性，文中假定其為節(jié)點(diǎn)的存儲(chǔ)空間大小.通過(guò)引入節(jié)點(diǎn)利用率的概念，在負(fù)載均衡過(guò)程中可有效地處理P2P系統(tǒng)中的節(jié)點(diǎn)異構(gòu)性問(wèn)題，并按照節(jié)點(diǎn)的實(shí)際承載能力分配相應(yīng)的負(fù)載，從而避免承載能力弱的節(jié)點(diǎn)承擔(dān)較高的負(fù)載量，使P2P系統(tǒng)中的負(fù)載均衡分布.

(4)均衡域利用率.均衡域利用率是指均衡域中所有節(jié)點(diǎn)的負(fù)載總量與總承載能力的比值.當(dāng)整個(gè)系統(tǒng)屬于同一個(gè)均衡域中時(shí)，均衡域利用率表示系統(tǒng)利用率.根據(jù)均衡域利用率，可以在不同的均衡域內(nèi)實(shí)施不同的負(fù)載均衡策略.

(5)海明距離.海明距離是計(jì)算機(jī)網(wǎng)絡(luò)通信理論中的一個(gè)概念，兩個(gè)碼字中對(duì)應(yīng)位的比特值不同的位數(shù)，即為兩個(gè)碼字的海明距離.由于文中采用二進(jìn)制數(shù)對(duì)超立方體P2P覆蓋網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)，因此，海明距離也可以用于表示節(jié)點(diǎn)間的最小距離.如節(jié)點(diǎn) A(10001001)和 B(10110001)的第3、4和5位對(duì)應(yīng)的比特值不同，其余的比特值均相同，因此，節(jié)點(diǎn)A和B之間的距離為3.一般將過(guò)載節(jié)點(diǎn)上的負(fù)載轉(zhuǎn)移到距離較近的節(jié)點(diǎn)上，以減少負(fù)載均衡的開(kāi)銷(xiāo).

1.2 基于二叉樹(shù)的層次負(fù)載均衡模型

超立方體結(jié)構(gòu)具有較優(yōu)的路由算法，其操作與維護(hù)簡(jiǎn)單，因而是P2P網(wǎng)絡(luò)中一個(gè)較常用的覆蓋網(wǎng)絡(luò)結(jié)構(gòu)，Pastry［10］、Tapestry［11］等都是基于超立方體結(jié)構(gòu)的P2P系統(tǒng).文獻(xiàn)［12］中提出的超立方體DHT覆蓋網(wǎng)絡(luò)，保持了覆蓋拓?fù)浜臀锢硗負(fù)涞囊恢滦?，有效地支持P2P系統(tǒng)的文件共享.文中在文獻(xiàn)［12］的超立方體DHT覆蓋結(jié)構(gòu)(見(jiàn)圖1)上，建立一個(gè)基于二叉樹(shù)的層次負(fù)載均衡模型(見(jiàn)圖2)，負(fù)責(zé)收集與分發(fā)P2P系統(tǒng)中的負(fù)載信息，以及執(zhí)行負(fù)載轉(zhuǎn)移操作，以解決動(dòng)態(tài)DHT網(wǎng)絡(luò)中的負(fù)載均衡問(wèn)題.

圖1 三維超立方體覆蓋網(wǎng)絡(luò)Fig.1 A 3-D hypercube overlay network

圖1中的h0、h1和h2分別表示超立方體的第0、1和2維度上的邊.二叉樹(shù)中的中間節(jié)點(diǎn)表示其下層相應(yīng)均衡域中的域頭節(jié)點(diǎn)，這些節(jié)點(diǎn)負(fù)責(zé)收集自身均衡域內(nèi)的負(fù)載信息以及控制均衡處理過(guò)程.例如，第1層的000、010、100和110節(jié)點(diǎn)分別負(fù)責(zé)第0層的2個(gè)均衡域(或節(jié)點(diǎn))的負(fù)載均衡操作，第2層的000和100節(jié)點(diǎn)分別負(fù)責(zé)其管轄的第1層的2個(gè)均衡域的負(fù)載均衡操作，第3層的000節(jié)點(diǎn)負(fù)責(zé)其管轄的第2層的2個(gè)均衡域的均衡操作過(guò)程，按照這種自下而上的層次處理方法，該二叉樹(shù)模型將系統(tǒng)組織成一個(gè)層次的負(fù)載均衡域結(jié)構(gòu)，分解了P2P系統(tǒng)的負(fù)載均衡處理過(guò)程.

圖2 基于二叉樹(shù)的負(fù)載均衡模型Fig.2 A binary-tree based load balancing model

根據(jù)二叉樹(shù)負(fù)載均衡模型，可以按照自下而上的層次方法，在不同規(guī)模的均衡域內(nèi)中實(shí)現(xiàn)負(fù)載轉(zhuǎn)移.例如，當(dāng)節(jié)點(diǎn)000超載時(shí)，由節(jié)點(diǎn)000觸發(fā)負(fù)載均衡事件，由于節(jié)點(diǎn)000是由節(jié)點(diǎn)000和節(jié)點(diǎn)001組成的均衡域中的域頭節(jié)點(diǎn)，因此，節(jié)點(diǎn)000分析節(jié)點(diǎn)001是否可以用來(lái)轉(zhuǎn)移負(fù)載，如果可以，則將節(jié)點(diǎn)000上過(guò)載的負(fù)載轉(zhuǎn)移到節(jié)點(diǎn)001上，否則，按照自下而上的層次方法將過(guò)載負(fù)載轉(zhuǎn)移到第2層或第3層的均衡域內(nèi)的節(jié)點(diǎn)上.另外，由于負(fù)載均衡操作可在不同層次的均衡域內(nèi)進(jìn)行，而且超立方體結(jié)構(gòu)路由算法簡(jiǎn)單，所以負(fù)載轉(zhuǎn)移易于實(shí)現(xiàn)，從而簡(jiǎn)化負(fù)載均衡的操作過(guò)程，降低負(fù)載均衡的開(kāi)銷(xiāo)和負(fù)載轉(zhuǎn)移代價(jià).

2 分布式負(fù)載均衡算法

首先每個(gè)節(jié)點(diǎn)向其父節(jié)點(diǎn)發(fā)送負(fù)載信息，然后域頭節(jié)點(diǎn)計(jì)算每棵子樹(shù)(均衡域)的負(fù)載狀態(tài)并依次傳到樹(shù)根節(jié)點(diǎn).當(dāng)某個(gè)節(jié)點(diǎn)(或均衡域)的節(jié)點(diǎn)利用率超過(guò)預(yù)設(shè)的閾值，則觸發(fā)負(fù)載均衡事件.由于DHT網(wǎng)絡(luò)中節(jié)點(diǎn)的異構(gòu)性，在設(shè)計(jì)負(fù)載均衡算法時(shí)，需要考慮節(jié)點(diǎn)承載能力的差異性，因此，文中根據(jù)節(jié)點(diǎn)利用率來(lái)計(jì)算需要轉(zhuǎn)移的超載量及確定可以接收超載量的節(jié)點(diǎn)(或節(jié)點(diǎn)集)，從而使分布式負(fù)載均衡算法便于處理異構(gòu)DHT網(wǎng)絡(luò)中的負(fù)載均衡問(wèn)題.

對(duì)于一個(gè)包含N個(gè)節(jié)點(diǎn)的P2P系統(tǒng)，負(fù)載均衡模型中第i層共有N/2i個(gè)均衡域.當(dāng)所有均衡域內(nèi)的負(fù)載都不均衡時(shí)(最壞的情形下)，每個(gè)均衡域內(nèi)最多發(fā)送的負(fù)載均衡請(qǐng)求信息和負(fù)載轉(zhuǎn)移次數(shù)均為2i－1，則每層中負(fù)載均衡操作次數(shù)最多為N/2.由于二叉樹(shù)模型共有l(wèi)og2N層，因此，整個(gè)P2P系統(tǒng)中負(fù)載均衡操作次數(shù)最多為Nlog2N.由于P2P系統(tǒng)的均衡域可以按照平均并行度為N/2的并行方式執(zhí)行負(fù)載均衡操作，因此，算法的時(shí)間復(fù)雜度為O(log2N).

3 仿真實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)使用P2PSim作為模擬器來(lái)評(píng)估文中提出的負(fù)載均衡算法.為了便于比較，文中同時(shí)實(shí)現(xiàn)了文獻(xiàn)［6］中提出的負(fù)載均衡算法，表1列出了實(shí)驗(yàn)參數(shù)值.實(shí)驗(yàn)采用P2P系統(tǒng)中3個(gè)主要的標(biāo)度進(jìn)行測(cè)定，即節(jié)點(diǎn)利用率、負(fù)載轉(zhuǎn)移因子和負(fù)載轉(zhuǎn)移跳步數(shù).其中，負(fù)載轉(zhuǎn)移因子是指負(fù)載均衡過(guò)程中的負(fù)載轉(zhuǎn)移代價(jià)與系統(tǒng)中所有負(fù)載轉(zhuǎn)移一次的總代價(jià)的比值［6］，它表示負(fù)載均衡過(guò)程中的負(fù)載轉(zhuǎn)移代價(jià).負(fù)載轉(zhuǎn)移跳步數(shù)是指在負(fù)載均衡過(guò)程中，負(fù)載從超載節(jié)點(diǎn)轉(zhuǎn)移到輕載節(jié)點(diǎn)路由過(guò)程中的物理跳步數(shù)，它表示負(fù)載均衡開(kāi)銷(xiāo)，負(fù)載轉(zhuǎn)移跳步數(shù)越小，負(fù)載均衡開(kāi)銷(xiāo)也越小.每次模擬時(shí)間均為20T，其中，T表示預(yù)設(shè)的均衡周期.對(duì)于每個(gè)實(shí)驗(yàn)情況進(jìn)行10次實(shí)驗(yàn)，取10次實(shí)驗(yàn)結(jié)果的平均值作為該實(shí)驗(yàn)的最終結(jié)果.

表1 實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Setting of experimental parameters

實(shí)驗(yàn)1 測(cè)試在不同的系統(tǒng)利用率下，執(zhí)行負(fù)載均衡后P2P系統(tǒng)中的節(jié)點(diǎn)利用率分布情況，結(jié)果如圖3所示.

圖3 負(fù)載均衡后節(jié)點(diǎn)利用率分布Fig.3 Distribution of node utilization rate after load balancing

圖3表明:負(fù)載均衡后，兩種負(fù)載均衡算法的節(jié)點(diǎn)利用率隨系統(tǒng)利用率增加呈近似線性遞增趨勢(shì)，且負(fù)載均衡后的節(jié)點(diǎn)利用率略大于系統(tǒng)利用率.由于文獻(xiàn)［6］中的算法由多個(gè)目錄節(jié)點(diǎn)負(fù)責(zé)整個(gè)系統(tǒng)的負(fù)載均衡操作，各個(gè)目錄節(jié)點(diǎn)之間相互獨(dú)立，一個(gè)目錄節(jié)點(diǎn)管轄內(nèi)節(jié)點(diǎn)上的負(fù)載無(wú)法轉(zhuǎn)移到另一個(gè)目錄節(jié)點(diǎn)管轄的節(jié)點(diǎn)中，因此，無(wú)法使整個(gè)P2P系統(tǒng)達(dá)到負(fù)載均衡.在文中提出的負(fù)載均衡方案中，各個(gè)節(jié)點(diǎn)按照均衡域的方式進(jìn)行組織，且均衡域可以按照由下至上的層次結(jié)構(gòu)進(jìn)行擴(kuò)展至整個(gè)系統(tǒng)，因此，可以使整個(gè)P2P系統(tǒng)達(dá)到一致性的負(fù)載均衡.從圖3可以看出，文中負(fù)載均衡算法的節(jié)點(diǎn)利用率均低于文獻(xiàn)［6］中算法的節(jié)點(diǎn)利用率，說(shuō)明文中算法比文獻(xiàn)［6］中的算法能取得更好的負(fù)載均衡效果，當(dāng)系統(tǒng)利用率為90%時(shí)，文中算法使網(wǎng)絡(luò)中93%的節(jié)點(diǎn)利用率低于100%，89%的節(jié)點(diǎn)利用率低于90%.

實(shí)驗(yàn)2 測(cè)試在不同的系統(tǒng)利用率下，負(fù)載均衡過(guò)程中的負(fù)載轉(zhuǎn)移因子分布情況，結(jié)果見(jiàn)圖4.

圖4 負(fù)載均衡過(guò)程中的負(fù)載轉(zhuǎn)移因子Fig.4 Load movement factor during load balancing

圖4表明:在不同的系統(tǒng)利用率下，兩種算法的負(fù)載轉(zhuǎn)移因子均隨系統(tǒng)利用率增加而增大，且兩種算法的負(fù)載轉(zhuǎn)移因子均較小，說(shuō)明兩種算法在負(fù)載均衡過(guò)程中，只需要轉(zhuǎn)移較小的負(fù)載量就能使P2P系統(tǒng)中的負(fù)載均衡分布.由于文中的負(fù)載均衡算法以均衡域模式進(jìn)行操作，負(fù)載均衡可以在局部范圍內(nèi)執(zhí)行，然后再擴(kuò)展至整個(gè)系統(tǒng);當(dāng)某個(gè)節(jié)點(diǎn)超載時(shí)，文獻(xiàn)［6］中的算法首先隨機(jī)地選擇d個(gè)目錄節(jié)點(diǎn)，再由目錄節(jié)點(diǎn)在其管轄的節(jié)點(diǎn)范圍內(nèi)執(zhí)行負(fù)載均衡操作.因此，對(duì)于不同的系統(tǒng)利用率，文中的負(fù)載均衡算法總保持較好的性能，在系統(tǒng)利用率為90%時(shí)，文中算法的負(fù)載均衡因子小于0.13，而文獻(xiàn)［6］中算法的負(fù)載轉(zhuǎn)移因子約為0.17.

實(shí)驗(yàn)3 測(cè)試負(fù)載均衡算法在P2P網(wǎng)絡(luò)動(dòng)態(tài)環(huán)境下的負(fù)載均衡效果.主要考察額外的10%系統(tǒng)負(fù)載總量快速到達(dá)系統(tǒng)對(duì)負(fù)載均衡算法的影響，并將這額外的10%負(fù)載量隨機(jī)地分布在P2P系統(tǒng)的標(biāo)識(shí)符空間上，額外增加的10%負(fù)載量不僅使節(jié)點(diǎn)的負(fù)載在短期內(nèi)的分布更加不均衡，而且使P2P系統(tǒng)中節(jié)點(diǎn)承擔(dān)更大的負(fù)載量，結(jié)果見(jiàn)圖5.

圖5 數(shù)據(jù)項(xiàng)動(dòng)態(tài)環(huán)境下的負(fù)載轉(zhuǎn)移因子Fig.5 Load movement factor under dynamism of data items

圖5表明:負(fù)載轉(zhuǎn)移因子隨系統(tǒng)利用率增加而呈線性遞增.當(dāng)系統(tǒng)利用率較低時(shí)，額外增加的10%負(fù)載只造成系統(tǒng)中少量的節(jié)點(diǎn)超載，兩種算法的負(fù)載轉(zhuǎn)移因子均較低.當(dāng)系統(tǒng)利用率較高時(shí)，系統(tǒng)中大部分節(jié)點(diǎn)的可承載容量較小，額外增加的10%負(fù)載使系統(tǒng)中超載的節(jié)點(diǎn)數(shù)增加，因此，負(fù)載轉(zhuǎn)移因子增大.由于文中算法以均衡域方式執(zhí)行負(fù)載均衡操作，各個(gè)均衡域規(guī)?？梢愿鶕?jù)負(fù)載狀態(tài)動(dòng)態(tài)地進(jìn)行擴(kuò)展，因此，在各種系統(tǒng)利用率的情況下，文中算法的負(fù)載轉(zhuǎn)移因子均比文獻(xiàn)［6］中算法小.在系統(tǒng)利用率為90%時(shí)，文中算法的負(fù)載轉(zhuǎn)移因子小于0.20，而文獻(xiàn)［6］中算法的為0.22，表明文中算法能有效地解決動(dòng)態(tài)P2P網(wǎng)絡(luò)環(huán)境下的負(fù)載均衡問(wèn)題.

實(shí)驗(yàn)4 測(cè)試負(fù)載均衡算法在節(jié)點(diǎn)動(dòng)態(tài)進(jìn)入/退出P2P系統(tǒng)情況下的負(fù)載均衡效果.P2P系統(tǒng)中節(jié)點(diǎn)總數(shù)固定為4096，每間隔1s有一個(gè)節(jié)點(diǎn)隨機(jī)地進(jìn)入/退出P2P系統(tǒng).為了評(píng)估負(fù)載均衡算法的動(dòng)態(tài)適應(yīng)性，文中將負(fù)載轉(zhuǎn)移因子定義為負(fù)載均衡算法所引起的負(fù)載轉(zhuǎn)移量與節(jié)點(diǎn)到達(dá)或離開(kāi)而產(chǎn)生的負(fù)載轉(zhuǎn)移量的比值，結(jié)果如圖6所示.

圖6 節(jié)點(diǎn)動(dòng)態(tài)性與負(fù)載轉(zhuǎn)移因子Fig.6 Load movement factor under dynamism of node

圖6表明:負(fù)載轉(zhuǎn)移因子隨系統(tǒng)利用率增加而增大.當(dāng)系統(tǒng)利用率較低時(shí)，兩種算法的負(fù)載轉(zhuǎn)移因子均較低，當(dāng)系統(tǒng)利用率較大時(shí)，系統(tǒng)中節(jié)點(diǎn)的可承載容量較小，節(jié)點(diǎn)隨機(jī)地加入或退出使P2P系統(tǒng)中的節(jié)點(diǎn)負(fù)載狀態(tài)變化增大，需要轉(zhuǎn)移的負(fù)載量增多，因此，負(fù)載轉(zhuǎn)移因子增大.在系統(tǒng)利用率為90%時(shí)，文中算法的負(fù)載轉(zhuǎn)移因子小于0.50，文獻(xiàn)［8］中算法的負(fù)載轉(zhuǎn)移因子為0.56，表明文中算法能有效地解決動(dòng)態(tài)P2P網(wǎng)絡(luò)環(huán)境下的負(fù)載均衡問(wèn)題.

實(shí)驗(yàn)5 測(cè)試負(fù)載均衡過(guò)程中轉(zhuǎn)移的負(fù)載在物理網(wǎng)絡(luò)上的跳步距離，以評(píng)估負(fù)載均衡算法的負(fù)載均衡開(kāi)銷(xiāo).

圖7 轉(zhuǎn)移負(fù)載的物理跳步數(shù)累積分布Fig.7 Cumulative distribution of moved load by physical distance hops

圖7顯示了兩種算法在負(fù)載均衡過(guò)程中負(fù)載轉(zhuǎn)移跳步數(shù)的分布情況.在文中的負(fù)載均衡模型中，各個(gè)均衡域按照節(jié)點(diǎn)的位置關(guān)系進(jìn)行組織，而且在各個(gè)均衡域中分別地執(zhí)行負(fù)載均衡操作，因此，超載節(jié)點(diǎn)和輕載節(jié)點(diǎn)都位于同一個(gè)均衡域內(nèi).當(dāng)同一個(gè)均衡域中有多個(gè)輕載節(jié)點(diǎn)可用于轉(zhuǎn)移負(fù)載時(shí)，文中算法總選擇距離超載節(jié)點(diǎn)最近的節(jié)點(diǎn)進(jìn)行負(fù)載轉(zhuǎn)移.在文獻(xiàn)［6］算法中，當(dāng)P2P系統(tǒng)中某個(gè)節(jié)點(diǎn)k超載時(shí)，節(jié)點(diǎn)k在P2P系統(tǒng)中隨機(jī)地選擇目錄節(jié)點(diǎn)d，然后由目錄節(jié)點(diǎn)d負(fù)責(zé)執(zhí)行負(fù)載均衡操作，由于目錄節(jié)點(diǎn)d在其管轄范圍內(nèi)的輕載節(jié)點(diǎn)中隨機(jī)地選擇輕載節(jié)點(diǎn)h用于轉(zhuǎn)移負(fù)載，因此，過(guò)載節(jié)點(diǎn)k與輕載節(jié)點(diǎn)h相距離可能較遠(yuǎn).從圖7可以看出，文中算法使50%的轉(zhuǎn)移負(fù)載量在12跳內(nèi)實(shí)現(xiàn)轉(zhuǎn)移，90%的轉(zhuǎn)移負(fù)載量在18跳內(nèi)實(shí)現(xiàn)轉(zhuǎn)移，文獻(xiàn)［6］中算法在12跳內(nèi)轉(zhuǎn)移13%的負(fù)載，18跳內(nèi)轉(zhuǎn)移22%的負(fù)載量，50%的負(fù)載量在22跳內(nèi)的節(jié)點(diǎn)間實(shí)現(xiàn)轉(zhuǎn)移.圖7的結(jié)果表明:文中算法能在鄰近節(jié)點(diǎn)間實(shí)現(xiàn)負(fù)載轉(zhuǎn)移，大大地降低了負(fù)載均衡的開(kāi)銷(xiāo).

4 結(jié)語(yǔ)

針對(duì)結(jié)構(gòu)化動(dòng)態(tài)P2P系統(tǒng)的負(fù)載不均衡問(wèn)題，文中通過(guò)建立二叉樹(shù)負(fù)載均衡模型，提出了一種分布式負(fù)載均衡算法.仿真結(jié)果表明:文中提出的負(fù)載均衡算法不僅能解決不同系統(tǒng)負(fù)載狀態(tài)下的負(fù)載均衡問(wèn)題，而且能有效地應(yīng)對(duì)動(dòng)態(tài)環(huán)境下負(fù)載的快速變化，有效地解決動(dòng)態(tài)DHT網(wǎng)絡(luò)環(huán)境下的負(fù)載均衡問(wèn)題.文中算法在負(fù)載轉(zhuǎn)移過(guò)程中，考慮了參與轉(zhuǎn)移負(fù)載的節(jié)點(diǎn)之間的位置關(guān)系，使負(fù)載在鄰近的節(jié)點(diǎn)間實(shí)現(xiàn)轉(zhuǎn)移，有效地降低了負(fù)載均衡的開(kāi)銷(xiāo).

［1］Karger D，Lehman E，Leighton T，et al.Consistent hashing and random trees:distributed caching protocols for relie-ving hot spots on the World Wide Web［C］∥Proceedings of the 29th Annual ACM Symposium on Theory of Computing.Texas:ACM，1997:654-663.

［2］Saroiu S，Gummadi P K，Gribble S D.A measurement study of peer-to-peer file sharing systems［C］∥Proceedings of Multimedia Computing and Networking.San Jose:SPIE，2002:156-170.

［3］Willebeek L H，Reeves A P.Strategies for dynamic load balancing on highly parallel computers［J］.IEEE Transactions on Parallel and Distributed Systems，1993，9(4):979-993.

［4］閆鈞華，張煥春，經(jīng)亞枝.基于Multi-agent的分布式系統(tǒng)負(fù)載平衡［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2004，32(12):74-79.Yan Jun-hu，Zhang Huan-chun，Jing Ya-zhi.Load balancing of the distributed system based on multi-agent［J］.Journal of South China University of Technology:Natural Science Edition，2004，32(12):74-79.

［5］Rao A，Lakshminarayanan K，Surana S，et al.Load balancing in structured P2P systems［C］∥Proceedings of the 2nd International Workshop Peer-to-Peer Systems.Berkeley:Springer-Verlag，2003:68-79.

［6］Godfrey B，Lakshminarayanan K，Surana S，et al.Load balancing in dynamic structured P2P systems［C］∥Proceeding of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.Los Alamiws:IEEE，2004:2253-2262.

［7］Zhu Yingwu，Hu Yiming.Efficient，proximity-aware load balancing for DHT-based P2P systems［J］.IEEE Transactions on Parallel and Distributed Systems，2005，16(4):349-361.

［8］李振宇，謝高崗.基于DHT的P2P系統(tǒng)的負(fù)載均衡算法［J］.計(jì)算機(jī)研究與發(fā)展，2006，43(9):1579-1585.Li Zhen-yu，Xie Gao-gang.A load balancing algorithm for DHT-based P2P systems［J］.Journal of Computer Research and Development，2006，43(9):1579-1585.

［9］Stoica I，Morris R，Karger D R，et al.Chord:a scalable peer-to-peer lookup protocol for internet applications［J］.IEEE/ACM Transactions on Networking，2003，11(1):17-32.

［10］Rowstron A，Druschel P.Pastry:scalable，decentralized object location and routing for large-scale peer-to-peer svstems［C］∥Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms.Heidelberg:Springer-Verlag，2001:329-350.

［11］Zhao B Y，Huang L，Stribling J，et al.Tapestry:a resilient global-scale overlay for service deployment［J］.IEEE Journal on Selected Areas in Communications，2004，22(1):41-53.

［12］Gharib M，Barzegar Z，Habibi J.A novel method for supporting locality in peer-to-peer overlays using hypercube topology［C］∥Proceeding of the 2010 International Conference on Intelligent Systems，Modelling and Simulation.Liverpool:IEEE，2010:391-395.