面向成本優(yōu)化的包簇機(jī)制虛擬化資源分配

王 磊，陳世平,2，盧浩洋

(1.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093;2.上海理工大學(xué) 信息化辦公室，上海 200093)

面向成本優(yōu)化的包簇機(jī)制虛擬化資源分配

王 磊1，陳世平1,2，盧浩洋1

(1.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093;2.上海理工大學(xué) 信息化辦公室，上海 200093)

現(xiàn)階段，以虛擬機(jī)為中心的云數(shù)據(jù)中心在資源分配的成本控制方面仍需改進(jìn)。針對(duì)此問(wèn)題，文中以驗(yàn)證基于包簇分配機(jī)制在成本控制方面要優(yōu)于現(xiàn)有的基于虛擬機(jī)機(jī)制為目的。對(duì)分配問(wèn)題所涉及的成本因素進(jìn)行了優(yōu)化，同時(shí)考慮在某個(gè)簇上對(duì)一個(gè)單位的資源使用一個(gè)時(shí)間槽的成本及使用成本隨時(shí)間的變化,而從得到了基于包簇框架下的成本函數(shù)。采用仿真數(shù)據(jù)，通過(guò)整數(shù)規(guī)劃得到一組基于包簇分配的營(yíng)運(yùn)成本數(shù)據(jù),并且使其與傳統(tǒng)的基于虛擬機(jī)分配的成本進(jìn)行對(duì)比，從而驗(yàn)證了包簇分配機(jī)制下成本函數(shù)的可用性及有效性。

云計(jì)算；數(shù)據(jù)中心；資源分配；虛擬機(jī)；包-簇

虛擬數(shù)據(jù)中心化指通過(guò)虛擬技術(shù)[1]來(lái)對(duì)數(shù)據(jù)中心進(jìn)行管理。然而數(shù)據(jù)中心的資源彈性分配特征，使得企業(yè)和組織在部署應(yīng)用時(shí)能夠根據(jù)實(shí)際業(yè)務(wù)需求分配虛擬化資源，從而減少資源浪費(fèi)[2]。因此，在按需付費(fèi)的云計(jì)算環(huán)境中部署應(yīng)用時(shí)，如何在保證應(yīng)用提供商和應(yīng)用使用者之間的服務(wù)等級(jí)協(xié)議(Service Level Agreement，SLA)的基礎(chǔ)上優(yōu)化分配虛擬化資源，從而盡可能降低應(yīng)用的資源使用成本，是目前解決資源浪費(fèi)的關(guān)鍵途徑。

與已有研究不同，本文針對(duì)基于包-簇的資源分配。并通過(guò)這種新型的分配機(jī)制提出一種以最小化資源使用成本為目標(biāo)的總體成本函數(shù)，使用動(dòng)態(tài)規(guī)劃來(lái)得出包-簇分配機(jī)制的最優(yōu)解，并將其最優(yōu)解與基于虛擬機(jī)的資源分配的成本最優(yōu)解進(jìn)行比較，從而來(lái)解決在數(shù)據(jù)中心使用時(shí)的資源利用最大化和合理化。

1 相關(guān)研究

現(xiàn)在流行的數(shù)據(jù)中心資源管理方式是以虛擬機(jī)(VM)為中心，每個(gè)用戶必須指明所需的虛擬機(jī)數(shù)量及每個(gè)虛擬機(jī)的資源要求[3]。

(1)可擴(kuò)展性(Scalability)挑戰(zhàn)?，F(xiàn)有的研究工作將資源分配(虛擬機(jī)-服務(wù)器映射)視為約束優(yōu)化問(wèn)題來(lái)解(如Non-linear Mixed-integer Programming)[4-5]。其它工作通過(guò)一些假設(shè)將資源分配簡(jiǎn)化成多維裝箱問(wèn)題(Bin-Packing)[6-7],但那仍然是NP-hard。一般而言，資源分配優(yōu)化可被視為計(jì)算一個(gè)最優(yōu)的資源分配矩陣

(1)

