結(jié)構(gòu)化Ｐ２Ｐ系統(tǒng)中基于網(wǎng)絡(luò)定位的負(fù)載均衡算法

摘 要：結(jié)構(gòu)化P2P系統(tǒng)中，各對(duì)等節(jié)點(diǎn)處理能力的差異以及關(guān)鍵字通常與一定的語(yǔ)義相關(guān)，導(dǎo)致系統(tǒng)中節(jié)點(diǎn)的負(fù)載不均衡。算法針對(duì)基于DHT的大規(guī)模計(jì)算網(wǎng)絡(luò)中，計(jì)算任務(wù)在節(jié)點(diǎn)間分布不均衡的問(wèn)題，提出了一種高效的基于網(wǎng)絡(luò)定位的負(fù)載均衡算法：當(dāng)某個(gè)節(jié)點(diǎn)的負(fù)載較小時(shí)，它將以自己為中心，與物理位置相近的節(jié)點(diǎn)構(gòu)成一個(gè)星型結(jié)構(gòu)區(qū)域，然后在這個(gè)物理位置相近的區(qū)域進(jìn)行負(fù)載轉(zhuǎn)移。該算法具有擴(kuò)展性好、效率高、維護(hù)簡(jiǎn)單的特點(diǎn)。仿真實(shí)驗(yàn)表明本算法可以達(dá)到理想的負(fù)載均衡效果，并使負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)減少了40%以上。

關(guān)鍵詞：點(diǎn)對(duì)點(diǎn)系統(tǒng)； 分布式哈希表； 負(fù)載均衡； 星型結(jié)構(gòu)； 網(wǎng)絡(luò)定位

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695(2008)08-2524-04

Load balancing algorithm based on network positioning in structured P2P systems

LI Li-juan， SUN Jian-hua， CHEN Hao， CHEN Tie-qun， SHI Lin

(A. I. M Laboratory， School of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:In structured P2P systems， the heterogeneity of node capacity and semantic relativity of keys could cause load imbalance among nodes. Aimed at the problem of tasks distributed unbalancedly among nodes on large-scaleDHT networks， this paper presented an efficientalgorithm based on network positioning. While the load of a node was light， the node， as a center， would construct a star-like structure area with other nodes physically close to it. And then， load could be transferred in that physically close area. This algorithm is scalable， efficient and simple. Simulation experiments show that the algorithm can achieve a good load balance and the load movement cost reduction rate is above 40%.

Key words:P2P system; DHT; load balancing; star-like structure; network positioning

0 引言

P2P是一種分布式系統(tǒng)，其中的參與者共享他們所擁有的一部分資源，這些共享資源能被其他對(duì)等節(jié)點(diǎn)直接訪(fǎng)問(wèn)而無(wú)須經(jīng)過(guò)中間實(shí)體。網(wǎng)絡(luò)中的參與者既是資源（服務(wù)和內(nèi)容）提供者，又是資源（服務(wù)和內(nèi)容）獲取者。P2P技術(shù)使得網(wǎng)絡(luò)上的溝通變得更容易、更直接。P2P改變了目前Internet以太網(wǎng)站為中心的狀態(tài)，重返非中心化，并把權(quán)利交還給用戶(hù)。

P2P系統(tǒng)一般分為非結(jié)構(gòu)化和結(jié)構(gòu)化兩種。近年來(lái)，基于DHT的結(jié)構(gòu)化P2P系統(tǒng)以其嚴(yán)格的節(jié)點(diǎn)組織規(guī)則，良好的容錯(cuò)能力、可擴(kuò)展性和查找速度等，得到了廣泛的應(yīng)用（如Chord、Pastry、Tapestry和CAN）。

結(jié)構(gòu)化P2P系統(tǒng)利用相容hash函數(shù)把資源關(guān)鍵字隨機(jī)分配在各對(duì)等節(jié)點(diǎn)中，從而各節(jié)點(diǎn)以很高的概率分配到相同數(shù)目的關(guān)鍵字。文獻(xiàn)[1]表明這種情況下，一個(gè)節(jié)點(diǎn)所負(fù)責(zé)的關(guān)鍵字?jǐn)?shù)可能是其他節(jié)點(diǎn)的O(log N)倍（N是系統(tǒng)的總節(jié)點(diǎn)數(shù)）。另外，它們假設(shè)系統(tǒng)各節(jié)點(diǎn)的能力是一樣的。但文獻(xiàn)[2]表明P2P系統(tǒng)中各節(jié)點(diǎn)的能力（CPU處理能力、存儲(chǔ)能力、網(wǎng)絡(luò)連接能力等）有很大的差異。所以必須進(jìn)行負(fù)載均衡，使能力強(qiáng)的節(jié)點(diǎn)處理更多的任務(wù)。

