A Survey and Taxonomy of Resource Optimisation for Executing Bag-of-Task Applications on Public Clouds
---
paper_title: Handling Uncertainty: Pareto-Efficient BoT Scheduling on Hybrid Clouds

paper_content:

Coping with uncertainty is a challenging and complex problem particularly in hybrid cloud environments-private cloud plus public cloud. Conflicting goals of minimizing the cost and performance, unknown prior knowledge about task running times, and a lack of estimation tools are just a few of the challenges that resource management systems in those environments encounter. The aim in this paper is to find Pareto-optimal schedules for large-scale Bag-of-Tasks (BoT) applications that meet user defined constraints, such as deadline or budget or some tradeoff between them. BoT applications are common in science and engineering and consist of many independent tasks. To achieve the user's chosen Pareto-optimal schedule, we develop a dynamic resource allocation process for hybrid clouds. We also present a hybrid approach to estimating task running times that incorporates several estimators with a feedback control system to cope with the inherent uncertainty in such estimation. Through extensive experiments on a test bed hybrid cloud, using Amazon EC2 as a public cloud, we show that the proposed approach can achieve near optimality with little overhead, and consistently achieves a solution within 2% of the user's chosen Pareto-optimal schedule. Further, we demonstrate that our approach performs better than an extended List scheduling approach by reducing both the total cost and time needed to run the application by almost 20% and 5% on average, respectively.
---
paper_title: Cooperative Scheduling of Bag-of-Tasks Workflows on Hybrid Clouds

paper_content:

We address the problem of scheduling a class of large-scale applications inspired from real-world on hybrid Clouds, characterized by a large number of homogeneous and concurrent tasks that are the main sources of bottlenecks but open great potential for optimization. We formulate the scheduling problem as a new sequential cooperative game and propose a communication- and storage-aware multi-objective algorithm that optimizes two user objectives (execution time and economic cost) while fulfilling two constraints (network bandwidth and storage requirements). We present comprehensive experiments using both simulation and real-world applications that demonstrate the efficiency and effectiveness of our approach in terms of algorithm complexity, make span, cost, system-level efficiency, fairness, and other aspects compared with other related algorithms.
---
paper_title: Investigating Business-Driven Cloudburst Schedulers for E-Science Bag-of-Tasks Applications

paper_content:

The new ways of doing science, rooted on the unprecedented processing, communication and storage infrastructures that became available to scientists, are collectively called e-Science. Many research labs now need non-trivial computational power to run e-Science applications. Grid and voluntary computing are well-established solutions that cater to this need, but are not accessible for all labs and institutions. Besides, there is an uncertainty about the future amount of resources that will be available in such infrastructures, which prevents the researchers from planning their activities to guarantee that deadlines will be met. With the emergence of the cloud computing paradigm come new opportunities. One possibility is to run e-Science activities at resources acquired on-demand from cloud providers. However, although very low, there is a cost associated with the usage of cloud resources. Besides that, the amount of resources that can be simultaneously acquired is, in practice, limited. Another possibility is the not new idea of composing hybrid infrastructures in which the huge amount of computational resources shared by the grid infrastructures are used whenever possible and extra capacity is acquired from cloud computing providers. We here investigate how to schedule e-Science activities in such hybrid infrastructures so that deadlines are met and costs are reduced.
---
paper_title: Monetary Cost-Aware Checkpointing and Migration on Amazon Cloud Spot Instances

paper_content:

Recently introduced spot instances in the Amazon Elastic Compute Cloud (EC2) offer low resource costs in exchange for reduced reliability; these instances can be revoked abruptly due to price and demand fluctuations. Mechanisms and tools that deal with the cost-reliability tradeoffs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. We study how mechanisms, namely, checkpointing and migration, can be used to minimize the cost and volatility of resource provisioning. Based on the real price history of EC2 spot instances, we compare several adaptive checkpointing schemes in terms of monetary costs and improvement of job completion times. We evaluate schemes that apply predictive methods for spot prices. Furthermore, we also study how work migration can improve task completion in the midst of failures while maintaining low monetary costs. Trace-based simulations show that our schemes can reduce significantly both monetary costs and task completion times of computation on spot instance.
---
paper_title: A Dynamic Hybrid Resource Provisioning Approach for Running Large-Scale Computational Applications on Cloud Spot and On-Demand Instances

paper_content:

Testing and executing large-scale computational applications in public clouds is becoming prevalent due to cost saving, elasticity, and scalability. However, how to increase the reliability and reduce the cost to run large-scale applications in public clouds is still a big challenge. In this paper, we analyzed the pricing schemes of Amazon Elastic Compute Cloud (EC2) and found the disturbance effect that the price of the spot instances can be heavily affected due to the large number of spot instances required. We proposed a dynamic approach which schedules and runs large-scale computational applications on a dynamic pool of cloud computational instances. We use hybrid instances, including both on-demand instances for high priority tasks and backup, and spot instances for normal computational tasks so as to further reduce the cost without significantly increasing the completion time. Our proposed method takes the dynamic pricing of cloud instances into consideration, and it reduces the cost and tolerates the failures for running large-scale applications in public clouds. We conducted experimental tests and an agent based Scalable complex System modeling for Sustainable city (S3) application is used to evaluate the scalability, reliability and cost saving. The results show that our proposed method is robust and highly flexible for researchers and users to further reduce cost in real practice.
---
paper_title: On-demand, Spot, or Both: Dynamic Resource Allocation for Executing Batch Jobs in the Cloud

paper_content:

Cloud computing provides an attractive computing paradigm in which computational resources are rented on-demand to users with zero capital and maintenance costs. Cloud providers offer different pricing options to meet computing requirements of a wide variety of applications. An attractive option for batch computing is spot-instances, which allows users to place bids for spare computing instances and rent them at a (often) substantially lower price compared to the fixed on-demand price. However, this raises three main challenges for users: how many instances to rent at any time? what type (on-demand, spot, or both)? and what bid value to use for spot instances? In particular, renting on-demand risks high costs while renting spot instances risks job interruption and delayed completion when the spot market price exceeds the bid. This paper introduces an online learning algorithm for resource allocation to address this fundamental tradeoff between computation cost and performance. Our algorithm dynamically adapts resource allocation by learning from its performance on prior job executions while incorporating history of spot prices and workload characteristics. We provide theoretical bounds on its performance and prove that the average regret of our approach (compared to the best policy in hindsight) vanishes to zero with time. Evaluation on traces from a large datacenter cluster shows that our algorithm outperforms greedy allocation heuristics and quickly converges to a small set of best performing policies.
---
paper_title: Towards Optimal Bidding Strategy for Amazon EC2 Cloud Spot Instance

paper_content:

With the recent introduction of Spot Instances in the Amazon Elastic Compute Cloud (EC2), users can bid for resources and thus control the balance of reliability versus monetary costs. Mechanisms and tools that deal with the cost-reliability trade-offs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. In this paper, we propose a set of bidding strategies to minimize the cost and volatility of resource provisioning. Essentially, to derive an optimal bidding strategy, we formulate this problem as a Constrained Markov Decision Process (CMDP). Based on this model, we are able to obtain an optimal randomized bidding strategy through linear programming. Using real Instance Price traces and workload models, we compare several adaptive check-pointing schemes in terms of monetary costs and job completion time. We evaluate our model and demonstrate how users should bid optimally on Spot Instances to reach different objectives with desired levels of confidence.
---
paper_title: Scheduling jobs in the cloud using on-demand and reserved instances

