一種通用云計(jì)算資源調(diào)度問題的快速近似算法

魏　蔚　劉　揚(yáng)　楊衛(wèi)東

(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院　鄭州　450001)

(nsyncw@126.com)

?

一種通用云計(jì)算資源調(diào)度問題的快速近似算法

魏蔚劉揚(yáng)楊衛(wèi)東

(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院鄭州450001)

(nsyncw@126.com)

A Fast Approximation Algorithm for the General Resource Placement Problem in Cloud Computing Platform

Wei Wei, Liu Yang, and Yang Weidong

(CollegeofInformationScienceandEngineering,HenanUniversityofTechnology,Zhengzhou450001)

AbstractThere are regionally distributed demands for various resources in cloud based large-scale online services. Given fixed resource budget, the service providers need to decide where to place resources to satisfy massive demands from all regions, where demands are usually represented by mean value in given time span. However, in scenarios with a large number of resources, demands are dynamic and stochastic, considering fine-grained demands and adopting stochastic model will further improve resource utilization. Compared with mean demand-based algorithm, considering demand stochasticity in algorithm will increase resource utilization ratio, but also leads to high time complexity. The time complexity of optimal algorithm is linear to total amount of resources, thus may be inefficient when dealing with a large number of resources. Based on nonlinear programming theory, we propose Fast Resource Placement (FRP), an effective resource placement method of high efficiency. In the algorithm, optimal solution is represented by continuous functions of input, and we construct approximation functions to reduce the computation complexity. The preliminary experiments show that in scenarios with general settings, compared with optimal algorithm, FRP can reduce the computation time by three orders of magnitude, and can achieve 99% effect of optimal solution. Therefore, FRP can be used to schedule large number of resources efficiently in time-tense scheduling scenarios.

Key wordsstochastic demand; resource scheduling; resource placement; nonlinear programming; cloud computing

摘要在分布式云計(jì)算平臺(tái)中，面向大規(guī)模用戶的在線應(yīng)用需處理針對(duì)海量資源的用戶需求，在給定的資源預(yù)算下，服務(wù)提供商需確定最優(yōu)資源放置位置，以最大程度地滿足用戶需求,通常需求用給定時(shí)間段內(nèi)均值表示.然而真實(shí)場景中用戶需求是高度動(dòng)態(tài)和隨機(jī)的，采用隨機(jī)需求模型以考慮更多需求細(xì)節(jié)，資源利用率可得到進(jìn)一步優(yōu)化.但相比均值調(diào)度方法，隨機(jī)需求模型會(huì)導(dǎo)致很高的計(jì)算復(fù)雜度.已有的最優(yōu)解求解算法的時(shí)間復(fù)雜度和資源總量成正比，無法滿足海量資源在線調(diào)度的效率要求.基于非線性規(guī)劃理論，提出了一個(gè)快速資源分配算法，該算法可將計(jì)算復(fù)雜度降低至最優(yōu)解算法的1‰，并逼近最優(yōu)解效果的99%，因此可用于在線應(yīng)用場景中海量資源的高效調(diào)度.

關(guān)鍵詞隨機(jī)需求；資源調(diào)度；資源放置；非線性規(guī)劃；云計(jì)算

大規(guī)模在線服務(wù)系統(tǒng)(如YouTube[1]和Facebook[2])面臨來自全球各個(gè)區(qū)域的高度動(dòng)態(tài)的用戶請(qǐng)求，可利用云計(jì)算平臺(tái)降低費(fèi)用并提升用戶體驗(yàn).在典型的分布式云計(jì)算平臺(tái)中，需妥善分配資源到全球各個(gè)云數(shù)據(jù)中心以滿足盡可能多的用戶請(qǐng)求；且對(duì)于單個(gè)用戶請(qǐng)求，傾向分發(fā)到較近的數(shù)據(jù)中心以提供較好的用戶體驗(yàn).