本文針對(duì)以上問(wèn)題，以Chord算法為基礎(chǔ)，提出了基于網(wǎng)絡(luò)定位的負(fù)載均衡算法。算法利用網(wǎng)絡(luò)定位技術(shù)產(chǎn)生系統(tǒng)中各節(jié)點(diǎn)的距離信息，使負(fù)載在物理位置相近的節(jié)點(diǎn)間進(jìn)行轉(zhuǎn)移，從而最小化帶寬和延遲的消耗，達(dá)到快速有效轉(zhuǎn)移負(fù)載的目的。該算法由負(fù)載較輕的節(jié)點(diǎn)負(fù)責(zé)主要的負(fù)載轉(zhuǎn)移操作，節(jié)省了過(guò)載節(jié)點(diǎn)的資源，提高了負(fù)載轉(zhuǎn)移質(zhì)量。

1 相關(guān)工作

現(xiàn)有的負(fù)載均衡算法，有的忽略了系統(tǒng)中節(jié)點(diǎn)負(fù)載能力的差異；有的在負(fù)載轉(zhuǎn)移時(shí)，沒(méi)有考慮節(jié)點(diǎn)間的位置關(guān)系；有的增加了系統(tǒng)的復(fù)雜性，減小了容錯(cuò)能力。

文獻(xiàn)[3]沒(méi)有考慮節(jié)點(diǎn)能力的差異，給每個(gè)DHT節(jié)點(diǎn)都分配O(log N)個(gè)虛擬服務(wù)器試圖解決負(fù)載均衡問(wèn)題。但根據(jù)經(jīng)典球盒問(wèn)題（balls and bins problem），這種方案下一些節(jié)點(diǎn)的負(fù)載可能是其他節(jié)點(diǎn)的O(log N/loglog N )倍，所以單純依靠虛擬服務(wù)器并不能完全解決這個(gè)問(wèn)題。CFS^[4]根據(jù)節(jié)點(diǎn)本身的能力來(lái)分配虛擬服務(wù)器，考慮到了節(jié)點(diǎn)能力的差異。當(dāng)一個(gè)節(jié)點(diǎn)過(guò)載時(shí)簡(jiǎn)單地刪除它的部分虛擬服務(wù)器。此算法在刪除過(guò)載節(jié)點(diǎn)的服務(wù)器時(shí)可能引起其他節(jié)點(diǎn)過(guò)載，過(guò)載節(jié)點(diǎn)需再次刪除虛擬服務(wù)器，從而使系統(tǒng)不穩(wěn)定，收斂時(shí)間過(guò)長(zhǎng)。

文獻(xiàn)[5]提出了三種簡(jiǎn)單的負(fù)載均衡算法:一對(duì)一、一對(duì)多、多對(duì)多。算法的基本思想是過(guò)載節(jié)點(diǎn)轉(zhuǎn)移虛擬服務(wù)器給非過(guò)載節(jié)點(diǎn)。在一對(duì)一方法中，非過(guò)載節(jié)點(diǎn)隨機(jī)選擇一個(gè)節(jié)點(diǎn)進(jìn)行探測(cè)，當(dāng)發(fā)現(xiàn)被探測(cè)節(jié)點(diǎn)是過(guò)載節(jié)點(diǎn)時(shí)轉(zhuǎn)移虛擬服務(wù)器到本節(jié)點(diǎn)。在一對(duì)多和多對(duì)多方法中，系統(tǒng)有d個(gè)目錄服務(wù)節(jié)點(diǎn)用來(lái)保存節(jié)點(diǎn)的負(fù)載信息，由目錄服務(wù)節(jié)點(diǎn)生成負(fù)載轉(zhuǎn)移策略。文獻(xiàn)[6]擴(kuò)展了一對(duì)多和多對(duì)多模式，使算法適應(yīng)了動(dòng)態(tài)P2P系統(tǒng)。然而，此算法在過(guò)載與非過(guò)載節(jié)點(diǎn)間轉(zhuǎn)移虛擬服務(wù)器時(shí)，并沒(méi)有考慮它們之間的位置相近關(guān)系，負(fù)載轉(zhuǎn)移需要消耗過(guò)多的帶寬和延遲。

