Decision Model Java (Memory Fix + Link EC2 API)

I handled two problems that still existed with the Java port of the spot model software attached to the "Decision Model for Cloud Computing under SLA Constraints" paper.

• The first problem I attacked is the fact that the software needed a lot of memory. This was the case because it first of all read a couple of 100000 records to memory from the input CSV file to then use this data to do a lot of simulations ... and to finally write all the results from memory back to file. I fixed this issue by adjusting the source code such that only the history spot prices of one instance type is read at once. Since there are no correlations between the data records of different instance types, it is possible to do the simulation (for the different task lengths and different checkpointing schemes) for every instance type/category separately.


• A second thing that I changed is the input file for this application, previously it took one data.csv file as input containing the spot price history data for every instance type (different columns). This file did not contain any date information, every record contained the price for a minute of time. Now the application takes the CSV files from cloudexchange.org as input, which means there is a separate file for every region-os-instance combination that has two columns: the first one contains the date, the second one the corresponding spot price for that instance at that time. Also, to use up-to-date spot price history information and to ensure that all my applications would remain usable would cloudexchange ever cease operations, I made a link with the EC2 API. So, in a separate project (called AmazonSDK) I created an application that connects with the different Amazon EC2 endpoints and requests the spot price history of the corresponding region. This data is then processed by my application and the output files are organised and formatted the same way as the ones that can be found on cloudexchange.org.

Both projects can be checked out from the SVN repository, but backups can be found here:

• The Decision Model project here.
• The AmazonSDK project here.

Decision Model Java Implementation

I made some little changes to the java port of the 'Decision Model ...' paper software. And added Javadoc comments to this source code, which can be checked out from the SVN repository. This software needs a lot of memory because it first of all reads a couple of 100000 records to memory from the input CSV file then uses it to do a lot of simulations ... and finally writes all the results from memory back to file. (Actually this process starts all over for every task length). I think to boost the performance it would not be a bad idea to only take the history spot prices of one instance type as input and do the simulation only for one category/instance type at a time. This would almost make all arrays used in the program a dimension smaller. And it's not that hard to then write something around it that runs the program a couple of times with different input for the different instance types. Also the program still takes its own input file, but this can easily be changed by implementing a data input reader that takes the cloudexchange CSV files as input. A backup of the source code of this program can be downloaded here.

Decision Model for Cloud Computing under SLA Constraints

Today I had a look at the software that comes with the "Decision Model for Cloud Computing under SLA Constraints" paper by Andrzejak A., Kondo D. and Yi S. The implementation of the presented model can be found on the project website.

The paper describes its contribution as follows:

Our main contribution is a probabilistic model that can
be used to answer the question of how to bid given SLA
constraints. A broker can easily apply this model to present
automatically to the user a bid (or set of bids) that will meet
reliability and performance requirements. This model is particularly
suited for Cloud Computing as it is tailored for environments
where resource pricing and reliability vary significantly
and dynamically, and where the number of resources allocated
initially is flexible and is almost unbounded. We demonstrate
the utility of this model with simulation experiments driven
by real price traces of Amazon Spot Instances, and workloads
based on real applications.

So, I had a look at the source file, they implemented the simulation process in one C-file. It took me a while to completely understand the code, especially the implementation of the actual simulation in the methods simulateOptimalCkpt() and simulateHourCkpt() was pretty hard. But now I'm sure this code can be used to develop a broker application (and it can be easily ported to another language). Note that other checkpointing schemes can easily be added since the required methods can be found in the source code that comes with the "Reducing Costs of Spot Instances via Checkpointing in the Amazon Elastic Compute Cloud" paper on this website.

The following quote from the paper describes how the output of the program can be used to make an intelligent (task is done before the given deadline and within the foreseen budget) bid for the spot price:

To find the optimal instance type and bid price, we compute ET(cdead) and M(cB) and check the feasibility (as stated in section 3D) for all relevant combinations of both parameters. As these computations are basically “look-ups” in tables of previously computed distributions, the processing effort is negligible. Among the feasible cases, we select the one with the smallest M(cB); if no feasible cases exist, the job cannot be performed under the desired constraints.

Their simulations resulted in some interesting findings found in the summary of the results in the paper (section 4F). Note that constraints on other random variables than ET and M can be introduced as well.

How do I see the broker application at the moment? It takes as input a collection of workloads and some properties and constraints should be provided for each workload. For a workload should first be determined on what kind of instance it should be executed (maybe in a first iteration of the software with simple CPU, Memory, ... usage thresholds). Then a division between reserved and other instances should be made (based on the on-demand price, since the spot price fluctuates too much). Then finally the algorithms provided in the paper can be used to determine whether the constraints can be met by using spot instances. The bid price and checkpointing scheme that should be chosen for the spot instances is determined when this is the case. Otherwise on-demand instances can be used. I'm thinking the broker should be a Java webservice that periodically downloads the spot price history and then reruns the simulations to update its data.

Papers

I read these 3 papers during the weekend:

1. "Exploiting Non-Dedicated Resources for Cloud Computing" by Andrzejak A., Kondo D. and Anderson D.P.:

   ABSTRACT Popular web services and applications such as Google Apps, DropBox, and Go.Pc introduce a wasteful imbalance of processing resources. Each host operated by a provider serves hundreds to thousands of users, treating their PCs as thin clients. Tapping the processing, storage and networking capacities of these non-dedicated resources promises to reduce the size of required hardware basis significantly. Consequently, it presents a noteworthy opportunity for service providers and operators of cloud computing infrastructures. We investigate how a mixture of dedicated (and so highly available) hosts and non-dedicated (and so highly volatile) hosts can be used to provision a processing tier of a large-scale web service. We discuss an operational model which guarantees long-term availability despite of host churn, and study multiple aspects necessary to implement it. These include: ranking of non-dedicated hosts according to their long-term availability behavior, short-term availability modeling of these hosts, and simulation of migration and group availability levels using real-world availability data from 10,000 non-dedicated hosts. We also study the tradeoff between a larger share of dedicated hosts vs. higher migration rate in terms of costs and SLA objectives. This yields an optimization approach where a service provider can find a suitable balance between costs and service quality. The experimental results show that it is possible to achieve a wide spectrum of such modes, ranging from 3.6 USD/hour to 5 USD/hour for a group of at least 50 hosts available with probability greater than 0.90.

2. "Reducing Costs of Spot Instances via Checkpointing in the Amazon Elastic Compute Cloud" by Andrzejak A., Kondo D. and Yi S.:

   ABSTRACT Recently introduced spot instances in the Amazon Elastic Compute Cloud (EC2) offer lower 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 trade-offs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. We study how one such a mechanism, namely check pointing, 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 check pointing schemes in terms of monetary costs and improvement of job completion times. Trace-based simulations show that our approach can reduce significantly both price and the task completion times.

3. "Decision Model for Cloud Computing under SLA Constraints" by Andrzejak A., Kondo D. and Yi S.:

   ABSTRACT 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. A critical challenge is to determine bid prices that minimize monetary costs for a user while meeting Service Level Agreement (SLA) constraints (for example, sufficient resource availability to complete a computation within a desired deadline). We propose a probabilistic model for the optimization of monetary costs, performance, and reliability, given user and application requirements and dynamic conditions. Using real instance price traces and workload models, we evaluate our model and demonstrate how users should bid optimally on Spot Instances to reach different objectives with desired levels of confidence.

It took a while (I read some parts more than 3 times) to understand everything the papers were talking about, but now I think I get what they are saying. And the presented models sure will be a good extension to the model I'm creating.