劉立幫，黃 剛

(南京郵電大學 計算機學院，江蘇 南京 210003)

一種多層網(wǎng)絡下動態(tài)負載均衡算法

劉立幫，黃 剛

(南京郵電大學 計算機學院，江蘇 南京 210003)

分布式系統(tǒng)由若干個獨立的節(jié)點組成，一些節(jié)點由于接收到大量請求而過載，還有一些節(jié)點卻負擔較少的請求任務。通過負載均衡技術可以使節(jié)點間的負載分配更加合理，最大化利用服務器集群的處理能力，達到擴展服務器集群的帶寬和增加吞吐量,加強網(wǎng)絡數(shù)據(jù)處理能力,提高網(wǎng)絡的靈活性和可用性的目的。傳統(tǒng)的集中式負載均衡方案采用靜態(tài)負載均衡算法，由控制器全權負責任務分配。它的優(yōu)點是功耗低而且穩(wěn)定性強，缺點則是負載均衡效果不是最佳，總體處理速度較慢，中央控制器節(jié)點由于負擔重容易成為系統(tǒng)瓶頸。同時，它的系統(tǒng)擴展在大規(guī)模集群中表現(xiàn)差。相比之下完全分布式方案是可擴展的，由于所有節(jié)點既是處理節(jié)點，也是分發(fā)器，而調度器只負責任務調度，從而減輕了控制器的負擔，避免成為系統(tǒng)瓶頸。提出了一種異構分布式計算系統(tǒng)集群的負載均衡策略。該算法采集各個節(jié)點CPU使用率、存儲器使用率兩個系統(tǒng)參數(shù)，以決定各節(jié)點的工作量。同時，設計兩層結構，解決全局通信負擔較重的問題。仿真結果表明，該算法有效提高了負載均衡的效率。

集群負載均衡；分布式系統(tǒng)；異構網(wǎng)絡；節(jié)點虛擬化

0 引 言

隨著用戶需求的增長和云計算的日益普及，以及Internet上廣泛的分布式應用對服務質量(QoS)需求的增長,各種服務應用對網(wǎng)絡所能提供的QoS提出了更高的要求。與此同時，企業(yè)間的競爭也要求服務提供商能提供更加快速、穩(wěn)定的服務[1]。通過負載均衡(Load Balance)技術可以使節(jié)點間的負載分配更加合理，最大化利用服務器集群的處理能力，達到擴展服務器集群的帶寬和增加吞吐量,加強網(wǎng)絡數(shù)據(jù)處理能力,提高網(wǎng)絡的靈活性和可用性的目的。服務器集群通過負載均衡技術可以將大量的數(shù)據(jù)流量和并發(fā)訪問均衡分攤到多個節(jié)點分別進行處理，以減少用戶等待和用戶響應時間，并將單個負載較重節(jié)點的運算分攤到多個節(jié)點進行并行處理，最大化地發(fā)揮集群的運算和服務能力。

1 概 述

分布式系統(tǒng)是若干獨立計算機的集合，主要目的是使用戶能夠方便地訪問、獲取遠程資源，這些資源包括計算機、存儲設備、數(shù)據(jù)、文件、Web網(wǎng)頁以及網(wǎng)絡。因為在提供這些資源的系統(tǒng)中的服務節(jié)點存在巨大差異，所以，討論分布式環(huán)境下的負載均衡問題首先要考慮系統(tǒng)中各個計算機之間的差別，以及計算機之間通信方式的差別。

進一步講，環(huán)境的動態(tài)網(wǎng)絡拓撲也并非固定。這項工作的重點是設計一種考慮分布式環(huán)境的動態(tài)、可擴展性和異構性的負載均衡算法。

研究人員對于分布式計算系統(tǒng)負載均衡問題進行了深入研究，對于該問題通常有兩種方法：

(1)靜態(tài)負載平衡方法。它取決于靜態(tài)信息，例如CPU能力、內存性能等來做出負載平衡決策。

(2)動態(tài)負載平衡策略[2-3]。該方法嘗試獲取系統(tǒng)的當前狀態(tài)，并以此為依據(jù)做出決策，因此，能夠進一步提高系統(tǒng)性能。

傳統(tǒng)的負載均衡算法，比如隨機法、輪轉調度算法[4](Round-Robin scheduling,RR)、最小連接數(shù)法(Least-Connection scheduling,LC)等，也有一些基于這些傳統(tǒng)算法改進而來的算法，這些算法在海量的請求壓力和復雜的異構網(wǎng)絡環(huán)境下顯得力不從心。

