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

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

(nsyncw@126.com)

?

一種通用云計算資源調度問題的快速近似算法

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

(河南工業(yè)大學信息科學與工程學院鄭州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

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

關鍵詞隨機需求；資源調度；資源放置；非線性規(guī)劃；云計算

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

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

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

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

1通用資源分配問題

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

(1)

(2)

(3)

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

(4)

因對于任意連續(xù)的非負隨機變量x與常量C有:

(5)

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

(6)

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

(7)

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

(8)

(9)

(10)

(11)

2快速資源分配算法

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

(12)

(13)

證畢.

(14)

因為Li(1≤i≤I)對給定的類型配置方案O是常量，則根據定理1，可由以下方法找到{P}O中達到最大i型期望收益的資源配置方案P′.

(15)

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

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

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

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

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

① FORi=1 toI

④ END IF

⑤ END FOR

⑥ FORk=0 toK

⑦v=wlockK;

⑧ FORi=1 toI

3實驗

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

(16)

(17)

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

Fig. 1　Expected revenue with different Zipf values under deficit scenario.圖1　資源不足時收益與Zipf的關系

Fig. 2　Expected revenue with different Zipf values under surplus scenario.圖2　資源盈余時收益與Zipf的關系

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

Fig. 3　Expected revenue with different number of resource types under deficit scenario.圖3　資源不足時收益與資源數量的關系

Fig. 4　Expected revenue with different number of resource types under surplus scenario.圖4　資源盈余時收益與資源數量的關系

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

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

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

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

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

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

4結束語

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

參考文獻

[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)(黃永鋒, 董永強, 張三峰, 等. 數據中心間空閑帶寬感知的內容分發(fā)算法[J]. 通信學報,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)(何智聰, 谷光昭, 王新, 等. 基于可重構路由器上緩存的流媒體協(xié)作分發(fā)策略[J]. 通信學報, 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)(周景才, 張滬寅, 查文亮, 等. 云計算環(huán)境下基于用戶行為特征的資源分配策略[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)境中面向隨機任務的用戶效用優(yōu)化模型[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

中圖法分類號TP301.6

基金項目：國家自然科學基金項目(U1504607,61202099);河南省教育廳科學技術研究重點基金項目(2010A520008,13A413001,14A520018);河南省重點科技攻關基金項目(102102210025);新世紀優(yōu)秀人才支持計劃基金項目(NCET-12-0692);河南工業(yè)大學博士基金項目(2012BS011,2013BS003);河南工業(yè)大學自然科學基礎研究重點培育計劃基金項目(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).