基于排隊論綜合指標評估的動態負載均衡算法

王文博，葉慶衛，周宇，陸志華

?

基于排隊論綜合指標評估的動態負載均衡算法

王文博，葉慶衛，周宇，陸志華

（寧波大學信息科學與工程學院，浙江 寧波 315211）

互聯網通信、計算機集群和云環境均具有一定的復雜性和動態性，極易發生負載失衡，從而降低服務效率、增加能耗。因此，負載均衡技術成為重點研究課題。現有的負載均衡策略均是以CPU、內存、進程等參數的占用率來評估服務器當前的負載情況，但服務器負載情況的復雜性往往使其難以得到準確評估。針對該問題，提出了一種基于排隊論綜合指標評估的動態負載均衡算法，首先引入排隊論模型評估各服務器的實時負載情況，然后根據各服務器的負載綜合指標，將輸入隊列中的任務逐一分配給各服務器。實驗結果表明，該方法可有效平衡各服務器的負載且減少任務請求的平均等待時間。

負載均衡；排隊論；性能

1 引言

近年來，大規模集群計算、云計算技術飛速發展。在實際應用中，經常出現負載失衡的情況[1]，使得系統利用率低，用戶請求得不到快速響應，服務質量急劇下降，因此負載均衡技術也變得日益重要[2]。目前國內外已經對此進行了大量的研究工作，先后提出了各種負載均衡算法[3]。其中，有經典算法，如阿里云和亞馬遜云等提供的負載均衡服務使用輪詢算法、最小連接數算法等，這類算法思想簡單、容易實現[4]、具有較好的實用性，但無法實時準確判斷服務器的負載狀況；有啟發式任務調度算法，如遺傳算法[5]、蟻群算法[6]、粒子群算法[7]等，這類算法與經典算法相比，負載均衡效果更好，但存在實現更復雜、速度較慢、易陷入局部最優解等缺點；排隊論在負載均衡領域中也有所應用，參考文獻[8]提出一種結合周期反饋原理的動態負載均衡策略，利用排隊論建模，獲得系統性能的計算公式。參考文獻[9]提出一種在黃金時間將工作轉移到空閑節點來平衡負載的策略，并通過排隊論建模分析性能指標。這些基于排隊論的負載均衡算法，都是通過排隊論對系統性能進行分析與評價，而負載評估的方法依然與其他算法相似，并沒有真正地將排隊論應用于指導任務的分配。

圖1 基于排隊論的負載均衡任務調度模型

本文從構建排隊綜合指標出發，提出了一種基于排隊論綜合指標評估的動態負載均衡算法，克服了以往算法中使用CPU、內存占用率等參數難以與負載評估直接掛鉤的難題，降低了服務器負載信息收集的復雜性，使排隊論模型真正起到均衡負載的作用。首先定時統計各服務器的服務率和任務到達率，其次通過排隊論建模計算各服務器的任務平均排隊長度和任務平均等待時間，然后根據求得的綜合指標來評估各服務器的實時負載情況，最后將下一任務分配給負載綜合評估指標最小的服務器。

2 基于排隊論的負載均衡調度模型

排隊論是一套非常成熟的經典理論，廣泛應用于人們的生產、生活等各個領域中[10]。在互聯網絡通信中，服務器處理客戶機請求的機制本身就是一個排隊理論的現實情況[11]，用戶以任務的形式作為要求服務的一方，向服務系統發起請求，未能及時處理的任務在服務器上形成排隊隊列，服務器端如何合理分配、處理這些任務，直接影響整個系統的性能[12]。

2.1 模型建立

其次，若在時間內服務器將~+個任務處理完畢，則該服務器的平均服務率為：

圖2 生滅狀態轉移

由圖2可得，系統處于穩態時的概率方程如下：

第個服務器的任務平均排隊長度為：

任務在服務器中的逗留時間分布函數為：

任務在系統中等待時間的期望值，等于任務在系統中逗留時間的期望值減去服務時間的期望值,因此任務平均等待時間為：

2.2 調度策略與隊列負載評價

服務器的平均排隊長度L越短，說明該服務器中排隊任務越少，但因任務的大小是不同的，只根據平均排隊長度不能夠完全反映服務器當前的負載情況。而平均等待時間W越短，說明該服務器處理任務的效率越高，因此在負載均衡調度系統中，使用平均排隊長度和平均等待時間的加權平均值作為綜合評估指標來反映當前服務器的負載情況，并指導任務調度器對任務的分配。值越大代表當前服務器的負載越重，值越小代表當前服務器的負載越輕，因此任務調度器根據各服務器的值，將輸入隊列中排在隊首的任務分配到當前值最小的服務器隊列中，以平衡各服務器的負載。式（13）為值的計算式：

由此可以計算出各服務器負載綜合評估指標的方差值，方差越小，表明各服務器當前的負載均衡度越好，為：

