一种基于动态规划的虚拟机分配方法

摘 要： 基于组合拍卖的动态分配机制使得云拍卖商能够根据市场需求高效地配置云资源，为拍卖商带来更高的收益。现有方法是贪婪法分配虚拟机资源，优先为投标密度高的用户分配资源，然而这种局部最优选择并不总能带来整体最优解。提出一种基于动态规划的虚拟机分配方法DP?VMPA，它以最大社会福利作为目标函数，使用CA?DP分配算法求出获得资源的用户集，最后采用VCG机制为用户定价。应用实例表明，DP?VMPA机制能够更有效地分配虚拟机资源，同时为拍卖商带来更高的收益。

关键词： 虚拟机； 动态规划； 分配； 定价

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2016）21?0159?05

A virtual machine allocation method based on dynamic planning

WANG Yan1， SUN Maosheng2， ZHU Junwu2， 3

（1. Center of Informatization， Xuzhou University of Technology， Xuzhou 221018， China；

2. School of Information Engineering， Yangzhou University， Yangzhou 225009， China；

3. Department of Computer Science and Technology， University of Guelph， Guelph NIG2K8， Canada）

Abstract： The dynamic allocation mechanism based on combination auction makes the cloud auctioneer allocate the cloud resource efficiently according to the market requirement， and brings high benefit for the auctioneer. The existing method uses the greed method to allocate the virtual machine resource， and allocates the resource for the high tender?density users optimally. Ho?wever this local optimal selection can′t bring the global optimal solution. A DP?VMPA （dynamic planning based virtual machine provision allocation） method is proposed， which takes the maximal social welfare as target function， uses CA?DP allocation algorithm to find out the obtained users set of resource. The VCG mechanism is used to price for the users. An application example shows that the DP?VMPA method can allocate the virtue machine resources efficiently， and bring a high benefit for the auctioneer.

Keywords： virtue machine； dynamic planning； allocation； pricing

0 引 言

当下云拍卖商们大都使用基于固定价格机制的方法分配和卖出云资源，例如Windows Azure[1]和Amazon EC2[2]。显然这种分配和定价体制有不少缺点，首先它不能保证资源的有效分配，那些对资源估价高的用户并不总能如愿获得请求资源，其次云拍卖商的利润偏低[3?4]。基于拍卖的机制可以有效地解决如上问题，它权衡用户请求的资源量及对资源的估价，决定对用户的分配及定价。

拍卖机制分静态拍卖和动态拍卖，静态机制需要拍卖商提前供应虚拟机资源并且不能改变资源量，动态拍卖下，拍卖商可以使用虚拟化技术，根据用户需求量动态配置各类虚拟资源，并将它们按单位虚拟机实例卖出，保证资源的高效利用。现有的方法大都使用贪婪算法[3?5]决定用户的分配。它对用户的投标价值密度由高到低排序，在资源容量内依次选择价值密度高的投标，将资源分配给用户，这种启发式的策略并不总能获得最优解。

通常WDP问题是个NP完全问题，可以对虚拟机供应与分配问题VMPA进行客观描述，给出目标函数，然后使用基于组合拍卖的动态规划算法（CA?DP Allocation Algorithm）求出分配最优解。DP算法是先把问题分成多个子问题（一般地，每个子问题是互相关联和影响的），再依次研究逐个问题的决策。动态规划方法设计算法的主要思路使用最优性原理找出递推关系， 再找最优决策序列。定价方案上采用基于最优分配的VCG（Vickrey?Clarke?Groves）机制，即用分配给该用户的资源对其余用户的社会损失给其定价。

本文根据虚拟机分配问题的目标函数，提出DP?VMPA Mechanism （Dynamic Programming Mechanism that solves VMPA problem），采用CA?DP allocation algorithm解决分配问题，同时使用VCG定价机制决定用户的支付。这个机制能保证资源的有效利用，并为提供商带来更高的利润。

1 相关工作