已有工作初步探討了在上述場景中進(jìn)行資源調(diào)度的若干問題.在流媒體分發(fā)的相關(guān)工作中，文獻(xiàn)[3]深入分析了面向流處理服務(wù)的資源部署問題，考慮了經(jīng)由中間節(jié)點(diǎn)響應(yīng)客戶請(qǐng)求的情況，采用集合覆蓋等方法從多角度規(guī)約問題獲取最優(yōu)解.文獻(xiàn)[4]分析了混合云中面向視頻點(diǎn)播服務(wù)的資源配置問題，通過限制平均延時(shí)以保證服務(wù)質(zhì)量，利用李雅普諾夫優(yōu)化方法獲得長時(shí)間范圍內(nèi)的統(tǒng)計(jì)平均最優(yōu).在內(nèi)容分發(fā)網(wǎng)絡(luò)研究方向上，文獻(xiàn)[5]考慮利用空閑帶寬分發(fā)容遲數(shù)據(jù)，通過延時(shí)調(diào)度充分復(fù)用帶寬資源并減少平均分發(fā)時(shí)間，采用任務(wù)調(diào)度與資源整合相結(jié)合的思路.文獻(xiàn)[6]中的MetaCDN架構(gòu)將用戶內(nèi)容分發(fā)到多個(gè)不同的存儲(chǔ)云中，最大化租用費(fèi)用及服務(wù)質(zhì)量相關(guān)的效用函數(shù).文獻(xiàn)[7]提出基于拉普洛夫優(yōu)化理論的通用優(yōu)化框架，在保證服務(wù)質(zhì)量的前提下最小化操作費(fèi)用.文獻(xiàn)[8]研究了存儲(chǔ)云中的內(nèi)容存放問題，以及在存儲(chǔ)云間的分發(fā)網(wǎng)絡(luò)構(gòu)建問題，并提出了多種啟發(fā)式算法.文獻(xiàn)[9]設(shè)計(jì)了一種結(jié)合樹形和網(wǎng)狀拓?fù)涞男滦突旌戏职l(fā)架構(gòu)，采用網(wǎng)絡(luò)編碼方法提高分發(fā)效率，保證服務(wù)質(zhì)量同時(shí)可大幅降低骨干網(wǎng)流量.文獻(xiàn)[10] 提出了基于用戶行為特征的資源分配策略，通過統(tǒng)計(jì)用戶工作習(xí)慣與任務(wù)完成時(shí)間期望值的變化規(guī)律，建立用戶行為特征信息表，從而動(dòng)態(tài)調(diào)整云計(jì)算系統(tǒng)的資源分配策略.文獻(xiàn)[11]引入用戶效用的概念，建立了云環(huán)境中用戶效用的描述模型，給出了用戶對(duì)任務(wù)執(zhí)行時(shí)間和費(fèi)用滿意程度的量化方法，基于線性規(guī)劃理論提出了云環(huán)境中面向用戶效用的任務(wù)調(diào)度優(yōu)化模型.除了高度相關(guān)的云計(jì)算方向研究工作，P2P領(lǐng)域中的相關(guān)工作也研究了類似的資源調(diào)度問題[12].

上述工作采用均值需求模型以保證調(diào)度算法效率，然而真實(shí)場景中用戶需求是高度動(dòng)態(tài)和隨機(jī)的，通過考慮更多需求細(xì)節(jié)，采用隨機(jī)需求模型，資源利用率可得到進(jìn)一步優(yōu)化.在均值模型中，資源需求通過給定調(diào)度時(shí)間間隔內(nèi)資源需求量均值表示，參與運(yùn)算的是代表均值的標(biāo)量值；隨機(jī)需求模型中，資源需求使用隨機(jī)變量表示，參與運(yùn)算的一般是需求的累積概率分布函數(shù).文獻(xiàn)[13-14]將基于隨機(jī)需求的通用資源調(diào)度問題轉(zhuǎn)化為最小費(fèi)用最大流問題，并提出基于連續(xù)最短路徑的最優(yōu)解算法.其中，文獻(xiàn)[13]的問題設(shè)定中，每區(qū)域有資源限制，目標(biāo)是最大化滿足的需求數(shù)量的期望值；文獻(xiàn)[14]的問題設(shè)定中，沒有區(qū)域資源限制，目標(biāo)是資源費(fèi)用和收益組合表示的整體代價(jià)最小化.但基于連續(xù)最短路徑求解算法的復(fù)雜度與資源總量成正比例，無法滿足大規(guī)模場景下實(shí)時(shí)快速調(diào)度的時(shí)間要求.

