具有兩類請求的云計算中心服務器數(shù)量的優(yōu)化

張江強，趙寧，劉文奇

(昆明理工大學 理學院,云南 昆明 650500)

具有兩類請求的云計算中心服務器數(shù)量的優(yōu)化

張江強，趙寧，劉文奇

(昆明理工大學 理學院,云南 昆明 650500)

為提高云計算中心的服務質(zhì)量，節(jié)約系統(tǒng)成本，針對具有兩類用戶請求的云計算中心，提出云計算中心的服務器數(shù)量的優(yōu)化方案。 首先，建立了具有兩類用戶請求的排隊模型，分析系統(tǒng)的穩(wěn)態(tài)概率分布、平均隊長等性能指標；然后,建立了云計算中心的能耗模型；最后，聯(lián)合系統(tǒng)的等待成本和能耗成本，構(gòu)建系統(tǒng)的成本函數(shù), 對系統(tǒng)的服務器數(shù)量進行優(yōu)化，從而使系統(tǒng)的成本最小。數(shù)值分析結(jié)果表明最優(yōu)服務器數(shù)量是用戶請求到達率的非減函數(shù)，為了使系統(tǒng)成本最小，云計算中心需要動態(tài)調(diào)整服務器的數(shù)量。

云計算；排隊系統(tǒng)；兩類請求；性能指標；能耗；成本；服務器數(shù)量的優(yōu)化

云計算中心是基于超級計算機系統(tǒng)對外提供計算資源、存儲資源等服務的機構(gòu)或單位，以高性能計算機為基礎面向各界提供高性能計算服務。當前，云計算中心主要面向大規(guī)?？茖W計算及工程計算應用，并在商業(yè)計算、互聯(lián)網(wǎng)、電子政務、電子商務等領域擁有巨大發(fā)展?jié)摿Αυ朴嬎阒行牡男阅芎湍芎倪M行全面地分析具有十分重要的意義。

云計算中心作為服務機構(gòu)，系統(tǒng)的性能指標(用戶請求的等待時間、系統(tǒng)的堵塞程度等)是刻畫服務質(zhì)量的重要因素。將用戶請求看作顧客，云計算中心的超級計算機的處理器作為服務器，而用戶請求的處理過程作為服務過程，云計算中心是一個典型的排隊系統(tǒng)。很多學者對云計算中心的性能及調(diào)度策略方面展開研究。廖倩文等[1]提出一種基于排隊論的批量到達的云計算中心性能分析模型,得到系統(tǒng)中用戶請求隊長的穩(wěn)態(tài)概率分布、系統(tǒng)的阻塞概率、立即服務概率等指標。徐小龍等[2]研究了云計算系統(tǒng)任務調(diào)度和數(shù)據(jù)部署層面的節(jié)能機制, 提出一種面向綠色云計算中心的動態(tài)數(shù)據(jù)聚集算法。許丞[3]建議將Hadoop云平臺的任務監(jiān)控和任務調(diào)度管理功能分離，從而提升云平臺的工作效率。倪志偉[4]綜合考慮了用戶最短等待時間資源負載均衡和經(jīng)濟原則，提出一種離散人工蜂群算法的云任務調(diào)度優(yōu)化策略。

