雲端運算是近來熱門的網路服務概念,其利用網路技術把巨量且複雜的運算隱蔽於使用者視野之外,將大規模且可擴充的資訊科技能力以計費服務方式提供。為
了降低營運成本及提高硬體資源使用率,資料中心成為集中管理雲端運算資源的核心設施。資料中心一般是由數量龐大的伺服器搭配特定網路組成。伺服器負責
提供運算資源等相關服務,該服務則透過資料中心網路快速來回於提供服務的伺服器和接受服務的使用者之間。為提高資源使用率,虛擬化技術被廣泛應用於資
料中心,將資料中心虛擬化成一個擁有巨量服務能力的資源池。透過虛擬化技術,所有服務皆可透過虛擬機提供給使用者。虛擬化技術賦予了資料中心彈性供給資
源的能力,也由於其隔離特性提供了一定程度的安全性。
即使有了虛擬化技術,雲端運算中資料中心的效能仍未臻究竟。許多報告及研究指出資料中心很大一部份能量消耗仍是由於資源使用率低下造成的。除此問題之外,網路元件故障造成的使用者體驗及服務品質的降低也成了資料中心需謹慎應對的重要課題。本篇論文將深入探討資料中心的伺服器資源配置問題以及不同資料中心網路拓樸所帶來的網路可用性和即時搬遷 (Live migration) 所帶來的影響。根據統計,絕大部分虛擬機上應用程式的實際資源需求會低於使用者最初購入虛擬機時的要求量,所以資料中心管理者藉由調整供應給虛擬機的資源量並將多台虛擬機配置在少數伺服器上來改善伺服器資源使用率。本篇論文提出預測虛擬機未來資源使用量並計算預留定量資源給虛擬機。預留定量資源些微降低了伺服器使用率,但它可用來減少因突發工作量 (Workload burst) 產生的即時搬遷數量。即時搬遷是在儘量不中斷虛擬機運作的前提下將虛擬機遷移至運算資源相對充沛的伺服器上執行,然而它會佔用網路頻寬並影響虛擬機上執行的應用程式效能。此外,本篇論文也提出應用節點不相交路徑以兼顧資料中心網路的節能和網路可用性,以避免由於網路元件故障造成的網路可用性大幅下降問題。模擬結果顯示,提出的方法能有效改善資源使用率減少能源消耗。

Cloud computing has attracted attentions in recent years. Users use the cloud services through the Internet in a pay-as-you-go manner. To provide the massive cloud services, a data center is built with thousands of servers and switches connected by a communication network called a data center network (DCN). The servers provide computing resources to run the cloud services and the cloud services are transmitted through the DCN to the users. Virtualization is a key technology that is widely applied to virtualize the physical resources and ensure the isolation of cloud services or applications. The cloud services are usually provided through Virtual Machines (VMs) to guarantee the security and scalability of physical resources.
Recent research shows that a large amount of energy is wasted because of the underutilization of physical resources in data centers. In addition, the data center manager has to maintain the network availability from the failures of network devices in order to provide reliable cloud services. This thesis addresses the above problems by exploring the dynamic VM consolidation algorithms, energy-efficient routing algorithms, resource allocation algorithms, and the features of DCNs. A dynamic VM consolidation algorithm is proposed to reduce the energy consumption and the service-level agreement (SLA) violation by predicting the future resource demand based on the historical utilization for each VM. To improve the energy efficiency and the network availability in different DCNs, this thesis finds two node-disjoint paths for each traffic flow so that the failed traffic flows which are caused by the failures of network devices can be routed through the backup path immediately. Since live migration can negatively impact the performance of the system depending on the amount of transferred data and the path length, this thesis proposes an online resource allocation algorithm to achieve energy efficiency and SLA violations of data centers while considering the power usage of servers, the number of migrations, and the path length of migrations in DCNs. Simulation results show that the proposed algorithms reduce the energy consumption while considering the SLA violation, the number of migrations, the network availability, and the path length of migrations.

