陳 斌，甘茂林，李 娟

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033； 2.海軍駐廣州地區(qū)通信軍事代表室，廣東 廣州 510220)

一種基于負(fù)載均衡的云資源調(diào)度方法

陳 斌1，甘茂林2，李 娟1

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033； 2.海軍駐廣州地區(qū)通信軍事代表室，廣東 廣州 510220)

虛擬化技術(shù)可以實(shí)現(xiàn)云系統(tǒng)中資源的按需分配，但同時(shí)可能會(huì)造成部分物理服務(wù)器負(fù)載過重，從而導(dǎo)致系統(tǒng)性能降低。云系統(tǒng)負(fù)載均衡，是決定系統(tǒng)計(jì)算和服務(wù)能力的核心因素。在對(duì)云資源調(diào)度問題的形式化描述基礎(chǔ)上，定義了負(fù)載均衡系數(shù)，構(gòu)建了云資源調(diào)度負(fù)載均衡模型。針對(duì)云資源調(diào)度中的用戶需求及服務(wù)器屬性的差異性問題，提出了一種基于最大需求優(yōu)先和最閑服務(wù)器被選原則的云計(jì)算資源調(diào)度方法，并進(jìn)行了算法設(shè)計(jì)與分析，給出了系統(tǒng)負(fù)載均衡系數(shù)的動(dòng)態(tài)計(jì)算公式。仿真實(shí)驗(yàn)結(jié)果表明，所提出的方法可得到理想的云計(jì)算負(fù)載均衡結(jié)果，與隨機(jī)調(diào)度、輪轉(zhuǎn)調(diào)度等傳統(tǒng)算法相比具有優(yōu)越的負(fù)載均衡性能和廣泛的適應(yīng)性。與此同時(shí)，所提出的方法可合理協(xié)調(diào)用戶需求和服務(wù)器屬性，以實(shí)現(xiàn)云資源負(fù)載均衡。

負(fù)載均衡；云資源調(diào)度；用戶需求；服務(wù)器屬性

0 引 言

云資源[1-3]在物理上以分布式的共享方式存在，在邏輯上以單一整體的形式呈現(xiàn)給用戶。云資源調(diào)度是將資源從資源提供方分配給用戶的一個(gè)過程。先進(jìn)的云計(jì)算資源調(diào)度技術(shù)[4-7]是提高云計(jì)算系統(tǒng)性能的關(guān)鍵之一。而云系統(tǒng)負(fù)載均衡[8-10]，是決定系統(tǒng)計(jì)算和服務(wù)能力的核心因素。

傳統(tǒng)的分配調(diào)度算法[11-12]，如輪轉(zhuǎn)法、最小負(fù)載優(yōu)先法、哈希法等，雖然在一定程度上考慮了負(fù)載均衡的問題，但很難達(dá)到負(fù)載均衡的需求。原因來自兩方面：一是用戶需求的差異性，表現(xiàn)在用戶可能在不同時(shí)刻提出不同的資源需求；二是服務(wù)器屬性的差異性，在數(shù)據(jù)中心的服務(wù)器集群中，每個(gè)物理服務(wù)器的配置是不相同的。

針對(duì)上述問題，在研究分析云資源調(diào)度方法的基礎(chǔ)上，提出了一種基于最大需求優(yōu)先和最閑服務(wù)器被選原則的云計(jì)算資源調(diào)度方法。仿真實(shí)驗(yàn)結(jié)果表明，該方法在云資源調(diào)度過程中通過合理協(xié)調(diào)用戶需求和服務(wù)器屬性，以達(dá)到云資源負(fù)載均衡的目的。

1 基本概念

云計(jì)算環(huán)境中，云資源調(diào)度流程如圖1所示。

圖1 云資源調(diào)度流程

云用戶向云平臺(tái)提交資源申請(qǐng)后，云計(jì)算環(huán)境中的調(diào)度中心節(jié)點(diǎn)，根據(jù)云調(diào)度策略，按照相應(yīng)的調(diào)度算法，進(jìn)行云資源調(diào)度，建立虛擬資源與物理資源的映射，同時(shí)將用戶所需資源部署到具體的物理節(jié)點(diǎn)上，最終將資源分配給用戶，在用戶申請(qǐng)期限內(nèi)，提供給用戶使用。

從虛擬資源的角度描述，云資源可以看作是若干種不同類型的集合，故有以下定義。