在云計算中心，能耗開銷是不容忽視的問題，著名IT企業(yè)如Google、Microsoft、 Amazon等云計算中心每年能耗超過百萬美元，給云計算中心長期運營帶來了巨大經(jīng)濟負擔。云計算中心的能耗問題最近得到學者的廣泛關注。羅亮等[5]從處理器性能計數(shù)器和系統(tǒng)使用情況入手，結(jié)合多元線性回歸和非線性回歸的數(shù)學方法，分析不同參數(shù)和方法對服務器能耗建模的影響，并提出適合云計算中心基礎架構(gòu)的服務器能耗模型?，F(xiàn)有內(nèi)存能耗模型研究發(fā)現(xiàn)，影響內(nèi)存能耗的主要因素是內(nèi)存讀寫的吞吐量[6]。何懷文等[7]在平均響應時間受限的條件下提出云計算中心異構(gòu)服務器之間的優(yōu)化能耗分配方法。針對云計算中心由于服務器空閑而產(chǎn)生大量空閑能耗，以及由于任務調(diào)度不匹配而產(chǎn)生大量“奢侈”能耗的問題，文獻[8-10]提出通過任務調(diào)度的方式優(yōu)化管理。文獻[11]研究了云計算中心的動態(tài)遷移問題。文獻[12]以利潤最大化為目標，分析了云計算中心的優(yōu)化配置。針對多個服務器切換過程存在大量冗余信號的問題，文獻[13]提出了一種改進的多業(yè)務切換機制。文獻[14]運用遺傳算法分析用戶請求的調(diào)度策略，從而提高云計算中心能源利用率。文獻[15-16]對云計算中心的能耗和性能進行了聯(lián)合優(yōu)化。

以上關于云計算中心的相關研究都假設系統(tǒng)只有一類用戶請求，但實際應用中，云計算中心根據(jù)用戶請求的重要程度分為不同等級[17]。例如，云計算中心將實時用戶請求賦予高優(yōu)先權(quán)，將非實時用戶請求賦予低優(yōu)先權(quán)。另外，為了吸引更多客戶，云計算中心為用戶提供免費體驗的服務，而付費的用戶相對免費用戶享有高優(yōu)先權(quán)。Liu等[18]運用博弈論的方法研究具有多類用戶請求的云計算中心的預約服務策略。

本文將研究具有兩類用戶請求的云計算中心能耗和性能的聯(lián)合優(yōu)化問題。假設兩類用戶請求的到達過程均為泊松過程，系統(tǒng)有多個平行的處理器，每個用戶請求的處理時間服從指數(shù)分布，系統(tǒng)最多容納有限的用戶請求。我們將該系統(tǒng)構(gòu)建為一個帶非搶占優(yōu)先權(quán)的馬爾可夫過程，基于排隊論對該系統(tǒng)的性能進行分析。將系統(tǒng)的能耗表示為處理器吞吐量和處理器個數(shù)的函數(shù)。最后，結(jié)合系統(tǒng)的性能和能耗構(gòu)建系統(tǒng)的成本函數(shù)，對系統(tǒng)處理器的個數(shù)進行優(yōu)化。

1 系統(tǒng)描述

假設云計算中心有c個平行的服務器，按照用戶的優(yōu)先級別，將用戶請求分為兩類，第i類用戶請求到達過程是參數(shù)為λi的泊松過程，i=1,2。系統(tǒng)最多容納N個用戶請求，當系統(tǒng)中的用戶請求個數(shù)小于N，用戶請求的到達率為λ=λ1+λ2，否則到達率λ=0。用戶請求到達云計算中心后，如果系統(tǒng)中有空閑的服務器，則用戶請求直接進入空閑服務器接受服務，反之則需要在緩沖區(qū)中排隊等待接受服務。第1類用戶請求相對第2類用戶請求具有非搶占優(yōu)先權(quán)，即系統(tǒng)中的第1類用戶請求被優(yōu)先服務，但是第1類用戶請求不能打斷第2類用戶請求的服務，對于每1類用戶請求，系統(tǒng)按照先到先服務的規(guī)則(FCFS)進行服務。第i類用戶請求的服務時間服從參數(shù)為μi的指數(shù)分布，i=1,2。

2 系統(tǒng)性能分析

具有兩類用戶請求的云計算中心是一個非搶占優(yōu)先權(quán)的M1,M2/M1,M2/(c/N)排隊模型，如圖1所示。

圖1 具有兩類用戶請求的排隊系統(tǒng)Fig.1 Queueing system with two demand classes

令(l1,l2)表示系統(tǒng)的狀態(tài)，其中l(wèi)i表示系統(tǒng)中第i類用戶請求的個數(shù)，該系統(tǒng)的狀態(tài)空間為

E={(l1,l2),l1,l2=0,1,…,N,l1+l2=N}。