文獻(xiàn)[7]在結(jié)構(gòu)化P2P系統(tǒng)之上再建立一個(gè)結(jié)構(gòu)（k-nary樹(shù)），由k-nary樹(shù)收集系統(tǒng)負(fù)載信息并生成虛擬服務(wù)器轉(zhuǎn)移策略。此算法考慮了節(jié)點(diǎn)之間的距離相近性，但是復(fù)雜化了P2P系統(tǒng)的覆蓋網(wǎng)絡(luò)，使系統(tǒng)容錯(cuò)能力有所下降；同時(shí)，系統(tǒng)某些節(jié)點(diǎn)（如k-nary樹(shù)的根節(jié)點(diǎn)）的失效將產(chǎn)生單點(diǎn)失敗問(wèn)題。

文獻(xiàn)[8]中每個(gè)資源關(guān)鍵字hash到d（d ≥ 2）個(gè)不同的IDs上，然后在其中選擇負(fù)載最輕的節(jié)點(diǎn)存放資源的索引，而其他d-1個(gè)節(jié)點(diǎn)只存放指向這個(gè)索引的索引。仿真實(shí)驗(yàn)表明，算法在d= O (log N)時(shí)，能達(dá)到最優(yōu)的負(fù)載均衡效果，但沒(méi)有考慮系統(tǒng)在動(dòng)態(tài)環(huán)境下對(duì)算法的影響。

2 基于網(wǎng)絡(luò)定位的負(fù)載均衡算法

本算法主要針對(duì)基于DHT的大規(guī)模P2P計(jì)算網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每一項(xiàng)資源都給系統(tǒng)造成相應(yīng)的負(fù)載（存儲(chǔ)空間、CPU計(jì)算時(shí)間和帶寬等）。作如下合理的假設(shè):a）系統(tǒng)中只有一種瓶頸資源；b）在負(fù)載均衡算法運(yùn)行期間各虛擬服務(wù)器的負(fù)載不變。

2.1 相關(guān)概念

1）虛擬服務(wù)器（virtual servers）

本算法利用了虛擬服務(wù)器。虛擬服務(wù)器的概念在Chord/CFS中作為一種負(fù)載均衡的方法被提出。一個(gè)虛擬服務(wù)器相當(dāng)于一個(gè)DHT節(jié)點(diǎn)，并負(fù)責(zé)一塊連續(xù)的ID空間。而一個(gè)物理DHT節(jié)點(diǎn)可以擁有m個(gè)虛擬服務(wù)器，所以一個(gè)物理節(jié)點(diǎn)對(duì)應(yīng)的ID空間可能是非連續(xù)的。

DHT節(jié)點(diǎn)之間以虛擬服務(wù)器為單位進(jìn)行負(fù)載轉(zhuǎn)移。當(dāng)某個(gè)物理節(jié)點(diǎn)過(guò)載時(shí)，該物理節(jié)點(diǎn)對(duì)應(yīng)的一個(gè)或多個(gè)虛擬服務(wù)器將被轉(zhuǎn)移到非過(guò)載節(jié)點(diǎn)上。同時(shí)，虛擬服務(wù)器的轉(zhuǎn)移可以由DHT的離開(kāi)和加入操作來(lái)實(shí)現(xiàn)，無(wú)須引入新的操作。利用虛擬服務(wù)器可以很方便地在任意兩個(gè)節(jié)點(diǎn)之間進(jìn)行負(fù)載轉(zhuǎn)移。

2）網(wǎng)絡(luò)定位(network positioning)

如今，網(wǎng)絡(luò)定位算法^[9~12]已經(jīng)廣泛應(yīng)用于產(chǎn)生因特網(wǎng)節(jié)點(diǎn)間的物理位置信息。網(wǎng)絡(luò)定位算法分為兩種，即基于基礎(chǔ)設(shè)施的（infrastructured-based）和不基于基礎(chǔ)設(shè)施的（infrastructured-less）。前者（如GNP^[9]）使用路標(biāo)節(jié)點(diǎn)作為參考節(jié)點(diǎn)；后者（如Vivaldi^[10]）中的任何節(jié)點(diǎn)都是其他節(jié)點(diǎn)的參考節(jié)點(diǎn)。本文使用第一種網(wǎng)絡(luò)定位算法的思想：物理位置相近的節(jié)點(diǎn)到指定的一組參考節(jié)點(diǎn)（路標(biāo)）有相近的距離信息，并作了適當(dāng)?shù)母膭?dòng)，以使它更好地應(yīng)用于本算法。

