Load balancing is vital for the efficient and long-term operation of cloud data centers. With virtualization, post (reactive) migration of virtual machines (VMs) after allocation is the traditional way for load balancing and consolidation. However, reactive migration is not easy to obtain predefined load balance objectives and may interrupt services and bring instability. Therefore, we provide a new approach, called Prepartition, for load balancing. It partitions a VM request into a few sub-requests sequentially with start time, end time and capacity demands, and treats each sub-request as a regular VM request. In this way, it can proactively set a bound for each VM request on each physical machine and makes the scheduler get ready before VM migration to obtain the predefined load balancing goal, which supports the resource allocation in a fine-grained manner. Simulations with real-world trace and synthetic data show that our proposed approach with offline version (PrepartitionOff) scheduling has 10%-20% better performance than the existing load balancing algorithms under several metrics, including average utilization, imbalance degree, makespan and Capacity_makespan. We also extend Prepartition to online load balancing. Evaluation results show that our proposed approach also outperforms existing online algorithms.

中文摘要：

1、研究背景（context）：云计算数据中心已发展成为目前信息技术的基石，并广泛支撑通用的网络应用以及许多关键性的应用，如银行系统和健康系统等。然后云数据中心的管理却面临着权衡性能和管理开销的挑战。由于负载均衡对云数据中心的重要性，近年来许多学者都投入了精力进行相关研究。尽管如此，云数据中心的负载均衡仍然是一个具有挑战性的问题，并需要给予关注。其挑战主要来自于虚拟机迁移开销，服务的可靠性，算法复杂性以及资源利用效率等方面。云数据中心本身的复杂性也促进了负载均衡的必要性。
2、目的（Objective）：现有的负载均衡算法大都是被动型的，如在虚拟机完成部署后，出现了负载不均衡的情况，才通过虚拟机迁移进行负载均衡操作。然后此类方法很难达到预先设定的负载均衡目标，并会中断服务且影响系统的稳定性。因此，本文的目的是设计在虚拟机完成分配前，提前进行负载均衡的决策，从而降低虚拟机迁移频率，并达到更好的负载均衡效果。
3、方法（Method）：我们设计了基于虚拟机预约方法的模型，对虚拟机的生命周期等特性进行了建模；我们分别设计了针对在线和离线虚拟机调度任务的预分割算法，该算法能够在虚拟机部署前对任务进行分割，并提供细粒度的管控机制；我们分别从理论上分析了在线和离线算法的复杂度；我们在模拟系统中对平均利用率等多个指标进行度量，验证了算法的性能。
4、结果（Result & Findings）：我们分别在真实和合成数据集上进行了算法性能测试，实验结果表明我们的方法相对业界主流算法，在平均利用率、负载不均衡都等指标上，能够有效提升10%-20%的系统性能。
5、结论（Conclusions）：通过理论分析和实验验证，证明了我们的方法在解决云数据中心负载均衡问题上的有效性。下一步研究中，我们拟考虑多租户和资源竞争的场景，以进一步优化算法适用范围。

Key words: cloud computing; physical machines; virtual machines; reservation; load balancing; Prepartition;