Virtual machine consolidated placement based on multi-objective biogeography-based optimization

https://doi.org/10.1016/j.future.2015.02.010Get rights and content

Highlights

  • Clarify problems of incremental placement and consolidated placement of virtual machine.

  • Build a optimization model of power consumption, resource wastage, server loads, inter-VM and storage network traffic.

  • Firstly apply the BBO meta heuristic to virtual machine consolidated placement problem.

  • Adopt a new strategy about migration rate generation, which beats original and other three strategies.

  • Experimental results verified the robustness, adaptability and extensibility of the proposed method.

Abstract

Virtual machine placement (VMP) is an important issue in selecting most suitable set of physical machines (PMs) for a set of virtual machines (VMs) in cloud computing environment. VMP problem consists of two sub problems: incremental placement (VMiP) problem and consolidated placement (VMcP) problem. The goal of VMcP is to consolidate the VMs to more suitable PMs. The challenge in VMcP problem is how to find optimal solution effectively and efficiently especially when VMcP is a kind of NP-hard problem. In this paper, we present a novel solution to the VMcP problem called VMPMBBO. The proposed VMPMBBO treats VMcP problem as a complex system and utilizes the biogeography-based optimization (BBO) technique to optimize the virtual machine placement that minimizes both the resource wastage and the power consumption at the same time. Extensive experiments have been conducted using synthetic data from related literature and data from two real datasets. First of all, the necessity of VMcP has been proved by experimental results obtained by applying VMPMBBO. Then, the proposed method is compared with two existing multi-objective VMcP optimization algorithms and it is shown that VMPMBBO has better convergence characteristics and is more computationally efficient as well as robust. And then, the issue of parameter setting of the proposed method has been discussed. Finally, adaptability and extensibility of VMPMBBO have also been proved through experimental results. To the best of our knowledge, this work is the first approach that applies biogeography-based optimization (BBO) to virtual machine placement.

Introduction

Cloud computing has been a popular computing paradigm in the IT industry since 2008. It delivers computing infrastructures, computing platforms, and software as hosted services on demand over the Internet. Cloud users can access computing resources without having to own, manage, and maintain them. There are three common cloud computing models known as Infrastructure-as-a-Service (IaaS), Platform-as-a-Service (PaaS), and Software-as-a-Service (SaaS)  [1], [2], [3]. In the most basic model IaaS, like Amazon Web Services, cloud users are provided with physical or, more frequently, virtual machines and additional resources like raw block storage, which are allocated from massive computing resource pools in large-scale data centers. The focus of this paper is on IaaS model.

From the perspective of a cloud provider, to reduce the operating cost, the use of computing resources in cloud needs to be maximized. In addition, the power consumption needs to be minimized as it has become a significant contributor to the operating cost  [4]. The total electricity used by data centers in the US increased about 56% from 2005 to 2010  [5].

The core technology in cloud computing is virtualization  [6], which separates resources and services from the underlying physical delivery environment. The resources of a single physical machine (PM) are sliced into multiple isolated execution environments for multiple virtual machines (VMs). Virtual Machine Placement (VMP) is an important topic in cloud environment virtualization, in particular in IaaS model. VMP maps a set of virtual machines to a set of physical machines. For the cloud providers, a good VMP solution should maximize resource utilization and minimize power consumption.

The problem of VMP consists of two sub problems: incremental placement (VMiP) problem and consolidated placement (VMcP) problem  [7], as shown in Fig. 1. VMiP deals with continuous arrival of VM deployment and removal requests at runtime. Quick response is a crucial metric for ensuring a high service quality of the VMiP. The problem of VMiP has received much attention  [7], [8], [9], [10]. However, as VMs are being continuously removed over time, this may leads to a situation where infrastructure may be brought to a poor VMs distribution state over a long period of time. Therefore, there is an urgent need for periodically redeploying existing VMs on more suitable servers  [7], [11]. The terms “physical machine” and “server” will be used interchangeably in this paper.

