数据中心虚拟机放置方法的研究

摘要

随着计算机网络的不断发展，云计算成为了最流行的前沿技术之一。云计算以其灵活、便捷和按需提供资源的特性，吸引了很多工业界和学术界人们的关注。数据中心做为云计算的基础设施，也让很多IT提供商开始关注和建立他们自己的数据中心（例如:谷歌、微软、亚马逊、甲骨文等）。
　　研究表明，合理的虚拟机放置方法能有效提高数据中心资源的利用率、减少数据中心整体任务的完成时间以及提高数据中心整体执行任务的吞吐量。本文将虚拟机放置方法分为动态放置和静态放置。动态放置，即虚拟机迁移，是虚拟机在执行任务过程中随着数据中心系统的需要，虚拟机在不同物理机之间改变位置;静态放置，即初始化放置，是虚拟机在执行任务之前根据数据中心系统的需要，将虚拟机安置到某个物理机或某个数据中心中，在执行任务结束前不会改变其位置。
　　本文在全面分析现有数据中心虚拟机放置方法和相关研究工作的基础上，重点对数据中心虚拟机优化放置方法展开了深入的研究，并取得了一些创新和成果。本文的主要研究内容如下:
　　1.通过虚拟机迁移提高数据中心物理机资源利用率，同时达到最小化虚拟机的迁移代价。随着数据中心不断发展的同时也带来了很多问题，其中如何提高数据中心资源利用率和如何减少数据中心中虚拟机的迁移代价是两个最主要的问题。现有的研究成果中要么只考虑物理机资源利用率最大化，要么只考虑虚拟机迁移代价最小化，这种单一优化目标的方法对于物理机资源的高使用率和带宽资源高使用率的数据中心来说是远远不够的。然而，很少有研究成果能同时对这两个目标进行优化。因此，本文针对这种物理机资源高使用率和带宽资源高使用率的数据中心提出了一种优化模型，该模型在多资源环境下（例如:内存、带宽、CPU和磁盘空间等）同时考虑物理机资源利用率最大化和虚拟机迁移代价最小化。由于该优化模型是NP-hard问题，因此提出了基于装箱算法的近似算法MinCost，该算法能获得近似的优化解。实验结果表明，提出的模型和算法可以有效提高数据中心物理机的资源利用率，同时达到最小化虚拟机迁移代价。
　　2.通过优化虚拟机静态放置来减少数据中心整体任务完成时间。数据中心分为数据密集型和计算密集型两种。在计算密集型的数据中心结构中，访问响应时间对整个任务的完成时间有着很重要的影响;而在数据密集型的数据中心结构中，数据的传输时间是影响整个任务完成时间的重要因素。研究表明，合理的虚拟机静态放置方法能有效解决上述问题。好的虚拟机静态优化放置方法可以在计算密集型的数据中心中得到较少的访问响应时间，以及在数据密集型的数据中心中得到较少的数据传输时间。本文针对数据中心的两种类型，分别提出两种虚拟机静态优化放置模型，以便在数据中心中获得较小的整体任务完成时间。从模型上分析，计算密集型的虚拟机静态优化放置模型是一个线性规划问题，本文用分支界定算法来解该模型，算法的时间复杂度是O(2NM)，同时本文也给出了贪心算法来解计算密集型的优化模型，该算法将时间复杂度降低至O(NM)。数据密集型的虚拟机静态优化放置模型是一个NP-Complete问题，在本文中给出了相应的证明。同时，提出了启发式算法来解数据密集型的优化模型。实验结果表明，提出的方法能合理优化虚拟机静态放置的位置，有效地减少数据中心整体任务完成时间。
　　3.基于虚拟机动态放置与静态放置相结合的方法来提高数据中心整体执行任务的吞吐量。先前大部分工作要么只考虑虚拟机动态放置方面问题，要么只考虑虚拟机静态放置方面的问题。很少有工作能研究虚拟机动态放置和虚拟机静态放置相结合的方法来解决问题。研究表明，只考虑动态放置或是只考虑静态放置已经不能满足现有数据中心对大量虚拟机任务处理的需求。然而，一个好的虚拟机放置策略是尽可能多的静态放置虚拟机到数据中心中去进行处理;同时，随着数据中心中物理机资源使用情况的变化，虚拟机不断的在不同物理机之间进行迁移，通过这种静态放置和动态放置相结合的方法来提高数据中心整体执行任务的吞吐量。本文提出的优化模型通过时间片技术将虚拟机静态放置和动态放置相结合，同时在动态放置的过程中使迁移代价达到最小。通过实验结果可知，提出的方法能有效地提高数据中心整体执行任务的吞吐量，并使迁移代价最小化。

目录

声明

摘要

1 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．2．1 虚拟机动态放置

1．2．2 虚拟机静态放置

1．2．3 虚拟机动态放置方法和静态放置方法相结合

1．3 本文主要研究思路与内容

2 最大化资源利用率且最小化迁移代价的虚拟机动态放置策略

2．1 引言

2．2 现有方案存在的问题和改进思路

2．2．1 现有方案存在的问题

2．2．2 本章的改进思路

2．3 模型描述

2．3．1 资源利用率模型

2．3．2 迁移代价模型

2．3．3 优化模型

2．4 算法描述

2．4．1 近似算法的说明

2．4．2 MinCost算法

2．5 实验结果

2．5．1 单资源环境下实验结果

2．5．2 多资源环境下实验结果

2．6 本章小结

3 最小化任务完成时间的虚拟机静态放置策略

3．1 引言

3．2 现有方案存在的问题和改进思路

3．2．1 现有方案存在的问题

3．2．2 本章的改进思路

3．3 预备知识

3．3．1 分支界定算法

3．3．2 布尔可满足性问题

3．4 模型描述

3．4．1 计算密集型数据中心优化模型

3．4．2 数据密集型数据中心优化模型

3．5 算法描述

3．5．1 计算密集型模型对应算法

3．5．2 数据密集型模型对应算法

3．6 实验结果

3．6．1 计算密集型数据中心环境下实验

3．6．2 数据密集型数据中心环境下实验

3．7 本章小节

4 高吞吐量的虚拟机动态和静态相结合的放置策略

4．1 引言

4．2 现有方案存在的问题和改进思路

4．2．1 现有方案存在的问题

4．2．2 本章的改进思路

4．3 模型描述

4．3．1 虚拟机静态放置模型

4．3．2 虚拟机动态放置代价模型

4．3．3 优化模型

4．3．4 NP-hard证明

4．4 算法描述

4．5 实验结果

4．6 本章小结

5 结论与展望

5．1 结论

5．2 创新点

5．3 展望

参考文献

攻读博士学位期间科研项目及科研成果

致谢

作者简介