陳 斌，甘茂林，李 娟

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

一種基于負載均衡的云資源調度方法

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

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

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

負載均衡；云資源調度；用戶需求；服務器屬性

0 引 言

云資源[1-3]在物理上以分布式的共享方式存在，在邏輯上以單一整體的形式呈現給用戶。云資源調度是將資源從資源提供方分配給用戶的一個過程。先進的云計算資源調度技術[4-7]是提高云計算系統性能的關鍵之一。而云系統負載均衡[8-10]，是決定系統計算和服務能力的核心因素。

傳統的分配調度算法[11-12]，如輪轉法、最小負載優先法、哈希法等，雖然在一定程度上考慮了負載均衡的問題，但很難達到負載均衡的需求。原因來自兩方面：一是用戶需求的差異性，表現在用戶可能在不同時刻提出不同的資源需求；二是服務器屬性的差異性，在數據中心的服務器集群中，每個物理服務器的配置是不相同的。

針對上述問題，在研究分析云資源調度方法的基礎上，提出了一種基于最大需求優先和最閑服務器被選原則的云計算資源調度方法。仿真實驗結果表明，該方法在云資源調度過程中通過合理協調用戶需求和服務器屬性，以達到云資源負載均衡的目的。

1 基本概念

云計算環境中，云資源調度流程如圖1所示。

圖1 云資源調度流程

云用戶向云平臺提交資源申請后，云計算環境中的調度中心節點，根據云調度策略，按照相應的調度算法，進行云資源調度，建立虛擬資源與物理資源的映射，同時將用戶所需資源部署到具體的物理節點上，最終將資源分配給用戶，在用戶申請期限內，提供給用戶使用。

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

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

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

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

在云資源集合CS定義運算“+”“-”“>”“<”：

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

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

向量pm.s是對應服務器pm的性能屬性，用以描述服務器的資源容量，其內容由物理服務器pm決定，在服務器正常工作中，不會發生變化。而向量pm.v表達的是對應服務器pm的實時狀態，用以描述服務器在當前時刻可用資源總量，其內容由物理服務器pm當前資源余量決定，在服務器正常工作中，隨資源的分配與釋放實時變化。

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

PMC={pm1,pm2,…,pmm}

由定義1、2、3可知，在包含m臺物理服務器的集群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 問題模型

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

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

ur=

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

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

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

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

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

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

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

以sa表示云系統滿足ur的資源分配，有：

sa==

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

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

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

所研究的云資源調度算法以負載均衡為目標，與負載相關的定義如下。

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

定義5：服務器集群負載率(Physical Machine Cluster Load Factor)，以F表示。對于PMC，F的計算方法如下：

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

根據以上定義及描述，可對問題建立如下模型：

已知PMC，UR；

求解SA；

使得min PMC.BF

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

3 算法設計及分析

3.1 算法策略

云應用中，導致服務器集群負載不均衡的因素有兩個[13-15]：一是用戶資源需求的隨機性，云用戶根據自己的實際情況向云系統申請規格不同的資源量，這些不同的資源需求將導致服務器負載的不均衡；二是服務器本身所能提供的資源量也是大小不一的，這種服務器屬性同樣導致負載的不均衡。針對這兩點，提出以下策略。

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

在資源部署時，資源量越大，越容易造成負載的不均衡。因而，采用“最大需求者優先”原則，先處理資源申請量大的用戶需求。

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

(2)最低利用率被選。

對應于每一個ur，理論上可以由云系統中的任意一臺服務器提供。所以對應m個服務器，有m種分配方案，為，，…，，對應這m種方案，提供資源的服務器相關參數更新為：

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

3.2 算法步驟

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

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

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

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

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

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

(6)按資源需求量大小，對每一個資源請求ur：

(6.1)依次將其預分配到每一臺服務器上，計算相應服務器均衡負載率。

(6.2)記錄最小均衡負載率及相應服務器pm。

(6.3)若pm合法，進行資源部署，更新pm狀態，并創建資源服務項，將其加入資源服務隊列中，轉到步驟(7)，否則轉步驟(4)。

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

(7)t=t+1。

(8)轉到步驟(2)。

算法描述如圖2所示。

圖2 算法描述

3.3 算法分析

(1)算法時間復雜度。

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

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

(2)相關參數計算。

在算法執行過程中，隨著資源的分配與釋放，物理服務器及服務器集群的相關參數也會發生變化。

在時刻t，首先系統釋放到期服務資源，再為該時刻的用戶需求進行資源分配。若：

則：

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

一輪算法執行完畢后，PMC中服務器可用資源及負載率為：

PMC的可用資源、負載率及負載均衡系數為：

4 實驗及結果分析

為進一步研究算法效果，通過仿真實驗分析算法演化過程及結果。實驗中，取服務器集群數量為6，僅考慮一種資源的情況，服務器資源參數如表1所示。

表1 服務器資源參數

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

兩組參數對應的服務器集群負載均衡系數為：

PMC(1).BF=0.062 21

PMC(2).BF=0.055 72

實驗結果表明，服務器集群中，無論服務器屬性是否有差異性，提出算法均可達到較好的負載均衡性能。

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

實驗結果表明，提出的負載均衡資源調度算法相比于傳統資源調度算法具有明顯的優越性，特別是在服務器屬性差異性較大的情況下。表2列出了第二組參數下，提出的“最大資源需求優先，最低利用率被選”資源調度策略和隨機調度策略下，各服務器及服務器集群的平均負載率數據。

(a)第一組實驗結果

(b)第二組實驗結果

(a)第一組實驗結果

(b)第二組實驗結果

表2 兩種策略下的服務器負載率

5 結束語

在云資源調度中，為保證服務器集群負載均衡，在構建云資源調度負載均衡模型的基礎上，提出了一種基于最大需求優先，最閑服務器被選原則的云計算資源調度方法。實驗結果表明，與傳統資源調度算法相比，提出方法具有優越的負載均衡性能和廣泛的適應性。該方法可合理協調用戶需求和服務器屬性，以實現云資源負載均衡。

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

[2] 洪 斌,彭甫陽,鄧 波,等.云資源狀態監控研究綜述[J].計算機應用與軟件,2016,33(6):1-6.

[3] 賴培源,馬衛民,劉 藝,等.云資源池網絡自動化部署技術研究與實踐[J].電信科學,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] 魏 蔚,劉 揚,楊衛東.一種通用云計算資源調度問題的快速近似算法[J].計算機研究與發展,2016,53(3):697-703.

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

[8] 孟 蒙,茅 蘇.基于云計算的可反饋負載均衡策略的研究[J].計算機技術與發展,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負載均衡研究[J].小型微型計算機系統,2016,37(3):417-421.

[11] Levitin A. 算法設計與分析基礎[M].潘 彥,譯.第3版.北京:清華大學出版社,2015.

[12] 王永明,尹紅麗,秦開大.作業車間調度理論及其優化方法研究[M].北京:科學出版社,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] 宋 滸.面向用戶服務需求的云計算管理機制研究[D].合肥:中國科學技術大學,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 網絡出版時間：2017-04-28

軍內科研計劃項目(HJ-502-2015-35)

陳 斌(1975-)，男，博士生，副教授，研究方向為通信與信息系統。

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