在一個(gè)基于DHT的結(jié)構(gòu)化網(wǎng)絡(luò)中，路標(biāo)節(jié)點(diǎn)可以從本結(jié)構(gòu)化網(wǎng)絡(luò)中選擇，也可以在因特網(wǎng)中任意選擇。假設(shè)有m個(gè)路標(biāo)節(jié)點(diǎn)，一個(gè)DHT節(jié)點(diǎn)A到它們的距離可表示成A的網(wǎng)絡(luò)坐標(biāo)〈d1，d2，…，dm〉。如果把節(jié)點(diǎn)A的網(wǎng)絡(luò)坐標(biāo)映射到m維笛卡兒空間上，這個(gè)笛卡兒空間就叫路標(biāo)空間。根據(jù)網(wǎng)絡(luò)定位技術(shù)^[13，14]，兩個(gè)物理位置相近的DHT節(jié)點(diǎn)A和B有相近的網(wǎng)絡(luò)坐標(biāo)，并且在路標(biāo)空間上的位置也是相近的。路標(biāo)節(jié)點(diǎn)越多，相近性誤差就越小。實(shí)驗(yàn)表明利用15個(gè)路標(biāo)節(jié)點(diǎn)足夠產(chǎn)生相近性誤差極小的坐標(biāo)信息。本算法實(shí)驗(yàn)將使用15個(gè)路標(biāo)節(jié)點(diǎn)，然后利用網(wǎng)絡(luò)定位技術(shù)，把十五維坐標(biāo)空間映射到一維坐標(biāo)空間并保存坐標(biāo)的相近性，從而使每一個(gè)DHT節(jié)點(diǎn)A的網(wǎng)絡(luò)坐標(biāo)都對(duì)應(yīng)一個(gè)坐標(biāo)數(shù)。網(wǎng)絡(luò)坐標(biāo)相近的節(jié)點(diǎn)，它們對(duì)應(yīng)的坐標(biāo)數(shù)大小也是相近的。

3）聚集系數(shù)（cluster coefficient）

節(jié)點(diǎn)的聚集系數(shù)可以反映網(wǎng)絡(luò)的局部密度。聚集系數(shù)越大，局部密度越高。聚集系數(shù)定義為 CC=(｜E(Γv)｜)/(C2kv)。其中:Γv={i:d(i，v)=1}；v為取得的中心點(diǎn)。本算法根據(jù)聚集系數(shù)的大小來(lái)調(diào)整星型結(jié)構(gòu)區(qū)域。

4）利用率（utilization）

節(jié)點(diǎn)A的利用率指A的負(fù)載與A的能力比值，即utlA=load A / capacityA。

節(jié)點(diǎn)A計(jì)算的系統(tǒng)局部利用率指與A物理位置相近的節(jié)點(diǎn)（包括A）的負(fù)載和與能力和之比，即utl_LA=(pi=1load i) / (pi-1capacity i)。其中：p為滿(mǎn)足條件|Hi -HA|<δ（Hi 、HA分別為其他節(jié)點(diǎn)和A節(jié)點(diǎn)的坐標(biāo)數(shù)，δ為常量）的節(jié)點(diǎn)個(gè)數(shù)。

5）與系統(tǒng)利用率的偏差（deviation）

與系統(tǒng)利用率的偏差dev指系統(tǒng)中的節(jié)點(diǎn)利用率與系統(tǒng)利用率utl之差的平方和，即dev=Ni=1(utl i-utl)2。其中：N表示系統(tǒng)中節(jié)點(diǎn)的個(gè)數(shù)。負(fù)載均衡算法的目標(biāo)就是使偏差dev盡量小。

6）負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)（load movement cost）

負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)包括轉(zhuǎn)移一定負(fù)載所消耗的帶寬和鏈路延遲時(shí)間。負(fù)載轉(zhuǎn)移消耗的帶寬可以通過(guò)負(fù)載轉(zhuǎn)移經(jīng)過(guò)的跳數(shù)來(lái)計(jì)算。負(fù)載轉(zhuǎn)移的延遲是轉(zhuǎn)移負(fù)載的大小與轉(zhuǎn)移時(shí)節(jié)點(diǎn)之間延遲的乘積和，即C=Si=1load i×lat i。其中：S表示轉(zhuǎn)移負(fù)載的個(gè)數(shù)。

2.2 算法過(guò)程

2.2.1 構(gòu)建星型結(jié)構(gòu)

