基于历史使用数据的虚拟机动态整合研究（文献阅读与问题理解）
基于历史的虚拟机动态整合技术
阅读文献：Optimal Online Deterministic Algorithms and Adaptive Heuristics for Energy and Performance Efficient Dynamic Consolidation of Virtual Machines in Cloud Data Centers
文献摘要：The rapid growth in demand for computational power driven by modern service applications combined with the shift to the Cloud computing model have led to the establishment of large-scale virtualized data centers. Such data centers consume enormous amounts of electrical energy resulting in high operating costs and carbon dioxide emissions. Dynamic consolidation of virtual machines (VMs) using live migration and switching idle nodes to the sleep mode allow Cloud providers to optimize resource usage and reduce energy consumption. However, the obligation of providing high quality of service to customers leads to the necessity in dealing with the energy-performance trade-off, as aggressive consolidation may lead to performance degradation. Due to the variability of workloads experienced by modern applications, the VM placement should be optimized continuously in an online manner. To understand the implications of the online nature
of the problem, we conduct competitive analysis and prove competitive ratios of optimal online deterministic algorithms for the single VM migration and dynamic VM consolidation problems. Furthermore, we propose novel adaptive heuristics for dynamic consolidation of VMs based on an analysis of historical data from the resource usage by VMs. The proposed algorithms significantly reduce energy consumption, while ensuring a high level of adherence to the Service Level Agreements (SLA). We validate the high efficiency of the proposed algorithms by extensive simulations using real-world workload traces from more than a thousand PlanetLab VMs.
总的来说，通过虚拟机的历史使用数据情况动态整合虚拟机来达到能耗与SLA违规的最佳平衡状态，基于此提出算法。
本文的主要贡献如下
1.针对单个VM迁移和动态VM整合问题的最佳在线确定性和离线算法的正式定义。
2.针对单个VM迁移问题的最佳离线算法所产生的成本的证明。
3.针对单个VM迁移和动态VM整合问题的最佳在线确定性算法的竞争比率的竞争分析和证明。
4.针对VM的能量和性能有效动态合并问题的新型自适应启发式算法，其优于最优在线确定性算法。
5.对所提算法进行广泛的基于仿真的评估和性能分析。
针对单个VM的迁移问题
C为花销，Cp为单位时间能耗花销，Cv为单位时间SLA违规花销，v为SLA违规时间节点，m为启动迁移时间节点，T为单个VM迁移所耗时间，n为停止时间节点（迁移结束或SLA违规发生），r为发生SLA违规以来的剩余时间r=n-v。
公式表示三种情况，成本函数C定义了三种情况，它们涵盖了v和m之间的所有可能关系。我们将（1）的情况分别表示为C1，C2和C3。C1描述了VM迁移发生在SLA违规（m <v）之前，但迁移的结束时间不晚于SLA违规开始的时间T（v-m≥T）。在这种情况下，成本仅为（v-m）Cp，即从VM迁移开始到潜在SLA违规开始时额外主机消耗的能量成本。没有SLA违规的成本，因为根据问题陈述，停止时间恰好是潜在SLA违规的开始，因此SLA违规的持续时间为0。迁移在发生SLA违规之前且迁移完成后还未发生SLA违规。
C2描述了在发生SLA违规（m≤v）之前发生迁移的情况，但迁移的开始时间晚于SLA违规开始之前的T（v-m <T）。 C2包含三个部分：（a）（v - m）Cp，从迁移开始到SLA违规开始时额外主机消耗的能量成本; （b）2（m - v + T）Cp，从SLA违规开始到n的主要主机和额外主机所消耗的能量成本; （c）（m - v + T）Cv，从SLA违规开始到VM迁移结束的SLA违规成本。迁移在发生SLA违规之前且迁移过程中发生SLA违规。
C3描述了迁移开始在SLA违规之后。在这种情况下，成本包括三个术语：（a）rCp，主要主机从SLA违规开始到n消耗的能源成本; （b）（r - m + v）Cp，费用从VM迁移开始到n的额外主机消耗的能量; （c）rCv，从SLA违规开始到n的SLA违规成本。迁移发生在SLA违规之后。
第一个的时间轴下面应该为v-m（写错了）。
最佳离线算法：
定理1
定义Cp=1，Cv=S，等价于Cp=1/S，Cv=1。
则当(v-m)/T=1时，VM迁移花销竞争率为T/S。
证明
定义v-m=aT,则m=v-aT,a=(v-m)/T。
因此：
公式（2）（3）直接将a=(v-m)/T带入(v-m)中得到。公式（4）对 （1）的第二种情况做了下变形，公式 （5）将T=r-m+v带入消去r，再进行化简得到。
由于 从公式 （5）得出C3(v,a)=C2(v,a)，也就是说只与v和a有关时，公式（1）可化简为公式（6）的样子。然后令Cp=1/S,Cv=1可得公式（7）。
很明显（7）在a = 1时达到其最小T / s，即当（v-m）/ T = 1时。该解决方案对应于总是在m = v-T时始终启动VM迁移的算法。这种算法必须完全了解SLA违规在实际发生之前耗费的时间，即v必须准确知道。该算法是单个VM迁移问题的最优离线算法。
最佳在线确定性算法
如果存在一个常量a对所有的有限序列输入I有：
公式（8）中ALG（I）为由于输入I导致的ALG花销，OPT(I)是在输入为I时的最佳离线算法的花销。
c必须独立于输入I，可以为一个函数。
定理2
单个虚拟机在线迁移算法的竞争率得出的结论是2+s，当m=v或者a=0时实现。
证明：
动态VM整合问题
定义每个主机的最大CPU能力为Ah。
每个虚拟机的最大CPU能力为Av。
当主机要求最大容量时可放置的VM为Ah/Av。
全部的VM数量为nm。
虚拟机的迁移时间为tm。
当请求超过了CPU能力时（Ah），发生SLA违规。
非空闲主机的能耗花销为：
t0为初始时间，ati和vtj为0或1。ati表示是否有主机i在时间t内是活动的，vtj表示是否有主机j在时间t内是SLA违规的。
总而言之要根据时间找到最小的C，也就是最小的能耗花销。
最佳在线确定性算法
Cp=1/s， Cv=1。
动态VM整合的自适应启发式
VM整合技术可以分为4个步骤：
1）确定主机何时被视为过载需要从该主机迁移一个或多个VM
2）确定主机何时被视为负载不足导致决定从该主机迁移所有VM并将主机切换到睡眠模式
3）选择应从过载主机迁移的VM
4）为过载和欠载找到一个放置VM的主机
一般的VM最优化放置方式通过算法1来表示：
首先，算法查看主机列表，并通过使用过载检测算法检查主机是否过载。 如果主机过载，则算法通过VM选择策略来选择需要从主机迁移的VM。构建要从过载主机迁移的VM列表后，将调用VM放置算法以查找要迁移的VM的新主机。该算法的第二阶段是查找负载不足的主机以及这些主机的VM的位置。该算法返回组合（欠载和过载主机中的VM组合）迁移map，其中包含从过载和欠载主机迁移的VM的新的位置信息。算法的复杂度为2N，其中N是主机的数量。
找到过载主机
以前是通过对主机的使用率进行上下域的划分，当主机使用率低于下阈值，则将该主机的全部VM迁移 ，若主机使用率高于上阈值，则迁移部分VM以确保SLA违规。