臺灣博碩士論文加值系統

在現今社會，雲端產業蓬勃發展，因此需要越來越多的資料中心
來當做雲端服務的基礎設施。而在之前的研究中不難發現，資料中心
的規模龐大，因此需要大量的電力來支持整個資料中心的運作。所以
如果我們能在資料中心省去一點點比例的電，最後帶來的獲益卻會是
很龐大的。而在資料中心裡，伺服器和交換機就耗掉了60% 的電，同
時，這兩項設備的能源消耗大多有一個特性就是，單純開機沒有額外
的工作量時，就會耗去滿載工作量時不少比例的電能。所以，能否再
滿足資源需求的情況下，關去不必打開的機器就成了資料中心能否更
省電的關鍵。在之前的研究中，對於資料中心的省電大多都只單純考
慮關去伺服器或是交換機，而我們是第一個同時考慮兩者的研究。我
們把這個問題建構出一個問題模型，但要解出這個模型的最佳解，需
要大量的計算時間，因此我們設計了一個多項式時間內可以解決的方
法。在實驗結果中我們可以發現借著同時考慮兩方面的需求，我們設
演算法相較於之前的方法大約有了30%的進步。同時，在考慮當前最
佳情況來做決定的這種設計方法，在有些時候可能會找不到滿足限制
的結果。我們所設計的演算法在我們跑的實驗中，得到不滿足限制的
結果的機率只有不到3%。

In a data center, virtual machines (VMs) not only require the server resource(e.g., CPU, memory) but also might generate a lot of network traffic among themselves. Existing research works on VMs placement are focusing on (1) how to place VMs to minimize server energy consumption without
considering consumption of network resources; or (2) how to minimize inter-VM network traffic without considering energy consumption. In this work,we tackle the power saving issue of data centers from the point of view of VM placement as well; but, our idea is to address VM placement problem by
joint consideration of both server and network energy consumption for minimizing total power consumption of a data center. First, we validate that the network power consumption plays an important part on the total power consumption of a data center by analyzing the data center architectures and the power benchmark of IT equipments. Next, we propose an energy-aware VM placement algorithm, called GreenGlue, which jointly optimizes the power consumed by servers and switches. GreenGlue is able to address (1) initial VM placement issue, in which VM requests are given and no running VM exists in a data center, and (2) adaptive VM placement issue, in which VM request arrivals and resource demands are dynamic over time. Furthermore, an
optimal (initial or adaptive) VM placement model is derived via the mixed integer linear programming. Finally, we present a comprehensive performance study via simulation with different scenarios generated by synthetic and real traffic traces. The results show that GreenGlue can perform better than existing VM placement schemes in terms of the power saving and the rate of finding feasible placement.

致謝 i
摘要 iii
Abstract v
1 Introduction 1
1.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Background and Motivation 9
2.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Problem Formulation 15
3.1 Problem Definition and Assumptions . . . . . . . . . . . . . . . . . . . . 16
3.2 Data Center Network and VM Model . . . . . . . . . . . . . . . . . . . 17
3.3 Optimization Model Formulation . . . . . . . . . . . . . . . . . . . . . . 18
3.3.1 Initial VM placement . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.2 Adaptive VM Placement . . . . . . . . . . . . . . . . . . . . . . 21
4 GreenGlue: Energy-aware VM Placement 25
4.1 Design Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Heuristic Algorithm for Initial VM placement . . . . . . . . . . . . . . . 27
4.3 Heuristic Algorithm for Adaptive VM Placement . . . . . . . . . . . . . 32
5 Performance Evaluation 35
5.1 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Compare Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6 Related Works 47
6.1 Server-Energy Efficient Resource Allocation. . . . . . . . . . . . . . . . 47
6.2 Traffic-aware VM Placement. . . . . . . . . . . . . . . . . . . . . . . . . 48
6.3 Network-Energy Efficient Traffic Consolidation. . . . . . . . . . . . . . . 48
7 Conclusion and Future Work 51
7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Bibliography 53

