In cloud systems, demand-prediction based resource provisioning schemes help assure the SLOs (service level objectives) of cloud tenants. We notice that if a provisioning scheme does not exclude bursts from historical resource demands in normal demand prediction or always uses a large padding to correct under-prediction, it will lead to resource over-provisioning and low resource utilization. To improve the previous schemes, in this paper, we present a Resource-efficient Predictive Resource Provisioning system in cloud systems (RPRP) that excludes bursts in demand prediction and has algorithms to specifically handle bursts to avoid resource over-provisioning. Rather than setting padding to a possibly high value, RPRP has a load-dependent padding algorithm that adaptively determines padding based on predicted demands. To handle bursts, RPRP has a burst-resilient shared padding algorithm that reserves resource shared by multiple co-located VMs rather than for individual VMs. It also embodies a responsive padding algorithm that adaptively adjusts padding to recover from both under-provisioning and over-provisioning. We implemented RPRP on top of Xen and conducted both trace-driven simulation and real-world testbed experiments. The experimental results show that RPRP achieves higher resource utilization, more accurate demand predictions, and fewer SLO violations than previous schemes.

To provide robust infrastructure as a service (IaaS), clouds currently perform load balancing by migrating virtual machines (VMs) from heavily loaded physical machines (PMs) to lightly loaded PMs. The unique features of clouds pose formidable challenges to achieving effective and efficient load balancing. First, VMs in clouds use different resources (e.g., CPU, bandwidth, memory) to serve a variety of services (e.g., high performance computing, web services, file services), resulting in different over utilized resources in different PMs. Also, the over utilized resources in a PM may vary over time due to the time-varying heterogeneous service requests. Second, there is intensive network communication between VMs. However, previous load balancing methods statically assign equal or predefined weights to different resources, which lead to degraded performance in terms of speed and cost to achieve load balance. Also, they do not strive to minimize the VM communications between PMs. We propose a Resource Intensity Aware Load balancing method (RIAL). For each PM, RIAL dynamically assigns different weights to different resources according to their usage intensity in the PM, which significantly reduces the time and cost to achieve load balance and avoids future load imbalance. It also tries to keep frequently communicating VMs in the same PM to reduce bandwidth cost, and migrates VMs to PMs with minimum VM performance degradation. We also propose an extended version of RIAL with three additional algorithms. First, it optimally determines the weights for considering communication cost and performance degradation due to VM migrations. Second, it has a more strict migration triggering algorithm to avoid unnecessary migrations while still satisfying Service Level Objects (SLOs). Third, it conducts destination PM selection in a decentralized manner to improve scalability. Our extensive trace-driven simulation results and real-world experimental results show the superior performance of RIAL compared to other load balancing methods.

Cloud computing offers a cost-effective and elastic computing paradigm that facilitates large scale data storage and analytics. By deploying virtualization technologies in the datacenter, cloud enables efficient resource management and isolation for various big data applications. Since the hotspots (i.e., overloaded machines) can degrade the performance of these applications, virtual machine migration has been utilized to perform load balancing in the datacenters to eliminate hotspots and guarantee Service Level Agreements (SLAs). However, the previous load balancing schemes make migration decisions based on deterministic resource demand estimation and workload characterization, without considering their stochastic properties. By studying real world traces, we show that the resource demand and workload of virtual machines are highly dynamic and bursty, which can cause these schemes to make inefficient migrations for load balancing. To address this problem, in this paper we propose a stochastic load balancing scheme which aims to provide probabilistic guarantee against the resource overloading with virtual machine migration, while minimizing the total migration overhead. Our scheme effectively addresses the prediction of the distribution of resource demand and the multidimensional resource requirements with stochastic characterization. Moreover, as opposed to the previous works that measure the migration cost without considering the network topology, our scheme explicitly takes into account the distance between the source physical machine and the destination physical machine for a virtual machine migration. The trace-driven experiments show that our scheme outperforms the previous schemes in terms of SLA violation and the migration cost.

