Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> The one-dimensional on-line bin-packing problem is considered, A simple <italic>O</italic>(1)-space and <italic>O</italic>(<italic>n</italic>)-time algorithm, called HARMONIC<italic><subscrpt>M</subscrpt></italic>, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the <italic>O</italic>(<italic>n</italic>)-space and <italic>O</italic>(<italic>n</italic> log <italic>n</italic>)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for <italic>all</italic> <italic>0</italic>(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONIC<italic><subscrpt>M </subscrpt></italic>, an <italic>O</italic>(<italic>n</italic>)-space and <italic>O</italic>(<italic>n</italic>)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636. ::: d <s> BIB001 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> Numerous systems have been designed which use virtualization to subdivide the ample resources of a modern computer. Some require specialized hardware, or cannot support commodity operating systems. Some target 100% binary compatibility at the expense of performance. Others sacrifice security or functionality for speed. Few offer resource isolation or performance guarantees; most provide only best-effort provisioning, risking denial of service.This paper presents Xen, an x86 virtual machine monitor which allows multiple commodity operating systems to share conventional hardware in a safe and resource managed fashion, but without sacrificing either performance or functionality. This is achieved by providing an idealized virtual machine abstraction to which operating systems such as Linux, BSD and Windows XP, can be ported with minimal effort.Our design is targeted at hosting up to 100 virtual machine instances simultaneously on a modern server. The virtualization approach taken by Xen is extremely efficient: we allow operating systems such as Linux and Windows XP to be hosted simultaneously for a negligible performance overhead --- at most a few percent compared with the unvirtualized case. We considerably outperform competing commercial and freely available solutions in a range of microbenchmarks and system-wide tests. <s> BIB002 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> Power management has become increasingly necessary in large-scale datacenters to address costs and limitations in cooling or power delivery. This paper explores how to integrate power management mechanisms and policies with the virtualization technologies being actively deployed in these environments. The goals of the proposed VirtualPower approach to online power management are (i) to support the isolated and independent operation assumed by guest virtual machines (VMs) running on virtualized platforms and (ii) to make it possible to control and globally coordinate the effects of the diverse power management policies applied by these VMs to virtualized resources. To attain these goals, VirtualPower extends to guest VMs `soft' versions of the hardware power states for which their policies are designed. The resulting technical challenge is to appropriately map VM-level updates made to soft power states to actual changes in the states or in the allocation of underlying virtualized hardware. An implementation of VirtualPower Management (VPM) for the Xen hypervisor addresses this challenge by provision of multiple system-level abstractions including VPM states, channels, mechanisms, and rules. Experimental evaluations on modern multicore platforms highlight resulting improvements in online power management capabilities, including minimization of power consumption with little or no performance penalties and the ability to throttle power consumption while still meeting application requirements. Finally, coordination of online methods for server consolidation with VPM management techniques in heterogeneous server systems is shown to provide up to 34% improvements in power consumption. <s> BIB003 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> A dynamic server migration and consolidation algorithm is introduced. The algorithm is shown to provide substantial improvement over static server consolidation in reducing the amount of required capacity and the rate of service level agreement violations. Benefits accrue for workloads that are variable and can be forecast over intervals shorter than the time scale of demand variability. The management algorithm reduces the amount of physical capacity required to support a specified rate of SLA violations for a given workload by as much as 50% as compared to static consolidation approach. Another result is that the rate of SLA violations at fixed capacity may be reduced by up to 20%. The results are based on hundreds of production workload traces across a variety of operating systems, applications, and industries. <s> BIB004 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> Power delivery, electricity consumption, and heat management are becoming key challenges in data center environments. Several past solutions have individually evaluated different techniques to address separate aspects of this problem, in hardware and software, and at local and global levels. Unfortunately, there has been no corresponding work on coordinating all these solutions. In the absence of such coordination, these solutions are likely to interfere with one another, in unpredictable (and potentially dangerous) ways. This paper seeks to address this problem. We make two key contributions. First, we propose and validate a power management solution that coordinates different individual approaches. Using simulations based on 180 server traces from nine different real-world enterprises, we demonstrate the correctness, stability, and efficiency advantages of our solution. Second, using our unified architecture as the base, we perform a detailed quantitative sensitivity analysis and draw conclusions about the impact of different architectures, implementations, workloads, and system design choices. <s> BIB005 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> There is growing incentive to reduce the power consumed by large-scale data centers that host online services such as banking, retail commerce, and gaming. Virtualization is a promising approach to consolidating multiple online services onto a smaller number of computing resources. A virtualized server environment allows computing resources to be shared among multiple performance-isolated platforms called virtual machines. By dynamically provisioning virtual machines, consolidating the workload, and turning servers on and off as needed, data center operators can maintain the desired quality-of-service (QoS) while achieving higher server utilization and energy efficiency. We implement and validate a dynamic resource provisioning framework for virtualized server environments wherein the provisioning problem is posed as one of sequential optimization under uncertainty and solved using a lookahead control scheme. The proposed approach accounts for the switching costs incurred while provisioning virtual machines and explicitly encodes the corresponding risk in the optimization problem. Experiments using the Trade6 enterprise application show that a server cluster managed by the controller conserves, on average, 22% of the power required by a system without dynamic control while still maintaining QoS goals. Finally, we use trace-based simulations to analyze controller performance on server clusters larger than our testbed, and show how concepts from approximation theory can be used to further reduce the computational burden of controlling large systems. <s> BIB006 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> Clusters provide powerful computing environments, but in practice much of this power goes to waste, due to the static allocation of tasks to nodes, regardless of their changing computational requirements. Dynamic consolidation is an approach that migrates tasks within a cluster as their computational requirements change, both to reduce the number of nodes that need to be active and to eliminate temporary overload situations. Previous dynamic consolidation strategies have relied on task placement heuristics that use only local optimization and typically do not take migration overhead into account. However, heuristics based on only local optimization may miss the globally optimal solution, resulting in unnecessary resource usage, and the overhead for migration may nullify the benefits of consolidation. In this paper, we propose the Entropy resource manager for homogeneous clusters, which performs dynamic consolidation based on constraint programming and takes migration overhead into account. The use of constraint programming allows Entropy to find mappings of tasks to nodes that are better than those found by heuristics based on local optimizations, and that are frequently globally optimal in the number of nodes. Because migration overhead is taken into account, Entropy chooses migrations that can be implemented efficiently, incurring a low performance overhead. <s> BIB007 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> Recent advances in virtualization technology have made it a common practice to consolidate virtual machines(VMs) into a fewer number of servers. An efficient consolidation scheme requires that VMs are packed tightly, yet receive resources commensurate with their demands. However, measurements from production data centers show that the network bandwidth demands of VMs are dynamic, making it difficult to characterize the demands by a fixed value and to apply traditional consolidation schemes. In this work, we formulate the VM consolidation into a Stochastic Bin Packing problem and propose an online packing algorithm by which the number of servers required is within equation of the optimum for any ∈ > 0. The result can be improved to within equation of the optimum in a special case. In addition, we use numerical experiments to evaluate the proposed consolidation algorithm and observe 30% server reduction compared to several benchmark algorithms. <s> BIB008 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> We consider a large-scale service system model proposed in [14], which is motivated by the problem of efficient placement of virtual machines to physical host machines in a network cloud, so that the total number of occupied hosts is minimized. Customers of different types arrive to a system with an infinite number of servers. A server packing configuration is the vector k = {ki}, where ki is the number of type-i customers that the server "contains". Packing constraints are described by a fixed finite set of allowed configurations. Upon arrival, each customer is placed into a server immediately, subject to the packing constraints; the server can be idle or already serving other customers. After service completion, each customer leaves its server and the system. It was shown in [14] that a simple real-time algorithm, called Greedy, is asymptotically optimal in the sense of minimizing ∑k Xk1+α in the stationary regime, as the customer arrival rates grow to infinity. (Here α > 0, and Xk denotes the number of servers with configuration k.) In particular, when parameter α is small, and in the asymptotic regime where customer arrival rates grow to infinity, Greedy solves a problem approximating one of minimizing ∑k Xk, the number of occupied hosts. In this paper we introduce the algorithm called Greedy with sublinear Safety Stocks (GSS), and show that it asymptotically solves the exact problem of minimizing ∑k Xk. An important feature of the algorithm is that sublinear safety stocks of Xk are created automatically - when and where necessary - without having to determine a priori where they are required. Moreover, we also provide a tight characterization of the rate of convergence to optimality under GSS. The GSS algorithm is as simple as Greedy, and uses no more system state information than Greedy does. <s> BIB009 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Energy-Aware Virtual Machine Assignment <s> Virtual machines (VMs) consolidation has emerged as an important method for the design of energy-efficient data centers. The purpose is to aggregate VMs to fewer physical machines and put the idle servers into power-saving mode. Existing researches mainly focus on transforming the VMs consolidation into various bin packing problems. However, VMs consolidation may cost Service Level Agreement (SLA) violations just after the migration due to the uncertainty of applications' demands. In this paper, we provide a SLA risk management framework, involving a stochastic program to solve the resource allocation for VMs and an algorithm for dynamic VMs consolidation at runtime, to optimize both the energy consumption saving and SLA violations. We validate the proposed algorithm using workloads from a real world system. The results compare with other VMs consolidation algorithms that without considering risk, and show that our SLA violations is reduced by four times from 25% to 2% – 5% while only losing little energy consumption saving. <s> BIB010
Underutilization in data centers is a major cause of excessive energy consumption. Moreover, modern servers are sufficiently powerful to use virtualization to present the illusion of many smaller virtual machines (VMs), each running independent applications BIB002 . Therefore, optimal virtual machine management (including allocation, consolidation, and migration) is an important technique for data centers that can facilitate the improvement of resource utilization and the reduction of energy consumption. The general idea is to efficiently map VMs to servers based on resource matching and improved performance metrics. An early study BIB003 extended virtualization solutions to support rich and effective policies for active power management, which had not been done before. The authors integrated "hard" and "soft" power states to achieve high power savings and showed that substantial benefits could be derived from the coordination of online methods for server consolidation using their proposed management techniques. In BIB005 , Raghavendra et al. proposed a power management solution that coordinated various individual approaches, including a virtual machine controller. Their design used techniques and actuators to optimize power at multiple system levels across both hardware and software. Hermenier et al. BIB007 proposed Entropy, a consolidation manager that performed dynamic consolidation of VMs based on constraint programming and accounted for migration overhead. The authors showed that their approach could significantly reduce the number of nodes and the migration time compared with results obtained using the FFD heuristic. They reported that the consumption of nodes per hour could be reduced by 25%. When exploiting the ability to consolidate several virtual machines on the same physical server, a key challenge is to explicitly account for the specified QoS in the optimization problem BIB004 ,  . Van et al. [106] defined the condition of SLA fulfillment and the resource management cost as a global utility function. The authors adopted the Constraint Programming approach to formulate and solve the considered problem. Kusic et al. BIB006 considered the problem of consolidating services into a smaller number of computing resources to achieve higher server utilization and energy efficiency while maintaining the desired QoS. The authors implemented a dynamic resource provisioning framework to treat this problem as a problem of sequential optimization and solve it using a lookahead control scheme. They reported 22% power savings compared with a system without dynamic control. Several other efforts have also been directed toward the online assignment of virtual machines to fewer servers. Beloglazov et al.  proposed novel adaptive heuristics for the dynamic consolidation of VMs based on an analysis of historical data related to VM resource usage. They applied a modification of the Best Fit Decreasing algorithm to perform the VM assignment, and they achieved significant reduction of energy consumption while ensuring a high level of adherence to the SLA. In BIB008 , the authors considered the problem of consolidating virtual machines when the network bandwidth demands of the VMs are dynamic. They converted the problem into a Stochastic Bin Packing problem and proposed an online packing algorithm. They reported that the performance ratio was within (1 + ǫ)( √ 2 + 1) for any ǫ > 0 and that the number of required servers was reduced by 30% compared with the results of the HARMONIC algorithm BIB001 . In BIB009 , policies that minimized the total number of occupied servers in the system were studied. The authors presented Greedy with sublinear Safety Stocks (GSS) and Modified GSS (GSS-M) policies. Generally speaking, these GSS and GSS-M policies scheduled incoming virtual machines in a manner that greedily minimized the total number of occupied physical servers. The authors demonstrated the asymptotic optimality and convergence rate of their policies. However, such beneficial consolidation also introduces an SLA violation risk. In BIB010 , the authors presented a risk management framework to address the problem of consolidating virtual machines for energy efficiency in data centers. They suggested a two-step approach to virtual machine scheduling: 1) they solved the problem of resource allocation for virtual machines using a stochastic program, and 2) they proposed an algorithm for dynamic virtual machine consolidation at run time. Using real-world workloads, they showed that SLA violations were reduced by a factor of four, from 25% to 2-5%, compared with other virtual machine consolidation algorithms that do not consider the SLA violation risk. Table V summarizes the various approaches to energy-aware virtual machine assignment and presents a comparison of the common features identified among the different proposals mentioned above. The features selected for comparison are as follows: 1) the resources considered, 2) the techniques used in the proposals, 3) the traces used for the experiments, 4) the performance metrics considered, and 5) the results of the proposals.