l=0的狀態(tài): (0，0)。

l=1的狀態(tài): (1，0)，(0，1)。

l=2的狀態(tài): (2,0), (1,1), (0,2)。

?

l=N的狀態(tài):(N,0)，(N-1,1)，(N-2,2)，…，

(2,N-2)，(1,N-1)，(0,N)。

任意水平l可能存在的狀態(tài)轉(zhuǎn)移為l→l-1，l→l，l→l+1。狀態(tài)轉(zhuǎn)移如圖2所示。按照水平的順序?qū)λ袪顟B(tài)排序，M1,M2/M1,M2/(c/N)排隊模型的Q矩陣可表示為

式中：Al,l-1對應水平l到水平l-1的矩陣塊，Al,l對應水平l到水平l的矩陣塊，Al,l+1對應水平l到水平l+1的矩陣塊(1≤l≤N-1)，B00對應l=0到l=0的值，B01對應l=0到l=1的矩陣塊。Q矩陣的矩陣塊隨著水平l的增大而逐漸增大。令

αi=min(i,c)

βl,i=min(l-i,c),i=0,1,2,…,l

B00=-λ1-λ2

B01=[λ1λ2]

圖2 系統(tǒng)狀態(tài)轉(zhuǎn)移圖Fig.2 Transitions among the system states

π=(π0,0,π1,0,π0,1,…,πN,0,πN-1,1,…,π0,N)

系統(tǒng)的穩(wěn)態(tài)概率π分布可以通過求解如下方程組得到：

系統(tǒng)中兩類用戶請求的平均隊長分別為

根據(jù)Little法則，兩類用戶請求的平均等待時間分別為

E(T1)=E(L1)/λ1

E(T2)=E(L2)/λ2

系統(tǒng)中用戶請求的平均等待時間為

3 系統(tǒng)能耗

云計算中心服務器的能耗主要包括靜態(tài)能耗和動態(tài)能耗。通常靜態(tài)能耗比較穩(wěn)定，假設每個服務器的靜態(tài)能耗P*為常數(shù)，c個服務器的靜態(tài)能耗為P靜=cP*。

根據(jù)文獻[19]，當服務器的服務速率為μ時，單個服務器的動態(tài)能耗為kμα(單位為瓦)，其中k為功耗比例因子，α≥3。由于系統(tǒng)中服務第i類用戶請求的平均服務器數(shù)量為cρi(i=1,2)，因此系統(tǒng)的動態(tài)能耗為

系統(tǒng)的總體能耗為

4 系統(tǒng)成本

云計算中心作為服務系統(tǒng)，用戶請求的等待時間反應了的系統(tǒng)的服務質(zhì)量，較長的等待時間必然影響用戶對系統(tǒng)的評價，從而導致系統(tǒng)用戶的丟失。系統(tǒng)可以通過增加服務器的方式減少用戶請求的等待時間。 但是服務器的增加，必然導致系統(tǒng)能耗增加。下面構(gòu)建系統(tǒng)成本，對系統(tǒng)服務器的數(shù)量進行優(yōu)化。

系統(tǒng)成本包括用戶的等待成本和系統(tǒng)能耗成本。令hi表示一個第i類用戶請求單位時間的逗留費用，則系統(tǒng)的等待成本為h1E(L1)+h2E(L2)；令β為單位能耗價格，則系統(tǒng)的能耗成本為βP總，其中higt;0，βgt;0，i=1,2。

因此，系統(tǒng)單位時間的成本為

f(c)=h1E(L1)+h2E(L2)+βP總

系統(tǒng)最優(yōu)成本可表示為如下數(shù)學規(guī)劃問題：

5 算例分析

下面針對具有兩類用戶請求的云計算中心的排隊模型進行數(shù)值實驗。假設h1=40，h2=20,β=0.8,N=100,μ1=μ2=1.5，調(diào)整參數(shù)λ1,λ2或服務器的數(shù)目c，計算系統(tǒng)的性能指標，并求解系統(tǒng)能耗及最優(yōu)的服務器的數(shù)目。