定義1：云資源(Cloud Source，CS)，含n類子資源，表示形式為：

cs=,csi∈{1,2,…,∞},i∈{1,2,…,n} ，CS={cs}

其中，csi表示云資源向量cs中含第i類子資源的數(shù)量值；CS表示云資源集合。

在云資源集合CS定義運(yùn)算“+”“-”“>”“<”：

從物理資源角度描述，云資源可以看作是若干物理服務(wù)器的集合，即服務(wù)器集群，每一臺(tái)物理服務(wù)器上，可提供若干云資源。故有如下定義。

定義2：物理服務(wù)器(Physical Machine,PM)位于云系統(tǒng)中，以pm.s表示位于服務(wù)器pm上的資源總數(shù)，pm.v表示pm上的可分配資源，有：

向量pm.s是對(duì)應(yīng)服務(wù)器pm的性能屬性，用以描述服務(wù)器的資源容量，其內(nèi)容由物理服務(wù)器pm決定，在服務(wù)器正常工作中，不會(huì)發(fā)生變化。而向量pm.v表達(dá)的是對(duì)應(yīng)服務(wù)器pm的實(shí)時(shí)狀態(tài)，用以描述服務(wù)器在當(dāng)前時(shí)刻可用資源總量，其內(nèi)容由物理服務(wù)器pm當(dāng)前資源余量決定，在服務(wù)器正常工作中，隨資源的分配與釋放實(shí)時(shí)變化。

定義3：物理服務(wù)器集群(Physical Machine Cluster,PMC)位于云系統(tǒng)中，含m個(gè)服務(wù)器，表示為：

PMC={pm1,pm2,…,pmm}

由定義1、2、3可知，在包含m臺(tái)物理服務(wù)器的集群PMC中，其能提供的云資源總量pmc.s和可分配資源總量pmc.v為：

pmc.s=pm1.s+pm2.s+…+pmm.s

pmc.v=pm1.v+pm2.v+…+pmm.v

其中，i∈{1,2,…,m},pmi∈PMC。

2 問題模型

物理服務(wù)器是云資源的提供者，而資源的使用者是云系統(tǒng)用戶(Cloud User，CU)。

從用戶的角度描述，云資源可以看作是云系統(tǒng)滿足用戶實(shí)時(shí)需求的服務(wù)能力。用戶在特定時(shí)刻的資源需求ur表示為：

ur=

其中， cu∈CU表示提出資源需求的云用戶；cs∈CS表示資源需求量；ts∈[0,∞)表示云用戶提出資源需求的初始時(shí)刻；te∈[0,∞)表示用戶資源占有時(shí)間長度。

用戶資源需求是一種實(shí)時(shí)變量，以UR(t)表示在t時(shí)刻云用戶的資源需求，則

UR(t)={ur|ur.ts=t}

可以計(jì)算，在t時(shí)刻用戶資源需求總量UR(t).CS為：

若在t時(shí)刻，服務(wù)器的集群PMC中的可分配資源總量為pmc.v(t)，則：pmc.v(t)>UR(t).CS為t時(shí)刻用戶資源需求得以滿足的必要條件。

從資源調(diào)度角度描述，云資源可以看作是云系統(tǒng)為云用戶服務(wù)的能力。云系統(tǒng)將部署在服務(wù)器上的資源按用戶需求分配給云用戶。故資源分配(Source Assignment，SA)的任務(wù)是根據(jù)用戶提出的資源需求，將用戶需求的資源部署在物理服務(wù)器上，并分配給用戶使用。資源分配的基本規(guī)則為：某個(gè)用戶的一次資源需求中，所有的資源均應(yīng)部署在同一個(gè)物理服務(wù)器上。即對(duì)于用戶需求ur,以下條件成立時(shí)，才可被滿足。

?pm∈PMC,pm.v>ur.cs

以sa表示云系統(tǒng)滿足ur的資源分配，有：

sa==

其中，∈UR；loc∈PMC表示用戶需求的資源所部署的物理服務(wù)器位置。

對(duì)應(yīng)于UR(t)，以SA(t)表示在t時(shí)刻云系統(tǒng)滿足所有用戶的資源分配集合，則：

SA(t)={|∈UR(t),loc∈PMC}

所研究的云資源調(diào)度算法以負(fù)載均衡為目標(biāo)，與負(fù)載相關(guān)的定義如下。