Functioning as an intermediary between tenants and cloud providers, cloud service brokerages (CSBs) can bring about great benefits to the cloud market. As energy costs of cloud computing have been increasing rapidly, there is a need for cloud providers to optimize energy efficiency while maintain high service level performance to tenants, not only for their own benefit but also for social welfares. Thus, for green cloud companies, two questions have arisen: 1) under what pricing policies from the cloud providers to the CSB, a profit-driven CSB is willing to minimize the total energy cost while satisfy tenant demands and 2) how should a CSB distribute tenants demands to achieve this objective? To address question 1), we find a pricing policy for cloud providers such that maximizing CSBs profit is equivalent to minimizing cloud providers energy cost. To address question 2), we first devise a greedy solution, and then propose an approximation algorithm and a decomposition-based solution with a constant approximation ratio. Both simulation and real-world Amazon EC2 experimental results demonstrate the effectiveness of our pricing policy to incentivize CSBs to save energy and the superior performance of our algorithms in energy efficiency and resource utilization over the previous algorithms.

Previous resource provisioning strategies in cloud datacenters allocate physical resources to virtual machines (VMs) based on the predicted resource utilization pattern of VMs. The pattern for VMs of a job is usually derived from historical utilizations of multiple VMs of the job. We observed that these utilization curves are usually misaligned in time, which would lead to resource over-prediction and hence over-provisioning. Since this resource utilization misalignment problem has not been revealed and studied before, in this paper, we study the VM resource utilization from public datacenter traces to verify the existence of the utilization misalignments. Then, to reduce resource over-provisioning, we propose three VM resource utilization pattern refinement algorithms to improve the original generated pattern by lowering the cap of the pattern, reducing cap provision duration and varying the minimum value of the pattern. These algorithms can be used in any resource provisioning strategy that considers predicted resource utilizations of VMs of a job. We then adopt these refinement algorithms in an initial VM allocation mechanism and test them in trace-driven experiments and real-world cluster experiments. The experimental results show that each improved mechanism can increase resource efficiency up to 74%, and reduce the number of PMs needed to satisfy tenant requests up to 47% while conforming the SLO requirement.

To provide robust infrastructure as a service, clouds currently perform load balancing by migrating virtual machines (VMs) from heavily loaded physical machines (PMs) to lightly loaded PMs. Previous reactive load balancing algorithms migrate VMs upon the occurrence of load imbalance, while previous proactive load balancing algorithms predict PM overload to conduct VM migration. However, both methods cannot maintain long-term load balance and produce high overhead and delay due to migration VM selection and destination PM selection. To overcome these problems, in this paper, we propose a proactive Markov Decision Process (MDP)-based load balancing algorithm. We handle the challenges of allying MDP in virtual resource management in cloud datacenters, which allows a PM to proactively find an optimal action to transit to a lightly loaded state that will maintain for a longer period of time. We also apply the MDP to determine destination PMs to achieve long-term PM load balance state. Our algorithm reduces the numbers of service level agreement (SLA) violations by long-term load balance maintenance, and also reduces the load balancing overhead (e.g., CPU time and energy) and delay by quickly identifying VMs and destination PMs to migrate. We further propose enhancement methods for higher performance. First, we propose a cloud profit oriented reward system in the MDP model so that when the MDP tries to maximize the rewards for load balance, it concurrently improves the actual profit of the datacenter. Second, we propose a new MDP model, which considers the actions for both migrating a VM out of a PM and migrating a VM into a PM, in order to reduce the overhead and improve the effectiveness of load balancing. Our trace-driven experiments show that our algorithm outperforms both previous reactive and proactive load balancing algorithms in terms of SLA violation, load balancing efficiency, and long-term load balance maintenance. Our experimental results also show the effectiveness of our proposed enhancement methods.

Demand-prediction based resource provisioning schemes help assure service level objectives (SLO) in cloud systems. We notice that if a provisioning scheme does not exclude bursts from historical resource demands in normal demand prediction or always uses a large padding to correct under-prediction, it will lead to resource over-provisioning and low resource utilization. To improve the previous schemes, in this paper, we present a Resource-efficient Predictive Resource Provisioning system in clouds (RPRP) that excludes bursts in demand prediction and has algorithms to specifically handle bursts to avoid resource over-provisioning. Rather than setting padding to a possibly high value, RPRP has a load-dependent padding algorithm that adaptively determines padding based on predicted demands. To handle bursts, RPRP embodies a responsive padding algorithm that adaptively adjusts padding to recover from both under-provisioning and over-provisioning. We implemented RPRP on top of Xen and conducted both trace-driven simulation and real-world testbed experiments. The experimental results show that RPRP achieves higher resource utilization, more accurate demand predictions, and fewer SLO violations than previous schemes.