VMcP is used by data centers to increase resource utilization and reduce electric power consumption costs  [11]. VMcP is particularly important when users’ workloads are unpredictable and VMcP need to be revisited periodically  [11]. Whenever VM instances change, VMs can be relocated and migrated to different physical servers if necessary  [11]. VMcP can be invoked periodically, or be triggered based on some preset conditions. The problem of VMcP is NP-hard  [12], [13], [14], [15], [16], [17]. The challenge in VMcP problem is how to find optimal solution effectively and efficiently.

The existing research in VMcP can be classified into five categories based on the techniques being used: heuristic bin packing  [18], [19], [20], [21], [22], [23], [24], [25], [12], [26], biology-based optimization  [27], [28], [29], [15], [30], [31], linear programming  [32], [33], constraint programming  [34], and simulated annealing optimization  [35]. Another type of classification is single-objective or multi-objective, based on the number of objectives to be optimized during the placement. Recent research  [5], [30], [36] focuses on multi-objective solutions. Both [5], [30] optimize resource utilization and power consumption. The thermal dissipation cost is also considered in some research efforts  [30]. The work in  [36] optimizes CPU utilization, network throughput, and disk I/O rate. Existing biology-based optimization algorithms for VMcP include genetic algorithms  [29], [5], particle swarm optimization  [28] and ant colony optimization  [27], [30].

In this paper, we propose a novel multi-objective VMcP solution named VMPMBBO. It employs a state-of-the-art evolutionary algorithm, biogeography-based optimization (BBO)  [37], [38], to find the optimal VM placements that simultaneously minimizes both the resource wastage and the power consumption. Compared with two existing multi-objective evolutionary algorithms  [5], [30], VMPMBBO has better convergence characteristics and is more computationally efficient. Extensive simulation results confirm the effectiveness, efficiency and robustness of the proposed approach. Adaptability and extensibility of VMPMBBO have also been proved by experimental results. To the best of our knowledge, this work is the first approach that applies biogeography-based optimization (BBO) and complex system optimization to VMP problem.

The paper is organized as follows. In Section  2, the existing VMcP solutions are reviewed. VM placement problem is formulated in Section  3. Section  4 presents background knowledge of the proposed VMPMBBO approach. The simulation results are presented in Section  4. Section  5 evaluates the effectiveness of the proposed approach. Section  6 proves the adaptability and extensibility of VMPMBBO and finally Section  7 concludes the paper.

Section snippets

Related work

VMcP is one the well research area in cloud computing [4], [18], [19], [20], [27], [28], [29], [15], [30]. These research efforts can be classified into five categories based on their underlying techniques: heuristic bin packing  [18], [19], [20], [32], [21], [22], [23], [24], [25], [12], [26], biology-based optimization  [27], [28], [29], [15], [30], [31], linear programming  [32], [33], constraint programming  [34], and simulated annealing optimization  [35].

Heuristic bin packing. Many

Problem formulation

The first part of this section describes a universal resource wastage model, which support multiple resource dimensions. And then, a power consumption model has been built based on literatures review and experiments. Finally we formalize VMcP optimization problem.

VMPMBBO—biogeography-based optimization for VM consolidated placement

In this section, we introduce background knowledge of biogeography-based optimization (BBO), provide an overview of the proposed VMPMBBO algorithm, and also provide discussion on migration and mutation.

Experiments and analysis

In this section, we evaluate the effectiveness of VMPMBBO applied to VMcP. For this purpose, a series of experiments have been carried out. First of all, we compare experimental results of two VMP processes with and without VMcP. Then we present the evaluation results comparing proposed VMPMBBO with two existing multi-objective VMcP algorithms, MGGA  [15] and VMPACS  [30]. The experimental results also verified the robustness of VMPMBBO. The parameter values concerning experiments have also

Adaptability and extensibility of VMPMBBO

In VMPMBBO, VMcP problem has been solved as a multi-objective optimization problem. As mentioned in Section  4, the feasible solutions of each objective have been obtained from different subsystems. The subsystems are loosely coupled and they communicate with each other by cross-subsystem migration. Therefore, VMPMBBO can easily solve more complex problems involving more objectives or constraints.