本算法利用改進(jìn)的分布式網(wǎng)絡(luò)定位技術(shù)產(chǎn)生的坐標(biāo)數(shù)作為節(jié)點(diǎn)的IDs。文獻(xiàn)[9]研究表明，網(wǎng)絡(luò)坐標(biāo)相近的節(jié)點(diǎn)，物理位置也相近，并且路標(biāo)節(jié)點(diǎn)越多，相近性誤差就越小。由于從網(wǎng)絡(luò)坐標(biāo)映射到坐標(biāo)數(shù)時(shí)，保存了節(jié)點(diǎn)間物理位置的相近性關(guān)系，坐標(biāo)數(shù)（IDs）相近的節(jié)點(diǎn)，物理位置也相近。基于網(wǎng)絡(luò)定位的負(fù)載均衡算法中，結(jié)構(gòu)化P2P系統(tǒng)的每一個(gè)節(jié)點(diǎn)周期性地計(jì)算系統(tǒng)局部利用率utl_LA和負(fù)載轉(zhuǎn)移閾值TA（ TA=(utl_LA+ε)×CA。其中：utl_LA為系統(tǒng)局部利用率；CA為節(jié)點(diǎn)A的能力；ε為可調(diào)參數(shù)），ε用來(lái)在負(fù)載均衡質(zhì)量和負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)之間取得折中，ε為0時(shí)，負(fù)載均衡質(zhì)量最好，但此時(shí)負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)也最大。當(dāng)節(jié)點(diǎn)A的負(fù)載LA小于TA時(shí)， 節(jié)點(diǎn)A通知坐標(biāo)數(shù)滿(mǎn)足條件|Hi-HA|<δ（Hi 、HA分別為其他節(jié)點(diǎn)和本節(jié)點(diǎn)的坐標(biāo)數(shù)，δ為常量）的節(jié)點(diǎn)，并以A為中心構(gòu)造一個(gè)星型結(jié)構(gòu)，如圖1所示。

同時(shí)，節(jié)點(diǎn)A獲得周?chē)恳粋€(gè)過(guò)載節(jié)點(diǎn)需要轉(zhuǎn)移的虛擬服務(wù)器的索引及其負(fù)載大小，并按負(fù)載從小到大的順序排列成一個(gè)鏈表a；同樣，節(jié)點(diǎn)A也會(huì)獲得周?chē)恳粋€(gè)負(fù)載較輕節(jié)點(diǎn)能夠接受的負(fù)載數(shù)量(Ti-Li)，包括節(jié)點(diǎn)A本身，并按負(fù)載數(shù)從小到大的順序排成一個(gè)鏈表b。仿真實(shí)驗(yàn)表明，δ值為CC×log(N)時(shí)具有良好的負(fù)載均衡效果。這個(gè)過(guò)程的偽代碼如下:

//以A為中心組織一個(gè)星型結(jié)構(gòu)和鏈表a，b

Procedure organize_starlike_structure(A，a，b)