通過觀察通用分配問題的內(nèi)部結(jié)構(gòu)，我們提出了快速近似算法，論文的創(chuàng)新點(diǎn)如下:1)證明該問題可轉(zhuǎn)化為一個(gè)2階段優(yōu)化問題，可逐步快速求解；2)證明在每階段的子問題中，最優(yōu)結(jié)果均可表示為輸入?yún)?shù)的函數(shù)，并給出函數(shù)的數(shù)學(xué)表達(dá)式；3)采用離散函數(shù)模擬算法中的連續(xù)函數(shù)，提出了快速近似算法.實(shí)驗(yàn)結(jié)果表明，該算法在達(dá)到最優(yōu)解效果99%的情況下，時(shí)間復(fù)雜度可縮減至最優(yōu)解算法的1‰.

1通用資源分配問題

對(duì)來自區(qū)域j的對(duì)i型資源的請(qǐng)求，若該請(qǐng)求被分配給資源i，則該請(qǐng)求被標(biāo)記為“已滿足”.一個(gè)來自區(qū)域j的i型資源的請(qǐng)求被滿足，則將它分配到：1)位于區(qū)域j的i型資源，稱之為本地滿足；或2)位于其他區(qū)域的i型資源，稱之為遠(yuǎn)程滿足.若請(qǐng)求沒有被分配到任何資源，則將其標(biāo)記為“未滿足”.

(1)

(2)

(3)

則方案P的i型收益期望值為

(4)

因?qū)τ谌我膺B續(xù)的非負(fù)隨機(jī)變量x與常量C有:

(5)

其中,cdfx(·)是x的累積概率分布函數(shù)，則式(4)中i型收益可轉(zhuǎn)化為最終形式：

(6)

則所有i型收益的期望值的總和為總期望收益:

(7)

在通用的離線資源分配場景中，服務(wù)提供商通常會(huì)預(yù)訂定量的全局資源(總量記為U)，有:

(8)

(9)

(10)

(11)

2快速資源分配算法

在典型的云計(jì)算系統(tǒng)中，通用離線資源調(diào)度問題的輸入數(shù)據(jù)量會(huì)非常大，在常見場景中一般會(huì)有資源類型和區(qū)域數(shù)的乘積I×J≥104.為尋找高效的解決算法，我們首先研究最優(yōu)解的特征，首先引入定理1.

(12)

(13)

證畢.

(14)

因?yàn)長i(1≤i≤I)對(duì)給定的類型配置方案O是常量，則根據(jù)定理1，可由以下方法找到{P}O中達(dá)到最大i型期望收益的資源配置方案P′.

(15)

通過下述推論可找到限制U下的最優(yōu)方案：

為得到最優(yōu)算法，還需明確最優(yōu)類型配置方案和最優(yōu)配置方案間的內(nèi)在關(guān)系，描述如下：

基于推論1至推論4，在構(gòu)建需要的函數(shù)后，原問題可轉(zhuǎn)化為2階段優(yōu)化問題并快速求解：階段1中，對(duì)給定的全局限制U，根據(jù)推論2～3快速定位最優(yōu)類型配置方案O′；階段2中，根據(jù)推論1在 {P}O′中快速定位最優(yōu)資源配置方案P′.由推論4可知，P′即為滿足全局資源約束U的最優(yōu)方案.