paper_content:

Deploying applications in leased cloud infrastructure is increasingly considered by a variety of business and service integrators. However, the challenge of selecting the leasing strategy -- larger or faster instances? on-demand or reserved instances? etc.-- and to configure the leasing strategy with appropriate scheduling policies is still daunting for the (potential) cloud user. In this work, we investigate leasing strategies and their policies from a broker's perspective. We propose, CoH, a family of Cloud-based, online, Hybrid scheduling policies that minimizes rental cost by making use of both on-demand and reserved instances. We formulate the resource provisioning and job allocation policies as Integer Programming problems. As the policies need to be executed online, we limit the time to explore the optimal solution of the integer program, and compare the obtained solution with various heuristics-based policies; then automatically pick the best one. We show, via simulation and using multiple real-world traces, that the hybrid leasing policy can obtain significantly lower cost than typical heuristics-based policies.
---
paper_title: Cutting Your Cloud Computing Cost for Deadline-Constrained Batch Jobs

paper_content:

Many web service providers use commercial cloud computing infrastructures like Amazon for flexible and reliable service deployment. For these web service providers, the cost of cloud computing usage becomes a big part of their IT department cost. Facing the diverse pricing models including on-demand, reserved, and spot instance, it is difficult for web service providers to optimize their cost. This paper introduces a new cloud brokerage service to help web service providers to minimize their cloud computing cost for deadline-constrained batch jobs, which have been a significant workload in web services. Our cloud brokerage service associates each batch job with deadline, and always tries to use cheaper reserved instances for computation to maintain a minimum cost. We achieve this with the following two steps: (1) given a set of jobs' specifications, determine the scheduling of jobs, (2) given the scheduling and pricing options, find an optimal instance renting strategy. We prove that both problems in two steps are computation intractable, and propose approximation algorithms for them. Trace-based evaluation shows that our cloud brokerage service can reduce up to 57% of the cloud computing cost.
---
paper_title: Executing Bag of Distributed Tasks on the Cloud: Investigating the Trade-Offs between Performance and Cost

paper_content:

Bag of Distributed Tasks (BoDT) can benefit from decentralised execution on the Cloud. However, there is a trade-off between the performance that can be achieved by employing a large number of Cloud VMs for the tasks and the monetary constraints that are often placed by a user. The research reported in this paper is motivated towards investigating this trade-off so that an optimal plan for deploying BoDT applications on the cloud can be generated. A heuristic algorithm, which considers the user's preference of performance and cost is proposed and implemented. The feasibility of the algorithm is demonstrated by generating execution plans for a sample application. The key result is that the algorithm generates optimal execution plans for the application over 91% of the time.
---
paper_title: Autonomic scheduling of deadline-constrained bag of tasks in hybrid clouds

paper_content:

The use of Hybrid Cloud technologies in large scale applications allows organizations to complement on-premises infrastructure with hired infrastructure from Public Cloud providers. The efficient use of the hired resources to provide the expected quality of service while dealing with the heterogeneity and uncertainty of Public Clouds is the main difficulty. A scheduler able to deal with deadline-constrained bag of tasks in Hybrid Clouds is presented in this work. The main contribution of this scheduler is that task runtime estimations are not necessary as inputs. The scheduler includes a runtime estimator based on sampled data to generate the estimation autonomously. A discrete event simulator was developed in order to validate the proposed scheduler in different scenarios. Results show that an estimator based on the Chebyshev's inequality obtains very good results in terms of deadlines met and cost.
---
paper_title: A SLA driven VM auto-scaling method in hybrid cloud environment

paper_content:

The advent of Science Clouds enables scientists to facilitate large-scale scientific computational experiments over cloud environment besides specialized supercomputers in diverse science domains. Cloud computing service elicits efficiency on on-demand resource usage and timely execution at any given time depending on experimental requirements. Hybrid clouds, composing of private and public clouds, even extend research opportunities on resource selection for further complicated experiments but increase the needs of dynamic resource management to maximize its utilization. At existing public cloud providers for commercial use, rule-based and schedule-based mechanisms have been tried for automatic resource allocation to provide resources for processing dynamic workload of modern applications. However, most of the auto-scaling methods just simply support performance metric such as CPU utilization but rarely are aware of Service Level Agreements (SLA) including execution deadline or cost. In this paper, we propose an auto-scaling method that automatically allocates resources depending on variable resource requirements in hybrid clouds satisfying a user's requirements on SLA. We present experimental results which show that the proposed auto-scaling can minimize SLA violations and acceptable cost if needed.
---
paper_title: Managing Deadline-constrained Bag-of-Tasks Jobs on Hybrid Clouds

paper_content:

Outsourcing jobs to a public cloud is a cost-effective way to address the problem of satisfying the peak resource demand when the local cloud has insufficient resources. In this paper, we studied the management of deadline-constrained bag-of-tasks jobs on hybrid clouds. We presented a binary nonlinear programming (BNP) problem to model the hybrid cloud management which minimizes rent cost from the public cloud while completes the jobs within their respective deadlines. To solve this BNP problem in polynomial time, we proposed a heuristic algorithm. The main idea is assigning the task closest to its deadline to current core until the core cannot finish any task within its deadline. When there is no available core, the algorithm adds an available physical machine (PM) with most capacity or rents a new virtual machine (VM) with highest cost-performance ratio. As there may be a workload imbalance between/among cores on a PM/VM after task assigning, we propose a task reassigning algorithm to balance them. Extensive experimental results show that our heuristic algorithm saves 16.2%-76% rent cost and improves 47.3%-182.8% resource utilizations satisfying deadline constraints, compared with first fit decreasing algorithm, and that our task reassigning algorithm improves the makespan of tasks up to 47.6%.
---
paper_title: Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds

paper_content:

Cloud computing has found broad acceptance in both industry and research, with public cloud offerings now often used in conjunction with privately owned infrastructure. Technical aspects such as the impact of network latency, bandwidth constraints, data confidentiality and security, as well as economic aspects such as sunk costs and price uncertainty are key drivers towards the adoption of such a hybrid cloud model. The use of hybrid clouds introduces the need to determine which workloads are to be outsourced, and to what cloud provider. These decisions should minimize the cost of running a partition of the total workload on one or multiple public cloud providers while taking into account the application requirements such as deadline constraints and data requirements. The variety of cost factors, pricing models and cloud provider offerings to consider, further calls for an automated scheduling approach in hybrid clouds. In this work, we tackle this problem by proposing a set of algorithms to cost-efficiently schedule the deadline-constrained bag-of-tasks applications on both public cloud providers and private infrastructure. Our algorithms take into account both computational and data transfer costs as well as network bandwidth constraints. We evaluate their performance in a realistic setting with respect to cost savings, deadlines met and computational efficiency, and investigate the impact of errors in runtime estimates on these performance metrics.
---
paper_title: Multi-Objective Game Theoretic Schedulingof Bag-of-Tasks Workflows on Hybrid Clouds

