一種基于節點信息的負載均衡算法

李成森，黃桂敏，周 婭，劉平山

(1.桂林電子科技大學 信息與通信學院,廣西 桂林 541004;2.桂林電子科技大學 計算機與信息安全學院,廣西 桂林 541004)

一種基于節點信息的負載均衡算法

李成森1，黃桂敏1，周 婭2，劉平山2

(1.桂林電子科技大學 信息與通信學院,廣西 桂林 541004;2.桂林電子科技大學 計算機與信息安全學院,廣西 桂林 541004)

在P2P流媒體點播系統中，節點可能收到過多的數據請求造成自身過載，導致網絡節點負載的不均衡，影響了系統的整體性能。為了平衡節點間的負載，通過建立節點的信息列表管理節點的動態負載信息，設計了一種基于請求遷移的負載均衡(LBRM)算法。實驗結果表明，LBRM算法解決了網絡節點負載不均衡，提高了播放質量。

負載均衡；對等網絡；請求遷移

對等網絡(peer to peer，簡稱P2P)的諸多優勢促進了P2P流媒體應用在視頻點播和視頻直播領域的發展[1]，但由于網絡中節點行為的隨意性，每個服務節點所接收到的數據請求量不同，某些節點可能承擔過多的請求任務。節點在處理過多的請求時，用戶請求被延遲甚至丟失，而其他一些節點卻處于空閑狀態，帶寬沒有得到有效利用。同時由于節點的帶寬資源、存儲容量以及網絡環境的差異，各個節點所能承受的請求壓力不同，個別節點因負載過重而失效。因此，必須保持節點間的負載平衡以避免個別節點處理的請求量過多而負載過重，并使其他節點的請求得到穩定快速的回應。

為了管理整個網絡的節點負載信息，文獻[2]采用超級節點管理部分節點的負載信息，然而，節點頻繁地與超級節點進行信息交換可能引起單點瓶頸現象的發生。Yao等[3]提出一種基于局部網絡信息的負載平衡算法提高系統負載平衡的速度，但該算法建立在假設每個節點的能力和存儲容量是一致的基礎上，不符合實際情況。文獻[4]采用隨機步長估算網絡中全局負載信息，但在一個含有N個節點的系統中，為了更精確地估計負載分布的情況，該算法需要使用lg N次隨機步長來輔助計算，增加了算法的復雜度和網絡的開銷。

為了有效地均衡網絡中的負載，避免節點超載，Xiong等[5]提出了一種自適應的負載均衡策略，該策略基于熱門文件創建備用節點用于接收超載節點轉移的負載，但未考慮待轉移請求的緊急性，可能引起轉移請求過期丟失，影響系統的穩定性。Yang等[6]提出一種SQS策略使節點在數據調度時主動向空閑節點發送請求，以避免節點突然收到過多的數據請求，但在系統中周期性檢測節點的請求數量并不準確[7]。Takayama等[8]提出了多屬性范圍查詢方法，其采用隨機抽樣的方式創建近似直方圖來管理節點,但引入了較大的計算開銷。Gupta等[9]提出了一種基于博弈論的激勵機制來改善節點間負載不均衡，但該算法需要獲取網絡全局信息，并且許多方面處于理論假設階段。

為此，提出了一種基于節點信息的負載均衡算法。該算法通過構造節點的信息管理列表，避免使用服務器來管理和傳播節點的負載信息，然后分析節點收到請求的差異性和網絡節點的異構性，采用優先級排序，將優先級低的請求轉移到輕載節點處理。通過節點選擇機制，選擇性能良好、穩定性高的節點作為接收被轉移請求的對象。

1 節點負載均衡策略

1.1 節點負載信息管理

為了方便管理和傳播節點的負載信息，構造一個節點信息管理列表，該表負責保存節點及其鄰居節點的相關信息。節點可通過該列表與其鄰居節點進行負載信息交換。由于節點的鄰居節點個數取20個左右能使網絡中資源共享的效率更高，并且能使系統達到理想的狀態[10]。因此，將20個具有鄰居關系的節點作為一個節點簇，然后生成基于每個節點簇的節點信息表，它們被用來當作節點負載的定義和負載等級的劃分以及負載轉移的依據。節點動態負載信息管理列表如表1所示。表1中記錄了節點負載的相關數據，它包含節點接收的各種數據包的信息，可用于節點負載度的計算。此外，該表還記錄了鄰居節點的能力值與負載狀態，利用這些信息可篩選出能力值大的輕載節點接收負載。其中，ID為節點的標識符，其值由服務器唯一給定，用于區分不同的鄰居節點。