算法1. 快速資源分配算法FRP.

輸入：需求累積分布函數(shù)cdfi(·),cdfi,j(·)及其反函數(shù);資源總量U;參數(shù)Xi,j=min(cdfi,j(x)=1|?x);

① FORi=1 toI

④ END IF

⑤ END FOR

⑥ FORk=0 toK

⑦v=wlockK;

⑧ FORi=1 toI

3實(shí)驗(yàn)

本文和文獻(xiàn)[13]問題設(shè)定較接近，且文獻(xiàn)[13]的求解方法具代表性，我們實(shí)現(xiàn)了文獻(xiàn)[13]中基于連續(xù)最短路徑(successive shortest path, SSP)的最優(yōu)求解算法，命名為SSP-RP(SSP based resource placement).基于相同的實(shí)驗(yàn)設(shè)定，比較均值算法、SSP-RP和FRP的求解效果，并驗(yàn)證FRP求解效率和效果之間的關(guān)系.其中，實(shí)驗(yàn)圖表涉及的比率型數(shù)據(jù)，均表示FRP方法收益與文獻(xiàn)[13]中SSP-RP方法收益的比值.在實(shí)驗(yàn)設(shè)定中，隨機(jī)用戶需求符合Zipf分布(同文獻(xiàn)[13])，即i型資源的平均需求占所有需求的比例如下：

(16)

(17)

首先我們比較3種方法在不同Zipf參數(shù)下效果的變化趨勢(shì).參考文獻(xiàn)[13]，實(shí)驗(yàn)設(shè)定如下：區(qū)域數(shù)量和資源數(shù)量分別是J=4和I=500，收益權(quán)值wloc=wsat=1，F(xiàn)RP的精度K=100，總請(qǐng)求量期望值λ=1 000.Zipf參數(shù)取較大范圍，為0.7～1.4.實(shí)驗(yàn)中我們比較3種方法在資源盈余(U=1 500>λ)和資源不足(U=500<λ)情況下的效果，如圖1和圖2所示，在圖1、圖2中，橫坐標(biāo)為Zipf參數(shù)，縱坐標(biāo)為期望收益.我們可看到在不同的Zipf參數(shù)下，F(xiàn)RP都要好于均值分配算法，且與SSP-RP算法的效果非常接近.

Fig. 1　Expected revenue with different Zipf values under deficit scenario.圖1　資源不足時(shí)收益與Zipf的關(guān)系

Fig. 2　Expected revenue with different Zipf values under surplus scenario.圖2　資源盈余時(shí)收益與Zipf的關(guān)系

為明確資料類型數(shù)量I對(duì)算法的影響，我們還比較了3種方法的效果隨資源類型數(shù)變化趨勢(shì)，實(shí)驗(yàn)設(shè)定如下：資源數(shù)量分別是J=4和I=500，收益權(quán)值wloc=wsat=1，F(xiàn)RP的精度K=100，總請(qǐng)求量期望值λ=1 000，Zipf=1.0.同文獻(xiàn)[13]，取I∈[100,1 000]，以涵蓋不同數(shù)量級(jí)的資源數(shù)量.我們比較了I為100～1 000時(shí)3種算法的求解效果，如圖3和圖4所示，在不同的資源數(shù)量I下，F(xiàn)RP的效果也始終優(yōu)于均值方法，和SSP-RP方法接近.

Fig. 3　Expected revenue with different number of resource types under deficit scenario.圖3　資源不足時(shí)收益與資源數(shù)量的關(guān)系

Fig. 4　Expected revenue with different number of resource types under surplus scenario.圖4　資源盈余時(shí)收益與資源數(shù)量的關(guān)系