(2)靈活性挑戰(zhàn)。在一個(gè)面向虛擬機(jī)(VM-Centric)的資源管理系統(tǒng)中，用戶需要明確指定每個(gè)虛擬機(jī)的資源要求[8-9]，有時(shí)還包括虛擬機(jī)間的流量矩陣，以對(duì)數(shù)據(jù)中心的網(wǎng)絡(luò)性能進(jìn)行優(yōu)化[10-11]。而現(xiàn)實(shí)中的用戶可能并不清楚每個(gè)虛擬機(jī)在將來(lái)的每個(gè)時(shí)刻有怎樣的資源要求。如果允許資源共享，則對(duì)每一個(gè)個(gè)體虛擬機(jī)就沒(méi)有固定的資源承諾，這種共享式的資源分配形式對(duì)于當(dāng)下實(shí)際使用的虛擬機(jī)資源分配模型而言是根本的背離，因而，對(duì)靈活性的追求將要求現(xiàn)階段進(jìn)行不同于現(xiàn)有技術(shù)的基礎(chǔ)性研究。

以虛擬機(jī)為中心(VM-Centric)來(lái)設(shè)計(jì)資源分配模型，使用扁平、細(xì)顆粒度的資源分配方式。這樣細(xì)顆粒度的管理模型導(dǎo)致所要解決的計(jì)算問(wèn)題規(guī)模巨大，對(duì)虛擬機(jī)固定的資源分配也不利于資源共享。

2 基于包-簇分配機(jī)制模型

為解決上述問(wèn)題，本文將使用一種全新的基于包簇分配機(jī)制[12]的模型。首先介紹包和簇的概念，以對(duì)用戶需求和云資源給出多級(jí)抽象的遞歸定義。

2.1 包的構(gòu)造

定義1“包”為虛擬機(jī)或其他包的集合(注：這是個(gè)遞歸定義，一個(gè)大包可以是許多小包的集合，而這些小包可能是虛擬機(jī)的集合，也可能是更小包的集合)。該遞歸定義允許用戶以一種層次結(jié)構(gòu)形式組織自己的資源要求。

如圖1所示，一個(gè)資源共享的虛擬機(jī)組合被模塊化為需求包，而多個(gè)包又進(jìn)一步被抽象成一個(gè)更高級(jí)別的包，進(jìn)而由虛擬機(jī)與包構(gòu)成一個(gè)層次化組織構(gòu)架。靈活性將由基于包的資源管理而獲得，因?yàn)榘鼉?nèi)允許資源共享。

圖1 包層次結(jié)構(gòu)

2.2 簇的構(gòu)造

定義2“簇”為數(shù)據(jù)中心拓?fù)渲形恢孟嘟姆?wù)器或更低級(jí)別的簇的集合。簇所擁有的資源是其組成部分的資源之和。

圖2用肥胖樹(shù)(Fat-tree)[13]來(lái)說(shuō)明簇的概念，圖2(a)是一個(gè)肥胖樹(shù)拓?fù)洌?dāng)用簇代表每個(gè)機(jī)架上的服務(wù)器后，其拓?fù)浣Y(jié)構(gòu)簡(jiǎn)化為圖2(b)。當(dāng)將低級(jí)別簇聚合成高級(jí)別簇后，其拓?fù)溆趾?jiǎn)化為圖2(c)。需要注意的是，每一個(gè)低級(jí)別簇實(shí)際上包含了大量的服務(wù)器，而每一個(gè)更高級(jí)別簇又包含了相當(dāng)數(shù)量的低級(jí)別簇。顯然，簇的概念比pod更具一般性，因?yàn)榇氐膶哟谓Y(jié)構(gòu)是可以依據(jù)包的遞歸層次結(jié)構(gòu)來(lái)隨意構(gòu)造的。更重要的是，在本文中簇的意義并不在于其定義本身，而在于包簇共同使用來(lái)降低數(shù)據(jù)中心資源管理的復(fù)雜度，這是過(guò)去研究所沒(méi)有的。

圖2 針對(duì)不同需求構(gòu)建不同的簇層次結(jié)構(gòu)

