大型云计算系统中虚拟机的放置优化算法
高燕飞 陈俊杰 强彦
摘 要： 为了减少骨干网络内的数据流量，研究确定和优化虚拟机在数据中心的放置问题。虚拟机放置问题是一个HL问题，但是它在大型的云计算系统中表现不能令人满意。为了解决这个问题，重新建模，提出MF模型，利用可变聚合方法和添加有效不等式加强这个模型。通过大量的实验表明，在运行时间和计算资源方面该模型是可行有效的。
关键词： 虚拟机； 云计算； 放置问题； MF模型
中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）10?0013?03
Abstract： The virtual machine placement in data center is researched and optimized to reduce the data flow in the backbone networks. The virtual machine placement can be considered as a HL （hub location） problem. It is not satisfactory in the large cloud computing system. In order to solve this problem， a new MF model is proposed in this paper， which is based on the variable aggregation method and the effective inequality. The results of a large number of experiments show that the model is feasible and effective in running time and computing resources.
Keywords： virtual machine； cloud computing； placement problem； MF model
在大型云计算系统中， 虚拟机的放置问题主要是采用正确的方法来设计和优化在地理分布数据中心中虚拟机的放置。本文在大规模的云计算系统中解决虚拟机放置问题，目的是尽量减少数据中心节点之间的通信流量[1?3]。
1 相关研究
最近几年，许多学者都从不同的角度对这个问题进行了研究。资源配置、服务器整合和能源消耗等很多方面在文献[4?6]已经详细研究。然而，这些研究在很大程度上忽略了网络性能及其对虚拟机放置的影响，他们尝试提高网络连接的程度和使用动态路由协议来平衡传输工作量[7?9]。最新的一些研究发现，通过优化数据中心的位置来减少地理分布数据中心的功耗或服务延迟[10]。
2 模型的建立
2.1 HL模型
在大型的云计算系统中的虚拟机放置问题，可以看作是一个变种的枢纽位置问题（Hub Location Problem，HL问题），一个由虚拟机和数据中心节点组成的图。
事实上，HL模型是对称的，它有一个弱下界可以影响最优解的质量和程序的运行时间。重新使用聚合的方法（Multi?commodity Flow Problem）可以解决最优解的质量和程序运行时间的问题。
2.2 MF模型
在MF模型中，上述可以用一个图[G=N，E]来表示。其中：N表示所有节点的集合；E表示图的边的集合。
引入决策变量：[fihk]表示从虚拟机[i∈V]出来的循环在数据中心的流量数值；[φijh]表示从虚拟机[i∈V]出来的循环在虚拟机[j∈V]和数据中心[h∈D]之间的流量数值；[αkh]表示两个节点k和h之间流量交换的数值。线性模型如下：
式（7）是最小化不同数据中心的流量；式（8）是虚拟机的流量等于其他虚拟机之间交换的流量；式（9）、式（10）是保证流量都是由源节点产生的；式（11）是保证每个虚拟机只在一个数据中心运行；式（12）是虚拟机分配到矩阵[ahi]的数据中心；式（13）是虛拟机i的流量等于i和j之间交换的流量；式（14）是i的流量等于i与其他虚拟机交换的流量；式（15）是虚拟机所占资源不超过数据中心拥有资源的数量。
2.3 有效不等式
有效不等式的目的是使目标函数[fikh]的决策变量的值与增加的有效的约束条件相结合，能够给应用于二值变量[σik]的分支界定算法提供更好的边界。
命题1：对于任意的虚拟机i和数据中心k，式（16）对MF是有效的。
3 实验部分
电脑配置CPU为Intel Xeon 3， 3 GHz，RAM为8 GB，使用CPLEX来解决、评估和对比不同的模型。
测试是在同一组实例下进行的，输入数据为虚拟机60台和数据中心6个。运行结果如图1所示。
如表1所示， MF是添加了有效不等式，[MFw]没有添加，S是CPLEX给的最优解的值，G是与下边界的差值（越小越好），T是运行时间。
4 结 论
通过实验表明，本文提出的MF重新建模，利用可变聚合方法和添加有效不等式来加强这个新的模型是可行有效的。
参考文献
[1] VALANCIUS V， LAOUTARIS N， MASSOULI? L， et al. Greening the internet with nano data centers [C]// Proceedings of the 5 th International Conference on Emerging Networking Experiments and Technologies. [S.l.： s.n.]， 2009： 37?48.
[2] CHURCH K， GREENBERG A， HAMILTON J. On delivering embarrassingly distributed cloud services [EB/OL]. [2008?09?22]. highscalability.com.
[3] DONG X， GREEN E L T. IP over WDM networks with data centers [J]. Lightwave technology journal， 2011， 29（12）： 1861?1880.
[4] SPEITKAMP B， BICHLER M A. Mathematical programming approach for server consolidation problems in virtualized data centers [J]. IEEE transactions on services computing， 2010， 3（4）： 266?278.
[5] ZHANG Bolei， QIAN Zhuhong， HUANG Wei， et al. Minimizing communication traffic in data centers with power?aware VM placement [C]// Proceedings of 2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous ComputingIEEE Computer Society. [S.l.]： IEEE， 2012： 280?285.
[6] COHEN R， LEWIN?EYTAN L， NAOR J， et al. Almost optimal virtual machine placement for traffic intense data centers [C]// Proceedings of 2013 INFOCOM. [S.l.]： IEEE， 2013： 355?359.
[7] SHYU M， WU G M， CHANG Y D， et al. Generic universal switch blocks [J]. IEEE transactions on computers， 2000， 49（4）： 348?359.
[8] GUO C， LU G， LI D， et al. BCube： A high performance，server?centric network architecture for modular data centers [J]. Sigcomm， 2009， 39（4）： 63?74.
[9] AL?FARES M， LOUKISSAS A， VAHDAT A. A scalable， commodity data center network architecture [C]// Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication. [S.l.]： ACM， 2008： 63?74.
[10] GREENBERG A， HAMILTON J R， JAIN N， et al. Vl2： A scalable and flexible data center network [C]// Proceedings of the ACM SIGCOMM 2009 conference on Data Communication. Barcelona， Spain： ACM， 2009： 51?62.
摘 要： 为了减少骨干网络内的数据流量，研究确定和优化虚拟机在数据中心的放置问题。虚拟机放置问题是一个HL问题，但是它在大型的云计算系统中表现不能令人满意。为了解决这个问题，重新建模，提出MF模型，利用可变聚合方法和添加有效不等式加强这个模型。通过大量的实验表明，在运行时间和计算资源方面该模型是可行有效的。
关键词： 虚拟机； 云计算； 放置问题； MF模型
中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）10?0013?03
Abstract： The virtual machine placement in data center is researched and optimized to reduce the data flow in the backbone networks. The virtual machine placement can be considered as a HL （hub location） problem. It is not satisfactory in the large cloud computing system. In order to solve this problem， a new MF model is proposed in this paper， which is based on the variable aggregation method and the effective inequality. The results of a large number of experiments show that the model is feasible and effective in running time and computing resources.
Keywords： virtual machine； cloud computing； placement problem； MF model
在大型云计算系统中， 虚拟机的放置问题主要是采用正确的方法来设计和优化在地理分布数据中心中虚拟机的放置。本文在大规模的云计算系统中解决虚拟机放置问题，目的是尽量减少数据中心节点之间的通信流量[1?3]。
1 相关研究
最近几年，许多学者都从不同的角度对这个问题进行了研究。资源配置、服务器整合和能源消耗等很多方面在文献[4?6]已经详细研究。然而，这些研究在很大程度上忽略了网络性能及其对虚拟机放置的影响，他们尝试提高网络连接的程度和使用动态路由协议来平衡传输工作量[7?9]。最新的一些研究发现，通过优化数据中心的位置来减少地理分布数据中心的功耗或服务延迟[10]。
2 模型的建立
2.1 HL模型
在大型的云计算系统中的虚拟机放置问题，可以看作是一个变种的枢纽位置问题（Hub Location Problem，HL问题），一个由虚拟机和数据中心节点组成的图。
事实上，HL模型是对称的，它有一个弱下界可以影响最优解的质量和程序的运行时间。重新使用聚合的方法（Multi?commodity Flow Problem）可以解决最优解的质量和程序运行时间的问题。
2.2 MF模型
在MF模型中，上述可以用一个图[G=N，E]来表示。其中：N表示所有节点的集合；E表示图的边的集合。
引入决策变量：[fihk]表示从虚拟机[i∈V]出来的循环在数据中心的流量数值；[φijh]表示从虚拟机[i∈V]出来的循环在虚拟机[j∈V]和数据中心[h∈D]之间的流量数值；[αkh]表示两个节点k和h之间流量交换的数值。线性模型如下：
式（7）是最小化不同数据中心的流量；式（8）是虚拟机的流量等于其他虚拟机之间交换的流量；式（9）、式（10）是保证流量都是由源节点产生的；式（11）是保证每个虚拟机只在一个数据中心运行；式（12）是虚拟机分配到矩阵[ahi]的数据中心；式（13）是虛拟机i的流量等于i和j之间交换的流量；式（14）是i的流量等于i与其他虚拟机交换的流量；式（15）是虚拟机所占资源不超过数据中心拥有资源的数量。
2.3 有效不等式
有效不等式的目的是使目标函数[fikh]的决策变量的值与增加的有效的约束条件相结合，能够给应用于二值变量[σik]的分支界定算法提供更好的边界。
命题1：对于任意的虚拟机i和数据中心k，式（16）对MF是有效的。
3 实验部分
电脑配置CPU为Intel Xeon 3， 3 GHz，RAM为8 GB，使用CPLEX来解决、评估和对比不同的模型。
测试是在同一组实例下进行的，输入数据为虚拟机60台和数据中心6个。运行结果如图1所示。
如表1所示， MF是添加了有效不等式，[MFw]没有添加，S是CPLEX给的最优解的值，G是与下边界的差值（越小越好），T是运行时间。
4 结 论
通过实验表明，本文提出的MF重新建模，利用可变聚合方法和添加有效不等式来加强这个新的模型是可行有效的。
参考文献
[1] VALANCIUS V， LAOUTARIS N， MASSOULI? L， et al. Greening the internet with nano data centers [C]// Proceedings of the 5 th International Conference on Emerging Networking Experiments and Technologies. [S.l.： s.n.]， 2009： 37?48.
[2] CHURCH K， GREENBERG A， HAMILTON J. On delivering embarrassingly distributed cloud services [EB/OL]. [2008?09?22]. highscalability.com.
[3] DONG X， GREEN E L T. IP over WDM networks with data centers [J]. Lightwave technology journal， 2011， 29（12）： 1861?1880.
[4] SPEITKAMP B， BICHLER M A. Mathematical programming approach for server consolidation problems in virtualized data centers [J]. IEEE transactions on services computing， 2010， 3（4）： 266?278.
[5] ZHANG Bolei， QIAN Zhuhong， HUANG Wei， et al. Minimizing communication traffic in data centers with power?aware VM placement [C]// Proceedings of 2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous ComputingIEEE Computer Society. [S.l.]： IEEE， 2012： 280?285.
[6] COHEN R， LEWIN?EYTAN L， NAOR J， et al. Almost optimal virtual machine placement for traffic intense data centers [C]// Proceedings of 2013 INFOCOM. [S.l.]： IEEE， 2013： 355?359.
[7] SHYU M， WU G M， CHANG Y D， et al. Generic universal switch blocks [J]. IEEE transactions on computers， 2000， 49（4）： 348?359.
[8] GUO C， LU G， LI D， et al. BCube： A high performance，server?centric network architecture for modular data centers [J]. Sigcomm， 2009， 39（4）： 63?74.
[9] AL?FARES M， LOUKISSAS A， VAHDAT A. A scalable， commodity data center network architecture [C]// Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication. [S.l.]： ACM， 2008： 63?74.
[10] GREENBERG A， HAMILTON J R， JAIN N， et al. Vl2： A scalable and flexible data center network [C]// Proceedings of the ACM SIGCOMM 2009 conference on Data Communication. Barcelona， Spain： ACM， 2009： 51?62.