DLB算法被提出[5-12]以監(jiān)視資源利用率，即，CPU、內存磁盤、I/O等，然后計算它們的加權作為服務器的負載。有研究者在此基礎上引入了反饋，動態(tài)調整每個資源的權重；提出了模糊控制理論將服務器負載分成不同的層次。但是這些算法仍沒有解決一個問題：在監(jiān)控的時間間隔之間,節(jié)點性能發(fā)生改變，而此時服務器管理節(jié)點并沒有及時獲知，導致請求被優(yōu)先分配到管理節(jié)點認為性能較優(yōu)越的服務器節(jié)點上，因此產生負載不均的情況。而如果片面縮短DLB算法中的時間間隔，將會大大增加系統(tǒng)開銷。

傳統(tǒng)的分布式系統(tǒng)模型中的每個節(jié)點都可以作為一個發(fā)送器或接收器。一個節(jié)點作為發(fā)送方，如果當時的工作量級大于它的容量。然后，嘗試與鄰國銷售當前的負載平衡其負載。為了使系統(tǒng)的工作原理有效，每個節(jié)點需要具備網(wǎng)絡中所有其他節(jié)點的知識。這是該系統(tǒng)的最大缺點。發(fā)送器/接收器通過發(fā)送廣播消息到所有其他節(jié)點，并期望一個響應于發(fā)現(xiàn)的節(jié)點。創(chuàng)建時會涉及所有節(jié)點一定的通信開銷。

為了解決以上問題，降低負載平衡過程的復雜性，并兼顧異質性和可擴展性,文中嘗試使用兩級策略，以平衡節(jié)點之間的工作量負載。異構系統(tǒng)被劃分為若干個簇，而每個簇由若干個節(jié)點組成。

負載平衡的一個重要因素是在負載均衡算法中使用的負載指標。在DLB算法的基礎上，提出的算法使用節(jié)點的處理器和內存利用率、節(jié)點中排隊的作業(yè)數(shù)量以及節(jié)點的處理能力三元組負荷指標。通過所使用的負載量度計算幾個現(xiàn)有負載尺度，提供關于一個節(jié)點的負載的更多信息。

整個負載平衡分為兩個過程。首先，系統(tǒng)負載會以各個簇的處理能力為標準，將作業(yè)均衡分配至各個簇，簇依據(jù)各個節(jié)點的處理能力將作業(yè)均衡分配至節(jié)點。當系統(tǒng)開始處理工作以后，各個節(jié)點依據(jù)當前負載計算得出的負載率，將其傳遞至簇管理節(jié)點，并為自己設定負載率閾值。如果超出閾值，則重新計算負載率向管理節(jié)點反饋。此時管理節(jié)點為此節(jié)點更新權值，繼續(xù)分配任務。如果節(jié)點超載，則在向管理節(jié)點更新權值的同時嘗試將作業(yè)分給簇內負載較輕的節(jié)點，如果不成功則嘗試向其他簇尋求負載較輕的節(jié)點。

仿真結果表明，提出的方法明顯地減少了作業(yè)的平均響應時間。

2 系統(tǒng)模型與問題定義

考慮N個異質節(jié)點P1,P2,…,PN通過通信網(wǎng)絡連接。每個節(jié)點具有一些計算設備和本地存儲器。對于分布式系統(tǒng)，假定作業(yè)在任何節(jié)點都按泊松率λi到達。而作業(yè)的服務時間服從指數(shù)分布，即每個作業(yè)的完成時間之間沒有依賴關系。作業(yè)被假定為獨立的，可以在任何節(jié)點上執(zhí)行。作業(yè)的連接時間長短各異，任務大小不同，在這里認為每一種類型的作業(yè)在所有作業(yè)中的分布是均勻的。因此，每個節(jié)點作為一個M/M/1隊列。節(jié)點接收作業(yè)請求并將其存入緩沖區(qū)，按照先來先服務的策略完成所有作業(yè)。該模型中的網(wǎng)絡被組織成多個小型集群。每個小型集群都有指定為群集管理器的節(jié)點，它負責收集集群內普通節(jié)點的負載信息，然后根據(jù)信息為子節(jié)點計算權值，并按照權值為其分配作業(yè)。

當某一集群中的節(jié)點出現(xiàn)負載不均衡時，該節(jié)點向其管理節(jié)點(CM)反饋。CM接收到反饋后，嘗試在本集群中進行負載均衡。而當CM發(fā)現(xiàn)本集群中所有節(jié)點均產生過載時，嘗試向主節(jié)點反饋，并由主節(jié)點進行全局負載均衡。全局平衡是通過平衡相鄰集群之間的負載來實現(xiàn)。這種結構分散了負載平衡過程，盡量減少通信開銷，所以它可以擴展到大系統(tǒng)。

