結構化Ｐ２Ｐ系統(tǒng)中基于網絡定位的負載均衡算法

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

關鍵詞：點對點系統(tǒng)； 分布式哈希表； 負載均衡； 星型結構； 網絡定位

中圖分類號：TP393 文獻標志碼：A 文章編號：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)，其中的參與者共享他們所擁有的一部分資源，這些共享資源能被其他對等節(jié)點直接訪問而無須經過中間實體。網絡中的參與者既是資源（服務和內容）提供者，又是資源（服務和內容）獲取者。P2P技術使得網絡上的溝通變得更容易、更直接。P2P改變了目前Internet以太網站為中心的狀態(tài)，重返非中心化，并把權利交還給用戶。

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

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

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

1 相關工作

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

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

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

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

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

2 基于網絡定位的負載均衡算法

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

2.1 相關概念

1）虛擬服務器（virtual servers）

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

DHT節(jié)點之間以虛擬服務器為單位進行負載轉移。當某個物理節(jié)點過載時，該物理節(jié)點對應的一個或多個虛擬服務器將被轉移到非過載節(jié)點上。同時，虛擬服務器的轉移可以由DHT的離開和加入操作來實現(xiàn)，無須引入新的操作。利用虛擬服務器可以很方便地在任意兩個節(jié)點之間進行負載轉移。

2）網絡定位(network positioning)

如今，網絡定位算法^[9~12]已經廣泛應用于產生因特網節(jié)點間的物理位置信息。網絡定位算法分為兩種，即基于基礎設施的（infrastructured-based）和不基于基礎設施的（infrastructured-less）。前者（如GNP^[9]）使用路標節(jié)點作為參考節(jié)點；后者（如Vivaldi^[10]）中的任何節(jié)點都是其他節(jié)點的參考節(jié)點。本文使用第一種網絡定位算法的思想：物理位置相近的節(jié)點到指定的一組參考節(jié)點（路標）有相近的距離信息，并作了適當?shù)母膭樱允顾玫貞糜诒舅惴ā?/p>

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

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

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

4）利用率（utilization）

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

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

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

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

6）負載轉移開銷（load movement cost）

負載轉移開銷包括轉移一定負載所消耗的帶寬和鏈路延遲時間。負載轉移消耗的帶寬可以通過負載轉移經過的跳數(shù)來計算。負載轉移的延遲是轉移負載的大小與轉移時節(jié)點之間延遲的乘積和，即C=Si=1load i×lat i。其中：S表示轉移負載的個數(shù)。

2.2 算法過程

2.2.1 構建星型結構

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

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

//以A為中心組織一個星型結構和鏈表a，b

Procedure organize_starlike_structure(A，a，b)

{

i=A;

do{

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

通知i加入到A組織的星型結構中;

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

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

//加入鏈表a

if(Li

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

i=i.successor;

}while(i!=A);

return;

}

2.2.2 生成負載轉移策略

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

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

b）利用DHT中的離開和加入操作把虛擬服務器從過載節(jié)點轉移到負載較輕節(jié)點，并刪除a、b鏈表中相應的節(jié)點。

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

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

//節(jié)點A運行負載轉移算法

Procedure Load_balancing_Algorithm(A，a，b)

{

if(LA

{

organize_starlike_structure( A，a，b);

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

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

while(p)

{

while(q)

{

if(p.L

{

把p指向的虛擬服務器轉移到q指向的接收節(jié)點;

S=p.next;

T=q.next;

delete p and q ;

p=S;

q=T;

break;

}

q=q.next;

}

if (!q) p=q;

}

}

解散星型結構;

}

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

3 仿真實驗及性能分析

3.1 仿真實驗

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

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

環(huán)境參數(shù)默認值系統(tǒng)利用率0.8虛擬服務器負載Pareto:shape=1.5，scale=0.295 3節(jié)點能力Clipped Pareto:shape=2，scale=150節(jié)點數(shù)2 048負載移動開銷與虛擬服務器負載成正比路標節(jié)點數(shù)15εCC×log(N)每個節(jié)點的虛擬服務器數(shù)12算法運行周期60 s實驗中，對MIT的kingdata數(shù)據庫中的mking-t拓撲文件作了適當?shù)臄U展，并使用它作為網絡拓撲結構。Mking-t拓撲結構是現(xiàn)有網絡的一部分，在它上面運行基于網絡定位的負載均衡算法能充分說明算法的有效性和實用性。

3.2 算法性能分析

1)負載均衡效果

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

2)負載轉移的開銷

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

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

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

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

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

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

4 結束語

本文針對結構化P2P系統(tǒng)中的負載均衡問題提出了一種基于網絡定位的負載均衡算法。算法由負載較輕的節(jié)點負責主要的負載轉移操作，節(jié)省了過載節(jié)點的資源，提高了負載轉移質量。同時，負載轉移在物理位置相近的節(jié)點之間進行，減少了負載轉移的開銷（帶寬、延遲）。本算法的優(yōu)勢有:

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

b）由負載較輕的節(jié)點負責主要的負載轉移操作，節(jié)省了過載節(jié)點的資源，因為過載節(jié)點本身負載量就比較大，在負載轉移過程中，應該把它們所消耗的資源減到最少。

c）負載轉移在物理位置相近的一個節(jié)點區(qū)域間進行，減少了負載轉移開銷。仿真實驗表明負載轉移開銷減少了40%以上。

d）算法無須修改已有拓撲結構和引入額外的操作，負載轉移操作借助DHT中節(jié)點的離開和加入操作就可以完成。

參考文獻：

[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.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文