表1 節點動態負載信息管理列表

1.2 節點負載

節點負載度是節點每秒上傳的數據總量占節點的帶寬資源總量的比例，負載越大，則節點所承受的請求壓力越大。

(1)

其中：Li為節點i的帶寬負載；Ui為節點i在t時刻上傳的數據總量，包含表1中各類數據包消息量總和；T為時間周期；t為任一時刻；B為節點的上傳帶寬。節點負載的計算僅依賴本地信息，無須獲取其他信息，計算方便并節省帶寬開銷。

1.3 負載的劃分及負載信息傳播

由于節點負載是動態變化的，因此，管理節點的負載信息是一個難題。解決思路為：將負載劃分為3種類型，當Li>80%為超載，記為類型O；Li<30%為輕載節點，記為類型L；其余記為N。劃分節點負載類型后則無須實時更新節點的負載值，只需關注節點的負載類型變化，有負載類型變更時才進行負載信息更新和傳播。一般在趨于穩態的P2P網絡中，有66%的節點不會對系統做任何貢獻，而20%的節點卻提供98%的共享文件[11]，顯然，提供資源的節點數量較少，負載類型變更的節點不多，因而節點無須頻繁地更新其負載信息。

在P2P點播系統中，擁有相似資源的節點具有鄰居關系，鄰居節點間定期地交換緩存位圖信息，相互告知節點的緩存信息。當請求節點向某一節點簇中的節點發送數據請求時，其所需要的請求資源存在于該節點簇中的其他節點中。因此，節點負載信息只需要在每個節點簇里面相互傳播即可。節點信息的傳播形式主要依靠Biased Gossip通信協議形成以節點簇為基礎的網絡視圖，當有節點負載類型變更時，才對這些節點的信息做局部的傳播和更新，節省了網絡開銷。

1.4 負載轉移

負載轉移的預期目的是節點轉移負載時要盡可能地不影響用戶的播放流暢度。然而，如果節點超載后把一些未經過篩選的請求轉移出去，雖然能緩解節點的負載壓力，但可能會出現這么一種情況：節點錯誤地將特別緊急的請求轉移出去，導致該請求不能得到及時回應，此時請求節點將丟失該數據片。因此，在轉移負載的過程中，不僅要考慮節點的負載情況，還需要考慮所轉移請求的緊急性，才能保證緊急的請求不被丟失。節點在遷移負載的過程中，使用請求優先級來衡量節點處理該請求的優先程度。當節點超載時將其還未處理的請求按優先級從低到高的次序轉移給其他節點處理，以保證用戶播放的流暢度。請求優先級包含了數據片稀缺度和請求的緊急度。

(2)

其中：Rj為數據片j的稀缺度；N為鄰居節點數量；M[k][j]為鄰居節點k是否丟失或未緩存有數據片j的情況，若鄰居節點k未緩存數據片j，則M[k][j]=0，否則M[k][j]=1。網絡中丟失該數據片的節點越多，就應越優先去處理，以降低數據片的稀有度，提升資源共享效率。

請求的緊急度

(3)

其中：Qj為節點請求的數據片j的序號；P為節點當前播放數據片的序號；S為視頻中數據片的總數。由式(3)可知，Qj越接近P，則表示該數據請求越緊急。由式(2)、(3)可知，請求的優先級

Pj=Uj×Rj。

(4)

1.5 目標節點選擇

在請求遷移的最后，需要分析如何選擇合適的輕載節點作為負載的接收者。節點選擇的目的是盡可能選擇可用帶寬大且穩定的節點作為負載的接收者，并采用節點的能力值函數作為選擇的依據。然而，節點不會自動知道自身的上傳帶寬[12]。換句話說，若超載節點在轉移負載的時候還要去測量其他節點的可用帶寬，勢必會影響信息的時效性，導致測量結果不準確。為了不發生額外的信息交換，節點通過記錄其歷史最大上傳速度的方式來預測節點所能提供帶寬的能力。此外，節點的能力值計算還要考慮其在線時長。節點的在線概率服從對數正態分布[13]。

(5)

其中：f(t)為節點的在線概率；μ為節點在線時長的均值；σ為節點在線時長的標準差。

為了更好地說明節點的穩定性，在節點能力值的計算中還需考慮其他因素，即節點i的最大上傳速度Si和上傳的數據片總量Pi。綜上所述，節點的能力值為

Wi=f(t)(Si+Pi)。

(6)

