Title

雲端運算下的節能負載平衡

Translated Titles

Energy Aware Load-Balancing for Cloud Computing

DOI

10.6842/NCTU.2011.00715

Authors

王柏翔

Key Words

雲端運算 ; 負載平衡 ; 虛擬機器 ; 實體機器 ; 雙分圖 ; Computing ; Load-Balancing ; Virtual Machine ; Physical Machine ; Live Migration ; CloudSim ; XCP

PublicationName

交通大學資訊科學與工程研究所學位論文

Volume or Term/Year and Month of Publication

2011年

Academic Degree Category

碩士

Advisor

陳健

Content Language

繁體中文

Chinese Abstract

雲端運算是近年來熱門的議題,透過虛擬化的機制讓虛擬機器共享同一台實體機器上的硬體資源進而提高實體機器上的資源利用度。然而,雲端資料中心需要負載平衡來避免系統中因為某些實體機器上的負擔過重,導致執行效率降低、硬體錯誤甚至當機的情形發生。我們在這篇論文中提出一個將雲端系統中的負載平衡問題轉換成一個權重雙分圖,再透過Hungarian演算法求解其上之最小權重的一組配對,依照得到的配對,平行的將虛擬機器遷移到負擔較低的機器上。一次的配對可以處理系統中多個負擔過重的實體機器來減低系統達到平衡的時間,降低虛擬機器間競爭資源的情形,進而提升系統的產能。我們利用CloudSim這個模擬器來測試我們演算法的效能,實驗的結果顯示我們在各種資源負載平衡的狀態之下,不論是系統達到平衡的時間以及各個虛擬機器上應用程式的執行完成時間皆大幅的下降。我們更利用XCP 雲端平台來搭建我們自己的小型雲端環境來證明我們的演算法在實際的雲端平台上也可以使用。此外,雲端的資料中心為了提供大量運算環境而需要許多伺服器,這些伺服器同時運行造成了大量的能源消耗和碳的排放量。所以我們改良我們的負載平衡演算法,當系統中的工作量降低時,去評估目前需要的伺服器數目,並將多餘的伺服器關閉,在負載平衡的同時達到節能的效果。

English Abstract

Recent movement in cloud computing is showing the trend that more and more companies start to deploy their services on the cloud instead of worrying about the troublesome server configuration and administration by themselves. This trend also helps in consolidating hardware resource usage because the same set of machine resources can serve multiple companies. Through a virtualization technique, different companies’ virtual machines (VMs) could share hardware resources on a single physical machine to improve the resource utilization. In order to maximize resource utilization, a load-balancing mechanism for cloud computing is needed to avoid performance degradation, hardware error or failure due to some overloading physical machines. Load balancing for cloud computing can be performed by migrating a VM from an overloaded host to an underutilized host. Since VM migration time are proportional to the amount of physical memory allocated to the VM. In a cloud data center with tens of thousands of physical machines and hundreds of thousands of VMs, one by one VM migration may take long time to reach a system load equilibrium state. In this paper, we propose an algorithm that transforms the load-balancing problem into a minimum weighted matching problem of a weighted bipartite graph. According to the minimum weighted matching obtained from Hungarian method, we concurrently migrate VMs from overloaded hosts to underutilized hosts. We use the CloudSim toolkit to test our algorithm’s performance and the experimental results show that our algorithm not only obtains a good load balance but also reduces the time to reach system load equilibrium state. We also build a cloud development platform via XCP OS to prove that our algorithm could be used in a realistic cloud environment. Furthermore, a major cause of energy inefficiency in a cloud datacenter is the idle power wasted when servers run at low utilization. Therefore, we modify our load-balancing algorithm to migrate all VMs out of low utilized hosts, then to turn off them to save energy during load-balancing process.

