About the Post

Author Information

Michele Mazzucco is a Post-Doctoral Research Fellow in the Software Engineering Group at the University of Tartu (Estonia) and a Researcher at the Software Technology and Applications Competence Center (STACC).

On delivering highly available services using spot instances

In the Infrastructure-as-a-Service (IaaS) cloud computing market, spot instances refer to virtual servers that are rented via an auction. Spot instances allow IaaS providers to sell spare capacity while enabling IaaS users to acquire virtual servers at a lower price than the regular market price (also called “on demand” price). Users bid for spot instances at their chosen limit price. Based on the bids and the available capacity, the IaaS provider sets a clearing price. A bidder acquires their requested spot instances if their bid is above the clearing price. However, these spot instances may be terminated by the IaaS provider impromptu if the auction’s clearing price goes above the user’s limit price. In this context, the paper “Achieving Performance and Availability Guarantees with Spot Instances” addresses the following question: Can spot instances be used to run paid web services while achieving performance and availability guarantees?

The paper examines the problem faced by a Software-as-a-Service (SaaS) provider who rents spot instances from an IaaS provider and uses them to provide a web service on behalf of a paying customer. The SaaS provider incurs a monetary cost for renting computing resources from the IaaS provider, while charging its customer for executing web service transactions and paying penalties to the customer for failing to meet performance and availability objectives. To address this problem, the paper proposes a bidding scheme and server allocation policies designed to optimize the average revenue earned by the SaaS provider per time unit. Experimental results show that the proposed approach delivers higher revenue to the SaaS provider than an alternative approach where the SaaS provider runs the web service using “on demand” instances. It also shows that the server allocation policies seamlessly adapt to varying market conditions, traffic conditions, penalty levels and transaction fees.

From the paper:

A very important issue that a SaaS renting “spot instances” faces is that in case of spot instance termination due to the clearing price crossing above the limit price, the web service is unavailable until the SaaS provider acquires new servers. This may result in the provider having to pay an unavailability penalty and losing revenue from unfulfilled web service transactions. On the other hand, the SaaS provider faces the decision of how many spot instances to acquire. The more instances it acquires, the better performance it can offer, but at a higher cost.

Our solution relies on two components:

To manage these tradeoffs, we propose a revenue maximization scheme to optimize the average net revenue per time unit on behalf of the SaaS provider. The scheme relies on two components:

  1. A price prediction model aimed at determining the lowest limit price to bid in order to achieve a given level of availability, and
  2. A policy for server allocation and admission control based on dynamic estimates of traffic parameters and models of system behavior.

The first pillar of our scheme is a model to determine an optimal limit price for the SaaS provider to bid on the spot market. Importantly, in a (multi-unit) Vickrey auction such as that used in the Amazon spot market, bidders have an incentive to bid truthfully (i.e., bid according to their value) rather than over- or under-bidding. In our context, the objective is to bid in such a way as to achieve a desired level of availability.

In the following table we report the performance of the proposed price prediction algorithm for m1.small (Linux/Unix) instances for different prediction horizons and availability targets. For testing purposes we employed the spot price traces over the period December 25, 2010 – February 23, 2011 (us-east-1 region). The price for “on demand” instances of type m1.small is 0.085 $/hour.
Prediction horizon (hours)

Availability

Avg. bid ($/h)

Target

Achieved

6

0.9

0.99673

0.03170

6

0.95

0.99673

0.03212

6

0.99

0.99673

0.03270

6

0.999

0.99673

0.03355

6

0.99999

0.99673

0.03463

12

0.9

0.99675

0.03207

12

0.95

0.99675

0.03250

12

0.99

0.99675

0.03307

12

0.999

0.99675

0.03385

12

0.99999

0.99675

0.03499

24

0.9

0.99679

0.03253

24

0.95

0.99679

0.03266

24

0.99

0.99679

0.03350

24

0.999

0.99679

0.03411

24

0.99999

0.99679

0.03253

Having determined the “best” price to bid, we have now left with choosing how many servers to rent from the spot market.