定義4：服務(wù)器負(fù)載率(Physical Machine Load Factor)，以f表示。對(duì)于pm，f的計(jì)算方法如下：

定義5：服務(wù)器集群負(fù)載率(Physical Machine Cluster Load Factor)，以F表示。對(duì)于PMC，F(xiàn)的計(jì)算方法如下：

定義6：服務(wù)器集群負(fù)載均衡系數(shù)(Physical Machine Cluster Load Balancing Factor)以BF表示。對(duì)于PMC，BF的計(jì)算方法如下：

根據(jù)以上定義及描述，可對(duì)問題建立如下模型：

已知PMC，UR；

求解SA；

使得min PMC.BF

其中，min PMC.BF表示某時(shí)刻云系統(tǒng)服務(wù)器集群最小的負(fù)載均衡系數(shù)，(1)保證當(dāng)前時(shí)刻所有的用戶需求均被處理，(2)保證所有資源在物理服務(wù)器上是可得的。

3 算法設(shè)計(jì)及分析

3.1 算法策略

云應(yīng)用中，導(dǎo)致服務(wù)器集群負(fù)載不均衡的因素有兩個(gè)[13-15]：一是用戶資源需求的隨機(jī)性，云用戶根據(jù)自己的實(shí)際情況向云系統(tǒng)申請(qǐng)規(guī)格不同的資源量，這些不同的資源需求將導(dǎo)致服務(wù)器負(fù)載的不均衡；二是服務(wù)器本身所能提供的資源量也是大小不一的，這種服務(wù)器屬性同樣導(dǎo)致負(fù)載的不均衡。針對(duì)這兩點(diǎn)，提出以下策略。

(1)最大資源需求優(yōu)先。

在資源部署時(shí)，資源量越大，越容易造成負(fù)載的不均衡。因而，采用“最大需求者優(yōu)先”原則，先處理資源申請(qǐng)量大的用戶需求。

因此，對(duì)應(yīng)t時(shí)刻的用戶需求集合UR(t)，首先按其中元素資源需求量ur.cs根據(jù)從大到小進(jìn)行排序。資源分配時(shí)，按排序后的用戶資源需求順序依次進(jìn)行處理。

(2)最低利用率被選。

對(duì)應(yīng)于每一個(gè)ur，理論上可以由云系統(tǒng)中的任意一臺(tái)服務(wù)器提供。所以對(duì)應(yīng)m個(gè)服務(wù)器，有m種分配方案，為，，…，，對(duì)應(yīng)這m種方案，提供資源的服務(wù)器相關(guān)參數(shù)更新為：

針對(duì)這些候選方案，選擇ua=，其中pm使得pmi.f最小，即：

3.2 算法步驟

根據(jù)“最大資源需求優(yōu)先，最低利用率被選”策略，問題求解步驟如下：

(1)初始化服務(wù)器集群PMC，用戶資源分配隊(duì)列UA,時(shí)間值t，確定算法終止條件TEND。

(2)若滿足終止條件，算法結(jié)束；否則繼續(xù)步驟(3)。