[1] A. Akella, T. Benson, B. Chandrasekaran, C. Huang, B. Maggs, and D. Maltz, “A universal approach to data center network design,” in Proceedings of the International Conference on Distributed Computing and Networking. New York, NY, USA: ACM, 2015.
[2] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” in ACM SIGCOMM Computer Communication Review, vol. 38, no. 4. ACM, 2008, pp. 63–74.
[3] E. Arianyan, H. Taheri, and S. Sharifian, “Novel heuristics for consolidation of virtual machines in cloud data centers using multi-criteria resource management solutions,” The Journal of Supercomputing, vol. 72, no. 2, pp. 688–717, 2016.
[4] M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia, “A view of cloud computing,” Communications of the ACM, vol. 53, no. 4, pp. 50–58, 2010.
[5] L. A. Barroso and U. Hölzle, “The case for energy-proportional computing,” Computer, vol. 40, no. 12, 2007.
[6] A. Beloglazov, “Energy-efficient management of virtual machines in data centers for cloud computing,” Ph.D. dissertation, Department of Computing and Information Systems, THE UNIVERSITY OF MELBOURNE, 2013.
[7] A. Beloglazov, J. Abawajy, and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing,” Future generation computer systems, vol. 28, no. 5, pp. 755–768, 2012.
[8] A. Beloglazov and R. Buyya, “Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers,” Concurrency and Computation: Practice and Experience, vol. 24, no. 13, pp. 1397–1420, 2012.
[9] A. Beloglazov and R. Buyya, “Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers under quality of service constraints,” IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 7, pp. 1366–1379, 2013.
[10] T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data centers in the wild,” in Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. New York, NY, USA: ACM, 2010, pp. 267–280.
[11] K. Bilal, M. Manzano, S. Khan, E. Calle, K. Li, and A. Zomaya, “On the characterization of the structural robustness of data center networks,” IEEE Transactions on Cloud Computing, vol. 1, no. 1, pp. 64–77, 2013.
[12] D. Boru, D. Kliazovich, F. Granelli, P. Bouvry, and A. Y. Zomaya, “Energy-efficient data replication in cloud computing datacenters,” Cluster Computing, vol. 18, no. 1, pp. 385–402, 2015.
[13] R. Buyya, C. Vecchiola, and S. T. Selvi, Mastering cloud computing: foundations and applications programming. Newnes, 2013.
[14] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. D. Rose, and R. Buyya, “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” Software: Practice and experience, vol. 41, no. 1, pp. 23–50, 2011.
[15] T. M. Chan, “All-pairs shortest paths for unweighted undirected graphs in O(mn) time,” ACM Transactions on Algorithms (TALG), vol. 8, no. 4, p. 34, 2012.
[16] L. Chiaraviglio, M. Mellia, and F. Neri, “Minimizing ISP network energy cost: formulation and solutions,” IEEE/ACM Transactions on Networking (TON), vol. 20, no. 2, pp. 463–476, 2012.
[17] Cisco, “Cisco Data Center Infrastructure 2.5 Design Guide,” Cisco Systems, Inc., Tech. Rep., 2011.
[18] C. Clark, K. Fraser, S. Hand, J. G. Hansen, E. Jul, C. Limpach, I. Pratt, and A. Warfield, “Live migration of virtual machines,” in Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation-Volume 2. USENIX Association, 2005, pp. 273–286.
[19] R. A. da Silva and N. L. da Fonseca, “Topology-aware virtual machine placement in data centers,” Journal of Grid Computing, vol. 14, no. 1, pp. 75–90, 2016.
[20] M. Dabbagh, B. Hamdaoui, M. Guizani, and A. Rayes, “Energy-efficient resource allocation and provisioning framework for cloud data centers,” IEEE Transactions on Network and Service Management, vol. 12, no. 3, pp. 377–391, 2015.
[21] M. Dayarathna, Y. Wen, and R. Fan, “Data center energy consumption modeling: A survey,” Communications Survey and Tutorials, vol. 18, no. 1, pp. 732–794, 2016.
[22] G. Dósa and J. Sgall, “First fit bin packing: A tight analysis,” in LIPIcs-Leibniz International Proceedings in Informatics, vol. 20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013.
[23] T. V. T. Duy, Y. Sato, and Y. Inoguchi, “Performance evaluation of a green scheduling algorithm for energy savings in cloud computing,” in IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, 2010, pp. 1–8.
[24] S. Even, A. Itai, and A. Shamir, “On the complexity of time table and multi-commodity flow problems,” in 16th Annual Symposium on Foundations of Computer Science. Berkeley, USA: IEEE, 1975, pp. 184–193.
[25] X. Fan, W.-D. Weber, and L. A. Barroso, “Power provisioning for a warehouse-sized computer,” in ACM SIGARCH Computer Architecture News, vol. 35, no. 2. ACM, 2007, pp. 13–23.
[26] P. Gill, N. Jain, and N. Nagappan, “Understanding network failures in data centers: measurement, analysis, and implications,” in ACM SIGCOMM Computer Communication Review, vol. 41, no. 4. New York, NY, USA: ACM, 2011, pp. 350–361.
[27] M. Gómez, D. Perales, and E. J. Torres, “An energy-aware design and reporting tool for on-demand service infrastructures,” in 10th IEEE/ACM International Conference on Grid Computing. IEEE, 2009, pp. 209–216.
[28] P. Graubner, M. Schmidt, and B. Freisleben, “Energy-efficient management of virtual machines in eucalyptus,” in IEEE International Conference on Cloud Computing (CLOUD). IEEE, 2011, pp. 243–250.
[29] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “BCube: A high performance, server-centric network architecture for modular data centers,” ACM SIGCOMM Computer Communication Review, vol. 39, no. 4, pp. 63–74, 2009.
[30] C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu, “DCell: A scalable and fault-tolerant network structure for data centers,” in ACM SIGCOMM Computer Communication Review, vol. 38, no. 4. ACM, 2008, pp. 75–86.
[31] D. Guo, C. Li, J. Wu, and X. Zhou, “DCube: A family of network structures for containerized data centers using dual-port servers,” Computer Communications, vol. 53, pp. 13–25, 2014.
[32] A. Hammadi and L. Mhamdi, “A survey on architectures and energy efficiency in data center networks,” Computer Communications, vol. 40, pp. 1–21, 2014.
[33] Z. Han, H. Tan, G. Chen, R. Wang, Y. Chen, and F. C. Lau, “Dynamic virtual machine management via approximate markov decision process,” in IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications. IEEE, 2016, pp. 1–9.
[34] B. Heller, S. Seetharaman, P. Mahadevan, Y. Yiakoumis, P. Sharma, S. Banerjee, and N. McKeown, “ElasticTree: Saving energy in data center networks.” in NSDI, vol. 10, 2010, pp. 249–264.
[35] F. Hermenier, X. Lorca, J.-M. Menaud, G. Muller, and J. Lawall, “Entropy: a consolidation manager for clusters,” in Proceedings of the ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. ACM, 2009, pp. 41–50.
[36] S. Hosseinimotlagh, F. Khunjush, and R. Samadzadeh, “Seats: smart energy-aware task scheduling in real-time cloud computing,” The Journal of Supercomputing, vol. 71, no. 1, pp. 45–66, 2015.
[37] Q. Huang, F. Gao, R. Wang, and Z. Qi, “Power consumption of virtual machine live migration in clouds,” in Third International Conference on Communications and Mobile Computing (CMC). IEEE, 2011, pp. 122–125.
[38] IBM ILOG, “Cplex optimization studio,” 2012, online at http://www-01.ibm.com/software/integration/optimization/cplex-optimization-studio/.
[39] H.-P. Jiang, D. Chuck, and W.-M. Chen, “Energy-aware data center networks,” Journal of Network and Computer Applications, vol. 68, pp. 80–89, 2016.
[40] H.-P. Jiang, M.-L. Weng, and W.-M. Chen, “Dynamic consolidation of virtual machines in cloud datacenters,” IEICE TRANSACTIONS on Information and Systems, vol. 97, no. 7, pp. 1727–1730, 2014.
[41] S. Kandula, S. Sengupta, A. Greenberg, P. Patel, and R. Chaiken, “The nature of data center traffic: measurements & analysis,” in Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference. ACM, 2009, pp. 202–208.
[42] D.-K. Kang, F. Al-Hazemi, S.-H. Kim, M. Chen, L. Peng, and C.-H. Youn, “Adaptive vm management with two phase power consumption cost models in cloud datacenter,” Mobile Networks and Applications, pp. 1–13, 2016.
[43] G. Katsaros, J. Subirats, J. O. Fitó, J. Guitart, P. Gilet, and D. Espling, “A service framework for energy-aware monitoring and vm management in clouds,” Future Generation Computer Systems, vol. 29, no. 8, pp. 2077–2091, 2013.
[44] A. Kertész, G. Kecskemeti, and I. Brandic, “An interoperable and self-adaptive approach for SLA-based service virtualization in heterogeneous Cloud environments,” Future Generation Computer Systems, vol. 32, pp. 54–68, 2014.
[45] J. Kim, W. J. Dally, and D. Abts, “Flattened butterfly: a cost-efficient topology for high-radix networks,” ACM SIGARCH Computer Architecture News, vol. 35, no. 2, pp. 126–137, 2007.
[46] D. Kliazovich, P. Bouvry, and S. U. Khan, “DENS: data center energy-efficient network-aware scheduling,” Cluster computing, vol. 16, no. 1, pp. 65–75, 2013.
[47] D. Kusic, J. O. Kephart, J. E. Hanson, N. Kandasamy, and G. Jiang, “Power and performance management of virtualized computing environments via lookahead control,” in ICAC’08 International Conference on Autonomic Computing. IEEE, 2008, pp. 3–12.
[48] F. T. Leighton, Introduction to Parallel Algorithms and Architectures. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1992.
[49] C. E. Leiserson, “Fat-trees: universal networks for hardware-efficient supercomputing,” IEEE Transactions on Computers, vol. 100, no. 10, pp. 892–901, 1985.
[50] H. Li and M. Muskulus, “Analysis and modeling of job arrivals in a production grid,” ACM SIGMETRICS Performance Evaluation Review, vol. 34, no. 4, pp. 59–70, 2007.
[51] D. Lin, Y. Liu, M. Hamdi, and J. Muppala, “Hyper-BCube: A scalable data center network,” in IEEE International Conference on Communications (ICC). IEEE, 2012, pp. 2918–2923.
[52] G. Lin, S. Soh, K.-W. Chin, and M. Lazarescu, “Energy aware two disjoint paths routing,” Journal of Network and Computer Applications, vol. 43, no. 0, pp. 27 – 41, 2014.
[53] H. Liu, H. Jin, C.-Z. Xu, and X. Liao, “Performance and energy modeling for live migration of virtual machines,” Cluster computing, vol. 16, no. 2, pp. 249–264, 2013.
[54] D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming. New York, NY, USA: Springer, 2008, vol. 116.
[55] H. Nguyen Van, F. Dang Tran, and J.-M. Menaud, “Autonomic virtual resource management for service hosting platforms,” in Proceedings of the ICSE Workshop on Software Engineering Challenges of Cloud Computing. IEEE Computer Society, 2009, pp. 1–8.
[56] D. Nurmi, R. Wolski, C. Grzegorczyk, G. Obertelli, S. Soman, L. Youseff, and D. Zagorodnov, “The eucalyptus open-source cloud-computing system,” in Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid. IEEE Computer Society, 2009, pp. 124–131.
[57] A.-C. Orgerie, M. D. de Assuncao, and L. Lefevre, “A survey on techniques for improving the energy efficiency of large-scale distributed systems,” ACM Computing Surveys (CSUR), vol. 46, no. 4, p. 47, 2014.
[58] K. Park and V. S. Pai, “CoMon: a mostly-scalable monitoring system for PlanetLab,” ACM SIGOPS Operating Systems Review, vol. 40, no. 1, pp. 65–74, 2006.
[59] S. Pelley, D. Meisner, T. F. Wenisch, and J. W. VanGilder, “Understanding and abstracting total data center power,” in Workshop on Energy-Efficient Design, 2009.
[60] J. Peng, X. Zhang, Z. Lei, B. Zhang, W. Zhang, and Q. Li, “Comparison of several cloud computing platforms,” in Second International Symposium on Information Science and Engineering (ISISE). IEEE, 2009, pp. 23–27.
[61] M. Rosenblum and T. Garfinkel, “Virtual machine monitors: Current technology and future trends,” Computer, vol. 38, no. 5, pp. 39–47, 2005.
[62] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no. 7, pp. 867–872, 1988.
[63] T. Setzer and A. Wolke, “Virtual machine re-assignment considering migration overhead,” in Network Operations and Management Symposium (NOMS). IEEE, 2012, pp. 631–634.
[64] Y. Shang, D. Li, and M. Xu, “Energy-aware routing in data center network,” in Proceedings of the first ACM SIGCOMM workshop on Green networking. ACM, 2010, pp. 1–8.
[65] S. Singh and I. Chana, “Resource provisioning and scheduling in clouds: QoS perspective,” The Journal of Supercomputing, vol. 72, no. 3, pp. 926–960, 2016.
[66] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: networking data centers randomly,” In NSDI’12. USENIX, 2012.
[67] J. Tai, J. Zhang, J. Li, W. Meleis, and N. Mi, “Ara: Adaptive resource allocation for cloud computing environments under bursty workloads,” in 30th IEEE International Performance Computing and Communications Conference. IEEE, 2011, pp. 1–8.
[68] A. Tchana, N. D. Palma, I. Safieddine, and D. Hagimont, “Software consolidation as an efficient energy and cost saving solution,” Future Generation Computer Systems, vol. 58, pp. 1–12, 2016.
[69] F. P. Tso and D. P. Pezaros, “Improving data center network utilization using near-optimal traffic engineering,” IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 6, pp. 1139–1148, 2013.
[70] A. Verma, G. Kumar, and R. Koller, “The cost of reconfiguration in a cloud,” in Proceedings of the 11th International Middleware Conference Industrial track. ACM, 2010, pp. 11–16.
[71] W. Vogels, “Beyond server consolidation,” Queue, vol. 6, no. 1, pp. 20–26, 2008.
[72] W. Voorsluys, J. Broberg, S. Venugopal, and R. Buyya, “Cost of virtual machine live migration in clouds: A performance evaluation,” in IEEE International Conference on Cloud Computing. Springer, 2009, pp. 254–265.
[73] L. Wang, F. Zhang, J. A. Aroca, A. V. Vasilakos, K. Zheng, C. Hou, D. Li, and Z. Liu, “GreenDCN: a general framework for achieving energy efficiency in data center networks,” IEEE Journal on Selected Areas in Communications, vol. 32, no. 1, pp. 4–15, 2014.
[74] T. Wang, B. Qin, Z. Su, Y. Xia, M. Hamdi, S. Foufou, and R. Hamila, “Towards bandwidth guaranteed energy efficient data center networking,” Journal of Cloud Computing, vol. 4, no. 1, pp. 1–15, 2015.
[75] X. Wang, X. Wang, K. Zheng, Y. Yao, and Q. Cao, “Correlation-aware traffic consolidation for power optimization of data center networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 4, pp. 992–1006, 2016.
[76] J. Wilkes, “More Google cluster data,” Google research blog, Nov. 2011, posted at http://googleresearch.blogspot.com/2011/11/more-google-cluster-data.html.
[77] Z. Xiao, W. Song, and Q. Chen, “Dynamic resource allocation using virtual machines for cloud computing environment,” IEEE Transactions on parallel and distributed systems, vol. 24, no. 6, pp. 1107–1117, 2013.
[78] F. Yao, J. Wu, G. Venkataramani, and S. Subramaniam, “A comparative analysis of data center network architectures,” in IEEE International Conference on Communications (ICC). Sydney, Australia: IEEE, 2014, pp. 3106–3111.
[79] H. Yu, D. Zheng, B. Y. Zhao, and W. Zheng, “Understanding user behavior in large-scale video-on-demand systems,” in ACM SIGOPS Operating Systems Review, vol. 40, no. 4. ACM, 2006, pp. 333–344.
[80] S. Zhang, Z. Qian, Z. Luo, J. Wu, and S. Lu, “Burstiness-aware resource reservation for server consolidation in computing clouds,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 4, pp. 964–977, 2016.
[81] Y. Zhang and N. Ansari, “HERO: Hierarchical energy optimization for data center networks,” IEEE Systems Journal, vol. 9, no. 2, pp. 406–415, 2015.
[82] Q. Zheng, R. Li, X. Li, N. Shah, J. Zhang, F. Tian, K.-M. Chao, and J. Li, “Virtual machine consolidated placement based on multi-objective biogeography-based optimization,” Future Generation Computer Systems, vol. 54, pp. 95–122, 2016.
[83] W. Zou, M. Janic, R. Kooij, and F. Kuipers, “On the availability of networks,” Proc. of BroadBand Europe, 2007.