paper_content:

Scheduling multiple large-scale parallel workflow applications on heterogeneous computing systems like hybrid clouds is a fundamental NP-complete problem that is critical to meeting various types of QoS (Quality of Service) requirements. This paper addresses the scheduling problem of large-scale applications inspired from real-world, characterized by a huge number of homogeneous and concurrent bags-of-tasks that are the main sources of bottlenecks but open great potential for optimization. The scheduling problem is formulated as a new sequential cooperative game and propose a communication and storage-aware multi-objective algorithm that optimizes two user objectives (execution time and economic cost) while fulfilling two constraints (network bandwidth and storage requirements). We present comprehensive experiments using both simulation and real-world applications that demonstrate the efficiency and effectiveness of our approach in terms of algorithm complexity, makespan, cost, system-level efficiency, fairness, and other aspects compared with other related algorithms.
---
paper_title: Cost-Aware Elastic Cloud Provisioning for Scientific Workloads

paper_content:

Cloud computing provides an efficient model to host and scale scientific applications. While cloud-based approaches can reduce costs as users pay only for the resources used, it is often challenging to scale execution both efficiently and cost-effectively. We describe here a cost-aware elastic cloud provisioner designed to elastically provision cloud infrastructure to execute analyses cost-effectively. The provisioner considers real-time spot instance prices across availability zones, leverages application profiles to optimize instance type selection, over-provisions resources to alleviate bottlenecks caused by oversubscribed instance types, and is capable of reverting to on-demand instances when spot prices exceed thresholds. We evaluate the usage of our cost-aware provisioner using four production scientific gateways and show that it can produce cost savings of up to 97.2% when compared to naive provisioning approaches.
---
paper_title: Bag-of-Tasks Scheduling under Budget Constraints

paper_content:

Commercial cloud offerings, such as Amazon’s EC2, let users allocate compute resources on demand, charging based on reserved time intervals. While this gives great?exibility to elastic applications, users lack guidance for choosing between multiple offerings, in order to complete their computations within given budget constraints. In this work, we present BaTS, our budget-constrained scheduler. BaTS can schedule large bags of tasks onto multiple clouds with different CPU performance and cost, minimizing completion time while respecting an upper bound for the budget to be spent. BaTS requires no a-priori information about task completion times, and learns to estimate them at runtime. We evaluate BaTS by emulating different cloud environments on the DAS-3 multi-cluster system. Our results show that BaTS is able to schedule within a user-definedbudget (if such a schedule is possible at all.) At the expense of extra compute time, significant cost savings can be achieved when comparing to a cost-oblivious round-robin scheduler.
---
paper_title: Toward Optimal Resource Provisioning for Cloud MapReduce and Hybrid Cloud Applications

paper_content:

Given the variety of resources available in public clouds and locally (hybrid clouds), it can be very difficult to determine the best number and type of resources to allocate (and where) for a given activity. In order to solve this problem we first define the requested computation in terms of an Integer Linear Programming (ILP) problem and then use an efficient ILP solver to make a provisioning decision in a few milliseconds. Our approach is based on the two most important metrics for the user: cost and job execution time. Thus, based on the user's preferences we can favor solutions that optimize speed or cost or a certain combination of both (e.g. Cheapest solution that meets a certain deadline). We evaluate our approach with two classes of cloud applications: MapReduce applications, and Monte Carlo simulations. A significant advantage in our approach is that our solution has been proved optimal by the ILP solver, the set of the scheduling decisions based on our model are plotted on a time vs. Cost graph that forms a Pareto efficient frontier. This way, we can avoid the pitfalls of a naïve strategy that can lead to a great increase in cost (91%) or job running time (21%) compared to optimal.
---
paper_title: Self-Adaptive Learning PSO-Based Deadline Constrained Task Scheduling for Hybrid IaaS Cloud

paper_content:

Public clouds provide Infrastructure as a Service (IaaS) to users who do not own sufficient compute resources. IaaS achieves the economy of scale by multiplexing, and therefore faces the challenge of scheduling tasks to meet the peak demand while preserving Quality-of-Service (QoS). Previous studies proposed proactive machine purchasing or cloud federation to resolve this problem. However, the former is not economic and the latter for now is hardly feasible in practice. In this paper, we propose a resource allocation framework in which an IaaS provider can outsource its tasks to External Clouds (ECs) when its own resources are not sufficient to meet the demand. This architecture does not require any formal inter-cloud agreement that is necessary for the cloud federation. The key issue is how to allocate users' tasks to maximize the profit of IaaS provider while guaranteeing QoS. This problem is formulated as an integer programming (IP) model, and solved by a self-adaptive learning particle swarm optimization (SLPSO)-based scheduling approach. In SLPSO, four updating strategies are used to adaptively update the velocity of each particle to ensure its diversity and robustness. Experiments show that, SLPSO can improve a cloud provider's profit by 0.25%-11.56% compared with standard PSO; and by 2.37%-16.71% for problems of nontrivial size compared with CPLEX under reasonable computation time.
---
paper_title: Minimising the Execution of Unknown Bag-of-Task Jobs with Deadlines on the Cloud

paper_content:

Scheduling jobs with deadlines, each of which defines the latest time that a job must be completed, can be challenging on the cloud due to the incurred costs and unpredictable performance. This problem is further complicated when there is not enough information to effectively schedule a job such that its deadline is satisfied, and the cost is minimised. In this paper, we present an approach to schedule jobs, whose performance are unknown before execution, with deadlines on the cloud. By performing a sampling phase to collect the necessary information about those jobs, our approach is able to deliver the scheduling decision within 10% cost and 16% violation rate when compared to the ideal setting, which has complete knowledge about each of the jobs from the beginning. Finally, our proposed algorithm outperforms existing approaches, which use a fixed amount of resources by reducing the violation cost by at least two times.
---
paper_title: Stochastic Tail-Phase Optimization for Bag-of-Tasks Execution in Clouds

paper_content:

Elastic applications like bags of tasks benefit greatly from Infrastructure as a Service (IaaS) clouds that let users allocate compute resources on demand, charging based on reserved time intervals. Users, however, still need guidance for mapping their applications onto multiple IaaS offerings, both minimizing execution time and respecting budget limitations. For budget-controlled execution of bags of tasks, we built Bats, a scheduler that estimates possible budget and make spancombinations using a tiny task sample, and then executes a bag within the user's budget constraints. Previous work has shown the efficacy of this approach. There remains, however, the risk of outlier tasks causing the execution to exceed the predicted make span. In this work, we present a stochastic optimization of the tail phase for Bats' execution. The main idea is to use the otherwise idling machines up until the end of their (already paid-for) allocation time. Using the task completion time information acquired during the execution, BaTS decides which tasks to replicate onto idle machines in the tail phase, reducing the make span and improving the tolerance to outlier tasks. Our evaluation results show that this effect is robust w.r.t. the quality of runtime predictions and is the strongest with more expensive schedules in which many fast machines are available.
---
paper_title: Allocation of Virtual Machines in Cloud Data Centers—A Survey of Problem Models and Optimization Algorithms