Topic Category 基礎與應用科學 > 資訊科學
資訊學院 > 資訊科學與工程研究所
Reference
  1. [4] “Microsoft Windows Azure,” http://www.microsoft.com/windowsazure/.
    連結:
  2. [5] G. Wang and T. S. Eugene Ng, “The Impact of Virtualization on Network Performance of Amazon EC2 Data Center,” in IEEE INFOCOM, March 2010, pp.1-9.
    連結:
  3. [6] S. K. Garg, C. S. Yeo, A. Anandasivam and R. Buyya, “Environment-conscious scheduling of HPC applications on distributed Cloud-oriented data centers,” Journal of Parallel and Distributed computing, vol.71, pp.732-749, January 2010.
    連結:
  4. [7] B. Li, J. Li, J. Huai, T. Wo, Q. Li, and L. Zhong, “EnaCloud: An Energy-saving Application Live Placement Approach for Cloud Computing Environments,” in Proceedings of the IEEE International Conference on Cloud Computing, September 2009, pp.17-24.
    連結:
  5. [10] Y. Lee and A. Zomaya, “Energy efficient utilization of resources in cloud computing systems”, The Journal of Supercomputing, pp.1-13, March 2010.
    連結:
  6. [11] T. Chieu, A. Mohindra, A. Karve and A. Segal, “Dynamic Scaling of Web Applications in a Virtualized Cloud Computing Environment,” in Proceedings of IEEE International Conference on e-Business Engineering, October 2009, pp.281-286.
    連結:
  7. [12] Y. Zhao and W. Huang, “Adaptive Distributed Load Balancing Algorithm based on Live Migration of Virtual Machines in Cloud,” in Proceedings of the Fifth International Joint Conference on INC, IMS and IDC, August 2009, pp.170-175.
    連結:
  8. [14] S. Nakrani and C. Tovey, “On Honey Bees and Dynamic Server Allocation in Internet Hosting Centers,” Adaptive Behavior – Animals, Animats, Software Agents, Robots, Adaptive Systems, vol. 12, September 2004, pp.223-240 .
    連結:
  9. [16] K. Sato, H. Sato and S. Matsuoka, “A Model-Based Algorithm for Optimizing I/O Intensive Applications in Clouds Using VM-Based Migration,” in Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, May 2009, pp.466-471.
    連結:
  10. [20] H. W. Kuhn, “The Hungarian Method for The Assignment Problem,” Naval Research Logistics Quarterly, vol.2 , pp. 83-97, December 1955.
    連結:
  11. [21] R. Buyya, R. Ranjan and R. N. Calheiros, “Modeling and Simulation of Scalable Cloud Computing Environments and the CloudSim Toolkit: Challenges and Opportunities,” in Proceedings of the 7th High Performance Computing and Simulation Conference, June 2009, pp.1-11.
    連結:
  12. [1] M. Armbrust et al., “Above the Clouds: A Berkeley View of Cloud Computing,” technical report No.UCB/EECS-2009-28, EECs department, U.C. Berkeley, Feburary 2009.
  13. [2] “Amazon EC2,” http://aws.amazon.com/ec2/.
  14. [3] “Google APPs,” http://www.google.com/apps/intl/en/business/index.html.
  15. [8] R. Buyya, A. Beloglazov and J. Abawajy, “Energy-Efficient Management of Data Center Resources for Cloud Computing: A Vision, Architectural Elements, and Open Challenges,” in Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, July 2010, .
  16. [9] S. Srikantaiah, A. Kansal and F. Zhao, “Energy Aware Consolidation for Cloud Computing,” in Proceedings of the Conference on Power Aware Computing and Systems, December 2008, p.10-10.
  17. [13] “EUCALYPTUS,” http://open.eucalyptus.com/
  18. [15] A. Singh, M. Korupolu and D. Mohapatra, “Server-Storage Virtualization: Integration and Load Balancing in Data Centers,” in Proceedings of the International Conference for High Perfirmance Computing, Networking, Storage and Analysis, November 2008, pp.1-12.
  19. [17] C. Clark, K. Fraser, S. Hand, J. G. Hansen, E. Jul, C. Limpach, I. Pratt, and A. Wareld, “Live Migration of Virtual Machines,” in Proceedings of the 2nd ACM/USENIX Symposium on Networked Systems Design and Implementation , May 2005, pp.273-286.
  20. [18] J. Zheng , T. S. Eugene Ng and K. Sripanidkulchai., “Workload-Aware Live Storage Migration for Clouds,” in Proceedings of the 7th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 2011, pp.133-144, .
  21. [19] K. Bubendorfer and J. H. Hine, “A Compositional Classification For Load-Balancing Algorithms,” technical report, No.CS-TR-99-9, Victroia University of Wellington, July 1998, .
  22. [22] “Xen Cloud Platform,” http://www.xen.org/products/cloudxen.html
  23. [23] “Xen,” http://www.xen.org/
  24. [24] “XenCenter,” http://community.citrix.com/display/xs/XenCenter
  25. [25] “Open XenCenter,” http://www.openxenmanager.com/
  26. [26] “Xen API,” http://wiki.xensource.com/xenwiki/XenApi
Times Cited
  1. 吳銘智(2013)。基於節能考量系統差易環境下最佳虛擬機器指派之研究。淡江大學電機工程學系碩士班學位論文。2013。1-53。 
  2. 陳仕彬(2012)。雲端運算之編譯排程系統設計與實作。成功大學電機工程學系碩士在職專班學位論文。2012。1-100。