同時(shí)從圖1～4的2個(gè)實(shí)驗(yàn)中，可看到隨著資源數(shù)量由不足轉(zhuǎn)為盈余，均值方法的效果也逐漸接近SSP-RP最優(yōu)求解算法，使得FRP和SSP-RP的優(yōu)勢(shì)不明顯.分析實(shí)驗(yàn)數(shù)據(jù)后發(fā)現(xiàn)，隨著資源數(shù)量的增加，由于待滿足的請(qǐng)求沒有變化，問題優(yōu)化空間縮小導(dǎo)致優(yōu)化效果不明顯.而實(shí)際場景中資源數(shù)量一般都略有不足，因此FRP相比均值算法仍有很大優(yōu)勢(shì).

我們同時(shí)在通用場景中比較了FRP和SSP-RP的效果.首先比較在不同Zipf參數(shù)和資源數(shù)量I下FRP和SSP-RP期望收益的比率，如圖5和圖6所示.我們可看到FRP受Zipf參數(shù)輕微影響，同時(shí)也會(huì)受資源總量I的影響，資源不足時(shí)資源收益略低一些.分析實(shí)驗(yàn)數(shù)據(jù)后我們發(fā)現(xiàn)，因?yàn)樽詈蟮姆峙浣Y(jié)果會(huì)4舍5入到整數(shù)，資源不足情況下，舍入對(duì)結(jié)果影響較大.

Fig. 5　Revenue ratio of FRP to SSP-RP with different Zipf values.圖5　FRP和SSP-RP的收益比率與Zipf的關(guān)系

Fig. 6　Revenue ratio of FRP to S-URP with different number of resource types.圖6　FRP和SSP-RP的收益比率與資源數(shù)量的關(guān)系

FRP算法的時(shí)間復(fù)雜度與精度K成正比，因而我們?cè)嚤容^不同K下FRP的期望收益和SSP-RP算法結(jié)果的比值，如圖7所示.其中橫坐標(biāo)為FRP求解精度K，取值為10～200；縱坐標(biāo)為單個(gè)K值下不同U時(shí)多次實(shí)驗(yàn)得到的多個(gè)FRP和SSP-RP收益比率的均值.我們可看到，F(xiàn)RP可通過很低的時(shí)間復(fù)雜度可獲得近優(yōu)解，在所有場景中都能達(dá)到SSP-RP的97%以上，且因SSP-RP和FRP的時(shí)間復(fù)雜度分別為O(IJU)和O(IJK+IKlogK),當(dāng)λ=10 000且K=10時(shí)，F(xiàn)RP能以降低3個(gè)數(shù)量級(jí)的時(shí)間復(fù)雜度接近最優(yōu)解99%，具明顯的改進(jìn)效果.

Fig. 7　Average revenue ratio of FURP to SSP-RP with different cycle counts.圖7　FRP和SSP-RP的平均收益比率與循環(huán)數(shù)的關(guān)系

4結(jié)束語

本文研究了分布式云計(jì)算平臺(tái)中基于隨機(jī)需求的通用資源分配問題，并提出了可獲取近似解的快速求解方法.相比已有文獻(xiàn)中的最優(yōu)解算法，我們的方法可達(dá)到最優(yōu)解的99%，同時(shí)計(jì)算復(fù)雜度只有最優(yōu)解算法的1‰，是對(duì)已有算法的有效補(bǔ)充.

參考文獻(xiàn)

[1]YouTube. YouTube homepage[EBOL]. (2005-02-15) [2015-03-12]. http:www.youtube.com

[2]Facebook. Facebook homepage[EBOL]. (2004-02-04) [2015-03-12]. http:www.facebook.com

[3]You Kun, Tang Bin, Qian Zhuzhong, et al. QoS-aware placement of stream processing service[J]. Journal of Supercomputing, 2013, 64(3): 919-941

[4]Qiu Xuanjia, Li Hongxing, Wu Chuan, et al. Dynamic scaling of VoD services into hybrid clouds with cost minimization and QoS guarantee[C]Proc of IEEE Int Packet Video Workshop. Piscataway, NJ: IEEE, 2012: 137-142