分層負載均衡系統(tǒng)模型如圖1所示。

圖1 分層負載均衡系統(tǒng)模型圖

每個節(jié)點負責：

(1)保持自身的工作負荷信息。

(2)發(fā)送該工作負載信息到CM。

(3)執(zhí)行負載均衡通過其集群管理器的決定。

除了節(jié)點基本功能,CM還負責：

(1)接收并保存其他提交的工作節(jié)點負荷信息。

(2)決定何時啟動本地負載均衡。

(3)向每個工作節(jié)點發(fā)送負載均衡決定。

(4)決定發(fā)起全局負載均衡。

為了進行負載平衡，每個管理節(jié)點負責維護子節(jié)點信息表。參數(shù)如表1所示。

表1 參數(shù)表

3 集群負載均衡策略(CLB)

3.1 CLB策略概述

集群中所有節(jié)點獲取自身性能參數(shù)信息，并把信息發(fā)送給CM，CM統(tǒng)計本組節(jié)點權值信息，計算出本組集群節(jié)點剩余權值信息，并將信息填入節(jié)點信息表。然后，CM按照節(jié)點信息表，將作業(yè)分配至各個節(jié)點。同時，CM計算本組節(jié)點負載均值，并提升10%作為超載閾值。如果有節(jié)點負載超過此閾值，則視為此節(jié)點過載，并啟動局部負載均衡策略，將此節(jié)點作業(yè)轉發(fā)至其他非過載節(jié)點處理。設定負載率80%為全局閾值，如果本組所有節(jié)點負載均超過80%，則認為本組集群過載，啟動全局負載均衡策略，將本組集群中各節(jié)點的作業(yè)轉發(fā)至其他組集群，同時，主節(jié)點減少向本集群轉發(fā)作業(yè)。

負載均衡過程開始從下級接收負載更新消息。在Te每個周期的時間間隔稱為估計間隔，每個處理器Pi系統(tǒng)計算其負載信息的參數(shù),然后將信息發(fā)送到集群管理器。

負載均衡策略包括以下階段：

(1)在每個Te，每個節(jié)點獲取自身信息，并發(fā)送負荷指標到集群管理器CM。

(2)CM從本集群中的各個節(jié)點處接收信息，計算并產生轉發(fā)表。同時，判斷本集群是否處于飽和狀態(tài)。

(3)如果集群已經(jīng)飽和，則CM啟動全局負載均衡。否則檢查穩(wěn)定性標準，以確定是否需要本地負載均衡。

(4)CM啟動本地負載均衡。由CM協(xié)調集群內節(jié)點，把作業(yè)從超載節(jié)點轉移到欠載節(jié)點。重復這個過程，直到該集群達到平衡。

3.2 CLB集群負載均衡過程

3.2.1 工作節(jié)點性能參數(shù)獲取

節(jié)點的負載情況在算法中起到至關重要的作用[13-14]。文中采集各節(jié)點CPU性能、內存性能、CPU利用率、內存利用率等多項指標。其中，CPU性能、內存性能指標為常量。

(1)CPU處理能力：該算法中，通過調用系統(tǒng)接口獲取服務器的CPU參數(shù)，包括核心數(shù)量和主頻等，并為其設定權值。用Ci表示，范圍為0～1。

(2)內存參數(shù)：同樣，獲取計算機的物理內存和虛擬內存的大小，以便設置內存權值。用Mi表示，范圍為0～1。

(3)節(jié)點的可用性由節(jié)點CPU剩余和內存剩余決定，如果節(jié)點的這兩個指標參數(shù)值較高，則反映此節(jié)點是空閑節(jié)點，反之，則是繁忙節(jié)點。這里由CPU利用率(CPUrate)和內存利用率(Rrate)計算節(jié)點的性能剩余指標W(i)(idle)。

(4)對任何服務節(jié)點Pi來講，假設所有作業(yè)到達的時間間隔服從泊松分布，則節(jié)點總連接數(shù)服從強度為λ的泊松過程，即單位時間內節(jié)點的連接總數(shù)為λ，也即認為每個作業(yè)到達時間間隔為1/λ。節(jié)點響應時間是從節(jié)點接收請求到返回服務信息所花費的總時間，平均節(jié)點響應時間在衡量節(jié)點負載時更有意義。類似的，認為在單位時間內，節(jié)點響應的請求數(shù)μ為節(jié)點響應時間的倒數(shù)，即節(jié)點響應時間為1/μ。所有工作被認為是獨立的。

