21-06-2014, 11:30 AM
Optimal Online Deterministic Algorithms and Adaptive Heuristics for Energy and Performance Efficient Dynamic Consolidation of Virtual Machines in Cloud Data Centers
[attachment=65139]
INTRODUCTION
The Cloud computing model leverages virtualization of computing resources allowing customers to
provision resources on-demand on a pay-as-you-go basis [1]. Instead of incurring high upfront costs
in purchasing IT infrastructure and dealing with the maintenance and upgrades of both software and
hardware, organizations can outsource their computational needs to the Cloud. The proliferation of
Cloud computing has resulted in the establishment of large-scale data centers containing thousands
of computing nodes and consuming enormous amounts of electrical energy. Based on the trends
from American Society of Heating, Refrigerating and Air-Conditioning Engineers (ASHRAE) [2],
it has been estimated that by 2014 infrastructure and energy costs would contribute about 75%,
whereas IT would contribute just 25% to the overall cost of operating a data center [3]
ENERGY AND PERFORMANCE EFFICIENT DYNAMIC CONSOLIDATION OF VIRTUAL MACHINES
is essential for Cloud computing environments; therefore, Cloud providers have to deal with the
energy-performance trade-off – the minimization of energy consumption, while meeting the SLAs.
The focus of this work is on energy and performance efficient resource management strategies that
can be applied in a virtualized data center by a Cloud provider (e.g. Amazon EC2). We investigate
performance characteristics of online algorithms for the problem of energy and performance
efficient dynamic VM consolidation. First, we study a simplified problem of determining the time
to migrate a VM from an oversubscribed host to minimize the cost consisting of the cost of energy
consumption and the cost incurred by the Cloud provider due to the SLA violation. We determine
and prove the cost of the optimal offline algorithm for this problem, as well as the competitive
ratio of the optimal online deterministic algorithm. Next, we investigate a more complex problem
of dynamic consolidation of VMs considering multiple hosts and multiple VMs. We find and prove
the competitive ratio of the optimal online deterministic algorithm for this problem.
It is widely known that randomized online algorithms usually provide better performance than
deterministic algorithms designed for the same problems [11]. Therefore, we enhance deterministic
algorithms and propose and evaluate novel heuristics that adapt their behavior based on an analysis
of historical data from the resource usage by VMs. We evaluate the proposed algorithms by
extensive simulation using the CloudSim toolkit and the workload data from 10 days of the resource
usage by more than a thousand PlanetLab VMs provisioned for multiple users. The algorithms
significantly reduce energy consumption, while providing a high level of adherence to the SLAs.
The main contributions of this paper are the following
RELATED WORK
One of the first works, in which power management has been applied in the context of virtualized
data centers, has been done by Nathuji and Schwan [12]. The authors have proposed an architecture
of a data center’s resource management system where resource management is divided into local and
global policies. At the local level the system leverages the guest OS’s power management strategies.
The global manager gets the information on the current resource allocation from the local managers
and applies its policy to decide whether the VM placement needs to be adapted. However, the
authors have not proposed a specific policy for automatic resource management at the global level.
Kusic et al. [13] have defined the problem of power management in virtualized heterogeneous
environments as a sequential optimization and addressed it using Limited Lookahead Control
(LLC). The objective is to maximize the resource provider’s profit by minimizing both power
consumption and SLA violation. Kalman filter is applied to estimate the number of future requests
to predict the future state of the system and perform necessary reallocations. However, in contrast
THE SINGLE VM MIGRATION PROBLEM
In this section we apply competitive analysis [28] to analyze a subproblem of the problem of energy
and performance efficient dynamic consolidation of VMs. There is a single physical server, or host,
and M VMs allocated to that host. In this problem the time is discrete and can be split into N
time frames, where each time frame is 1 second. The resource provider pays the cost of energy
consumed by the physical server. It is calculated as Cptp, where Cp is the cost of power (i.e.
energy per unit of time), and tp is a time period. The resource capacity of the host and resource
usage by VMs are characterized by a single parameter, the CPU performance. The VMs experience
dynamic workloads, which means that the CPU usage by a VM arbitrarily varies over time. The
host is oversubscribed, i.e. if all the VMs request their maximum allowed CPU performance, the
total CPU demand will exceed the capacity of the CPU. We define that when the demand of the
CPU performance exceeds the available capacity, a violation of the SLAs established between the
resource provider and customers occurs. An SLA violation results in a penalty incurred by the
provider, which is calculated as Cvtv, where Cv is the cost of SLA violation per unit of time, and
tv is the time duration of the SLA violation. Without loss of generality, we can define Cp = 1 and
Cv = s, where s ∈ R+. This is equivalent to defining Cp = 1/s and Cv = 1.
At some point in time v, an SLA violation occurs and continues until N. In oth
THE DYNAMIC VM CONSOLIDATION PROBLEM
In this section we analyze a more complex problem of dynamic VM consolidation considering
multiple hosts and multiple VMs. For this problem, we define that there are n homogeneous hosts,
and the capacity of each host is Ah. Although VMs experience variable workloads, the maximum
CPU capacity that can be allocated to a VM is Av. Therefore, the maximum number of VMs
allocated to a host when they demand their maximum CPU capacity is m =
Ah
Av
. The total number
of VMs is nm. VMs can be migrated between hosts using live migration with a migration time tm.
As for the single VM migration problem defined in Section 3, an SLA violation occurs when the
total demand for the CPU performance exceeds the available CPU capacity, i.e. Ah. The cost of
power is Cp, and the cost of SLA violation per unit of time is Cv. Without loss of generality, we
can define Cp = 1 and Cv = s, where s ∈ R+. This is equivalent to defining Cp = 1/s and Cv = 1.
We assume that when a host is idle, i.e. there is no allocated VMs, it is switched off and consumes
ADAPTIVE HEURISTICS FOR DYNAMIC VM CONSOLIDATION
According to the analysis presented in Sections 3 and 4, in this section we propose several heuristics
for dynamic consolidation of VMs based on an analysis of historical data of the resource usage by
VMs. We split the problem of dynamic VM consolidation into four parts: (1) determining when
a host is considered as being overloaded requiring migration of one or more VMs from this host;
(2) determining when a host is considered as being underloaded leading to a decision to migrate
all VMs from this host and switch the host to the sleep mode; (3) selection of VMs that should
be migrated from an overloaded host; and (4) finding a new placement of the VMs selected for
migration from the overloaded and underloaded hosts. We discuss the defined subproblems in the
following sections.
The general algorithm of VM placement optimization is shown in Algorithm 1. First, the
algorithm looks through the list of hosts and by applying the overloading detection algorithm checks
whether a host is overloaded. If the host is overloaded, the algorithm applies the VM selection
policy to select VMs that need to be migrated from the host. Once the list of VMs to be migrated
from the overloaded hosts is built, the VM placement algorithm is invoked to find a new placement
for the VMs to be migrated. The second phase of the algorithm is finding underloaded hosts and
a placement of the VMs from these hosts. The algorithm returns the combined migration map that
contains the information on the new VM placement of the VM selected to be migrated from both
overloaded and underloaded hosts. The complexity of the algorithm is 2N, where N is the number
[attachment=65139]
INTRODUCTION
The Cloud computing model leverages virtualization of computing resources allowing customers to
provision resources on-demand on a pay-as-you-go basis [1]. Instead of incurring high upfront costs
in purchasing IT infrastructure and dealing with the maintenance and upgrades of both software and
hardware, organizations can outsource their computational needs to the Cloud. The proliferation of
Cloud computing has resulted in the establishment of large-scale data centers containing thousands
of computing nodes and consuming enormous amounts of electrical energy. Based on the trends
from American Society of Heating, Refrigerating and Air-Conditioning Engineers (ASHRAE) [2],
it has been estimated that by 2014 infrastructure and energy costs would contribute about 75%,
whereas IT would contribute just 25% to the overall cost of operating a data center [3]
ENERGY AND PERFORMANCE EFFICIENT DYNAMIC CONSOLIDATION OF VIRTUAL MACHINES
is essential for Cloud computing environments; therefore, Cloud providers have to deal with the
energy-performance trade-off – the minimization of energy consumption, while meeting the SLAs.
The focus of this work is on energy and performance efficient resource management strategies that
can be applied in a virtualized data center by a Cloud provider (e.g. Amazon EC2). We investigate
performance characteristics of online algorithms for the problem of energy and performance
efficient dynamic VM consolidation. First, we study a simplified problem of determining the time
to migrate a VM from an oversubscribed host to minimize the cost consisting of the cost of energy
consumption and the cost incurred by the Cloud provider due to the SLA violation. We determine
and prove the cost of the optimal offline algorithm for this problem, as well as the competitive
ratio of the optimal online deterministic algorithm. Next, we investigate a more complex problem
of dynamic consolidation of VMs considering multiple hosts and multiple VMs. We find and prove
the competitive ratio of the optimal online deterministic algorithm for this problem.
It is widely known that randomized online algorithms usually provide better performance than
deterministic algorithms designed for the same problems [11]. Therefore, we enhance deterministic
algorithms and propose and evaluate novel heuristics that adapt their behavior based on an analysis
of historical data from the resource usage by VMs. We evaluate the proposed algorithms by
extensive simulation using the CloudSim toolkit and the workload data from 10 days of the resource
usage by more than a thousand PlanetLab VMs provisioned for multiple users. The algorithms
significantly reduce energy consumption, while providing a high level of adherence to the SLAs.
The main contributions of this paper are the following
RELATED WORK
One of the first works, in which power management has been applied in the context of virtualized
data centers, has been done by Nathuji and Schwan [12]. The authors have proposed an architecture
of a data center’s resource management system where resource management is divided into local and
global policies. At the local level the system leverages the guest OS’s power management strategies.
The global manager gets the information on the current resource allocation from the local managers
and applies its policy to decide whether the VM placement needs to be adapted. However, the
authors have not proposed a specific policy for automatic resource management at the global level.
Kusic et al. [13] have defined the problem of power management in virtualized heterogeneous
environments as a sequential optimization and addressed it using Limited Lookahead Control
(LLC). The objective is to maximize the resource provider’s profit by minimizing both power
consumption and SLA violation. Kalman filter is applied to estimate the number of future requests
to predict the future state of the system and perform necessary reallocations. However, in contrast
THE SINGLE VM MIGRATION PROBLEM
In this section we apply competitive analysis [28] to analyze a subproblem of the problem of energy
and performance efficient dynamic consolidation of VMs. There is a single physical server, or host,
and M VMs allocated to that host. In this problem the time is discrete and can be split into N
time frames, where each time frame is 1 second. The resource provider pays the cost of energy
consumed by the physical server. It is calculated as Cptp, where Cp is the cost of power (i.e.
energy per unit of time), and tp is a time period. The resource capacity of the host and resource
usage by VMs are characterized by a single parameter, the CPU performance. The VMs experience
dynamic workloads, which means that the CPU usage by a VM arbitrarily varies over time. The
host is oversubscribed, i.e. if all the VMs request their maximum allowed CPU performance, the
total CPU demand will exceed the capacity of the CPU. We define that when the demand of the
CPU performance exceeds the available capacity, a violation of the SLAs established between the
resource provider and customers occurs. An SLA violation results in a penalty incurred by the
provider, which is calculated as Cvtv, where Cv is the cost of SLA violation per unit of time, and
tv is the time duration of the SLA violation. Without loss of generality, we can define Cp = 1 and
Cv = s, where s ∈ R+. This is equivalent to defining Cp = 1/s and Cv = 1.
At some point in time v, an SLA violation occurs and continues until N. In oth
THE DYNAMIC VM CONSOLIDATION PROBLEM
In this section we analyze a more complex problem of dynamic VM consolidation considering
multiple hosts and multiple VMs. For this problem, we define that there are n homogeneous hosts,
and the capacity of each host is Ah. Although VMs experience variable workloads, the maximum
CPU capacity that can be allocated to a VM is Av. Therefore, the maximum number of VMs
allocated to a host when they demand their maximum CPU capacity is m =
Ah
Av
. The total number
of VMs is nm. VMs can be migrated between hosts using live migration with a migration time tm.
As for the single VM migration problem defined in Section 3, an SLA violation occurs when the
total demand for the CPU performance exceeds the available CPU capacity, i.e. Ah. The cost of
power is Cp, and the cost of SLA violation per unit of time is Cv. Without loss of generality, we
can define Cp = 1 and Cv = s, where s ∈ R+. This is equivalent to defining Cp = 1/s and Cv = 1.
We assume that when a host is idle, i.e. there is no allocated VMs, it is switched off and consumes
ADAPTIVE HEURISTICS FOR DYNAMIC VM CONSOLIDATION
According to the analysis presented in Sections 3 and 4, in this section we propose several heuristics
for dynamic consolidation of VMs based on an analysis of historical data of the resource usage by
VMs. We split the problem of dynamic VM consolidation into four parts: (1) determining when
a host is considered as being overloaded requiring migration of one or more VMs from this host;
(2) determining when a host is considered as being underloaded leading to a decision to migrate
all VMs from this host and switch the host to the sleep mode; (3) selection of VMs that should
be migrated from an overloaded host; and (4) finding a new placement of the VMs selected for
migration from the overloaded and underloaded hosts. We discuss the defined subproblems in the
following sections.
The general algorithm of VM placement optimization is shown in Algorithm 1. First, the
algorithm looks through the list of hosts and by applying the overloading detection algorithm checks
whether a host is overloaded. If the host is overloaded, the algorithm applies the VM selection
policy to select VMs that need to be migrated from the host. Once the list of VMs to be migrated
from the overloaded hosts is built, the VM placement algorithm is invoked to find a new placement
for the VMs to be migrated. The second phase of the algorithm is finding underloaded hosts and
a placement of the VMs from these hosts. The algorithm returns the combined migration map that
contains the information on the new VM placement of the VM selected to be migrated from both
overloaded and underloaded hosts. The complexity of the algorithm is 2N, where N is the number