The shared nature of cloud network infrastructures causes unpredictable network performance, which may degrade the performance of these applications. Recently, several works propose to explicitly reserve the network bandwidth in the cloud with virtual network abstraction models, which pre-specify the network bandwidth between virtual machines (VMs) for a tenant job. However, the pre-specification fails to exploit the elastic feature of the bandwidth resource (i.e., more reserved bandwidth within no-elongation threshold bandwidth leads to shorter job execution time and vice versa) in job scheduling. It is difficult for ordinary tenants (without specialized network knowledge) to estimate the exact needed bandwidth. In this paper, we propose a new cloud job scheduler, in which each tenant only needs to specify job deadline and each job's reserved bandwidth is elastically determined by leveraging the elastic feature to maximize the total job rewards, which represent the worth of successful completion by deadlines. Finally, the scheduler tries to reduce the execution time of each job. It also jointly considers the computational capacity of VMs and reserved VM bandwidth in job scheduling. Using trace-driven and real cluster experiments, we show the efficiency and effectiveness of our job scheduler in comparison with other scheduling strategies.

In cloud systems, achieving high resource utilization and low Service Level Objective (SLO) violation rate are important to the cloud provider for high profit. For this purpose, recently, some methods have been proposed to predict allocated but unused resources and reallocate them to long-running service jobs. However, the accuracy of their prediction method relies on the existence of patterns in jobs' resource utilization. Therefore, these methods cannot be used for short-lived jobs, which usually do not have certain patterns but exhibit frequent fluctuations in resource requirements. Also, these methods may result in resource fragmentation and lead to low resource utilization because they neglect job resource intensity in multi-resource allocation and may allocate much more resources to jobs. To handle this problem, we propose a Cooperative Opportunistic Resource Provisioning scheme (CORP) for short-lived jobs. CORP uses the deep learning method to predict the amount of temporarily-unused resource of each short-lived job. It also predicts the fluctuations of the amount of unused resource using Hidden Markov Model, and adjusts the predicted amount for the peak and valley of unused resource, and dynamically allocates the corrected amount of resource to jobs. Further, CORP uses a job packing strategy by leveraging complementary jobs' requirements on different resource types and allocates such jobs to the same VM to fully utilize unused resources, which increases resource utilization. Extensive experimental results based on a real cluster and Amazon EC2 show that CORP achieves high resource utilization and low SLO violation rate compared to previous resource provisioning schemes.

In cloud datacenters, multiple Virtual Machines (VMs) are co-located in a Physical Machine (PM) to serve different applications. Prior VM consolidation methods for cloud datacenters schedule VMs mainly based on resource (CPU and memory) constraints in PMs but neglect serious shared Last Level cache contention between VMs. This may cause severe VM performance degradation due to cache thrashing and starvation for VMs. Current cache contention aware VM consolidation strategies either estimate cache contention by coarse VM classification for each individual VM without considering co-location and (or) require the aid of hardware to monitor the online miss rate of each VM. Therefore, these strategies are insufficiently accurate and (or) difficult to adopt for VM consolidation in clouds. In this paper, we formalize the problem of cache contention aware VM placement and migration in cloud datacenters using integer linear programming. We then propose a cache contention aware VM placement and migration algorithm (CacheVM). It estimates the total cache contention degree of co-locating a given VM with a group of VMs in a PM based on the cache stack distance profiles of the VMs. Then, it places the VM to the PM with the minimum cache contention degree and chooses the VM from a PM that generates the maximum cache contention degree to migrate out. We implemented CacheVM and its comparison methods on a supercomputing cluster. Trace-driven simulation and real-testbed experiments show that CacheVM outperforms other methods in terms of the number of cache misses, execution time and throughput.

Functioning as an intermediary between cloud tenants and providers, cloud service brokerages (CSBs) bring about great benefits to the cloud market. To maximize its own profit, a CSB is faced with a challenge: how to reserve servers and distribute tenant demands to the reserved servers such that the total reservation cost is minimized while the reserved servers can satisfy the tenant service level agreement (SLA)? Demand prediction and demand allocation are two steps to solve this problem. However, previous demand prediction methods cannot accurately predict tenant demands since they cannot accurately estimate prediction errors and also assume the existence of seasonal periods of demands. Previous demand allocation methods only aim to minimize the number of reserved servers rather than the server reservation cost, which is more challenging. To solve this challenge, we propose a Probabilistic Demand Allocation system (PDA). It predicts demands and more accurate prediction errors without the assumption of the existence of seasonal periods. It then formulates a nonlinear programming problem and has a decentralized method to find the problem solution. In addition to overcoming the shortcomings in previous methods, PDA is novel in that rather than separately conducting the prediction and demand allocation, it considers prediction errors in demand allocation in order to allocate demands with offsetting prediction errors (e.g., -1 and +1) to the same server, which helps find the problem solution. Both simulation and real-world experimental results demonstrate the superior performance of our system in reducing servers' reservation cost.