2.3 算法流程

算法的總體流程如圖3所示，主要包括兩部分：一是前端任務調度器，主要任務是獲取各后端服務器的負載信息，計算綜合評估指標，并將任務分配給各個服務器；二是后端服務器，主要是執行隊列中的任務，并收集相關信息傳遞給任務調度器。

圖3 基于排隊論綜合指標評估的動態負載均衡算法流程

3 仿真實驗與性能分析

因MATLAB編程簡單，仿真算法容易實現，所以本文使用MATLAB編寫仿真任務調度器。由于多個服務器需要同時運行，因此使用C語言編寫多個可執行exe程序來仿真服務器。系統由1個任務調度器和4個任務服務器組成，且4個服務器能力相同。對輪詢算法、最小連接數法和基于排隊理論的動態負載均衡算法進行仿真對比和分析，經過多次實驗，結果如圖4、圖5所示。圖4中，通過求取3種算法綜合指標的方差來評估服務器的負載均衡度，由圖3可知本文算法的負載均衡度明顯優于最小連接數算法和輪詢算法。

圖4 各個服務器負載均衡綜合指標的方差

前文已經提到在實際應用中，用戶希望得到快速的響應，因此任務的平均等待時間也是衡量一個負載均衡算法優劣的指標之一。圖5仿真了本文算法、最小連接數算法和輪詢算法的任務平均等待時間。當有新任務到達服務器時，服務器的任務到達率會相應增加，任務的平均等待時間也會隨之增加，而沒有新任務到達時，任務的平均等待時間會逐漸下降，因此任務的平均等待時間大約呈周期性變化。如圖5（a）所示，本文算法中各個服務器的任務平均等待時間為0.6~3 s，4條曲線分布較為集中，數值較小且相差不大；而圖5（b）中最小連接數算法的任務平均等待時間為2~6 s，比本文算法更長，且4條任務平均等待時間曲線與本文算法相比更為分散，這可能會導致部分任務請求長時間得不到響應；圖5（c）中輪詢算法的任務平均等待時間集中為1.4~8 s，且上下浮動較大，在大部分運行時間中都比本文算法的平均等待時間長，因此本文算法效果更好。

圖5 各個服務器的任務平均等待時間

由圖5（c）中可知，輪詢算法運行到大約70 s時，服務器的任務平均等待時間出現很大的值，說明此時一些任務請求需要等待較長的時間才能響應，可能已有服務器出現過載情況。雖然此時4個服務器綜合指標的方差沒有相差特別大，但由于處理不同的任務需要的時間長短是不同的，因此服務器可能出現排隊長度較短而任務平均等待時間較大的情況或排隊長度較長而任務平均等待時間較小的情況，這也進一步印證了本文中選用平均排隊長度和平均等待時間的加權平均值作為綜合評估指標的合理性。

4 結束語

現有的排隊論負載均衡算法，都只利用排隊論建模求得的指標來評價系統性能，任務的調度策略仍然以其他算法為主。本文將排隊論模型應用在計算機集群負載均衡系統中，提出了一種基于排隊論綜合指標評估的動態負載均衡算法。實驗結果表明，該算法與輪詢算法和最小連接數算法相比，有更好的負載均衡度和更短的任務平均等待時間。

本文算法具有一定的延后性，主要是指在任務平均服務率的統計部分花費較多時間，但只是毫秒級的延后，在邏輯上不存在延后性，對實驗結果不會產生很大影響。本文算法仍具有一定的局限性：第一，本文算法通過仿真實驗進行評測，而真實環境中會出現更多復雜不可預知的因素，因此今后將在真實集群環境中對算法的實用性和通用性進行驗證測試。第二，本文算法只與輪詢算法和最小連接數算法這類經典算法，在負載均衡度、平均等待時間方面進行了對比，今后將在算法速度、復雜度等方面與該領域的最新算法進行多維度、多指標的綜合對比與改進。

[1] 李永平, 鄒華. 應用服務器的負載平衡技術和實現方案[J]. 電信科學, 2013, 29(10): 15-18.

LI Y P, ZOU H. Load balancing technology and implementation scheme of application servers[J]. Telecommunications Science, 2013, 29(10): 15-18.

[2] DHINESH B L D, KRISHNA P V. Honey bee behavior inspired load balancing of tasks in cloud computing environments[J]. Applied Soft Computing, 2013, 13(5): 2292-2303.

[3] 孫喬, 鄧仆僑, 王志強, 等. 一種基于分布式服務器集群的可擴展負載均衡策略技[J]. 電信科學, 2017, 33(9): 190-196.

SUN Q, DENG P Q, WANG Z Q, et al. A scalable load balancing strategy based on distributed server cluster[J]. Telecommunications Science, 2017, 33(9): 190-196.