具體地說(shuō)，使用包和簇來(lái)將虛擬機(jī)-服務(wù)器映射問(wèn)題轉(zhuǎn)換成一系列小得多的包-簇映射問(wèn)題：首先，將最上層的大型包映射給最上層的大型簇，每個(gè)簇應(yīng)有足夠的資源來(lái)支持映射的包的總需求。然后，對(duì)于每一個(gè)簇及所支持的包，并且在進(jìn)一步將其下一級(jí)別的包映射到下一級(jí)別的簇，這個(gè)過(guò)程遞歸重復(fù)，直到虛擬機(jī)被映射到服務(wù)器。該方法將一個(gè)指數(shù)級(jí)復(fù)雜度的問(wèn)題分解為一些小問(wèn)題，而這些小問(wèn)題每個(gè)計(jì)算規(guī)模都不大，可以逐個(gè)利用動(dòng)態(tài)規(guī)劃方法[14]來(lái)解決。

3 基于包-簇分配成本函數(shù)

以簇層次結(jié)構(gòu)中任意一個(gè)簇ρ來(lái)描述資源分配問(wèn)題，該簇具有N個(gè)子簇(或服務(wù)器)，以p為子簇標(biāo)號(hào)，1≤p≤N。假設(shè)已分配給ρ的包由M個(gè)子包(或虛擬機(jī))組成，標(biāo)號(hào)為v，1≤v≤M。要解決的問(wèn)題是如何最優(yōu)地將這M個(gè)子包分配給ρ中的N個(gè)子簇，應(yīng)該強(qiáng)調(diào)的是同一個(gè)算法又可以遞歸調(diào)用來(lái)把子包的子包映射到子簇的子簇，直至最終的虛擬機(jī)到服務(wù)器的映射。假設(shè)存在J種資源，以1,2,…,J為序。每個(gè)子包均對(duì)應(yīng)一個(gè)描述所需資源總量的向量，其中每一項(xiàng)表示一個(gè)資源類(lèi)型。每一個(gè)子簇p，1≤p≤N，也對(duì)應(yīng)一個(gè)描述可資分配的資源總量的向量。

3.1 優(yōu)化分配問(wèn)題所涉及的變量

3.2 資源約束

每個(gè)簇p的資源使用量不能超過(guò)可用資源量。在時(shí)間t，對(duì)任何資源i而言，給定分配矩陣x，簇p上對(duì)資源i的總用量是∑v∈VRv,i[t]xv,p[t]。因此，要求

∑v∈VRv,i[t]xv,p[t]≤Ap,i[t]
1≤p≤N,1≤i≤J,1≤t≤T

(2)

1≤p≤N，1≤i≤J，1≤t≤T

3.3 營(yíng)運(yùn)成本

假設(shè)在某個(gè)子簇p上對(duì)一個(gè)單位的資源i使用一個(gè)時(shí)間槽的成本是ep,i[t]，包括設(shè)備折舊、管理開(kāi)支、能源開(kāi)支等。為了反映不同簇的異質(zhì)性，允許不同簇上對(duì)每個(gè)資源的使用成本不同。同時(shí)為了反映能源價(jià)格與時(shí)間的關(guān)聯(lián)，也允許使用成本隨時(shí)間而變化。在時(shí)間t時(shí)，把包v分配給簇p的成本為

(3)

因而，簇p在時(shí)間t的營(yíng)運(yùn)總成本為

∑v∈VCv,p[t]xv,p[t]

(4)

(5)

其中，yp[t]是一個(gè)0-1變量，當(dāng)且僅當(dāng)存在有包被分配給簇p時(shí)，其值為1。為此，可以增加一個(gè)約束條件

yp[t]≤∑vxv,p[t],Byp[t]≥∑vxv,p[t]

(6)

其中，B為一個(gè)給定的足夠大的常數(shù)。這樣，yp[t]=1當(dāng)且僅當(dāng)存在某個(gè)v，使xv,p[t]=1。設(shè)定y為向量yp[t])，1≤p≤N，1≤t≤T。

綜上所述，總體成本目標(biāo)函數(shù)U(x,y)定義如下

(7)

在包-簇框架下，簇資源分配問(wèn)題就是找到最優(yōu)的分配矩陣來(lái)把成本目標(biāo)函數(shù)U(x,y)最小化。而云資源分配問(wèn)題就是依據(jù)包簇的層次結(jié)構(gòu)來(lái)求解一系列的簇資源分配規(guī)劃問(wèn)題。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