(3)在UA隊(duì)列中尋找已到期資源服務(wù)(即ua.tb+ua.te

(4)讀入當(dāng)前用戶資源需求集合。

(5)根據(jù)資源需求量大小對(duì)用戶資源需求排序。

(6)按資源需求量大小，對(duì)每一個(gè)資源請(qǐng)求ur：

(6.1)依次將其預(yù)分配到每一臺(tái)服務(wù)器上，計(jì)算相應(yīng)服務(wù)器均衡負(fù)載率。

(6.2)記錄最小均衡負(fù)載率及相應(yīng)服務(wù)器pm。

(6.3)若pm合法，進(jìn)行資源部署，更新pm狀態(tài)，并創(chuàng)建資源服務(wù)項(xiàng)，將其加入資源服務(wù)隊(duì)列中，轉(zhuǎn)到步驟(7)，否則轉(zhuǎn)步驟(4)。

(6.4)無法滿足ur，資源分配失敗。

(7)t=t+1。

(8)轉(zhuǎn)到步驟(2)。

算法描述如圖2所示。

圖2 算法描述

3.3 算法分析

(1)算法時(shí)間復(fù)雜度。

設(shè)云系統(tǒng)中PMC的服務(wù)器數(shù)量為m,CU中用戶總數(shù)為u,用戶提出資源需求的概率為p，用戶資源占有平均時(shí)長為τ，則在每個(gè)時(shí)刻t，UR中元素平均個(gè)數(shù)，即需要處理的資源需求數(shù)量平均值為up，服務(wù)集合UA平均長度為upτ。

算法從T=0開始運(yùn)行，至T=TEND終止，在每一輪運(yùn)行中，主要完成遍歷UA、UR排序、遍歷UR×PMC。故可計(jì)算其時(shí)間復(fù)雜度為：(TEND*up(τ+log(up)+m))。

(2)相關(guān)參數(shù)計(jì)算。

在算法執(zhí)行過程中，隨著資源的分配與釋放，物理服務(wù)器及服務(wù)器集群的相關(guān)參數(shù)也會(huì)發(fā)生變化。

在時(shí)刻t，首先系統(tǒng)釋放到期服務(wù)資源，再為該時(shí)刻的用戶需求進(jìn)行資源分配。若：

則：

UA(t)=UA(t-1)+SA(t)-{ |∈UA(t-1),te=t}

一輪算法執(zhí)行完畢后，PMC中服務(wù)器可用資源及負(fù)載率為：

PMC的可用資源、負(fù)載率及負(fù)載均衡系數(shù)為：

4 實(shí)驗(yàn)及結(jié)果分析

為進(jìn)一步研究算法效果，通過仿真實(shí)驗(yàn)分析算法演化過程及結(jié)果。實(shí)驗(yàn)中，取服務(wù)器集群數(shù)量為6，僅考慮一種資源的情況，服務(wù)器資源參數(shù)如表1所示。

表1 服務(wù)器資源參數(shù)

其余參數(shù)設(shè)定為：CU中用戶總數(shù)為20,用戶提出資源需求的概率為0.5，用戶資源需求量均勻分布在(0,50)之間，用戶資源占有時(shí)長均勻分布在(0,10)之間，算法演化時(shí)長為100。算法演化過程中，服務(wù)器負(fù)載率及服務(wù)器集群負(fù)載率變化如圖3所示。

兩組參數(shù)對(duì)應(yīng)的服務(wù)器集群負(fù)載均衡系數(shù)為：

PMC(1).BF=0.062 21

PMC(2).BF=0.055 72

實(shí)驗(yàn)結(jié)果表明，服務(wù)器集群中，無論服務(wù)器屬性是否有差異性，提出算法均可達(dá)到較好的負(fù)載均衡性能。

為進(jìn)一步分析算法優(yōu)越性，以隨機(jī)分配方案、輪轉(zhuǎn)分配方案、最低利用率被選方案(與所提算法相比，不對(duì)資源需求進(jìn)行排序)作為對(duì)比，在相同兩組服務(wù)器資源參數(shù)下進(jìn)行相同的仿真實(shí)驗(yàn)。不同方案下，服務(wù)器集群負(fù)載均衡系數(shù)值如圖4所示。

實(shí)驗(yàn)結(jié)果表明，提出的負(fù)載均衡資源調(diào)度算法相比于傳統(tǒng)資源調(diào)度算法具有明顯的優(yōu)越性，特別是在服務(wù)器屬性差異性較大的情況下。表2列出了第二組參數(shù)下，提出的“最大資源需求優(yōu)先，最低利用率被選”資源調(diào)度策略和隨機(jī)調(diào)度策略下，各服務(wù)器及服務(wù)器集群的平均負(fù)載率數(shù)據(jù)。

(a)第一組實(shí)驗(yàn)結(jié)果

(b)第二組實(shí)驗(yàn)結(jié)果

(a)第一組實(shí)驗(yàn)結(jié)果

(b)第二組實(shí)驗(yàn)結(jié)果

表2 兩種策略下的服務(wù)器負(fù)載率

5 結(jié)束語

在云資源調(diào)度中，為保證服務(wù)器集群負(fù)載均衡，在構(gòu)建云資源調(diào)度負(fù)載均衡模型的基礎(chǔ)上，提出了一種基于最大需求優(yōu)先，最閑服務(wù)器被選原則的云計(jì)算資源調(diào)度方法。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)資源調(diào)度算法相比，提出方法具有優(yōu)越的負(fù)載均衡性能和廣泛的適應(yīng)性。該方法可合理協(xié)調(diào)用戶需求和服務(wù)器屬性，以實(shí)現(xiàn)云資源負(fù)載均衡。