QoS can be guaranteed by means of different techniques.
We employ a general approach based on two complementary policies. The first one is a resource allocation policy that, based on traffic estimates, determines the number of servers to rent. This policy is invoked periodically. The intervals between consecutive allocation policy invocations are called “observation windows” or “epochs”. During an epoch, the number of running servers is constant, unless the acquired servers are terminated due to the clearing price crossing above the provider’s limit price. Also, during an epoch, the revenue optimization system collects traffic and service statistics (e.g., mean arrival rate and service time), which are used by the allocation policy at the start of the next epoch.
The second policy is an admission control policy, i.e., a mechanism which may deliberately decide to reject some jobs. The admission policy is defined by means of a threshold K (the buffer size). Incoming jobs are rejected if K other requests are in the system, without influencing future arrivals. The extreme values K = 0 and K = ∞ correspond to accepting none or all jobs.

A simpler heuristic exploits the observation that in multi-server queueing systems the response time is often dominated by the service time, while the waiting time decreases if the load is scaled up with the number of servers, e.g., a 20 servers system with a normalized load of 0.90 is less congested than a 2 servers system with a normalized load of 0.70. Hence, a simple approximation is to assume that the buffer size is unbounded, thus allowing all the traffic into the system.

In the figure below we evaluate via simulation the performance of the two policies we propose. The load varies between 7.5 and 25 by increasing the arrival rate from 15 to 50 requests/second. The average revenues obtained per hour are plotted against the arrival rate. Each point in the figure represents one run lasting 28 days, and include the corresponding 95% confidence interval. That value is calculated using the Student’s t-distribution. Allocation and admission decisions are taken every six hours. In other words in the scenarios where the SaaS employs “spot instances”, they are replaced every six hours. Spot prices vary every hour according to the Amazon traces, while the algorithm used to predict the prices limits the probability of disaster to 0.001. Finally, servers’ bootstrap as well as recovery from disasters take 5 minutes.

Apart from the revenues increase as a consequence of the load increase, the most notable feature of the graph plotted in figure is that the system is much more profitable when using “spot instances” compared to the case where “on demand” instances are employed, hence showing that the price prediction scheme performs well. It is worth stressing that in case of premature termination of the running instances the SaaS provider is liable to pay availability, disaster and performance penalties to the users (see the paper for more details).

To conclude, we have presented an approach to maximize the net revenue per time unit earned by a SaaS provider who hosts a paid web service using spot instances. Since the revenue is affected by the number of successfully served customers, paid penalties and server rental cost, the proposed approach aims at maximizing the first while minimizing the last two factors by deciding:

  1. How much to bid for resources on the spot market, and
  2. How many servers to allocate for a given time period (and how many jobs to accept).

To address the first question, we outlined an algorithm to determine the optimal (truthful) limit price to bid on the spot market to achieve a desired availability level. The second question is addressed by means of dynamic policies for server allocation and admission control.

Questions or comments?, write me.


Tags: ,

Trackbacks/Pingbacks

  1. Research group digest – ulno.net - July 15, 2011

    [...] On delivering reliable services using spot instances In the Infrastructure-as-a-Service (IaaS) cloud computing market, spot instances refer to virtual servers that are rented via an auction. Spot instances allow IaaS providers to sell spare capacity while enabling IaaS users to acquire virtual servers at a lower price than the regular market price (also called “on demand” price). Users bid for spot instances at [...] [...]

  2. More Cloud Computing Economics « Cloud Comments .net - July 19, 2011

    [...] One of their authors touched on a pet subject of mine (Spot Pricing) with a paper on how to deliver a robust SaaS whilst using using IaaS and Spots to maximise revenue http://cloud-computing-economics.com/business-benefits-applications/delivering-reliable-services-spo… [...]

  3. Canon Hf20 - May 16, 2012

    for more click here…

    [...]we like to honor other sites on the web, even if they aren’t related to us, by linking to them. Below are some sites worth checking out[...]…

Leave a Reply