驗(yàn)證基于包-簇分配機(jī)制下成本函數(shù)的可用性和合理化，所以只使用仿真數(shù)據(jù)即可。在云計(jì)算中物理主機(jī)的取值為10,15,20,25,30,35,40,45,50。并且各個(gè)物理主機(jī)中每一個(gè)資源的數(shù)量在一定的范圍之內(nèi)隨機(jī)變化，表1給出了可用資源的單位(unit)、價(jià)格(price)以及可用范圍(range)。

表1 物理機(jī)可用資源和單位價(jià)格

4.2 與基于虛擬機(jī)的成本函數(shù)對(duì)比

該組實(shí)驗(yàn)通過(guò)物理機(jī)的數(shù)量在10～50臺(tái)之間變化，根據(jù)包簇分配過(guò)程首先根據(jù)式(3)計(jì)算出Cv,p[t],其中t∈[1,T]，接著找到Cv,p[t]的第一個(gè)和最后一個(gè)局部最小點(diǎn)對(duì)應(yīng)的時(shí)間T1和TK。最后使t在[1～T1],[T1～TK],[TK～T]的情況下分別求解式(7)并由此求出最優(yōu)解。

根據(jù)式(9)及包簇分配算法，求解出基于包簇分配機(jī)制下云數(shù)據(jù)中心資源分配營(yíng)運(yùn)成本，如表2所示。

表2 包簇營(yíng)運(yùn)分配成本表

基于包-簇分配成本函數(shù)與基于虛擬機(jī)的成本函數(shù)所需求的最小資源使用成本做對(duì)比[15]，如圖3所示。

圖3 資源使用成本對(duì)比

根據(jù)圖3可知，當(dāng)物理機(jī)數(shù)量在10～30臺(tái)時(shí)，基于包簇分配與基于虛擬機(jī)分配的資源使用代價(jià)幾乎相同并且趨于降低。在35臺(tái)之后，基于包簇分配仍然在減少，并在45臺(tái)之后呈現(xiàn)出穩(wěn)定的趨勢(shì)，而基于虛擬機(jī)的資源使用代價(jià)出現(xiàn)了增長(zhǎng)的趨勢(shì)，這正是因?yàn)楝F(xiàn)在云數(shù)據(jù)中心中基于虛擬機(jī)的資源分配策略是扁平化設(shè)計(jì)的，當(dāng)物理機(jī)數(shù)量增多時(shí)資源使用代價(jià)將呈指數(shù)級(jí)增長(zhǎng)。根據(jù)實(shí)驗(yàn)結(jié)果，對(duì)于不同的物理機(jī)數(shù)量的逐漸增加，兩者的資源使用代價(jià)都逐漸減少，但隨著物理機(jī)數(shù)量越來(lái)越多，包-簇框架的減少幅度更大。當(dāng)物理機(jī)的數(shù)量越來(lái)越多時(shí)，基于包-簇框架資源分配機(jī)制在成本控制上要比基于虛擬機(jī)的分配機(jī)制更有效，并且成本更低。

5 結(jié)束語(yǔ)

對(duì)基于虛擬機(jī)機(jī)制的數(shù)據(jù)中心的管理問(wèn)題進(jìn)行了分析，并就此問(wèn)題提出了新的包簇框架的分配機(jī)制，將虛擬機(jī)機(jī)制中需要將所有虛擬機(jī)映射到服務(wù)器轉(zhuǎn)換為包簇機(jī)制中的將用戶所需的包資源映射到簇上。在復(fù)雜的云系統(tǒng)中計(jì)算、存儲(chǔ)、帶寬等資源限制條件下，滿足所有用戶要求，并對(duì)包簇分配機(jī)制進(jìn)行分析，從中提取出基于包簇分配機(jī)制的成本函數(shù)。實(shí)驗(yàn)驗(yàn)證了基于包簇分配機(jī)制在成本控制方面要優(yōu)于現(xiàn)有的虛擬機(jī)機(jī)制。