例1 假設兩類用戶請求的到達率不變，分析服務器數(shù)量c對系統(tǒng)的影響。假設h1=40，h2=20，β=0.8，N=100，μ1=μ2=1.5，λ1=1，λ2=2.5，c=1,2,…,7。表1計算了服務器個數(shù)c取不同值的情況下，系統(tǒng)的服務強度ρ、平均隊長E(L1)和E(L2)、平均等待時間E(T)、系統(tǒng)能耗P總及系統(tǒng)單位時間成本f(c)。表1顯示隨著服務器個數(shù)c的增加，ρ、E(L1)、E(L2)、E(T)均減小，但是P總增加。隨著c增加，系統(tǒng)的單位時間成本先增大后減小，在c=4時f(c)取得最小值，且f(c*)=77.671 8。實際上，對于任意的(λ1,λ2)，最優(yōu)值c*總是存在的，我們都可以通過表1的方式求解最優(yōu)值c*。

表1 云計算中心的性能、能耗及成本分析(例1)

例2 假設第二類用戶請求的到達率不變，分析第一類用戶請求的到達率增大對系統(tǒng)的影響。假設h1=40，h2=20，β=0.8，N=100,μ1=μ2=1.5，λ2=3，λ1∈[0.5,3]。首先，對于給定的λ1，通過例1的方法求解最優(yōu)值c*。其次，令c=c*，分析系統(tǒng)的如下性能參數(shù)：ρ、E(L1)、E(L2)、E(T)、P總及f(c*)。表2的數(shù)值結(jié)果顯示隨著λ1增大，c*不變或增大(如圖3所示)，E(L1)、P總及f(c*)均隨著λ1增大而增大。

表2 云計算中心的性能、能耗及成本分析(例2)

例3 假設第一類用戶請求的到達率不變，分析第二類用戶請求的到達率增大對系統(tǒng)的影響。假設h1=40，h2=20，β=0.8，N=100,μ1=μ2=1.5，λ1=1，λ2∈[1.25,4]。首先，對于給定的λ2，通過例1的方法求解最優(yōu)值c*。 其次，令c=c*，分析系統(tǒng)的如下性能指標：ρ、E(L1)、E(L2)、E(T)、P總及f(c*)。表3的數(shù)值結(jié)果顯示，隨著λ2增大，c*不變或增大(如圖4所示)，E(L2)、P總及f(c*)隨著λ2增大而增大，而ρ、E(L1)、E(T)未呈現(xiàn)單調(diào)性。

圖3 最優(yōu)服務器數(shù)量(例2)Fig.3 The optimal number of servers (example 2)

λ2c?ρE(L1)E(L2)E(T)P總f(c?)1．2530．50000．67580．85550．680613．883955．24771．530．55560．67571．04530．688414．239259．32641．7530．61110．67571．25050．700414．544163．6717230．66670．67561．47740．717714．806568．41702．2540．54170．66751．54440．680619．968673．56302．540．58330．66771．73970．687820．211677．67182．7540．62500．66751．94770．697420．418981．9911340．66670．66752．17330．710220．596286．64353．2540．70830．66752．42320．727220．747891．76183．550．60000．66662．42290．686626．049095．96283．7550．63330．66672．62980．694026．1811100．2115450．66670．66662．85090．703526．2935104．7176

圖4 最優(yōu)服務器數(shù)量(例3)Fig.4 The optimal number of servers (example 3)

6 結(jié)束語

本文基于排隊論分別對具有兩類用戶請求的云計算中心建立相應的排隊模型，分析系統(tǒng)中用戶請求的穩(wěn)態(tài)概率分布、平均隊長等性能指標；通過引入等待成本和能耗成本，構(gòu)建系統(tǒng)單位時間的成本函數(shù)，分析系統(tǒng)的最優(yōu)服務器的數(shù)量。研究發(fā)現(xiàn)，隨著用戶請求到達率變化，最優(yōu)服務器數(shù)量可能會發(fā)生變化，服務器數(shù)量的最優(yōu)值是用戶請求到達率的非減函數(shù)。對于任意的到達率，都可以得到最優(yōu)的服務器數(shù)量，這為云計算中心的資源配置提供理論依據(jù)。