{

i=A;

do{

if(i∈(|HA-Hi|<δ))

通知i加入到A組織的星型結(jié)構(gòu)中;

if(Li>Ti)

a.join(指向i的虛擬服務(wù)器的指針，虛擬服務(wù)器負(fù)載);

//加入鏈表a

if(Li

b.join(指向i的指針，i的剩余能力); //加入鏈表b

i=i.successor;

}while(i!=A);

return;

}

2.2.2 生成負(fù)載轉(zhuǎn)移策略

系統(tǒng)中負(fù)載較輕節(jié)點(diǎn)完成星型結(jié)構(gòu)和鏈表a、b的組織之后，進(jìn)行負(fù)載轉(zhuǎn)移。步驟如下：

a）鏈表a中的每一個(gè)虛擬服務(wù)器V與鏈表b里符合條件 (Ti-Li)≥load(V)中(Ti-Li)值最小的節(jié)點(diǎn)匹配。

b）利用DHT中的離開(kāi)和加入操作把虛擬服務(wù)器從過(guò)載節(jié)點(diǎn)轉(zhuǎn)移到負(fù)載較輕節(jié)點(diǎn)，并刪除a、b鏈表中相應(yīng)的節(jié)點(diǎn)。

c）循環(huán)執(zhí)行前面兩個(gè)步驟，直到鏈表a為空或者星型結(jié)構(gòu)中沒(méi)有節(jié)點(diǎn)能夠接收剩下的虛擬服務(wù)器(鏈表a不為空)。這時(shí)，節(jié)點(diǎn)A通知其他各節(jié)點(diǎn)解散星型結(jié)構(gòu)。

對(duì)于大規(guī)模網(wǎng)絡(luò)，如果需要加快負(fù)載的擴(kuò)散能力，當(dāng)匹配完成后，鏈表a不為空，即還有虛擬服務(wù)器沒(méi)有被轉(zhuǎn)移。這時(shí)可以拓展星型結(jié)構(gòu)，即通知δ≤|Hi-HA|<η的節(jié)點(diǎn)與原來(lái)不能進(jìn)行負(fù)載轉(zhuǎn)移的過(guò)載節(jié)點(diǎn)構(gòu)成星型結(jié)構(gòu)，并按上面的方法進(jìn)行負(fù)載轉(zhuǎn)移。轉(zhuǎn)移完成后，解散星型結(jié)構(gòu)。算法的偽代碼如下:

//節(jié)點(diǎn)A運(yùn)行負(fù)載轉(zhuǎn)移算法

Procedure Load_balancing_Algorithm(A，a，b)

{

if(LA

{

organize_starlike_structure( A，a，b);

把鏈表a，b從小到大排列;

p=a; q=b;//a，b分別為虛服務(wù)器鏈表和剩余能力鏈表

while(p)

{

while(q)

{

if(p.L

{

把p指向的虛擬服務(wù)器轉(zhuǎn)移到q指向的接收節(jié)點(diǎn);

S=p.next;

T=q.next;

delete p and q ;

p=S;

q=T;

break;

}

q=q.next;

}

if (!q) p=q;

}

}

解散星型結(jié)構(gòu);

}

基于網(wǎng)絡(luò)定位的負(fù)載均衡算法中，負(fù)載的轉(zhuǎn)移可以利用DHT中的離開(kāi)和加入操作來(lái)完成，無(wú)須引入新的操作。同時(shí)需要轉(zhuǎn)移的虛擬服務(wù)器索引和負(fù)載過(guò)輕節(jié)點(diǎn)的剩余能力按從小到大的順序分布在鏈表中排列，從而生成負(fù)載轉(zhuǎn)移策略的速度非常快。另外，負(fù)載在物理位置相近的節(jié)點(diǎn)之間進(jìn)行，大大地節(jié)約了系統(tǒng)帶寬和延時(shí)等資源。系統(tǒng)中的節(jié)點(diǎn)周期性地執(zhí)行負(fù)載均衡算法，所以本算法能夠適應(yīng)動(dòng)態(tài)P2P系統(tǒng)。

3 仿真實(shí)驗(yàn)及性能分析

3.1 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)在結(jié)構(gòu)化P2P系統(tǒng)的Chord協(xié)議上實(shí)現(xiàn)。實(shí)驗(yàn)中，Chord具有32 bit的ID空間，并且虛擬服務(wù)器對(duì)應(yīng)的ID空間大小是呈指數(shù)分布的^[13]。實(shí)驗(yàn)用Pareto分布來(lái)產(chǎn)生各虛擬服務(wù)器的負(fù)載，由于Pareto分布的重尾（heavy-tailed）性，算法有效性的驗(yàn)證是在最不利于負(fù)載均衡的情況下進(jìn)行的^[6]。其他具體參數(shù)的設(shè)置如表1所示。

表 1 模擬環(huán)境及算法參數(shù)

環(huán)境參數(shù)默認(rèn)值系統(tǒng)利用率0.8虛擬服務(wù)器負(fù)載Pareto:shape=1.5，scale=0.295 3節(jié)點(diǎn)能力Clipped Pareto:shape=2，scale=150節(jié)點(diǎn)數(shù)2 048負(fù)載移動(dòng)開(kāi)銷(xiāo)與虛擬服務(wù)器負(fù)載成正比路標(biāo)節(jié)點(diǎn)數(shù)15εCC×log(N)每個(gè)節(jié)點(diǎn)的虛擬服務(wù)器數(shù)12算法運(yùn)行周期60 s實(shí)驗(yàn)中，對(duì)MIT的kingdata數(shù)據(jù)庫(kù)中的mking-t拓?fù)湮募髁诉m當(dāng)?shù)臄U(kuò)展，并使用它作為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。Mking-t拓?fù)浣Y(jié)構(gòu)是現(xiàn)有網(wǎng)絡(luò)的一部分，在它上面運(yùn)行基于網(wǎng)絡(luò)定位的負(fù)載均衡算法能充分說(shuō)明算法的有效性和實(shí)用性。

3.2 算法性能分析

1)負(fù)載均衡效果