[1] Ian Foster,Zhao Yong,Ioan Raicu,et al.Cloud computing and grid computing 360-degree compared[C].Beijing:IEEE International Conference,2008.

[2] Durao F,Carvalho J F S,Fonseka A,et al.A systematic review on cloud computing [J].The Journal of Supercomputing,2014,68(3):1321-1346.

[3] Rodrigues H,Santos J R,Turner Y,et al. Gatekeeper: supporting bandwidth guarantees for multi-tenant datacenter networks[C].Berlin:Proceeding of ACM SIGCOMM,2011.

[4] 李菡薏.云計(jì)算環(huán)境下任務(wù)調(diào)度算法的研究[J].電子科技,2015,28(11):43-47.

[5] Xu J,Fortes J.Optimization in autonomic data center resource and performance management[R].Florida,USA:University of Florida,2012.

[6] Chen M,Zhang H,Su Y Y,et al.Effective VM sizing in virtualized data centers[C].Macro:Proceeding of ACM SIGCOMM,2011.

[7] Ajiro Y,Tanaka A.Improving packing algorithms for server consolidation[C]. MA,USA:Proceeding of Computer Measurement Group Conference,2007.

[8] Xu J,Fortes J A B.Multi-objective virtual machine placement in virtualized data center environments[C].Beijing:IEEE International Conference,2010.

[9] Mehta S,Neogi A.Recon: a tool to recommend dynamic server consolidation in multicluster data centers[C].Beijing:IEEE International Conference,2008.

[10] Guo C,Lu G,Wang H J,et al.Secondnet: a data center network virtualization architecture with bandwidth guarantees[C].Nanjing:Proceeding of ACM SIGCOMM,2010.

[11] Meng X,Pappas V,Zhang L.Improving the scalability of data center networks with trafficaware virtual machine placement[C].Beijing:IEEE International Conference,2010.

[12] 盧浩洋,陳世平.基于包簇映射的云計(jì)算資源分配框架[J].計(jì)算機(jī)應(yīng)用,2016,36(10):2704-2709.

[13] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[C].Paris:Proceeding of ACM SIGCOMM,2008.

[14] 宛楠,張義.動(dòng)態(tài)規(guī)劃算法分析[J].長(zhǎng)江大學(xué)學(xué)報(bào),2013,10(7):34-38.

[15] 張斌,朱孟笑,趙秀濤,等.面向成本優(yōu)化的SBS虛擬化資源分配[J].東北大學(xué)學(xué)報(bào),2015,36(10):929-932.

Cost Oriented Virtualized Resource Optimization Allocation for Package-Cluster

WANG Lei1，CHEN Shiping1，2，LU Haoyang1

(1.School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China；2.Network and Information Center Office,University of Shanghai for Science and Technology,Shanghai 200093,China)

At this stage,the virtual machine as the center of the cloud data center in the cost control of resource allocation still need to improve. In order to solve this problem,this paper is based on the cluster allocation mechanism in order to better control the cost of the existing virtual machine mechanism for the purpose of. The cost factors involved in the allocation problem are optimized,taking into account the time and cost of using a time slot for a unit of resources on a cluster. The cost function based on the clustering framework is obtained. The simulation data are used to obtain a set of operating cost data based on cluster assignment by integer programming. Compared with the traditional cost allocation based on virtual machine,the availability and effectiveness of the cost function under the cluster allocation mechanism are verified.

cloud computing; data center; resource allocation; VM; package-cluster

TP391

A

1007-7820(2017)11-085-05

2017- 01- 05

國(guó)家自然科學(xué)基金(61472256)；上海市教委科研創(chuàng)新重點(diǎn)項(xiàng)目(12zz137)；上海市一流學(xué)科建設(shè)項(xiàng)目(S1201YLXK)。

王磊(1991-)，男，碩士研究生。研究方向：云計(jì)算。陳世平(1964-)，男，博士，教授，博士生導(dǎo)師。研究方向：云計(jì)算,分布式計(jì)算。盧浩洋(1991-)，男，碩士研究生。研究方向：云計(jì)算。

10.16180/j.cnki.issn1007-7820.2017.11.023