paper_content:

Data centers in public, private, and hybrid cloud settings make it possible to provision virtual machines (VMs) with unprecedented flexibility. However, purchasing, operating, and maintaining the underlying physical resources incurs significant monetary costs and environmental impact. Therefore, cloud providers must optimize the use of physical resources by a careful allocation of VMs to hosts, continuously balancing between the conflicting requirements on performance and operational costs. In recent years, several algorithms have been proposed for this important optimization problem. Unfortunately, the proposed approaches are hardly comparable because of subtle differences in the used problem models. This article surveys the used problem formulations and optimization algorithms, highlighting their strengths and limitations, and pointing out areas that need further research.
---
paper_title: Monetary Cost-Aware Checkpointing and Migration on Amazon Cloud Spot Instances

paper_content:

Recently introduced spot instances in the Amazon Elastic Compute Cloud (EC2) offer low resource costs in exchange for reduced reliability; these instances can be revoked abruptly due to price and demand fluctuations. Mechanisms and tools that deal with the cost-reliability tradeoffs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. We study how mechanisms, namely, checkpointing and migration, can be used to minimize the cost and volatility of resource provisioning. Based on the real price history of EC2 spot instances, we compare several adaptive checkpointing schemes in terms of monetary costs and improvement of job completion times. We evaluate schemes that apply predictive methods for spot prices. Furthermore, we also study how work migration can improve task completion in the midst of failures while maintaining low monetary costs. Trace-based simulations show that our schemes can reduce significantly both monetary costs and task completion times of computation on spot instance.
---
paper_title: Budget Constrained Execution of Multiple Bag-of-Tasks Applications on the Cloud

paper_content:

Optimising the execution of Bag-of-Tasks (BoT) applications on the cloud is a hard problem due to the trade-offs between performance and monetary cost. The problem can be further complicated when multiple BoT applications need to be executed. In this paper, we propose and implement a heuristic algorithm that schedules tasks of multiple applications onto different cloud virtual machines in order to maximise performance while satisfying a given budget constraint. Current approaches are limited in task scheduling since they place a limit on the number of cloud resources that can be employed by the applications. However, in the proposed algorithm there are no such limits, and in comparison with other approaches, the algorithm on average achieves an improved performance of 10%. The experimental results also highlight that the algorithm yields consistent performance even with low budget constraints which cannot be achieved by competing approaches.
---
paper_title: Cloud auto-scaling with deadline and budget constraints

paper_content:

Clouds have become an attractive computing platform which offers on-demand computing power and storage capacity. Its dynamic scalability enables users to quickly scale up and scale down underlying infrastructure in response to business volume, performance desire and other dynamic behaviors. However, challenges arise when considering computing instance non-deterministic acquisition time, multiple VM instance types, unique cloud billing models and user budget constraints. Planning enough computing resources for user desired performance with less cost, which can also automatically adapt to workload changes, is not a trivial problem. In this paper, we present a cloud auto-scaling mechanism to automatically scale computing instances based on workload information and performance desire. Our mechanism schedules VM instance startup and shut-down activities. It enables cloud applications to finish submitted jobs within the deadline by controlling underlying instance numbers and reduces user cost by choosing appropriate instance types. We have implemented our mechanism in Windows Azure platform, and evaluated it using both simulations and a real scientific cloud application. Results show that our cloud auto-scaling mechanism can meet user specified performance goal with less cost.
---
paper_title: Bag-of-Tasks Scheduling under Budget Constraints

paper_content:

Commercial cloud offerings, such as Amazon’s EC2, let users allocate compute resources on demand, charging based on reserved time intervals. While this gives great?exibility to elastic applications, users lack guidance for choosing between multiple offerings, in order to complete their computations within given budget constraints. In this work, we present BaTS, our budget-constrained scheduler. BaTS can schedule large bags of tasks onto multiple clouds with different CPU performance and cost, minimizing completion time while respecting an upper bound for the budget to be spent. BaTS requires no a-priori information about task completion times, and learns to estimate them at runtime. We evaluate BaTS by emulating different cloud environments on the DAS-3 multi-cluster system. Our results show that BaTS is able to schedule within a user-definedbudget (if such a schedule is possible at all.) At the expense of extra compute time, significant cost savings can be achieved when comparing to a cost-oblivious round-robin scheduler.
---
paper_title: Handling Uncertainty: Pareto-Efficient BoT Scheduling on Hybrid Clouds

paper_content:

Coping with uncertainty is a challenging and complex problem particularly in hybrid cloud environments-private cloud plus public cloud. Conflicting goals of minimizing the cost and performance, unknown prior knowledge about task running times, and a lack of estimation tools are just a few of the challenges that resource management systems in those environments encounter. The aim in this paper is to find Pareto-optimal schedules for large-scale Bag-of-Tasks (BoT) applications that meet user defined constraints, such as deadline or budget or some tradeoff between them. BoT applications are common in science and engineering and consist of many independent tasks. To achieve the user's chosen Pareto-optimal schedule, we develop a dynamic resource allocation process for hybrid clouds. We also present a hybrid approach to estimating task running times that incorporates several estimators with a feedback control system to cope with the inherent uncertainty in such estimation. Through extensive experiments on a test bed hybrid cloud, using Amazon EC2 as a public cloud, we show that the proposed approach can achieve near optimality with little overhead, and consistently achieves a solution within 2% of the user's chosen Pareto-optimal schedule. Further, we demonstrate that our approach performs better than an extended List scheduling approach by reducing both the total cost and time needed to run the application by almost 20% and 5% on average, respectively.
---
paper_title: Cloud Benchmarking for Performance

paper_content:

How can applications be deployed on the cloud to achieve maximum performance? This question has become significant and challenging with the availability of a wide variety of Virtual Machines (VMs) with different performance capabilities in the cloud. The above question is addressed by proposing a six step benchmarking methodology in which a user provides a set of four weights that indicate how important each of the following groups: memory, processor, computation and storage are to the application that needs to be executed on the cloud. The weights along with cloud benchmarking data are used to generate a ranking of VMs that can maximise performance of the application. The rankings are validated through an empirical analysis using two case study applications, the first is a financial risk application and the second is a molecular dynamics simulation, which are both representative of workloads that can benefit from execution on the cloud. Both case studies validate the feasibility of the methodology and highlight that maximum performance can be achieved on the cloud by selecting the top ranked VMs produced by the methodology.
---
paper_title: Autonomic scheduling of deadline-constrained bag of tasks in hybrid clouds

paper_content:

The use of Hybrid Cloud technologies in large scale applications allows organizations to complement on-premises infrastructure with hired infrastructure from Public Cloud providers. The efficient use of the hired resources to provide the expected quality of service while dealing with the heterogeneity and uncertainty of Public Clouds is the main difficulty. A scheduler able to deal with deadline-constrained bag of tasks in Hybrid Clouds is presented in this work. The main contribution of this scheduler is that task runtime estimations are not necessary as inputs. The scheduler includes a runtime estimator based on sampled data to generate the estimation autonomously. A discrete event simulator was developed in order to validate the proposed scheduler in different scenarios. Results show that an estimator based on the Chebyshev's inequality obtains very good results in terms of deadlines met and cost.
---
paper_title: A Dynamic Hybrid Resource Provisioning Approach for Running Large-Scale Computational Applications on Cloud Spot and On-Demand Instances

paper_content:

Testing and executing large-scale computational applications in public clouds is becoming prevalent due to cost saving, elasticity, and scalability. However, how to increase the reliability and reduce the cost to run large-scale applications in public clouds is still a big challenge. In this paper, we analyzed the pricing schemes of Amazon Elastic Compute Cloud (EC2) and found the disturbance effect that the price of the spot instances can be heavily affected due to the large number of spot instances required. We proposed a dynamic approach which schedules and runs large-scale computational applications on a dynamic pool of cloud computational instances. We use hybrid instances, including both on-demand instances for high priority tasks and backup, and spot instances for normal computational tasks so as to further reduce the cost without significantly increasing the completion time. Our proposed method takes the dynamic pricing of cloud instances into consideration, and it reduces the cost and tolerates the failures for running large-scale applications in public clouds. We conducted experimental tests and an agent based Scalable complex System modeling for Sustainable city (S3) application is used to evaluate the scalability, reliability and cost saving. The results show that our proposed method is robust and highly flexible for researchers and users to further reduce cost in real practice.
---
paper_title: Toward Optimal Resource Provisioning for Cloud MapReduce and Hybrid Cloud Applications

paper_content:

Given the variety of resources available in public clouds and locally (hybrid clouds), it can be very difficult to determine the best number and type of resources to allocate (and where) for a given activity. In order to solve this problem we first define the requested computation in terms of an Integer Linear Programming (ILP) problem and then use an efficient ILP solver to make a provisioning decision in a few milliseconds. Our approach is based on the two most important metrics for the user: cost and job execution time. Thus, based on the user's preferences we can favor solutions that optimize speed or cost or a certain combination of both (e.g. Cheapest solution that meets a certain deadline). We evaluate our approach with two classes of cloud applications: MapReduce applications, and Monte Carlo simulations. A significant advantage in our approach is that our solution has been proved optimal by the ILP solver, the set of the scheduling decisions based on our model are plotted on a time vs. Cost graph that forms a Pareto efficient frontier. This way, we can avoid the pitfalls of a naïve strategy that can lead to a great increase in cost (91%) or job running time (21%) compared to optimal.
---
paper_title: Cost-Aware Elastic Cloud Provisioning for Scientific Workloads

paper_content:

Cloud computing provides an efficient model to host and scale scientific applications. While cloud-based approaches can reduce costs as users pay only for the resources used, it is often challenging to scale execution both efficiently and cost-effectively. We describe here a cost-aware elastic cloud provisioner designed to elastically provision cloud infrastructure to execute analyses cost-effectively. The provisioner considers real-time spot instance prices across availability zones, leverages application profiles to optimize instance type selection, over-provisions resources to alleviate bottlenecks caused by oversubscribed instance types, and is capable of reverting to on-demand instances when spot prices exceed thresholds. We evaluate the usage of our cost-aware provisioner using four production scientific gateways and show that it can produce cost savings of up to 97.2% when compared to naive provisioning approaches.
---
paper_title: Executing Bag of Distributed Tasks on the Cloud: Investigating the Trade-Offs between Performance and Cost

paper_content:

Bag of Distributed Tasks (BoDT) can benefit from decentralised execution on the Cloud. However, there is a trade-off between the performance that can be achieved by employing a large number of Cloud VMs for the tasks and the monetary constraints that are often placed by a user. The research reported in this paper is motivated towards investigating this trade-off so that an optimal plan for deploying BoDT applications on the cloud can be generated. A heuristic algorithm, which considers the user's preference of performance and cost is proposed and implemented. The feasibility of the algorithm is demonstrated by generating execution plans for a sample application. The key result is that the algorithm generates optimal execution plans for the application over 91% of the time.
---
paper_title: On-demand, Spot, or Both: Dynamic Resource Allocation for Executing Batch Jobs in the Cloud

paper_content:

Cloud computing provides an attractive computing paradigm in which computational resources are rented on-demand to users with zero capital and maintenance costs. Cloud providers offer different pricing options to meet computing requirements of a wide variety of applications. An attractive option for batch computing is spot-instances, which allows users to place bids for spare computing instances and rent them at a (often) substantially lower price compared to the fixed on-demand price. However, this raises three main challenges for users: how many instances to rent at any time? what type (on-demand, spot, or both)? and what bid value to use for spot instances? In particular, renting on-demand risks high costs while renting spot instances risks job interruption and delayed completion when the spot market price exceeds the bid. This paper introduces an online learning algorithm for resource allocation to address this fundamental tradeoff between computation cost and performance. Our algorithm dynamically adapts resource allocation by learning from its performance on prior job executions while incorporating history of spot prices and workload characteristics. We provide theoretical bounds on its performance and prove that the average regret of our approach (compared to the best policy in hindsight) vanishes to zero with time. Evaluation on traces from a large datacenter cluster shows that our algorithm outperforms greedy allocation heuristics and quickly converges to a small set of best performing policies.
---
paper_title: A SLA driven VM auto-scaling method in hybrid cloud environment

paper_content:

The advent of Science Clouds enables scientists to facilitate large-scale scientific computational experiments over cloud environment besides specialized supercomputers in diverse science domains. Cloud computing service elicits efficiency on on-demand resource usage and timely execution at any given time depending on experimental requirements. Hybrid clouds, composing of private and public clouds, even extend research opportunities on resource selection for further complicated experiments but increase the needs of dynamic resource management to maximize its utilization. At existing public cloud providers for commercial use, rule-based and schedule-based mechanisms have been tried for automatic resource allocation to provide resources for processing dynamic workload of modern applications. However, most of the auto-scaling methods just simply support performance metric such as CPU utilization but rarely are aware of Service Level Agreements (SLA) including execution deadline or cost. In this paper, we propose an auto-scaling method that automatically allocates resources depending on variable resource requirements in hybrid clouds satisfying a user's requirements on SLA. We present experimental results which show that the proposed auto-scaling can minimize SLA violations and acceptable cost if needed.
---
paper_title: Self-Adaptive Learning PSO-Based Deadline Constrained Task Scheduling for Hybrid IaaS Cloud

paper_content:

Public clouds provide Infrastructure as a Service (IaaS) to users who do not own sufficient compute resources. IaaS achieves the economy of scale by multiplexing, and therefore faces the challenge of scheduling tasks to meet the peak demand while preserving Quality-of-Service (QoS). Previous studies proposed proactive machine purchasing or cloud federation to resolve this problem. However, the former is not economic and the latter for now is hardly feasible in practice. In this paper, we propose a resource allocation framework in which an IaaS provider can outsource its tasks to External Clouds (ECs) when its own resources are not sufficient to meet the demand. This architecture does not require any formal inter-cloud agreement that is necessary for the cloud federation. The key issue is how to allocate users' tasks to maximize the profit of IaaS provider while guaranteeing QoS. This problem is formulated as an integer programming (IP) model, and solved by a self-adaptive learning particle swarm optimization (SLPSO)-based scheduling approach. In SLPSO, four updating strategies are used to adaptively update the velocity of each particle to ensure its diversity and robustness. Experiments show that, SLPSO can improve a cloud provider's profit by 0.25%-11.56% compared with standard PSO; and by 2.37%-16.71% for problems of nontrivial size compared with CPLEX under reasonable computation time.
---
paper_title: Scheduling jobs in the cloud using on-demand and reserved instances

paper_content:

Deploying applications in leased cloud infrastructure is increasingly considered by a variety of business and service integrators. However, the challenge of selecting the leasing strategy -- larger or faster instances? on-demand or reserved instances? etc.-- and to configure the leasing strategy with appropriate scheduling policies is still daunting for the (potential) cloud user. In this work, we investigate leasing strategies and their policies from a broker's perspective. We propose, CoH, a family of Cloud-based, online, Hybrid scheduling policies that minimizes rental cost by making use of both on-demand and reserved instances. We formulate the resource provisioning and job allocation policies as Integer Programming problems. As the policies need to be executed online, we limit the time to explore the optimal solution of the integer program, and compare the obtained solution with various heuristics-based policies; then automatically pick the best one. We show, via simulation and using multiple real-world traces, that the hybrid leasing policy can obtain significantly lower cost than typical heuristics-based policies.
---
paper_title: Minimising the Execution of Unknown Bag-of-Task Jobs with Deadlines on the Cloud

paper_content:

Scheduling jobs with deadlines, each of which defines the latest time that a job must be completed, can be challenging on the cloud due to the incurred costs and unpredictable performance. This problem is further complicated when there is not enough information to effectively schedule a job such that its deadline is satisfied, and the cost is minimised. In this paper, we present an approach to schedule jobs, whose performance are unknown before execution, with deadlines on the cloud. By performing a sampling phase to collect the necessary information about those jobs, our approach is able to deliver the scheduling decision within 10% cost and 16% violation rate when compared to the ideal setting, which has complete knowledge about each of the jobs from the beginning. Finally, our proposed algorithm outperforms existing approaches, which use a fixed amount of resources by reducing the violation cost by at least two times.
---
paper_title: Managing Deadline-constrained Bag-of-Tasks Jobs on Hybrid Clouds

paper_content:

Outsourcing jobs to a public cloud is a cost-effective way to address the problem of satisfying the peak resource demand when the local cloud has insufficient resources. In this paper, we studied the management of deadline-constrained bag-of-tasks jobs on hybrid clouds. We presented a binary nonlinear programming (BNP) problem to model the hybrid cloud management which minimizes rent cost from the public cloud while completes the jobs within their respective deadlines. To solve this BNP problem in polynomial time, we proposed a heuristic algorithm. The main idea is assigning the task closest to its deadline to current core until the core cannot finish any task within its deadline. When there is no available core, the algorithm adds an available physical machine (PM) with most capacity or rents a new virtual machine (VM) with highest cost-performance ratio. As there may be a workload imbalance between/among cores on a PM/VM after task assigning, we propose a task reassigning algorithm to balance them. Extensive experimental results show that our heuristic algorithm saves 16.2%-76% rent cost and improves 47.3%-182.8% resource utilizations satisfying deadline constraints, compared with first fit decreasing algorithm, and that our task reassigning algorithm improves the makespan of tasks up to 47.6%.
---
paper_title: Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds

paper_content:

Cloud computing has found broad acceptance in both industry and research, with public cloud offerings now often used in conjunction with privately owned infrastructure. Technical aspects such as the impact of network latency, bandwidth constraints, data confidentiality and security, as well as economic aspects such as sunk costs and price uncertainty are key drivers towards the adoption of such a hybrid cloud model. The use of hybrid clouds introduces the need to determine which workloads are to be outsourced, and to what cloud provider. These decisions should minimize the cost of running a partition of the total workload on one or multiple public cloud providers while taking into account the application requirements such as deadline constraints and data requirements. The variety of cost factors, pricing models and cloud provider offerings to consider, further calls for an automated scheduling approach in hybrid clouds. In this work, we tackle this problem by proposing a set of algorithms to cost-efficiently schedule the deadline-constrained bag-of-tasks applications on both public cloud providers and private infrastructure. Our algorithms take into account both computational and data transfer costs as well as network bandwidth constraints. We evaluate their performance in a realistic setting with respect to cost savings, deadlines met and computational efficiency, and investigate the impact of errors in runtime estimates on these performance metrics.
---
paper_title: Multi-Objective Game Theoretic Schedulingof Bag-of-Tasks Workflows on Hybrid Clouds

paper_content:

Scheduling multiple large-scale parallel workflow applications on heterogeneous computing systems like hybrid clouds is a fundamental NP-complete problem that is critical to meeting various types of QoS (Quality of Service) requirements. This paper addresses the scheduling problem of large-scale applications inspired from real-world, characterized by a huge number of homogeneous and concurrent bags-of-tasks that are the main sources of bottlenecks but open great potential for optimization. The scheduling problem is formulated as a new sequential cooperative game and propose a communication and storage-aware multi-objective algorithm that optimizes two user objectives (execution time and economic cost) while fulfilling two constraints (network bandwidth and storage requirements). We present comprehensive experiments using both simulation and real-world applications that demonstrate the efficiency and effectiveness of our approach in terms of algorithm complexity, makespan, cost, system-level efficiency, fairness, and other aspects compared with other related algorithms.
---
paper_title: Towards Optimal Bidding Strategy for Amazon EC2 Cloud Spot Instance

paper_content:

With the recent introduction of Spot Instances in the Amazon Elastic Compute Cloud (EC2), users can bid for resources and thus control the balance of reliability versus monetary costs. Mechanisms and tools that deal with the cost-reliability trade-offs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. In this paper, we propose a set of bidding strategies to minimize the cost and volatility of resource provisioning. Essentially, to derive an optimal bidding strategy, we formulate this problem as a Constrained Markov Decision Process (CMDP). Based on this model, we are able to obtain an optimal randomized bidding strategy through linear programming. Using real Instance Price traces and workload models, we compare several adaptive check-pointing schemes in terms of monetary costs and job completion time. We evaluate our model and demonstrate how users should bid optimally on Spot Instances to reach different objectives with desired levels of confidence.
---
paper_title: Cutting Your Cloud Computing Cost for Deadline-Constrained Batch Jobs

paper_content:

Many web service providers use commercial cloud computing infrastructures like Amazon for flexible and reliable service deployment. For these web service providers, the cost of cloud computing usage becomes a big part of their IT department cost. Facing the diverse pricing models including on-demand, reserved, and spot instance, it is difficult for web service providers to optimize their cost. This paper introduces a new cloud brokerage service to help web service providers to minimize their cloud computing cost for deadline-constrained batch jobs, which have been a significant workload in web services. Our cloud brokerage service associates each batch job with deadline, and always tries to use cheaper reserved instances for computation to maintain a minimum cost. We achieve this with the following two steps: (1) given a set of jobs' specifications, determine the scheduling of jobs, (2) given the scheduling and pricing options, find an optimal instance renting strategy. We prove that both problems in two steps are computation intractable, and propose approximation algorithms for them. Trace-based evaluation shows that our cloud brokerage service can reduce up to 57% of the cloud computing cost.
---
paper_title: Stochastic Tail-Phase Optimization for Bag-of-Tasks Execution in Clouds

paper_content:

Elastic applications like bags of tasks benefit greatly from Infrastructure as a Service (IaaS) clouds that let users allocate compute resources on demand, charging based on reserved time intervals. Users, however, still need guidance for mapping their applications onto multiple IaaS offerings, both minimizing execution time and respecting budget limitations. For budget-controlled execution of bags of tasks, we built Bats, a scheduler that estimates possible budget and make spancombinations using a tiny task sample, and then executes a bag within the user's budget constraints. Previous work has shown the efficacy of this approach. There remains, however, the risk of outlier tasks causing the execution to exceed the predicted make span. In this work, we present a stochastic optimization of the tail phase for Bats' execution. The main idea is to use the otherwise idling machines up until the end of their (already paid-for) allocation time. Using the task completion time information acquired during the execution, BaTS decides which tasks to replicate onto idle machines in the tail phase, reducing the make span and improving the tolerance to outlier tasks. Our evaluation results show that this effect is robust w.r.t. the quality of runtime predictions and is the strongest with more expensive schedules in which many fast machines are available.
---
paper_title: Investigating Business-Driven Cloudburst Schedulers for E-Science Bag-of-Tasks Applications

paper_content:

The new ways of doing science, rooted on the unprecedented processing, communication and storage infrastructures that became available to scientists, are collectively called e-Science. Many research labs now need non-trivial computational power to run e-Science applications. Grid and voluntary computing are well-established solutions that cater to this need, but are not accessible for all labs and institutions. Besides, there is an uncertainty about the future amount of resources that will be available in such infrastructures, which prevents the researchers from planning their activities to guarantee that deadlines will be met. With the emergence of the cloud computing paradigm come new opportunities. One possibility is to run e-Science activities at resources acquired on-demand from cloud providers. However, although very low, there is a cost associated with the usage of cloud resources. Besides that, the amount of resources that can be simultaneously acquired is, in practice, limited. Another possibility is the not new idea of composing hybrid infrastructures in which the huge amount of computational resources shared by the grid infrastructures are used whenever possible and extra capacity is acquired from cloud computing providers. We here investigate how to schedule e-Science activities in such hybrid infrastructures so that deadlines are met and costs are reduced.
---
paper_title: Matrix: Achieving Predictable Virtual Machine Performance in the Clouds

paper_content:

The success of cloud computing builds largely upon on-demand supply of virtual machines (VMs) that provide the abstraction of a physical machine on shared resources. Unfortunately, despite recent advances in virtualization technology, there still exists an unpredictable performance gap between the real and desired performance. The main contributing factors include contention to the shared physical resources among co-located VMs, limited control of VM allocation, as well as lack of knowledge on the performance of a specific VM out of tens of VM types offered by public cloud providers. In this work, we propose Matrix, a novel performance and resource management system that ensures the desired performance of an application achieved on a VM. To this end, Matrix utilizes machine learning methods clustering models with probability estimates to predict the performance of new workloads in a virtualized environment, choose a suitable VM type, and dynamically adjust the resource configuration of a virtual machine on the fly. The evaluations on a private cloud, and two public clouds (Rackspace and Amazon EC2) show that for an extensive set of cloud applications, Matrix is able to estimate application performance with average 90% accuracy. In addition, Matrix can deliver the target performance within 3% variance, and do so with the best cost-efficiency in most cases.
---
paper_title: Exploiting Hardware Heterogeneity within the same Instance Type of Amazon EC2

paper_content:

Cloud computing providers might start with near-homogeneous hardware environment. Over time, the homogeneous environment will most likely evolve into heterogeneous one because of possible upgrades and replacement of outdated hardware. In turn, the hardware heterogeneity will result into performance variation. In this paper, we look into the hardware heterogeneity and the corresponding performance variation within the same instance type of Amazon Elastic Compute Cloud (Amazon EC2). Standard large instance is selected as the example. We find out that there exist three different subtypes of hardware configuration in the standard large instance. Through a set of detailed micro-benchmark and application-level benchmark measurements, we observe that the performance variation within the same subtype of instance is relatively small, whilst the variation between different sub-types can be up to 60%. By selecting better-performing instances to complete the same task, end-users of Amazon EC2 platform can achieve up to 30% cost saving.
---
paper_title: A Performance Study on the VM Startup Time in the Cloud

paper_content:

One of many advantages of the cloud is the elasticity, the ability to dynamically acquire or release computing resources in response to demand. However, this elasticity is only meaningful to the cloud users when the acquired Virtual Machines (VMs) can be provisioned in time and be ready to use within the user expectation. The long unexpected VM startup time could result in resource under-provisioning, which will inevitably hurt the application performance. A better understanding of the VM startup time is therefore needed to help cloud users to plan ahead and make in-time resource provisioning decisions. In this paper, we study the startup time of cloud VMs across three real-world cloud providers -- Amazon EC2, Windows Azure and Rackspace. We analyze the relationship between the VM startup time and different factors, such as time of the day, OS image size, instance type, data center location and the number of instances acquired at the same time. We also study the VM startup time of spot instances in EC2, which show a longer waiting time and greater variance compared to on-demand instances.
---
paper_title: Observing the clouds: a survey and taxonomy of cloud monitoring

paper_content:

Monitoring is an important aspect of designing and maintaining large-scale systems. Cloud computing presents a unique set of challenges to monitoring including: on-demand infrastructure, unprecedented scalability, rapid elasticity and performance uncertainty. There are a wide range of monitoring tools originating from cluster and high-performance computing, grid computing and enterprise computing, as well as a series of newer bespoke tools, which have been designed exclusively for cloud monitoring. These tools express a number of common elements and designs, which address the demands of cloud monitoring to various degrees. This paper performs an exhaustive survey of contemporary monitoring tools from which we derive a taxonomy, which examines how effectively existing tools and designs meet the challenges of cloud monitoring. We conclude by examining the socio-technical aspects of monitoring, and investigate the engineering challenges and practices behind implementing monitoring strategies for cloud computing.
---
paper_title: Patterns in the Chaos—A Study of Performance Variation and Predictability in Public IaaS Clouds

paper_content:

Benchmarking the performance of public cloud providers is a common research topic. Previous research has already extensively evaluated the performance of different cloud platforms for different use cases, and under different constraints and experiment setups. In this paper, we present a principled, large-scale literature review to collect and codify existing research regarding the predictability of performance in public Infrastructure-as-a-Service (IaaS) clouds. We formulate 15 hypotheses relating to the nature of performance variations in IaaS systems, to the factors of influence of performance variations, and how to compare different instance types. In a second step, we conduct extensive real-life experimentation on Amazon EC2 and Google Compute Engine to empirically validate those hypotheses. At the time of our research, performance in EC2 was substantially less predictable than in GCE. Further, we show that hardware heterogeneity is in practice less prevalent than anticipated by earlier research, while multi-tenancy has a dramatic impact on performance and predictability.
---
paper_title: User-Centric Heterogeneity-Aware MapReduce Job Provisioning in the Public Cloud

paper_content:

Cloud datacenters are becoming increasingly heterogeneous with respect to the hardware on which virtual machine (VM) instances are hosted. As a result, ostensibly identical instances in the cloud show significant performance variability depending on the physical machines that host them. In our case study on Amazon’s EC2 public cloud, we observe that the average execution time of Hadoop MapReduce jobs vary by up to 30% in spite of using identical VM instances for the Hadoop cluster. In this paper, we propose and develop U-CHAMPION, a user-centric middleware that automates job provisioning and configuration of the Hadoop MapReduce framework in a public cloud to improve job performance and reduce the cost of leasing VM instances. It addresses the unique challenges of hardware heterogeneity-aware job provisioning in the public cloud through a novel selective-instance-reacquisition technique. It applies a collaborative filtering technique based on UV Decomposition for online estimation of ad-hoc job execution time. We have implemented U-CHAMPION on Amazon EC2 and compared it with a representative automatedMapReduce job provisioning system. Experimental results with the PUMA benchmarks show that U-CHAMPION improves MapReduce job performance and reduces the cost of leasing VM instances by as much as 21%.
---
paper_title: Exploiting Hardware Heterogeneity within the same Instance Type of Amazon EC2

paper_content:

Cloud computing providers might start with near-homogeneous hardware environment. Over time, the homogeneous environment will most likely evolve into heterogeneous one because of possible upgrades and replacement of outdated hardware. In turn, the hardware heterogeneity will result into performance variation. In this paper, we look into the hardware heterogeneity and the corresponding performance variation within the same instance type of Amazon Elastic Compute Cloud (Amazon EC2). Standard large instance is selected as the example. We find out that there exist three different subtypes of hardware configuration in the standard large instance. Through a set of detailed micro-benchmark and application-level benchmark measurements, we observe that the performance variation within the same subtype of instance is relatively small, whilst the variation between different sub-types can be up to 60%. By selecting better-performing instances to complete the same task, end-users of Amazon EC2 platform can achieve up to 30% cost saving.
---
paper_title: Coordinated Rescheduling of Bag-of-Tasks for Executions on Multiple Resource Providers

paper_content:

Metaschedulers can distribute parts of a Bag-of-Tasks (BoT) application among various resource providers in order to speed up its execution. The expected completion time of the user application is then calculated based on the run-time estimates of all applications running and waiting for resources. However, because of inaccurate run time estimates, initial schedules are not those that provide users with the earliest completion time. These estimates increase the time distance between the first and last tasks of a BoT application, which increases average user response time, especially in multi-provider environments. This paper proposes a coordinated rescheduling algorithm to handle inaccurate run-time estimates when executing BoT applications in multi-provider environments. The coordinated rescheduling defines which tasks can have start time updated based on the expected completion time of the entire BoT application. We have also evaluated the impact of system-generated run-time estimates to schedule BoT applications on multiple providers. We performed experiments using simulations and a real distributed platform, Grid'5000. From our experiments, we obtained reductions of up to 5 and 10% for response time and slowdown metrics, respectively, by using coordinated rescheduling over a traditional rescheduling solution. Moreover, coordinated rescheduling requires little modification of existing scheduling systems. System-generated predictions, on the other hand, are more complex to be deployed and may not reduce response times as much as coordinated rescheduling. Copyright © 2011 John Wiley & Sons, Ltd.
---
paper_title: Inter-Cloud Architectures and Application Brokering: Taxonomy and Survey

paper_content:

Although Cloud computing itself has many open problems, researchers in the field have already made the leap to envision Inter-Cloud computing. Their goal is to achieve better overall Quality of Service QoS, reliability and cost efficiency by utilizing multiple clouds. Inter-Cloud research is still in its infancy, and the body of knowledge in the area has not been well defined yet. In this work, we propose and motivate taxonomies for Inter-Cloud architectures and application brokering mechanisms. We present a detailed survey of the state of the art in terms of both academic and industry developments 20 projects, and we fit each project onto the discussed taxonomies. We discuss how the current Inter-Cloud environments facilitate brokering of distributed applications across clouds considering their nonfunctional requirements. Finally, we analyse the existing works and identify open challenges and trends in the area of Inter-Cloud application brokering. Copyright © 2012 John Wiley & Sons, Ltd.
---
paper_title: MapReduce: simplified data processing on large clusters

paper_content:

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. ::: ::: Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. ::: ::: Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day.
---

Title: A Survey and Taxonomy of Resource Optimisation for Executing Bag-of-Task Applications on Public Clouds

Section 1: Introduction
Description 1: This section introduces the significance of cloud computing in the industry and outlines the aim of the survey which includes comparisons of existing frameworks and presenting taxonomy for resource optimization.

Section 2: Data Collection
Description 2: This section explains the methodology used for data collection, including sources and criteria for selecting research publications used in the survey.

Section 3: Organisation
Description 3: This section describes the structure of the survey and provides an overview of the topics covered in each subsequent section.

Section 4: Current Research
Description 4: This section surveys current research on developing frameworks for scheduling the execution of Bag-of-Task (BoT) jobs on public cloud resources, distinguishing between homogeneous and heterogeneous cloud environments.

Section 5: Scheduling in Homogeneous Cloud Environments
Description 5: This section explores research on scheduling techniques in environments where virtual machines (VMs) are of a single, fixed type.

Section 6: Scheduling in Heterogeneous Cloud Environments
Description 6: This section examines research that employs a variety of VM types in scheduling methods, offering more flexibility and complexity.

Section 7: Taxonomy 
Description 7: This section develops a taxonomy of common themes, characteristics, requirements, and challenges found in the surveyed research, based on six identified themes.

Section 8: Literature Analysis
Description 8: This section provides an analysis of the literature surveyed, highlighting the critical aspects of resource selection, scaling, and allocation, among others.

Section 9: Dynamic Scheduling
Description 9: This section identifies how dynamic scheduling is triggered and performed during runtime to handle unexpected events or parameter variations.

Section 10: Discussion
Description 10: This section summarises current trends in the research area and proposes future research directions to improve cloud resource utilization for executing BoT applications.

Section 11: Current Trends
Description 11: This section identifies and discusses the predominant trends observed from the literature surveyed, including resource scaling, type selection, and more.

Section 12: Future Directions
Description 12: This section outlines potential avenues for future research to advance the optimization of cloud usage for BoT applications, including heterogeneous architecture awareness, cross-cloud scheduling, and performance prediction.

Section 13: Conclusions
Description 13: This section concludes the survey by summarizing the findings, developed taxonomy, current trends, and proposed directions for future research, emphasizing the need for effective scheduling to meet user requirements and application performance.