圖2是負(fù)載均衡效果圖。負(fù)載均衡過(guò)程中的系統(tǒng)利用率為0.8。負(fù)載均衡之前，節(jié)點(diǎn)利用率與系統(tǒng)利用率的偏差(dev)為957.12;負(fù)載均衡之后，dev下降為12.58，比負(fù)載均衡之前下降了98.68%。從圖 2可以看出，基于網(wǎng)絡(luò)定位的負(fù)載均衡算法可以得到理想的負(fù)載均衡效果。

2)負(fù)載轉(zhuǎn)移的開(kāi)銷(xiāo)

圖3是負(fù)載轉(zhuǎn)移帶寬消耗累積分布圖。實(shí)驗(yàn)通過(guò)轉(zhuǎn)移虛擬服務(wù)器經(jīng)過(guò)的跳數(shù)來(lái)衡量負(fù)載轉(zhuǎn)移需消耗的帶寬。從圖中可以看出，考慮節(jié)點(diǎn)間的物理位置相近關(guān)系時(shí)，在兩跳之內(nèi)可以轉(zhuǎn)移68%的負(fù)載，十跳之內(nèi)可以轉(zhuǎn)移89%的負(fù)載。而不考慮節(jié)點(diǎn)間的物理位置相近關(guān)系時(shí)，十跳之內(nèi)只轉(zhuǎn)移了15%的負(fù)載。從以上的比較可以看出，基于網(wǎng)絡(luò)定位的負(fù)載均衡算法能夠有效地在物理位置相近的節(jié)點(diǎn)之間進(jìn)行負(fù)載轉(zhuǎn)移，從而減少轉(zhuǎn)移負(fù)載所需要的跳數(shù)，達(dá)到節(jié)省帶寬的目的。

圖 4是負(fù)載轉(zhuǎn)移延遲消耗累積分布圖。從圖中可以看到，當(dāng)考慮節(jié)點(diǎn)間的物理位置相近關(guān)系時(shí)，62%的負(fù)載轉(zhuǎn)移在鏈路延遲小于50的節(jié)點(diǎn)之間進(jìn)行，98%的負(fù)載轉(zhuǎn)移在鏈路延遲小于200的節(jié)點(diǎn)之間進(jìn)行；當(dāng)不考慮節(jié)點(diǎn)間的物理位置相近關(guān)系時(shí)，只有19%的負(fù)載轉(zhuǎn)移在鏈路延遲小于200的節(jié)點(diǎn)之間進(jìn)行。從以上可以看出，基于網(wǎng)絡(luò)定位的負(fù)載均衡算法可以節(jié)省負(fù)載轉(zhuǎn)移所耗費(fèi)的時(shí)間，加快負(fù)載轉(zhuǎn)移速度。

3)系統(tǒng)利用率對(duì)負(fù)載均衡效果的影響

負(fù)載轉(zhuǎn)移因子(load movement factor)定義為負(fù)載轉(zhuǎn)移總的開(kāi)銷(xiāo)與系統(tǒng)中所有負(fù)載移動(dòng)一次時(shí)的總開(kāi)銷(xiāo)之比(只考慮延遲開(kāi)銷(xiāo))。例如，負(fù)載移動(dòng)因子為0.1時(shí)，表示負(fù)載轉(zhuǎn)移消耗的帶寬是初始插入這些負(fù)載時(shí)的10%。

99.9百分位節(jié)點(diǎn)利用率(99.9th percentile node utilization)定義為一個(gè)利用率，它大于99.9%的節(jié)點(diǎn)利用率。節(jié)點(diǎn)i的利用率為其負(fù)載與能力之比:ui=Li/Ci。

從圖 5可以看出，每一條線(xiàn)代表一個(gè)特定的系統(tǒng)利用率。每一個(gè)點(diǎn)表示負(fù)載均衡周期在60~1 200 s時(shí)取得的一個(gè)值。經(jīng)過(guò)負(fù)載均衡后，即使系統(tǒng)高達(dá)0.912，仍然可保持99.9%的節(jié)點(diǎn)非過(guò)載，并且其中有一個(gè)負(fù)載轉(zhuǎn)移因子小于0.08。

4 結(jié)束語(yǔ)