本文討論的云計算中心具有兩類用戶請求，服務規(guī)則是非搶占優(yōu)先服務，然而，在實際中存在搶占服務規(guī)則的情況及多類型用戶請求的云計算中心，在后續(xù)的研究中可以討論更多類型的用戶請求問題及搶占服務規(guī)則的情況，并對多類用戶請求的調(diào)度策略進行分析。

[1]廖倩文, 潘久輝, 王開杰. 基于排隊理論的云計算中心性能分析模型[J]. 計算機工程, 2015, 41(9): 51-55.

LIAO Qianwen, PAN Jiuhui, WANG Kaijie. Performance analysis model of cloud computing center based on queueing theory[J]. Computer engineering, 2015, 41(9): 51-55.

[2]徐小龍，楊庚，李玲娟，等. 面向綠色云計算數(shù)據(jù)中心的動態(tài)數(shù)據(jù)聚集算法[J]. 系統(tǒng)工程與電子技術, 2012, 34(9): 1923-1929.

XU Xiaolong, YANG Geng， LI Lingjuan， el al. Dynamic data aggregation algorithm for data centers of green cloud computing[J]. Systems engineering and electronics, 2012, 34(9): 1923-1929.

[3]許丞, 劉洪, 譚良. Hadoop云平臺的一種新的任務調(diào)度和監(jiān)控機制[J]. 計算機科學, 2013, 40(1): 112-117.

XU Chen, LIU Hong, TAN Liang. New mechanism of monitoring on Hadoop cloud platform[J]. Computer science, 2013, 40(1): 112-117.

[4]倪志偉, 李蓉蓉， 方清華，等. 基于離散人工蜂群算法的云任務調(diào)度優(yōu)化[J]. 計算機應用, 2016, 36(1): 107-112,121.

NI Zhiwei, LI Rongrong, FANG Qinghua，et al. Optimization of cloud task scheduling based on discrete artificaial bee colony algorithm[J]. Journal of computer applications, 2016, 36(1): 107-112,121.

[5]羅亮, 吳文峻, 張飛. 面向云計算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學報, 2014, 25(7): 1371-1387.

LUO Liang, WU Wenjun, ZHANG Fei. Energy modeling based on cloud data center[J]. Journal of software, 2014, 25(7)： 1371-1387.

[6]CAO J, LI K, STOJMENOVIC I. Optimal power allocation and load distribution for multiple heterogeneous multicore server processors across clouds and data centers[J]. IEEE transactions on computers, 2014, 63(1): 45-58.

[7]何懷文, 傅瑜, 楊亮，等. 性能受限下云中心異構(gòu)服務器的能耗優(yōu)化[J]. 計算機應用, 2015, 35(1): 39-42,61.

HE Huaiwen，F(xiàn)U Yu，YANG Liang, et al. Optimal power consumption of heterogeneous servers in cloud center under performance constraint[J]. Journal of computer applications, 2015, 35(1): 39-42,61.

[8]譚一鳴, 曾國蓀, 王偉. 隨機任務在云計算平臺中能耗的優(yōu)化管理方法[J]. 軟件學報,2012, 23(2): 266-278.

TAN Yiming, ZENG Guosun, WANG Wei. Policy of energy optimal management for cloud computing platform with stochastic tasks[J]. Journal of software, 2012, 23(2): 266-278.

[9]KE M, YEH C, SU C. Cloud computing platform for real-time measurement and verification of energy performance[J]. Applied energy, 2017, 188: 497-507.

[10]SINGH S, CHANA I. EARTH: Energy-aware autonomic resource scheduling in cloud computing[J]. Journal of intelligent amp; fuzzy systems, 2016, 30(3):1581-1600.

[11]TAO F, LI C, LIAO T, et al. BGM-BLA: a new algorithm for dynamic migration of virtual machines in cloud computing[J]. IEEE transactions on services computing, 2016, 9(6): 910-925.