[5]Huang Yongfeng, Dong Yongqiang, Zhang Sanfeng, et al. Leftover bandwidth-aware peer selection algorithm for inter-datacenter content distribution[J]. Journal on Communi-cations, 2013, 34(7): 24-33 (in Chinese)(黃永鋒, 董永強(qiáng), 張三峰, 等. 數(shù)據(jù)中心間空閑帶寬感知的內(nèi)容分發(fā)算法[J]. 通信學(xué)報(bào),2013, 34(7): 24-33)

[6]Broberg J, Buyya R, Tari Z. Metacdn: Harnessing storage clouds for high performance content delivery[J]. Journal of Network and Computer Applications, 2009, 32(5): 1012-1022

[7]Qiu Xuanjia, Li Hongxing, Wu Chuan, et al. Cost-minimizing dynamic migration of content distribution services into hybrid clouds[C]Proc of INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 2571-2575

[8]Chen Fangfei, Guo Katherine, Lin John, et al. Intra-cloud lightning: Building CDNs in the cloud[C]Proc of IEEE INFOCOM’12. Piscataway, NJ: IEEE, 2012: 433-441

[9]He Zhicong, Gu Guangzhao, Wang Xin, et al. Novel cooperative caching strategies for video streaming distribution based on reconfiguration routers[J]. Journal on Communications, 2012, 33(6): 82-90 (in Chinese)(何智聰, 谷光昭, 王新, 等. 基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略[J]. 通信學(xué)報(bào), 2012, 33(6): 82-90)

[10]Zhou Jingcai, Zhang Huyan, Zha Wenliang, et al. User-aware resource provision policy for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(5): 1108-1119 (in Chinese)(周景才, 張滬寅, 查文亮, 等. 云計(jì)算環(huán)境下基于用戶行為特征的資源分配策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5): 1108-1119)

[11]Tang Zhuo, Zhu Min, Yang Li, et al. Random Task-oriented user utility optimization model in the cloud environment[J]. Journal of Computer Research and Development, 2014, 51(5): 1120-1128 (in Chinese)(唐卓, 朱敏, 楊黎, 等. 云環(huán)境中面向隨機(jī)任務(wù)的用戶效用優(yōu)化模型[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5): 1120-1128)

[12]Tan B, Massoulie L. Optimal content placement for peer-to-peer video-on-demand systems[C]Proc of IEEE INFOCOM’12. Piscataway, NJ: IEEE, 2012: 694-702

[13]Rochman Y, Levy H, Brosh E. Resource placement and assignment in distributed network topologies[C]Proc of IEEE INFOCOM’13. Piscataway, NJ: IEEE, 2013: 1914-1922

中圖法分類號(hào)TP301.6

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(U1504607,61202099);河南省教育廳科學(xué)技術(shù)研究重點(diǎn)基金項(xiàng)目(2010A520008,13A413001,14A520018);河南省重點(diǎn)科技攻關(guān)基金項(xiàng)目(102102210025);新世紀(jì)優(yōu)秀人才支持計(jì)劃基金項(xiàng)目(NCET-12-0692);河南工業(yè)大學(xué)博士基金項(xiàng)目(2012BS011,2013BS003);河南工業(yè)大學(xué)自然科學(xué)基礎(chǔ)研究重點(diǎn)培育計(jì)劃基金項(xiàng)目(2014JCYJ04)

收稿日期：2014-12-08；修回日期：2015-04-08

This work was supported by the National Natural Science Foundation of China (U1504607,61202099), the Key Science and Technology Research Project of Education Department of Henan Province (2010A520008,13A413001,14A520018), Henan Provincial Key Scientific and Technological Plan (102102210025), the Program for New Century Excellent Talents in University of Ministry of Education of China (NCET-12-0692), the Doctor Foundation of Henan University of Technology (2012BS011,2013BS003), and the Plan of Nature Science Fundamental Research in Henan University of Technology (2014JCYJ04).