節點的f(t)值越大，則節點未來的在線時間越長。評估f(t)和Pi參數的值預示節點的穩定性，而當節點處于輕載狀態時，Si越大則預示著它的可用帶寬就越大。

基于上述對負載均衡策略的相關分析，LBRM算法基本流程如下:

當節點剛剛變為超載節點時，超載節點將其還未處理的請求按優先級從低到高的順序排列，然后將優先級低的請求作為轉移的對象。超載節點根據緩存位圖了解其鄰居節點的緩存信息，選擇能力值高的鄰居節點來轉移請求，而當該鄰居節點由于持續地接收負載使得自身的負載狀態由L轉向N時，又發起新一輪的負載類型更新。節點重新更新鄰居節點的負載信息和能力值并重新排列，并選擇新的節點來接收被轉移的數據請求。若鄰居節點中無輕載節點，則選擇N狀態的節點進行傳輸，而當該節點由N轉到O狀態后進行新一輪的數據更新時，則舍棄該節點選擇其他節點進行請求的遷移。

2 實驗結果與分析

為了評估LBRM算法的性能，將其與SQS算法[6]和SALB算法[5]做了對比實驗。實驗從播放流暢度，平均上行帶寬利用率，超載節點比例3個方面對算法的性能進行對比和分析。

實驗采用PeerSim工具評估LBRM算法，其參數設置為：1)在網絡中放置3000個節點和500個共享視頻，節點的上傳帶寬隨機設置為70～200 kbit/s。2)設置Tracker服務器上傳帶寬為20 Mbit/s，延時為10 ms。

2.1 上傳帶寬利用率

由于超載節點將其負載轉移給空閑的輕載節點，網絡節點的帶寬利用率相對提高。在實驗中，采用CDF描繪3種算法在節點上傳帶寬利用率上的表現，如圖1所示。

圖1 節點上傳帶寬利用率Fig.1 Upload bandwidth utilization of nodes

從圖1可看出，在使用LBRM算法的系統中，大約30%的節點的上傳帶寬利用率小于0.5，而在使用SQS和SALB算法中的比例卻分別達到了95%和57%。這是因為SQS算法主要是優先向低負載的節點發送請求，所以網絡中大部分節點的負載都處在一個比較低的均值。而SALB算法中用于接受負載的可選對象相對較少，所以低的帶寬利用率的節點數量比LBRM算法多。通過觀察圖1中0.6～0.8內的節點總數，LBRM算法要比其他2種算法多。可見，LBRM算法優于SQS算法和SALB算法。

2.2 節點播放流暢度

播放流暢度是指節點在開始播放視頻后，各時間段內節點所獲得數據與應獲得數據的比值[12]，它反映了用戶播放視頻的流暢程度。該值越高，表示視頻播放越流暢。3種算法在播放流暢度方面的比較如圖2所示。

圖2 播放流暢度Fig.2 Playback fluency

從圖2可看出，3種算法隨著節點數量的增加，播放質量有所提升。原因是節點數量的增多使得可選的輕載節點數量變多，節點負載的轉移更加方便。當節點的數量超過1000后，SQS算法的播放質量無太大的提升，這是因為它未考慮請求的緊急性和接收者的帶寬，使得請求得到及時回應的幾率不高。因此，使用LBRM算法能獲得更高的播放流暢度。

2.3 超載節點比例

超載節點比例是指單位時間內網絡中超載節點數量占節點總數的比例，它反映了系統中超載節點數量的變化情況以及不同算法在均衡節點負載上的效果。單位時間內系統中的超載節點數量減少得越多，說明該負載平衡算法越有效。3種算法在超載節點比例對比如圖3所示。

實驗中，當網絡中超載節點數量占節點總數的10%時，開始記錄3種算法的數據，在0～100 s，使用LBRM算法和SQS算法的網絡中，超載節點的數量明顯降低，SALB算法中超載節點數量減少的速度比前2種算法要慢。這是因為LBRM算法使用的是直接轉移請求方法，SQS算法則是直接更改發送請求的方式向低負載的節點發送請求，所以改善速率較快。而SALB算法則需要根據待轉移的請求建立后備節點，然后開始轉移負載，效率較低。在300～500 s，由于SQS算法在請求發送的問題上不考慮接收者的帶寬和承受能力，負載重的節點數量依然比LBRM算法多。因此，LBRM算法在降低網絡超載節點的速度和效率上要優于其他2種算法。

圖3 網絡負載平衡度Fig.3 Network load balancing index

3 結束語