本文針對(duì)結(jié)構(gòu)化P2P系統(tǒng)中的負(fù)載均衡問(wèn)題提出了一種基于網(wǎng)絡(luò)定位的負(fù)載均衡算法。算法由負(fù)載較輕的節(jié)點(diǎn)負(fù)責(zé)主要的負(fù)載轉(zhuǎn)移操作，節(jié)省了過(guò)載節(jié)點(diǎn)的資源，提高了負(fù)載轉(zhuǎn)移質(zhì)量。同時(shí)，負(fù)載轉(zhuǎn)移在物理位置相近的節(jié)點(diǎn)之間進(jìn)行，減少了負(fù)載轉(zhuǎn)移的開(kāi)銷(xiāo)（帶寬、延遲）。本算法的優(yōu)勢(shì)有:

a）解決了P2P系統(tǒng)中負(fù)載分布與節(jié)點(diǎn)能力不一致的問(wèn)題，并能達(dá)到理想的均衡效果。

b）由負(fù)載較輕的節(jié)點(diǎn)負(fù)責(zé)主要的負(fù)載轉(zhuǎn)移操作，節(jié)省了過(guò)載節(jié)點(diǎn)的資源，因?yàn)檫^(guò)載節(jié)點(diǎn)本身負(fù)載量就比較大，在負(fù)載轉(zhuǎn)移過(guò)程中，應(yīng)該把它們所消耗的資源減到最少。

c）負(fù)載轉(zhuǎn)移在物理位置相近的一個(gè)節(jié)點(diǎn)區(qū)域間進(jìn)行，減少了負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)。仿真實(shí)驗(yàn)表明負(fù)載轉(zhuǎn)移開(kāi)銷(xiāo)減少了40%以上。

d）算法無(wú)須修改已有拓?fù)浣Y(jié)構(gòu)和引入額外的操作，負(fù)載轉(zhuǎn)移操作借助DHT中節(jié)點(diǎn)的離開(kāi)和加入操作就可以完成。

參考文獻(xiàn)：

[1]KARGER D， LEHMAN E， LEIGHTON T，et al.Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proc of the 29th Annual ACM Symposium on Theory of Computing. Texas：[s.n.]，1997:654-663.

[2]SAROIU S， GUMMADI P K， GRIBBLE S D. A measurement study of peer-to-peer file sharing systems[C]//KIENZLE M G， SHENOY P J.Procof Multimedia Computing and Networking Conference.San Jose: SPIE， 2002: 156-170.

[3]STOICA I， MORRIS R， KARGER D， et al. Chord: a scalable peer-to-peer lookup service for Internet applications [J].Computer Communication Review，2001， 31(4): 149-160.

[4]DABEK F， KAASHOEK M F， KARGER D， et al.Wide-area coo- perative storage with CFS [C]//Proc of the 18th ACM Symp Operating Systems Principles (SOSP). Banff:[s.n.]，2001: 202-215.

[5]RAO A， LAKSHMINARAYANAN K， SURANA S， et al.Load balan- cing in structured P2P systems[C]//Proc of IPTPS. Berkeley:[s.n.]，2003:68-79.

[6]GODFREY B， LAKSHMINARAYANAN K， SURANA S， et al.Load balancing in dynamic structured P2P systems[C]//Proc of IEEE INFOCOM. Hong Kong:[s.n.]，2004:46-50.

[7]ZHU Y，HU Y M.Efficient， proximity-aware load balancing for DHT-based P2P systems[J]. IEEE Trans on Parallel and Distributed Systems，2005， 16(4):349- 361.

[8]BYERS J， CONSIDINE J， MITZENMACHER M. Simple load balancing for distributed hash tables[C]//Proc of IPTPS. Berkeleg:[s.n.]，2003:80-87.

[9]NG E，ZHANG H.Predicting Internet network distance with coordinates-based approaches[C]//Proc of the 21st Annual Joint Confe-rence of the IEEE Computer and Communications Societies，2002:170-179.

[10]COX R， DABEK F， KAASHOEK F， et al. Practical， distributed network coordinates[C]//Proc of the 2nd Workshop on Hot Topics in Networks (HotNets-II).2003:113 -118.

[11]COSTA M， CASTRO M， ROWSTRON A， et al. PIC: practical Internet coordinates for distance estimation[C]//Proc of the 24th International Conference on Distributed Computing Systems (ICDCS’04). Washington DC: IEEE Computer Society，2004:178-187.

[12]NG E， ZHANG H.A network positioning system for the Internet[C]//Proc of USENIX Conference.2004:141 -154.

[13]RATHASAMY S， FRANCIS P， HANDLEY M，et al. A scalable content-addressable network[C]//Proc of ACM SIGCOMM’01. San Diego：[s.n.]，2001:161-172.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文