[12]MEI J, LI K, OUYANG A, et al. A profit maximization scheme with guaranteed quality of service in cloud computing[J]. IEEE transactions on computers, 2015, 64(11): 3064-3078.

[13] QI Q, LIAO J, WANG J.Integrated multi-service handoff mechanism with QoS-support strategy in mobile cloud computing[J]. Wireless personal communications, 2016, 87(2): 593-614.

[14]HUANG Z, LU Y, OUYANG H. Scheduling strategy based on genetic algorithm for cloud computer energy optimization[C]//2015 IEEE International Conference on Communication Problem-Solving. Guilin, China, 2015:516-519.

[15]YANG B, LI Z, CHEN S, et al. Stackelberg game approach for energy-aware resource allocation in data centers[J]. IEEE transactions on parallel and distributed systems, 2016， 27(12): 3646-3658.

[16]SURESH S, SAKTHIVEL S. System modeling and evaluation on factors influencing power and performance management of cloud load balancing algorithms[J]. Journal of web engineering, 2016, 15(5/6): 484-500.

[17]李春艷，何一舟，戴彬. Hadoop平臺的多隊列作業(yè)調(diào)度優(yōu)化方法研究[J]. 計算機應用研究, 2014(03): 705-707,738.

LI Chunyan, HE Yizhou, DAI Bin. Research on optimization of job scheduling based on multi-queue for Hadoop platform[J]. Application research of computers, 2014(3): 705-707, 738.

[18]LIU C, LI K, XU C, et al. Strategy configurations of multiple users competition for cloud service reservation[J].IEEE transactions on parallel and distributed systems, 2016, 27(2): 508-520.

[19]ZHURAVLEV S, CARLOS SAEZ J, BLAGODUROV S. Survey of energy-cognizant scheduling techniques[J]. IEEE transactions on parallel and distributed systems, 2013, 24(7): 1447-1464.

張江強，男，1992年生，碩士研究生，主要研究方向為排隊論。

趙寧，女，1980年生，副教授，博士，主要研究方向為排隊論。發(fā)表學術論文10余篇。

劉文奇，男，1965年生，教授，主要研究方向為數(shù)據(jù)挖掘和決策分析。發(fā)表學術論文40余篇，出版學術專著2部。

Optimizationofthenumberofserversinacloudcomputationcenterwithtwodemandclasses

ZHANG Jiangqiang， ZHAO Ning， LIU Wenqi

(Faculty of Science, Kunming University of Science and Technology, Kunming 650500, China)

In order to improve the service quality and to save the system cost of the cloud computing center, for a cloud computing center with two demand classes, a method to optimize the number of servers was proposed. First, a queuing model having two demand classes was established for analyzing performance measures such as distribution of the probability of stability and mean queue length; next, a power consumption model was established on the cloud computing center; finally, the wait and power-consumption cost of the system were used together to construct the cost function of the system and optimize the server quantity for realizing the lowest cost. The numerical results show that the optimal number of servers is a non-decreasing function of the arrival rate of demands. To minimize the system cost, dynamically adjusting the number of servers is necessary.

cloud computing; queuing system; two demand classes; performance measure; power consumption; cost; optimization of the number of servers

10.11992/tis.201703042

http://kns.cnki.net/kcms/detail/23.1538.TP.20170702.1547.036.html

TP393.02

A

1673-4785(2017)05-0601-07

中文引用格式：張江強，趙寧，劉文奇.具有兩類請求的云計算中心服務器數(shù)量的優(yōu)化J.智能系統(tǒng)學報， 2017, 12(5): 601-607.

英文引用格式：ZHANGJiangqiang，ZHAONing，LIUWenqi.OptimizationofthenumberofserversinacloudcomputationcenterwithtwodemandclassesJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 601-607.

2017-03-27. < class="emphasis_bold">網(wǎng)絡出版日期

日期：2017-07-02.

國家自然科學基金項目(71501086，61573173).

趙寧. E-mail：zhaoning@kmust.edu.cn.