在P2P流媒體點播系統中，節點負載均衡算法能降低超載節點的負載，并提升輕載節點的帶寬利用率。LBRM算法主要通過劃分鄰居節點簇和節點負載類型切換的方式管理網絡中節點的負載信息，同時利用分布式節點層的優勢，減輕服務器負載。此外，該算法還考慮了轉移負載過程中請求的緊急性，避免了傳統的負載均衡策略中由于轉移負載造成的數據片的丟失。該算法利用節點的能力值選出合適的節點作為請求轉移的接收者。通過這些措施，該算法解決了網絡中節點負載不均的問題。仿真實驗結果表明，該負載均衡算法能均衡網絡中節點的負載。

[1] QIAO Y,BOCHMANN G.Load balancing in peer-to-peer systems using a diffusive approach[J].Computing,2012,94(8-10):649-678.

[2] GRAFFI K,KAUNE S,PUSSEP K,et al.Load balancing for multimedia streaming in heterogeneous peer-to-peer systems[C]//Proceedings of the 18th International Workshop on Network and Operating Systems Support for Digital Audio and Video,2008:99-104.

[3] YAO L,DAI G Z,ZHANG H X,et al.Load balancing algorithm for P2P systems based on partial network information[J].Journal of Computer Applications,2007,27(5):1080-1082.

[4] BHARAMBE A R,AGRAWAL M,SESHAN S.Mercury:supporting scalable multi-attribute range queries[J]//SIGCOMM Computer Communication Review,2004, 34(4):353-366.

[5] XIONG N,XU K,CHEN L,et al.An effective self-adaptive load balancing algorithm for peer-to-peer networks[C]//26th IEEE International Conference on Parallel and Distributed Processing Symposium Workshops & PhD Forum,2012:1425-1432.

[6] YANG S,SHEN Y,QU W,et al.A novel on-demand streaming service based on improved bittorrent[C]//Fifth IEEE International Conference on Frontier of Computer Science and Technology,2010:46-50.

[7] YANG Y,CHOW A L H,GOLUBCHIK L,et al. Improving QoS in bittorrent-like VoD systems[C]//Proceedings of INFOCOM,2010:1-9.

[8] TAKAYAMA K,FUJIMOTO T,ENDO R,et al.Neighbor selection based on transmission bandwidth on P2P live streaming service[C]// 26th IEEE International Conference on Advanced Information Networking and Applications Workshops,2012:105-110.

[9] GUPTA R,SOMANI A K.Game theory as a tool to strategize as well as predict nodes' behavior in peer-to-peer networks[C]//11th IEEE International Conference on Parallel and Distributed Systems,2005:244-249.

[10] YING H,ZHIGANG C.USMI:an ultra-node selection mechanism with incentive in P2P network[C]//13th IEEE International Conference on Multimedia Information Networking and Security,2010:131-135.

[11] WANG Y, FU T Z J, CHIU D M. Design and evaluation of load balancing algorithms in P2P streaming protocols[J].Computer Networks,2011,55(18):4043-4054.

[12] VLAVIANOS A,ILIOFOTOU M,FALOUTSOS M.BiToS:Enhancing BitTorrent for supporting streaming applications[C]//25th IEEE International Conference on Computer Communications,2006:1-6.

[13] VELOSO E,ALMEIDA V,MEIRA W,et al. A hierarchical characterization of a live streaming media workload[C]//Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurment,2002:117-130.

編輯：曹壽平

A load balancing algorithm based on node information

LI Chengsen1, HUANG Guimin1, ZHOU Ya2, LIU Pingshan2

(1.School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China;2.School of Computer and Information Security, Guilin University of Electronic Technology, Guilin 541004, China)

In P2P VoD systems, the nodes may receive too many data request and result in overload, this phenomenon leads to the imbalance of network load of nodes and affects performance of the system. In order to balance the load between nodes, a management list of the nodes information is established to manage the dynamic load information of nodes. Based on the load information, a load balancing algorithm based on request migration(LBRM) is proposed. Experimental result indicates that LBRM can solve load imbalance of nodes in network and improve play back quality.

load balance; peer to peer; request migration

2016-03-10

國家自然科學基金(61063038)

黃桂敏(1967-)，男，廣西桂林人，教授，博士，研究方向為計算機網絡、自然語言處理。E-mail:sen_5200@163.com

李成森，黃桂敏，周婭，等.一種基于節點信息的負載均衡算法[J].桂林電子科技大學學報，2016,36(6):449-453.

TN311

A

1673-808X(2016)06-0449-05