[1] 陳 星,張 穎,張曉東,等.基于運(yùn)行時(shí)模型的多樣化云資源管理方法[J].軟件學(xué)報(bào),2014,25(7):1476-1491.

[2] 洪 斌,彭甫陽,鄧 波,等.云資源狀態(tài)監(jiān)控研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(6):1-6.

[3] 賴培源,馬衛(wèi)民,劉 藝,等.云資源池網(wǎng)絡(luò)自動(dòng)化部署技術(shù)研究與實(shí)踐[J].電信科學(xué),2015,31(7):96-103.

[4] Singh S,Chana I.A survey on resource scheduling in cloud computing:issues and challenges[J].Journal of Grid Computing,2016,14(2):217-264.

[5] Singh S,Chana I.QRSF:QoS-aware resource scheduling framework in cloud computing[J].Journal of Supercomputing,2015,71(1):241-292.

[6] 魏 蔚,劉 揚(yáng),楊衛(wèi)東.一種通用云計(jì)算資源調(diào)度問題的快速近似算法[J].計(jì)算機(jī)研究與發(fā)展,2016,53(3):697-703.

[7] 李媛禎,楊 群,賴尚琦,等.一種Hadoop Yarn的資源調(diào)度方法研究[J].電子學(xué)報(bào),2016,44(5):1017-1024.

[8] 孟 蒙,茅 蘇.基于云計(jì)算的可反饋負(fù)載均衡策略的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(10):135-139.

[9] 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.

[10] 陶永才,張丹丹,石 磊,等.基于Maxdiff直方圖的MapReduce負(fù)載均衡研究[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(3):417-421.

[11] Levitin A. 算法設(shè)計(jì)與分析基礎(chǔ)[M].潘 彥,譯.第3版.北京:清華大學(xué)出版社,2015.

[12] 王永明,尹紅麗,秦開大.作業(yè)車間調(diào)度理論及其優(yōu)化方法研究[M].北京:科學(xué)出版社,2013.

[13] Pushpalatha K,Shaji R S,Jayan J P.A cost effective load balancing scheme for better resource utilization in cloud computing[J].Journal of Emerging Technologies in Web Intelligence,2014,6(3):280-290.

[14] 宋 滸.面向用戶服務(wù)需求的云計(jì)算管理機(jī)制研究[D].合肥:中國科學(xué)技術(shù)大學(xué),2013.

[15] Madni S H H,Latiff M S A,Coulibaly Y,et al.Resource scheduling for infrastructure as a service (IaaS) in cloud computing:challenges and opportunities[J].Journal of Network and Computer Applications,2016,68(6):173-200.

A Cloud Resource Scheduling Method Based on Load Balancing

CHEN Bin1,GAN Mao-lin2,LI Juan1

(1.College of Electronic Engineering,Naval University of Engineering,Wuhan 430033,China; 2.Representative Office on Military Communication,Navy in Guangzhou,Guangzhou 510220,China)

Virtualization technology can achieve the distribution of cloud resources according to need.However,it also may cause the heavy load for some physical servers which make system performance reduced.Load balancing of cloud system is the core factor that determines the system computing and service capability.Based on the formal description of cloud resource problem,load balancing coefficient has been defined and load balancing scheduling model for cloud resource has been built.Then,aiming at differences issues such as user demands and servers properties involving in cloud resource scheduling,a method has been proposed focusing on the principle of maximum demand prior and the freest server selected.It has been implemented for algorithm design and analysis further.Dynamic calculation of load balancing coefficient has been put forward as well.The result of simulation experiment has proved that the method proposed has excellent performance for load balancing and wide adaptability especially comparing to the random scheduling and rotation scheduling algorithm.It has also shown that the method can achieve load balancing of cloud resources with reasonably coordinating user demands and the server properties.

load balancing；cloud resource scheduling；user demands；server properties

2016-07-10

2016-10-13 網(wǎng)絡(luò)出版時(shí)間：2017-04-28

軍內(nèi)科研計(jì)劃項(xiàng)目(HJ-502-2015-35)

陳 斌(1975-)，男，博士生，副教授，研究方向?yàn)橥ㄐ排c信息系統(tǒng)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.062.html

TP393

A

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

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