Functioning as an intermediary between tenants and cloud providers, cloud service brokerages (CSBs) can bring about great benefits to the cloud market. CSBs buy the cloud resources, i.e., servers, with lower prices from cloud providers and sell the resources to the tenants with higher prices. To maximize its own profit, a CSB may distribute tenants' requests to the clouds that waste energy resources. However, as energy costs of cloud computing have been increasing rapidly, there is a need for cloud providers to optimize energy efficiency while maintain high service level performance to tenants, not only for their own benefit but also for social welfares (e.g., protecting environment). Thus, for green cloud companies, two questions have arisen: 1) under what pricing policies from the cloud providers to the CSB, a profit-driven CSB is willing to minimize the total cloud energy cost while satisfy tenant demands and 2) how should a CSB distribute tenants' demands to achieve this objective? To address question 1), we find a pricing policy for cloud providers such that maximizing CSB's profit is equivalent to minimizing cloud providers' energy cost. To address question 2), we first devise a greedy solution, and then propose an approximation algorithm with a constant approximation ratio. Both simulation and real-world Amazon EC2 experimental results demonstrate the effectiveness of our pricing policy to incentivize CSBs to save energy for cloud providers and the superior performance of our algorithms in energy efficiency and resource utilizations in comparison with the previous algorithms.

As video streaming applications are deployed on the cloud, cloud providers are charged by ISPs for inter-data enter transfers under the dominant percentile-based charging models. In order to minimize the payment costs, existing works aim to keep the traffic on each link under the charging volume (i.e., 95th percentile traffic volume from the beginning of a charging period up to current time). However, these methods cannot fully utilize each link's available bandwidth capacity, and may increase the charging volumes. To further reduce the bandwidth payment cost by fully utilizing link bandwidth, we propose an economical and deadline-driven video flow scheduling system, called EcoFlow. Considering different video flows have different transmission deadlines, EcoFlow transmits videos in the order of their deadline tightness and postpones the deliveries of later-deadline videos to later time slots so that the charging volume at current time interval will not increase. The flows that are expected to miss their deadlines are divided into sub flows to be rerouted to other underutilized links in order to meet their deadlines without increasing charging volumes. Experimental results on Planet Lab and EC2 show that compared to existing methods, EcoFlow achieves the least bandwidth costs for cloud providers.

Virtualization is a key technology for cloud data centers to implement infrastructure as a service (IaaS) and to provide flexible and cost-effective resource sharing. It introduces an additional layer of abstraction that produces resource utilization overhead. Disregarding this overhead may cause serious reduction of the monitoring accuracy of the cloud providers and may cause degradation of the VM performance. However, there is no previous work that comprehensively investigates the virtualization overhead. In this paper, we comprehensively measure and study the relationship between the resource utilizations of virtual machines (VMs) and the resource utilizations of the device driver domain, hypervisor and the physical machine (PM) with diverse workloads and scenarios in the Xen virtualization environment. We examine data from the real-world virtualized deployment to characterize VM workloads and assess their impact on the resource utilizations in the system. We show that the impact of virtualization overhead depends on the workloads, and that virtualization overhead is an important factor to consider in cloud resource provisioning. Based on the measurements, we build a regression model to estimate the resource utilization overhead of the PM resulting from providing virtualized resource to the VMs and from managing multiple VMs. Finally, our trace-driven real-world experimental results show the high accuracy of our model in predicting PM resource consumptions in the cloud datacenter, and the importance of considering the virtualization overhead in cloud resource provisioning.

