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

?

基于排隊(duì)論綜合指標(biāo)評(píng)估的動(dòng)態(tài)負(fù)載均衡算法

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

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

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

負(fù)載均衡；排隊(duì)論；性能

1 引言

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

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

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

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

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

2.1 模型建立

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

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

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

第個(gè)服務(wù)器的任務(wù)平均排隊(duì)長(zhǎng)度為：

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

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

2.2 調(diào)度策略與隊(duì)列負(fù)載評(píng)價(jià)

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

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

2.3 算法流程

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

圖3 基于排隊(duì)論綜合指標(biāo)評(píng)估的動(dòng)態(tài)負(fù)載均衡算法流程

3 仿真實(shí)驗(yàn)與性能分析

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

圖4 各個(gè)服務(wù)器負(fù)載均衡綜合指標(biāo)的方差

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

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

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

4 結(jié)束語(yǔ)

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

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

[1] 李永平, 鄒華. 應(yīng)用服務(wù)器的負(fù)載平衡技術(shù)和實(shí)現(xiàn)方案[J]. 電信科學(xué), 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] 孫喬, 鄧仆僑, 王志強(qiáng), 等. 一種基于分布式服務(wù)器集群的可擴(kuò)展負(fù)載均衡策略技[J]. 電信科學(xué), 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ù)集群負(fù)載均衡方法[J]. 電信科學(xué), 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è)計(jì)和蟻群優(yōu)化的自組網(wǎng)負(fù)載均衡路由協(xié)議[J]. 電子學(xué)報(bào), 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ìn)動(dòng)態(tài)負(fù)載均衡策略[J]. 計(jì)算機(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] 于國(guó)防, 王耀才, 莊立運(yùn), 等. 基于分配器隊(duì)列模糊控制的集群負(fù)載平衡[J]. 計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.51675286，No.61071198）；浙江省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)資助項(xià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?），女，寧波大學(xué)信息科學(xué)與工程學(xué)院碩士生，主要研究方向?yàn)榉?wù)器負(fù)載均衡技術(shù)等。

葉慶衛(wèi)（1970?），男，博士，寧波大學(xué)信息科學(xué)與工程學(xué)院教授、碩士生導(dǎo)師，主要研究方向?yàn)樾盘?hào)檢測(cè)、最優(yōu)化搜索、視頻識(shí)別與跟蹤等。

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

陸志華（1983?），男，博士，寧波大學(xué)信息科學(xué)與工程學(xué)院講師，主要研究方向?yàn)樾盘?hào)處理、多運(yùn)動(dòng)目標(biāo)的實(shí)時(shí)跟蹤、統(tǒng)計(jì)信號(hào)處理算法和應(yīng)用等。