(5)需要采集系統(tǒng)連接數(shù)Na和系統(tǒng)響應時間Tr來評價該算法與其他算法孰優(yōu)孰劣。系統(tǒng)連接數(shù)是在時刻T時，節(jié)點所建立的連接數(shù)，反映節(jié)點當前的負載情況。系統(tǒng)響應時間是從服務器接收到請求至響應請求所花費時間的總量，反映服務器在處理作業(yè)時的效率。

3.2.2 工作負載評估

在評估節(jié)點工作負載時，需要建立權值衡量函數(shù)模型。對于在集群中建立節(jié)點服務器工作負載的數(shù)學模型，Watts和Taylor[3]通過研究證明：使用線性加權法可以定量描述服務器負載量的有效性。故文中采用該方法建立改進算法的數(shù)學模型。

線性加權法[15]的理論思路是：各個度量指標在總目標數(shù)值中所占的重要程度是不同的，那么就可以根據(jù)其各自的重要性分別為它們設定系數(shù)，并將這些帶有系數(shù)的度量指標值相加，最終得到總目標的值。這樣，在多個指標共同作用且作用力不同的情況下，得到的目標值能夠很好地反映實際情況。

因此，可以得出改進的基于多衡量指標的負載均衡衡量函數(shù)：

(1)

其中，ω為權值系數(shù)；f為權值。

第i臺服務器的剩余權值為：

W(i)(idle)=ω(i)(C)*Ci*CPUidle+ω(i)(R)* Mi*Ridle

(2)

其中，CPUidle是CPU剩余利用率,CPUidle=1-CPUrate；Ridle是內存剩余利用率，Ridle=1-Rrate。

3.2.3 集群負載均衡

在這個過程中，CM節(jié)點獲取集群內節(jié)點的負載信息，并根據(jù)節(jié)點性能剩余利用率來判斷本集群負載情況。在集群中，有的節(jié)點出現(xiàn)過載，有點則會出現(xiàn)欠載的情況，具體可以分為高負載、中等負載和欠載。需要將作業(yè)從高負載節(jié)點轉發(fā)至欠載節(jié)點進行處理。

3.2.4 全局負載均衡

在某一集群中會出現(xiàn)負載不均衡的情況，同樣的情況在不同的集群間依然不可避免。依照負載情況，集群可以分為飽和集群(超載集群)、非飽和集群(平均負載集群和欠載集群)。當一個集群出現(xiàn)飽和的情況時，它嘗試向主節(jié)點報告狀態(tài)，請求減輕負載。此時，主節(jié)點啟動策略，詢問各集群管理節(jié)點集群是否飽和，并按照非飽和集群的剩余利用率權值，將作業(yè)轉發(fā)至這些非飽和集群。

4 實驗結果

為了驗證該算法的可行性，搭建了基于WindowsServer2008的虛擬機集群，并編寫程序進行模擬實驗。

實驗平臺環(huán)境由16臺物理主機(CPU四核八線程，主頻2.4GHz，內存32GB)、2臺千兆路由器以及若干臺客戶機組成。利用這些硬件設備搭建虛擬機集群，為了使環(huán)境更貼近實際，為各個虛擬機分配不同的資源，具體見表2。

表2 虛擬機配置表

在集群中，把性能較優(yōu)秀的虛擬機設置為各個簇的管理節(jié)點，其他節(jié)點設為普通節(jié)點。在模擬程序中，采用VisualStudio開發(fā)環(huán)境，C++語言編寫代碼，并部署至環(huán)境中。

負載均衡前后各類型節(jié)點訪問量分別如圖2和圖3所示。

圖2 負載均衡前各類型節(jié)點訪問量

圖3 負載均衡后各類型節(jié)點訪問量

5 結束語

在考慮異構環(huán)境的情況下，提出了分布式系統(tǒng)兩層結構節(jié)點自適應虛擬機集群系統(tǒng)負載均衡算法。算法主要通過節(jié)點權值和負載率來評估節(jié)點性能，進而進行資源的合理配置。而當請求間差異過大導致資源分配不均時，該算法能在代價較小的情況下解決問題。

在下一步的工作中，將考慮引入軟件定義網(wǎng)絡(SDN)，嘗試將集群網(wǎng)絡負載均衡算法在新的網(wǎng)絡環(huán)境中進行驗證。另外，算法在提高整體響應速度的同時并沒有側重點，對于單個請求來說，算法給出的響應時間并非最優(yōu)解，將在這方面做進一步研究。