In the following subsections, the adaptability and extensibility have been proved by using a

Conclusion and future work

In this paper, we propose a novel VMcP solution called VMPMBBO. VMPMBBO treats VMcP problem as a complex system, and uses a biogeography based optimization method to optimally solve VMcP problem. The proposed VMcP solution optimizes multiple objectives such as power consumption and resource wastage at the same time. VMPMBBO is tested using both synthetic data from related literature and real data from two real-world data centers.

We conducted extensive simulations, evaluated the different

Acknowledgments

This research was partially supported by National Science Foundation of China under Grant Nos. 91118005, 91218301, 61221063, 61103160 and 61103239, 61472315, the National Key Technologies R&D Program of China under Grant No. 2012BAH16F02, Cheung Kong Scholar’s Program, the Ministry of Education Innovation Research Team No. IRT13035, the MOE-Intel Special Research Foundation of Information Technology under Grant No. MOE-INTEL-2012-04, the Shanghai Special Foundation of Software and Integrated

Qinghua Zheng received his B.S. and M.S. degrees in computer science and technology from Xi’an Jiaotong University in 1990 and 1993, respectively, and his Ph.D. degree in systems engineering from the same university in 1997. He was a postdoctoral researcher at Harvard University in 2002. Since 1995 he has been with the Department of Computer Science and Technology at Xi’an Jiaotong University, and was appointed director of the Department in 2008 and Cheung Kong Professor in 2009. His research

