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

王文博，葉慶衛(wèi)，周宇，陸志華

?

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

王文博，葉慶衛(wèi)，周宇，陸志華

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

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

負載均衡；排隊論；性能

1 引言

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

圖1 基于排隊論的負載均衡任務(wù)調(diào)度模型

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

2 基于排隊論的負載均衡調(diào)度模型

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

2.1 模型建立

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

圖2 生滅狀態(tài)轉(zhuǎn)移

由圖2可得，系統(tǒng)處于穩(wěn)態(tài)時的概率方程如下：

第個服務(wù)器的任務(wù)平均排隊長度為：

任務(wù)在服務(wù)器中的逗留時間分布函數(shù)為：

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

2.2 調(diào)度策略與隊列負載評價

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

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

2.3 算法流程

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

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

3 仿真實驗與性能分析

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

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

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

圖5 各個服務(wù)器的任務(wù)平均等待時間

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

4 結(jié)束語

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

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

[1] 李永平, 鄒華. 應用服務(wù)器的負載平衡技術(shù)和實現(xiàn)方案[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] 孫喬, 鄧仆僑, 王志強, 等. 一種基于分布式服務(wù)器集群的可擴展負載均衡策略技[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的服務(wù)集群負載均衡方法[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] 鄭相全, 郭偉, 葛利嘉, 等. 一種基于跨層設(shè)計和蟻群優(yōu)化的自組網(wǎng)負載均衡路由協(xié)議[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] 陳超, 趙躍龍, 王文豐, 等. 基于反饋的改進動態(tài)負載均衡策略[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）；浙江省重點科技創(chuàng)新團隊資助項目（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?），女，寧波大學信息科學與工程學院碩士生，主要研究方向為服務(wù)器負載均衡技術(shù)等。

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

周宇（1960?），男，寧波大學信息與工程學院教授、碩士生導師，主要研究方向為信號處理、網(wǎng)絡(luò)與信息安全、物聯(lián)網(wǎng)技術(shù)等。

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