雲端計算中虛擬機器轉移之排程演算法

Virtual Machine Migration Scheduling for Cloud Computing

何雨帆(Yu-Fan Ho)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.00169

摘要

在雲端運算的環境中，伺服器合併是達成能源最佳化的重要方法之一。 虛擬機器在系統中會動態的進入、離開，因此必須把虛擬機器重新配置 到伺服器中來維持伺服器合併。然而，虛擬機器的搬遷會造成執行時額 外的負擔，並造成額外的能源損耗，所以需要對搬遷做仔細的規畫。我 們用修改過的裝箱問題來建立虛擬機器搬遷的問題模型，並提出一個演 算法，這個演算法保證了伺服器的合併程度，且搬遷所造成的額外能源 損耗是有限的。對於演算法所造成的能源損耗，我們做了理論上的分析 ，並給出一個上限。最後，我們做了模擬的實驗並和其他搬遷方法做比 較。實驗結果顯示出，在伺服器合併和搬遷成本之間有個值得關注的權 衡關係。和其他的方法比較後，我們的演算法能夠節省接近一半的搬遷 成本，而只需要犧牲不到百分之一的伺服器合併程度。

關鍵字

能源最佳化 ； 伺服器合併 ； 虛擬機器搬遷

並列摘要

Consolidation of virtual machines is essential to achieve energy optimization in cloud computing environments. As virtual machines dynamically enter and leave a cloud system, it becomes necessary to relocate virtual machines among servers. However, relocation of virtual machines introduces run-time overheads and consumes extra energy, thus an careful planning for relocation is necessary. We model the relocation problem as a modified bin packing problem and propose a new server consolidation algorithm that guarantees server consolidation with bounded relocation costs. We also conduct a detailed analysis on the complexity of the server consolidation problem, and give a upper bound on the cost of relocation. Finally, we conduct simulations and compare our server consolidation algorithm with other relocation methods, like First Fit and Best Fit method. The experiment results suggest an interesting trade-off between server consolidation quality and relocation cost. Our algorithm is able to trade about 1% in server consolidation quality for a reduction about 50% in relocation cost, when compared with other well known bin packing algorithms.

並列關鍵字

Energy Optimization ； Server Consolidation ； VM Relocation

參考文獻

[2] Gong Chen, Wenbo He, Jie Liu, Suman Nath, Leonidas Rigas, Lin Xiao, and Feng

internet services. In Proceedings of the 5th USENIX Symposium on Networked Sys-

[3] Vijay V. Vazirani. Approximation Algorithms, chapter Bin Packing, pages 74–78.

[4] Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to

[5] Binzhou Xia and Zhiyi Tan. Tighter bounds of the first fit algorithm for the bin-