[1] Dennis Abts, Michael R. Marty, Philip M. Wells, Peter Klausler, and Hong Liu. Energy Proportional Datacenter Networks. In ISCA’10: Proceedings of the 37th annual international symposium on Computer architecture, pages 338–347. ACM,2010.
[2] Faraz Ahmad and T. N. Vijaykumar. Joint Optimization of Idle and Cooling Power in Data Centers While Maintaining Response Time. In ASPLOS’10: Proceedings of the fifteenth edition of ASPLOS on Architectural support for programming languages and operating systems, pages 243–256. ACM.
[3] Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A Scalable, Commodity Data Center Network Architecture. In SIGCOMM’08: Proceedings of the ACM SIGCOMM 2008 conference on Data communication, pages 63–74. ACM,2008.
[4] ARISTA switch data sheet.http://www.aristanetworks.com/.
53
[5] Anton Beloglazov, Jemal Abawajy, and Rajkumar Buyya. Energy-aware Resource Allocation Heuristics for Efficient Management of Data Centers for Cloud Computing. Future Generation Computer Systems, 28(5):755 – 768, 2012.
[6] Michael Cardosa, Madhukar R. Korupolu, and Aameek Singh. Shares and Utilities based Power Consolidation in Virtualized Server Environments. In IM’09: Proceedings
of the 11th IFIP/IEEE international conference on Symposium on Integrated Network Management, pages 327–334. IEEE Press, 2009.
[7] Cisco switch data sheet. http://www.cisco.com/en/US/prod/collateral
/switches/ps5718/ps5023/product data sheet0900aecd80371991.html.
[8] Teofilo F. Gonzalez. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science, 38(0):293 – 306, 1985.
[9] Albert Greenberg, James Hamilton, David A. Maltz, and Parveen Patel. The Cost of a Cloud: Research Problems in Data Center Networks. SIGCOMM Comput. Commun. Rev., 39(1):68–73, December 2008.
[10] Albert Greenberg, James R. Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A. Maltz, Parveen Patel, and Sudipta Sengupta. VL2: A Scalable and Flexible Data Center Network. In SIGCOMM’09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication, pages 51–62. ACM, 2009.
[11] B. Guenter, N. Jain, and C. Williams. Managing Cost, Performance, and Reliability Tradeoffs for Energy-aware Server Provisioning. In INFOCOM’11: Proceedings of the 30th IEEE International Conference on Computer Communications, pages 1332–1340, april 2011.
[12] Chuanxiong Guo, Guohan Lu, Dan Li, Haitao Wu, Xuan Zhang, Yunfeng Shi, Chen Tian, Yongguang Zhang, and Songwu Lu. BCube: A High Performance, Servercentric Network Architecture for Modular Data Centers. In SIGCOMM’09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication, pages 63–74. ACM, 2009.
[13] Maruti Gupta and Suresh Singh. Greening of the internet. In SIGCOMM’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 19–26. ACM, 2003.
[14] James Hamilton. Internet-scale Service Infrastructure Efficiency. In ISCA 2009 Keynote, 2009.
[15] Brandon Heller, Srinivasan Seetharaman, Priya Mahadevan, Yiannis Yiakoumis, Puneet Sharma, Sujata Banerjee, and Nick McKeown. ElasticTree: Saving Energy in Data Center Networks. In NSDI’10: Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation, pages 249–264. USENIX Association, 2010.
[16] HP switch data sheet. http://h17007.www1.hp.com/.
[17] J.W. Jiang, Tian Lan, Sangtae Ha, Minghua Chen, and Mung Chiang. Joint VM Placement and Routing for Data Center Traffic Engineering. In INFOCOM’12: Proceedings of the 31th IEEE International Conference on Computer Communications,
pages 2876 –2880, march 2012.
[18] Dara Kusic, Jeffrey O. Kephart, James E. Hanson, Nagarajan Kandasamy, and Guofei Jiang. Power and Performance Management of Virtualized Computing Environments Via Lookahead Control. In ICAC’08: Proceedings of the 2008 International Conference on Autonomic Computing, pages 3–12. IEEE, 2008.
[19] Sanghwan Lee and S. Sahu. Efficient Server Consolidation Considering Intra-Cluster Traffic. In GLOBECOM’11: Global Telecommunications Conference, pages
1 –6, dec. 2011.
[20] Haikun Liu, Cheng-Zhong Xu, Hai Jin, Jiayu Gong, and Xiaofei Liao. Performance and Energy Modeling for Live Migration of Virtual Machines. In HPDC’11: Pro-ceedings of the 20th international symposium on High performance distributed computing,pages 171–182. ACM, 2011.
[21] Priya Mahadevan, Puneet Sharma, Sujata Banerjee, and Parthasarathy Ranganathan.A Power Benchmarking Framework for Network Devices. In NETWORKING’09:Proceedings of the 8th International IFIP-TC 6 Networking Conference, pages 795–
808. Springer-Verlag, 2009.
[22] Xiaoqiao Meng, V. Pappas, and Li Zhang. Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement. In IINFOCOM’10: Proceedings
of the 29th IEEE International Conference on Computer Communications,pages 1 –9, march 2010.
[23] Yue Miny. A Simple Proof of the Inequality FFD(L)!11/9 OPT(L)+1, 8L For the FFD Bing-Packing Algorithm. ACTA Mathematicae Applicatae Sinica, 7(4):321–331, 1991.
[24] Ripal Nathuji and Karsten Schwan. VirtualPower: Coordinated Power Management in Virtualized Enterprise Systems. In SOSP’07: Proceedings of twenty-first ACM
SIGOPS symposium on Operating systems principles, pages 265–278. ACM, 2007.
[25] Asfandyar Qureshi, RickWeber, Hari Balakrishnan, John Guttag, and Bruce Maggs. Cutting the Electric Bill for Internet-scale Systems. In SIGCOMM’09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication, pages 123–134. ACM, 2009.
[26] Ramya Raghavendra, Parthasarathy Ranganathan, Vanish Talwar, ZhikuiWang, and Xiaoyun Zhu. No ”Power” Struggles: Coordinated Multi-level Power Management for the Data Center. In ASPLOS’08: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems,pages 48–59. ACM, 2008.
[27] V. Shrivastava, P. Zerfos, Kang won Lee, H. Jamjoom, Yew-Huey Liu, and S. Banerjee. Application-aware Virtual Machine Migration in Data Centers. In INFOCOM’11:Proceedings of the 30th IEEE International Conference on Computer Communications, pages 66 –70, april 2011.
[28] Shekhar Srikantaiah, Aman Kansal, and Feng Zhao. Energy aware Consolidation for Cloud Computing. In HotPower’08: Proceedings of the 2008 conference on Power aware computing and systems, pages 10–10. USENIX Association, 2008.
[29] The Green Grid.
[30] The Standard Performance Evaluation Corporation (SPEC). http://www.spec.org/.
[31] Guido Urdaneta, Guillaume Pierre, and Maarten van Steen. Wikipedia Workload Analysis for Decentralized Hosting. Elsevier Computer Networks, 53(11):1830–1845, July 2009.
[32] U.S. EPA. Report to congress on server and data center energy efficiency. U.S.Environmental Protection Agency, Tech. Rep., Aug. 2007.
[33] Akshat Verma, Puneet Ahuja, and Anindya Neogi. pMapper: Power and Migration Cost aware Application Placement in Virtualized Systems. In Middleware’08: Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware,
pages 243–264. Springer-Verlag New York, Inc., 2008.
[34] Xiaodong Wang, Yanjun Yao, Xiaorui Wang, Kefa Lu, and Qing Cao. CARPO: Correlation-aware Power Optimization in Data Center Networks. In INFOCOM’12: Proceedings of the 31th IEEE International Conference on Computer Communications,
pages 1125 –1133, march 2012.
[35] Pengcheng Xiong, Yun Chi, Shenghuo Zhu, Hyun Jin Moon, Calton Pu, and Hakan Hacigumus. Intelligent management of virtualized resources for database systems in cloud environment. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering, ICDE ’11, pages 87–98, Washington, DC, USA, 2011. IEEE Computer Society.