References (69)

  • X. Shi et al.

    Developing an optimized application hosting framework in clouds

    J. Comput. System Sci.

    (2013)
  • H. Ma

    An analysis of the equilibrium of migration models for biogeography-based optimization

    Inform. Sci.

    (2010)
  • H. Ma et al.

    Analysis of migration models of biogeography-based optimization using Markov theory

    Eng. Appl. Artif. Intell.

    (2011)
  • P. Mell et al.

    The nist definition of cloud computing

    Natl. Inst. Stand. Technol.

    (2009)
  • W. Voorsluys et al.

    Introduction to cloud computing

    Cloud Comput.

    (2011)
  • D. Filani, J. He, S. Gao, M. Rajappa, A. Kumar, P. Shah, R. Nagappan, Dynamic data center power management: Trends,...
  • J. Koomey, Growth in Data Center Electricity use 2005 to 2010, A report by Analytical Press, Completed at the request...
  • P. Barham et al.

    Xen and the art of virtualization

    SIGOPS Oper. Syst. Rev.

    (2003)
  • W. Yue et al.

    Dynamic placement of virtual machines with both deterministic and stochastic demands for green cloud computing

    Math. Probl. Eng.

    (2014)
  • J. Zhu, D. Li, J. Wu, H. Liu, Y. Zhang, J. Zhang, Towards bandwidth guarantee in multi-tenancy cloud computing...
  • M. Alicherry et al.

    Network aware resource allocation in distributed clouds

  • T. Wood, P.J. Shenoy, A. Venkataramani, M.S. Yousif, Black-box and gray-box strategies for virtual machine migration,...
  • M.H. Ferdaus et al.

    Virtual machine consolidation in cloud data centers using aco metaheuristic

  • M. Wang et al.

    Consolidating virtual machines with dynamic bandwidth demand in data centers

  • J. Xu et al.

    Multi-objective virtual machine placement in virtualized data center environments

  • D. Jayasinghe et al.

    Improving performance and availability of services hosted on iaas clouds with structural constraint-aware virtual machine placement

  • C.-C. Lin et al.

    Energy-aware virtual machine dynamic provision and scheduling for cloud computing

  • L. Grit et al.

    Virtual machine hosting for networked clusters: building the foundations for autonomic orchestration

  • A. Verma et al.

    pMapper: power and migration cost aware application placement in virtualized systems

  • M. Cardosa et al.

    Shares and utilities based power consolidation in virtualized server environments

  • M. Bichler, T. Setzer, B. Speitkamp, Capacity planning for virtualized servers, in: Workshop on Information...
  • S. Srikantaiah, A. Kansal, F. Zhao, Energy aware consolidation for cloud computing, in: Proceedings of the 2008...
  • B. Li et al.

    Enacloud: an energy-saving application live placement approach for cloud computing environments

  • A. Verma et al.

    Power-aware dynamic placement of hpc applications

  • Cited by (138)

    • An ACO for energy-efficient and traffic-aware virtual machine placement in cloud computing

      2022, Swarm and Evolutionary Computation
      Citation Excerpt :

      This section compares the proposed ETA-ACO against six widely used heuristics listed below. MBF: the modified best fit algorithm, where PMs are sorted in descending order by their current power consumption [47]. Each VM is placed into the first PM that has sufficient resources for hosting it.

    View all citing articles on Scopus

    Qinghua Zheng received his B.S. and M.S. degrees in computer science and technology from Xi’an Jiaotong University in 1990 and 1993, respectively, and his Ph.D. degree in systems engineering from the same university in 1997. He was a postdoctoral researcher at Harvard University in 2002. Since 1995 he has been with the Department of Computer Science and Technology at Xi’an Jiaotong University, and was appointed director of the Department in 2008 and Cheung Kong Professor in 2009. His research interests include intelligent e-learning and network security.

    Rui Li is currently a Ph.D. student in the Department of Computer Science and Technology, Xi’an Jiaotong University, China and also a member of MOE Key Lab for Intelligent Networks and Network Security, and also a member of the Satellite–Terrestrial Network Technology R&D Key Laboratory, Shaanxi Province. He has completed his Bachelor’s and Master’s degrees from Xi’an Jiaotong University in 2005 and 2009. His research interests include cloud computing and e-learning.

    Xiuqi Li is an Associate Professor at Department of Computer Science and Mathematics in University of North Carolina at Pembroke (UNCP), Pembroke, North Carolina, USA. Prior to joining UNCP, she worked as a senior instructor in Florida Atlantic University, Boca Raton, Florida, USA for five years. She earned Faculty Summer Research Fellowship in 2010. She served as a program committee member and session chair in 20 conferences, a journal reviewer for 10 journals. She was an NSF panelist in 2008. She holds 29 peer-reviewed journal and conference papers. Her research interests include networking, security, multimedia, and web mining. She is a member of ACM and IEEE.

    Nazaraf Shah is a senior lecturer at Coventry University, Coventry, UK. His research interests include intelligent agents, service-oriented computing, web application security and cloud computing. He has over 50 publications in various international conferences and journals.

    Jianke Zhang is currently an associate professor of applied mathematics, Xi’an University of Posts and Telecommunications. He received the B.S. degree in mathematics from Harbin University of Science and Technology in 2001 and the M.S. and Ph.D. degree in applied mathematics from Xidian University, China in 2006 and 2012, respectively. He current research interests include the development and applications of computational intelligence, robust optimization and interval-valued programming.

    Feng Tian is an associate Professor of Systems Engineering Institute at Xi’an Jiaotong University, China and also is a member of the Satellite–Terrestrial Network Technology R&D Key Laboratory, Shaanxi Province, and also a member of the MOE Key Lab for Intelligent Networks and Network Security. His research interests include system modeling and analysis, cloud computing, Petri nets, and intelligent distance learning environment. He has over 50 publications in books, journals, conference proceedings. He is a member of the IEEE.

    Kuo-Ming Chao is a professor of computing at Coventry University, UK. His research interests include the areas of intelligent agents, service-oriented computing, cloud computing and big data etc. as well as their applications such as energy efficiency management and green manufacturing etc. He has over 150 refereed publications in books, journals, conference proceedings. He is a member of the IEEE.

    Jia Li is currently a graduate student in the Department of Computer Science and Technology, Xi’an Jiaotong University, China and also a member of MOE Key Lab for Intelligent Networks and Network Security, and also a member of the Satellite–Terrestrial Network Technology R&D Key Laboratory, Shaanxi Province. He received his Bachelor’s degree in Computer Science from Xi’an Jiaotong University in 2013. He is interested in the scheduling and the migration of virtual machines in Cloud Computing.

    View full text