Zaman等人首先详细介绍了基于固定价格的分配机制[3]，然后提出两种基于拍卖的静态虚拟机分配机制CA?GREEDY机制和CA?LP机制，并将它们与Fixed?Price机制比较，相比于固定价格机制，基于拍卖的机制能更有效地分配虚拟机资源，提高拍卖商利益。CA?LP机制在分配资源和增大收益方面表现突出，CA?GREEDY机制因其快速有效的分配性能被广泛认可。文献[4]中，拍卖商结合虚拟化技术对资源实现动态配置，使用CA?PROVISION机制分配虚拟机资源。本文尝试将此机制与静态分配下的CA?GREEDY机制比较，实验表明，动态分配下，拍卖商根据市场需求动态供应资源，可以保证资源的高效利用，增大拍卖商的利润。它还通过设置保留价格进一步提升拍卖商的收益。文献[6]提出一种有效投标策略，帮助云计算用户生成最佳投标（请求的虚拟机资源组合和对这组资源的估价）。这种投标策略能够帮助用户高效地完成云计算任务，提高执行效用。资源的有效利用也使得拍卖商收益增加。Nejad在文献[5]中提出动态虚拟机资源的启发式贪婪分配算法，它详细描述了用户对多类虚拟机资源CPU、内存和容量的请求数量，然后根据各类资源稀缺性参数重新定义价值密度，按贪婪算法进行资源分配。文献[3?5]均采用贪婪法分配资源，贪婪法一步步的构造局部最优解，使得最终分配解保持可行性且能产生较大效益。

Garfinkel提出了集分割算法解决组合拍卖下的分配问题[7]；Nisan将Winner集决定问题表示成一个标准的混合整数规划问题[8]，提出使用商用软件和一些简单算法求解该问题。Sandholm在文献[9]提出使用软件CPLEX可以高效地解决WDP问题，使资源充分利用。Fujisima推荐CASS软件来处理更大规模的WDP[10]。将组合拍卖下的分配借助各类软件的整数规划实现，这是完全可行的，不过这些软件无法用算法描述，另外它们只能给出最优分配集合，对用户的定价问题却无法解决。文献[11]在众包分配与定价问题中介绍了4种可行的机制：OPT，GREEDY，VCG和TruTeam，并通过实验比较各个机制，得出结论VCG机制和TruTeam机制均能高效利用资源，同时证明其满足个体理性和真实性。

2 动态虚拟机供应与分配问题