Cloud providers are charged by ISPs for inter-datacenter transfers under the dominant percentile-based charging models. In order to minimize the payment costs, existing works aim to keep the traffic on each link under the charging volume. However, these methods cannot fully utilize each link's available bandwidth capacity, and may increase the charging volumes. To further reduce the bandwidth payment cost by fully utilizing link bandwidth, we propose an economical and deadline-driven video flow scheduling system, called EcoFlow. Considering different video flows have different transmission deadlines, EcoFlow transmits videos in the order of their deadline tightness and postpones the deliveries of later-deadline videos to later time slots so that the charging volume at current time interval will not increase. The flows that are expected to miss their deadlines are divided into subflows to be rerouted to other under-utilized links in order to meet their deadlines without increasing charging volumes. We also design the implementation of EcoFlow in a distributed manner. Experimental results on EC2 show that compared to existing methods, EcoFlow achieves the least bandwidth costs for cloud providers.

To provide robust infrastructure as a service (IaaS), clouds currently perform load balancing by migrating virtual machines (VMs) from heavily loaded physical machines (PMs) to lightly loaded PMs. Previous reactive load balancing algorithms migrate VMs upon the occurrence of load imbalance, while previous proactive load balancing algorithms predict PM overload to conduct VM migration. However, both methods cannot maintain long-term load balance and produce high overhead and delay due to migration VM selection and destination PM selection. To overcome these problems, in this paper, we propose a proactive Markov Decision Process (MDP)-based load balancing algorithm. We handle the challenges of allying MDP in virtual resource management in cloud datacenters, which allows a PM to proactively find an optimal action to transit to a lightly loaded state that will maintain for a longer period of time. We also apply the MDP to determine destination PMs to achieve long-term PM load balance state. Our algorithm reduces the numbers of Service Level Agreement (SLA) violations by long-term load balance maintenance, and also reduces the load balancing overhead (e.g., CPU time, energy) and delay by quickly identifying VMs and destination PMs to migrate. Our trace-driven experiments show that our algorithm outperforms both previous reactive and proactive load balancing algorithms in terms of SLA violation, load balancing efficiency and long-term load balance maintenance.

In cloud datacenters, effective resource provisioning is needed to maximize energy efficiency and utilization of cloud resources while guaranteeing the Service Level Agreement (SLA) for tenants. Previous resource provisioning strategies either allocate physical resources to virtual machines (VMs) based on static VM resource demands or dynamically handle the variations in VM resource requirements through live VM migrations. However, the former fail to maximize energy efficiency and resource utilization while the latter produce high migration overhead. To handle these problems, we propose an initial VM allocation mechanism that consolidates complementary VMs with spatial/temporal-awareness. Complementary VMs are the VMs whose total demand of each resource dimension (in the spatial space) nearly reaches their host's capacity during VM lifetime period (in the temporal space). Based on our observation of the existence of VM resource utilization patterns, the mechanism predicts the lifetime resource utilization patterns of short-term VMs or periodical resource utilization patterns of long-term VMs. Based on the predicted patterns, it coordinates the requirements of different resources and consolidates complementary VMs in the same physical machine (PM). This mechanism reduces the number of PMs needed to provide VM service hence increases energy efficiency and resource utilization and also reduces the number of VM migrations and SLA violations. Simulation based on two real traces and real-world testbed experiments show that our initial VM allocation mechanism significantly reduces the number of PMs used, SLA violations and VM migrations of the previous resource provisioning strategies.

To provide robust infrastructure as a service (IaaS), clouds currently perform load balancing by migrating virtual machines (VMs) from heavily loaded physical machines (PMs) to lightly loaded PMs. The unique features of clouds pose formidable challenges to achieving effective and efficient load balancing. First, VMs in clouds use different resources (e.g., CPU, bandwidth, memory) to serve a variety of services (e.g., high performance computing, web services, file services), resulting in different overutilized resources in different PMs. Also, the overutilized resources in a PM may vary over time due to the time-varying heterogenous service requests. Second, there is intensive network communication between VMs. However, previous load balancing methods statically assign equal or predefined weights to different resources, which leads to degraded performance in terms of speed and cost to achieve load balance. Also, they do not strive to minimize the VM communications between PMs. We propose a Resource Intensity Aware Load balancing method (RIAL). For each PM, RIAL dynamically assigns different weights to different resources according to their usage intensity in the PM, which significantly reduces the time and cost to achieve load balance and avoids future load imbalance. It also tries to keep frequently communicating VMs in the same PM to reduce bandwidth cost, and migrate VMs to PMs with minimum VM performance degradation. Our extensive trace-driven simulation results and real-world experimental results show the superior performance of RIAL compared to other load balancing methods.