[1]YangG.Dynamicload-balancinginiSCSIsystemsbasedonafeedbackcontrolmechanism[C]//Proceedingsofthe2011fifthinternationalconferenceonmanagementofe-commerceande-government.[s.l.]:IEEEComputerSociety,2011:187-192.

[2]SaxenaS,KhanMZ,SinghR.Performanceanalysisindistributedsystemofdynamicloadbalancingusingfuzzylogic[C]//2012springcongressonengineeringandtechnology.[s.l.]:IEEE,2012:1-5.

[3]WattsJ,TaylorS.Apracticalapproachtodynamicloadbalancing[J].IEEETransactionsonParallel&DistributedSystems,1998,9(3):235-248.

[4]ChatterjeeM,SetuaSK.Anewclusteredloadbalancingapproachfordistributedsystems[C]//Thirdinternationalconferenceoncomputer,communication,controlandinformationtechnology.[s.l.]:IEEE,2015:1-7.

[5]ZhangL,LiXP,YuanS.Acontent-baseddynamicload-balancingalgorithmforheterogeneouswebservercluster[J].ComputerScience&InformationSystems,2010,7(1):153-162.

[6] 李 坤.基于動態(tài)反饋機制的服務器負載均衡算法研究[J].電子科技,2015,28(9):45-49.

[7]KaurS,SinghJ,KumarK,etal.Round-robinbasedloadbalancinginsoftwaredefinednetworking[C]//2ndinternationalconferenceoncomputingforsustainableglobaldevelopment.[s.l.]:[s.n.],2015.

[8]JainD,JainSC.Loadbalancingreal-timeperiodictaskschedulingalgorithmformultiprocessorenvironment[C]//Internationalconferenceoncircuit,powerandcomputingtechnologies.[s.l.]:IEEE,2015.

[9] 袁 剛.基于服務分類的預測型動態(tài)負載均衡調度算法[J].計算機技術與發(fā)展,2015,25(6):96-100.

[10] 楊 洋,楊家海,王 會,等.IP網(wǎng)絡時延敏感型業(yè)務流自適應負載均衡算法[J].通信學報,2015,36(3):131-141.

[11] 童瑞霞.基于動態(tài)反饋機制的集群負載均衡算法研究[D].武漢:武漢理工大學,2011.

[12] 馮秀玲.云計算環(huán)境下的負載均衡算法的研究與設計[D].北京:北京郵電大學,2012.

[13] 葉春森.企業(yè)云計算服務的商業(yè)價值創(chuàng)造研究[D].合肥:合肥工業(yè)大學,2014.

[14] 馬華偉,吳曉莉.云計算環(huán)境下虛擬機負載均衡問題研究[J].微電子學與計算機,2014,31(4):10-12.

[15] 康承昆,劉曉潔.一種基于多衡量指標的HDFS負載均衡算法[J].四川大學學報:自然科學版,2014,51(6):1163-1169.

A Dynamic Load Balancing Algorithm in a Multi-level Network

LIU Li-bang,HUANG Gang

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

A distributed system consists of several independent nodes,in which some nodes may be overloaded due to massive requests arrivals,and another some are idle without any requests.Load balancing techniques can be used to effectively distribute the load between nodes to reach the purpose of extending bandwidth of server clusters,increasing its throughput,enhancing network data processing capability,improving network flexibility and availability.Traditional centralized load balancing adopts static load balancing algorithm,solely responsible for the tasks assigned by the controller.Its advantage is low power consumption and high stability,and its disadvantage is not the best in the load balancing effect and slow overall processing speed.Due to the heavy burden,the central controller node can easily become a bottleneck.At the same time,its system scalability is poor,with bad performance in large scale cluster.By contrast,a fully distributed solution is scalable,because all nodes are both processing nodes and the dispatcher,while the load scheduler is only task scheduling,thereby reducing the burden on the controller to prevent it from becoming a system bottleneck.A heterogeneous distributed computing systems in the cluster load balancing strategy is proposed.The algorithm requires the CPU usage and memory usage to determine the workload of each node.At the same time,two-level structure is designed to solve the problem of heavier global communications burden.Simulation results show that the algorithm can effectively improve the efficiency of load balancing.

cluster load balancing;distributed systems;heterogeneous network;node utilization

2016-03-30

2016-07-05

時間：2017-01-10

國家自然科學基金資助項目(61171053);南京郵電大學基金(SG1107)

劉立幫(1988-)，男，研究方向為計算機云計算與虛擬化應用；黃 剛，教授，研究方向為計算機軟件理論及應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1019.046.html

TP301.6

A

1673-629X(2017)02-0051-05

10.3969/j.issn.1673-629X.2017.02.012