通过虚拟化技术的应用，云计算提供商可以将计算资源动态配置成任意类型的虚拟机组合。一个云拍卖商向用户提供[m]类虚拟机实例资源，[VM1，VM2，…，][VMm。]虚拟机类型[VMi]的计算能力表示为[wi，]其中[w1]=1，[w1

考虑有[n]个用户[u1，u2，…，un]向云提供商请求虚拟机。用户[uj]向拍卖商提交一组投标[Bj=（rj1，…，rmj，vj），]其中[rij]是请求的虚拟机[VMi]的数量，[vj]是单位时间内用户[j]得到虚拟机愿意最大支付的金额。拍卖商阶段性的组织拍卖分配虚拟机，一单位时间即这轮拍卖的拍卖商的分配与定价决策到下轮拍卖的决策之间的时间间隔。为了定义云提供商获得的利益，定义[P={p1，p2，…，pn}，]其中用[pj]表示用户[j]获得请求的资源时需要支付的金额，通常小于[vj]；将分配问题的解定义为[x=（x1，x2，…，xn）]，分配向量中的元素[xj∈{0，1}，][xj=1]表示用户[j]得到虚拟机组合，反之[xj=0]表示用户未得到；集合[W=uj1≤j≤n，xj=1]作为投标胜利用户集。[sj=][i=1mwirij]表示用户[uj]请求的单位计算资源的数量，其中单位资源也就是一个[VM1]类型的虚拟机实例。

定义1：动态虚拟机供应与分配问题可以形式化描述为：

[maxj=1nxjpj]

[s.t. j=1nxjsj≤Mxj∈0，10≤pj≤vj]

式中：约束条件（1） 表明成功投标的用户请求的虚拟机资源总量不得超过拍卖商所拥有的资源量；式（2）表示规定分配向量[xj]的取值范围；式（3）表示此不等式保证用户的支付金额不超过用户对其请求资源的最大估价，也就是确保用户的效用[Uj=vj-pj]不为负。组合拍卖的最优方案应该是最大化云拍卖商的利益，但很难找出一个客观函数描述它，通常寻找最大化社会总福利（成功获得虚拟机资源的用户投标总价值）作为解决组合拍卖问题的方案。这种分配方案决定了拍卖商对每类虚拟机的配置，计算[ki=j=1nxjrij，]即[VMi]类虚拟机需要供应的数量为[ki]。

定义2：真实的（Truthful， Incentive Compatible）假定任意用户[j]其在真实报价情形下获得的效用为[u1，]任意虚假报价下获得的效用为[u2，]若给定机制中[u1-u2≥0，]则称该机制是Truthful的。即用户只有通过向机制提交真实的估价，他才能获得最大效用。真实性使得用户在投标决策时不需考虑复杂的投标策略，更不需考虑其他用户的投标方案。

定义3：个体理性（Individual Rationality），即在一机制中，对每个用户[j]，用户的效用[Uj=vj-pj]大于等于0，则称用户[j]是个体理性的。

3 基于组合拍卖的动态虚拟机供应与分配机制

本文提出的DP?VMPA Mechanism决定了获得虚拟机的Winner用户集和这个集合中每个用户的定价。这种组合拍卖机制能有效分配虚拟机资源，为拍卖商带来更高的收益（Efficient）。

Algorithm 1：DP?VMPA Mechanism

Input：[M；m；wi：1，…，m；]

Output：[W；P；ki：1，…，m；]

1.{phase： Collect [Bids]}

a.Initialize [BNΦ]

b.For [j]=[1，2，…，n，]

Collect bid [Bj=（rj1，…，rjm，vj）] from user [uj]

c.[BNBN?{Bj}]

2.{phase 2： Winner Determination and Provision}

（[W，][BestValue]） = CA?DP（[BN，][M]） //Algorithm 3

For [i=1，…，m，]

[kij：uj∈Wrij]

3.{phase 3：[Payment]}

For all [j∈W]

（[W，][BestValue]） = CA?DP（[BN-{uj}，][M]） //Algorithm 3

[pjBestValue-（BestValue-vj）]

For all [j?W，]

[pj0]

Return （[W；P；ki：1，…，m]）

动态规划求解虚拟机供应与分配机制（DP?VMPA）如上，机制被云提供商阶段性的调用，运行该机制需要提供三个输入参数：虚拟机资源总量[M，]虚拟机的类型数量[m]和相应的虚拟机权重[wi，]输出三个参数：成功获得虚拟机资源的用户集合[W，]用户支付向量[P]以及提供商对每类虚拟机的供应数量[ki]。

动态规划机制也分为三个阶段。第一阶段，拍卖商收集用户的投标，所有用户的投标构成集合[BN。]第二阶段使用动态规划分配算法（算法3给出CA?DP分配算法）决定获得资源的Winner集合，求出该集合下产生的最大社会总价值[BestValue]，同时决定出拍卖商的虚拟机供应方案。第三阶段，使用VCG机制求出Winner集合每个用户应当支付的金额，即用户[j]不参与拍卖所能得到的最大价值总和减去用户[j]参与拍卖并获得资源时其他用户的价值量总和，未获得虚拟机的用户支付量为0。

Algorithm 2： CA?DP allocation algorithm

Input：[BN，M]

Output：[W，BestValue]

1.Initialize [BNΦ，nsize（BN），] [bestValues[n+1][M+1]]

2.For [j=0，1，…，n，]

[sji=1mwirij]

For [h=0，1，…，M，]

If [h=0j=0] then [bestValues[i][j]0]

Else

If [sj>h]then [bestValues[j][h]bestValues[j-1][h]]

Else[bestValues[j][h]][max{bestValues[j-1][h]，bestValues[j-1]]

[[h-sj]+vj}]

3.[hM]

4.For [j]=[n，…，1]

If [bestValues[j][h]>bestValues[j-1][h]]

then [WW?{uj}，][hh-sj]

5.[BestValuebestValues[n][M]]

Return （[W，][BestValue]）

基于组合拍卖的动态规划分配算法如上所述，该算法需要提供两个参数，即所有参与投标的用户集合[BN]和虚拟机资源总量[M。]运行算法可以得到两个值，即最优分配下的投标成功用户集合[W]和对应的最大估价之和BestValue。

组合拍卖问题的最优解结构：可以将组合拍卖分配问题的求解过程看作是进行一系列的决策过程，即决定哪些用户应该获得虚拟机资源，哪些用户不该获得请求资源。如果一个问题的最优解包含了用户[n]，即[xn=1，]那么其余[（x1，x2，…，xn-1）]一定构成子问题1，2，[…]，[n-1]在云提供商拥有虚拟机资源为[M-sj]时的最优解。如果这个最优解不包含物品[n]，即[xn=0，]那么其余[（x1，x2，…，xn-1）]一定构成子问题1，2，[…]，[n-1]在资源量为[M]时的最优解。

那么根据上述分析的最优解的结构性质，递归地定义问题最优解。[bestValues[j][h]]表示虚拟机资源量为[h]时，前[j]个用户导致的最优解的总价值，那么总有：

[bestValues[j][h]=bestValues[j-1][h]，sj>hmaxbestValues[j-1][h]， bestValues[j-1][h-sj]+vj，sj≤h]

当用户[j]请求的资源量大于[h]时，[bestValues[j][h]]由虚拟机资源量为[h]时，前[j-1]个用户最优解的总价值决定；当用户[j]请求的资源量不大于[h]时，通过比较不允许[j]获得资源的总价值[bestValues[j-1][h]]和允许[j]获得请求的资源产生的总价值[bestValues[j-1][h-sj]+vj]，总价值高的作为[bestValues[j][h]]的最优解价值。显然最终要求的是[bestValues[j][h]]。

求出最优解下的总价值后，可以通过回溯找出所有成功获得虚拟机资源的用户，即通过比较虚拟机资源量为[h]时，前[j-1]个用户最优解的总价值[bestValues[j-1][h]]和虚拟机资源量为[h]时，前[j]个用户最优解的总价值[bestValues[j][h]]，来得出用户[j]能否获得请求资源。回溯需要从[j=n]，[h=M]处开始，直至[j=1]，[h=0，]并将结果保存在集合[W]中。

命题1 DP?VMPA机制的时间复杂度为[O（nnM）]

证明：CA?DP分配算法中递归求最优解，使用两个for循环对[j=0，1，…，n]和[h=0，1，…，M]下每种状态求出最优解，时间复杂度为[O（nM），]回溯法求投标成功用户集合[W]只需遍历一个for循环，其时间复杂度为[O（n），]总共时间复杂度为[O（nM）]。使用VCG机制对Winner集中每个用户求支付金额，对每个用户需要调用CA?DP分配算法，最坏时间复杂度为[O（nnM）]。

命题2 DP?VMAP机制是Truthful的

证明：证明真实性（Truthful），首先证明其分配单调性（Monotone），即用户可以通过增大对请求的虚拟机组合的估价[vj]，或者减少请求的虚拟机资源总量[sj]来增加获得请求资源的几率，所以说机制是单调性的。

其次证明支付金额为临界价格（Critical Value），动态规划机制求出分配最优解的前提下，使用VCG机制对投标成功的用户定价，用户[j]不参与拍卖所能得到的最大价值总和减去用户[j]参与拍卖时其他用户的价值量总和，求出的支付金额[pj]是临界价值。

命题3 DP?VMAP机制满足个体理性

证明：对获得资源的每个用户[pj=BestValue-][（BestValue-vj），]因为动态规划基于最优分配，所以公式中[bestValue≤bestValue，]即证[Uj=vj-pj=bestValue-][bestValue≥0]。未获得虚拟机的用户[Uj=0，]所以综上机制满足个体理性。

4 应用案例及分析

假定[n=4，][M=8，]4个用户的请求虚拟机数量和报价：（3，3），（2，4），（4，1），（1，2），[bestValue[j][c]]取值如表1所示（[j=]0或[c=0，][bestValue[j][c]]=0）。

时间复杂度：基于组合拍卖的动态规划分配算法中，根据最优解结构性质，对[j∈[0，n]]和[c∈[0，M]]每种状态下使用递归式求出最优解，使用两个for循环，其时间复杂度为[O（nM）]。回溯法求投标成功用户集合[W]只需遍历一个for循环，其时间复杂度为[O（n），]总共时间复杂度为[O（nM）]。

空间复杂度：动态规划求最优解需要构造（n+1）×（[M+1]）的二维数组，用于存储[（j，c）]下的最大价值[bestValue[j][c]，]空间复杂度为[O（nM）]。

5 结 论

为了解决虚拟机动态分配问题，提出一种基于动态规划的虚拟机分配机制。这种机制以最大社会福利为目标函数，递归求解最优分配下的用户集，并使用VCG机制对用户资源定价。DP?VMPA机制能够使更多的用户完成应用，高效利用虚拟机资源，明显增大了拍卖商的收益。这个机制时间复杂度较高，不建议对大规模用户参与的虚拟机分配问题使用该机制，后续工作将围绕对CA?DP分配函数进行优化处理，并对VCG机制进行改进，使得定价机制更加简易高效。

参考文献

[1] Microsoft. Windows azure platform [EB/OL]. [2015?09?11]. http：///windowsazure/.

[2] Amazon. Amazon elastic compute cloud （Amazon EC2） [EB/OL]. [2016?01?17]. http：///ec2/.

[3] ZAMAN S， GROSU D. Combinatorial auction?based allocation of virtual machine instances in clouds [J]. Journal of parallel and distributed computing， 2013， 73（4）： 495?508.

[4] ZAMAN S， GROSU D. Combinatorial auction?based dynamic VM provisioning and allocation in clouds [C]// Proceedings of 2011 Third IEEE International Conference on Cloud Computing Technology and Science. [S.l.]： IEEE， 2011： 107?114.

[5] NEJAD M M， MASHAYEKHY L， GROSU D. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds [J]. IEEE transactions on parallel & distribu?ted systems， 2014， 26（2）： 594?603.

[6] ZAMAN S， GROSU D. Efficient bidding for virtual machine instances in clouds [C]// Proceedings of 2011 IEEE International Conference on Cloud Computing. [S.l.]： IEEE， 2011： 41?48.

[7] GARFINKEL R S， NEMHAUSER G L. The set partitioning problem： set covering with equality constraints [J]. Operations research， 1969， 17（5）： S40?S47.

[8] NISAN N. Bidding and allocation in combinatorial auctions [C]// Proceedings of 2000 2nd ACM Conference on Electronic Commerce. New York： ACM， 2001： 1?12.

[9] SANDHOLM T. Algorithm for optimal winner determination in combinatorial auctions [J]. Artificial intelligence， 2002， 135（1/2）： 1?54.

[10] FUJISIMA YUZO， LEYTON?BROWN K， SHOHAM Y. Ta?ming the computational complexity of combinatorial auctions [C]// Proceedings of 1999 International Joint Conference on Artificial Intelligence. [S.l.： s.n.]， 1999： 548?553.

[11] LIU Q， LUO T， TANG R， et al. An efficient and truthful pricing mechanism for team formation in crowdsourcing markets [C]// Proceedings of 2015 IEEE International Conference on Communications. Singapore： IEEE， 2015： 567?572.