[4] THAKUR A, GORAYA M S. A taxonomic survey on load balancing in cloud[J]. Journal of Network and Computer Applications, 2017(98): 43-57.

[5] 包曉安, 魏雪, 陳磊, 等. 基于mean-variance的服務集群負載均衡方法[J]. 電信科學, 2017, 33(1): 1-8.

BAO X A, WEI X, CHEN L, et al. Load balancing for server cluster based on mean-variance[J]. Telecommunications Science, 2017, 33(1): 1-8.

[6] 鄭相全, 郭偉, 葛利嘉, 等. 一種基于跨層設計和蟻群優化的自組網負載均衡路由協議[J]. 電子學報, 2006(7): 1199-1208.

ZHENG X Q, GUO W, GE L J, et al. A load balancing routing protocol for ad hoc networks based on cross layer design and ant colony optimization[J]. Chinese Journal of Electronics, 2006(7): 1199-1208.

[7] MILANI A S, NAVIMIPOUR N J. Load balancing mechanisms and techniques in the cloud environments: systematic literature review and future trends[J]. Journal of Network and Computer Applications, 2016(71): 86-98.

[8] 陳超, 趙躍龍, 王文豐, 等. 基于反饋的改進動態負載均衡策略[J]. 計算機工程,2010, 36(14): 34-36, 39.

CHEN C, ZHAO Y L,WANG W F, et al. An improved dynamic load balancing strategy based on feedback[J]. Computer Engineering, 2010, 36(14): 34-36, 39.

[9] YIN F, JIANG C J, DENG R, et al. Grid resource management policies for load-balancing and energy-saving by vacation queuing theory[J]. Computers & Electrical Engineering, 2009, 35(6): 966-979.

[10] KUMAR M, SHARMA S C. Dynamic load balancing algorithm for balancing the workload among virtual machine in cloud computing[J]. Procedia Computer Science, 2017(115): 322-329.

[11] ZHANG Z J, FAN W G. Web server load balancing: a queueing analysis[J]. European Journal of Operational Research, 2008, 186(2): 681-693.

[12] CIARDO G, RISKA A, SMIRINI E. Equiload: a load balancing policy for clustered Web servers[J]. Performance Evaluation, 2001(46): 670-684.

[13] KO Y M, CHO Y. A distributed speed scaling and load balancing algorithm for energy efficient data centers[J]. Performance Evaluation, 2014(79): 120-133.

[14] ROSS S. Queueing theory[J]. Introduction to Probability Models, 2014: 481-558.

[15] 于國防, 王耀才, 莊立運, 等. 基于分配器隊列模糊控制的集群負載平衡[J]. 計算機工程, 2008(6): 129-130, 136.

YU G F, WANG Y C, ZHUANG L Y, et al. Cluster load balancing based on fuzzy control of distributor queue[J]. Computer Engineering, 2008(6): 129-130, 136.

Dynamic load balancing algorithm based on queuing theory comprehensive index evaluation

WANG Wenbo, YE Qingwei, ZHOU Yu, LU Zhihua

School of Information Science and Engineering, Ningbo University, Ningbo 315211, China

Internet communication, computer cluster and cloud environment have complex and dynamic characteristics, which can cause load imbalance easily, reduce the service efficiency and increase the energy consumption. Therefore, the load balancing technology becomes the focus of research. The existing load balancing strategy uses the occupancy of CPU, memories, processes to estimate the current load of each server. But it is hard to guarantee its accuracy. Aiming at this problem, a dynamic load balancing algorithm based on queuing theory comprehensive index evaluation was proposed. Firstly, queuing theory model was introduced to estimate the real-time load of each server, and then the tasks of input queue was distributed to each server separately according to the load comprehensive index of each server. Experimental results show that this method can balance the load of each server effectively and reduce the average waiting time of the task requests, which is of great application value.

load balancing, queuing theory, performance

TP393

A

10.11959/j.issn.1000?0801.2018204

2017?10?30；

2018?06?26

國家自然科學基金資助項目（No.51675286，No.61071198）；浙江省重點科技創新團隊資助項目（No.2013TD21）

The National Natural Science Foundation of China (No.51675286, No.61071198), The Key Scientific and Technological Innovation Group of Zhejiang Province (No.2013TD21)

王文博（1992?），女，寧波大學信息科學與工程學院碩士生，主要研究方向為服務器負載均衡技術等。

葉慶衛（1970?），男，博士，寧波大學信息科學與工程學院教授、碩士生導師，主要研究方向為信號檢測、最優化搜索、視頻識別與跟蹤等。

周宇（1960?），男，寧波大學信息與工程學院教授、碩士生導師，主要研究方向為信號處理、網絡與信息安全、物聯網技術等。

陸志華（1983?），男，博士，寧波大學信息科學與工程學院講師，主要研究方向為信號處理、多運動目標的實時跟蹤、統計信號處理算法和應用等。