A Brief Overview of Problems Addressed in My PhD Thesis “Resource Provisioning under Uncertainty in Cloud Computing”

This post gives an overview of my thesis titled Resource Provisioning under Uncertainty in Cloud Computing which was submitted to the Nanyang Technological University (NTU) in fulfillment of the requirement for my PhD degree in 2013. Specifically, this post mainly presents research challenges addressed in my PhD thesis in layman’s terms and gives a brief introduction of my PhD research contributions.

When pursuing the PhD, I mainly focused on a problem of resource provisioning in cloud computing where cloud computing resources can be provisioned from cloud service providers (CSP) to cloud consumers (i.e. cloud users, cloud customers) through two provisioning options, namely  on-demand option (which is also called pay-per-use/pay-as-you-go option) and reservation option. The reservation option is cheaper and able to guarantee prices and capacities of resources. However, a cloud consumer has to make upfront payment for the reserved resources. Due to uncertainties, the common problems encountered in resource provisioning with the reservation option are overprovisioning and underprovisioning.

The underprovisioning problem can be mitigated by the on-demand option. If reserved resources are underprovisioned to accommodate to extra demand, the on-demand option can be additionally provisioned for the extra demand. However, the price of an on-demand option cannot be guaranteed and can be increased when the underprovisioning problem is incurred. For the overprovisioning problem, if reserved resources are overprovisioned, the overspent resources can be wasted as the upfront payment are not refundable. If overprovisioned resources cannot be reassigned to other demand (e.g. other users’ demands for the same resources), investment in the resources will be wasteful.

In my thesis, I considered different uncertainties in this resource provisioning problem i.e. uncertainties of resource demand, resource price, resource availability, and even electricity prices. My major contributions include resource provisioning algorithms based on stochastic programming to deal with uncertainties for three different cloud stakeholders including cloud consumer/user, cloud provider, and cloud retailer.

I derived stochastic programming (SP) models to be used in the resource provisioning algorithms for finding resource provisioning solutions to purchase/rent cloud computing resources from one or more CSPs offering cloud customers reservation and/or on-demand options. Many CSPs, e.g.  Amazon Web Services (AWS), Microsoft Azure, Google, SoftLayer, DigitalOcean, VULTR, etc., offer the on-demand option. AWS, SoftLayer, Cloud9 and GoGrid (acquired by Datapipe) are, for example, CSPs offering  reservation options. Microsoft Azure used to offer a 6-month plan and a 12-month prepay offer which are equivalent to reservation options.

Several SP models were proposed during my PhD study but I would introduce only some of them in this website.

What is a cloud computing resource?

Cloud computing resources can be any resources offered by a CSP e.g. CPU-hours (i.e. processing power) of a virtual machine (VM) or a server, storage, network bandwidth, software, domain names, helpdesk support, etc.

Differences between Reservation and On-demand Options

Unit price (e.g. dollars per CPU-hour, dollars per GB-month) of the reservation option of the same resource type is cheaper than that of the on-demand option. Resources of the reservation option (i.e. reserved resources) are purchased with one upfront payment and a cheaper unit price of the resources will be fixed (i.e. reserved) for a certain period of time (e.g. 12 months or 36 months). In contrast, resources of the on-demand option (i.e. on-demand resources) can be provisioned at any time without any upfront cost. We can provision on-demand resources at the moment we want the resources and we can terminate/destroy the them when they are unwanted, and the on-demand resources are charged on a pay-per-use basis.

Let’s see examples of reservation and on-demand prices of EC2 Instances, which are servers offered by AWS. AWS provides EC2 Instances in many regions and zones (i.e. geographical locations) and different EC2 Instance Types (i.e. specifications/capabilities of EC2 Instances). The table below shows prices of the Linux EC2 Instance Types t2.microc4.large, and x1.16xlarge in US-East (Ohio).

Prices of Linux t2.micro in US-East (Ohio)
Provisioning Option Upfront Effective Hourly Price Savings
On-demand option No upfront $0.012
1-year-term reservation with all upfront $69 $0.008 33%
3-year-term reservation with all upfront $124 $0.005 58%

Prices of Linux c4.large in US-East (Ohio)
Provisioning Option Upfront Effective Hourly Price Savings
On-demand option No upfront $0.100
1-year-term reservation with all upfront $515 $0.059 41%
3-year-term reservation with all upfront $1,013 $0.039 61%

Prices of Linux x1.16xlarge in US-East (Ohio)
Provisioning Option Upfront Effective Hourly Price Savings
On-demand option No upfront $6.669
1-year-term reservation with all upfront $33,601 $3.836 42%
3-year-term reservation with all upfront $49,036 $1.866 72%

Check prices of EC2 Instances at the AWS website

Clearly, the unit price, i.e. the effective hourly price, of the 3-year-term reservation option is the cheapest — longer commitment, more cost savings. For example, if a Linux x1.16xlarge server in US-East (Ohio) is provisioned by this 3-year reservation option, this option can save up to 72%!

Reservation or On-demand?

You can skip this section and its following, and then move to the Challenging Question section if you just want to know what my thesis is about and you should still understand the whole story of this post. But if you want to know simple equations for determining whether the on-demand option or the reservation option is more suitable for a resource, this section may be helpful.

The reservation option is attractive but we have to pay the non-refundable upfront payment and reserved resources may not be fully utilized or may result in wasteful investment. The more expensive on-demand option is more flexible as on-demand resources can be provisioned at the moment they are demanded without any upfront cost. The on-demand option really makes cloud computing even more attractive, very on-demand utility computing.

Should we prefer the on-demand option to the reservation option? The on-demand option is an attractive worry-free option. But savings deals of the reservation option (like 72% savings as shown above) are also attractive. Hard to decide?

How cheap is the reservation option?

Let’s see how cheap a reservation option is through the following simple equations. Let  denote the total number of hours in the term of reservation option. Let  denote the upfront cost of a reservation option. The effective hourly cost/price of this reservation option (e.g. $ per hour) denoted by  be

.

Suppose a month equals 30 days. Hence the one-year time equals 8,640 hours and the three-year time equals 25,920 hours. Let’s use our equation with the Linux t2.micro in US-East (Ohio). The effective hourly costs of 1-yearreservation and 3-year reservation options are

and

, respectively.

We can validate our answers by comparing them with the effective hourly prices shown in the price table above. When using a reservation option, we can find how much savings over the on-demand option are by the following equation:

where   denotes the hourly cost of the on-demand option and   denotes  the percentage savings over the on-demand option. For the Linux t2.micro in US-East (Ohio), the savings over the on-demand options are 33.33% and 58.33% when the 1-year and 3-year reservation options are applied, respectively. (Check the price table above to validate our answers).

Again, we can clearly see that the effective hourly cost (or unit price) of the reservation option is cheaper. But this cheap cost is just an ideal saving as it is based on an assumption that the reserved resource is utilized or active all the time.

In practice, most of our resources are not utilized all the time. For example, a server (which includes CPU power, RAM, disk I/O, and network I/O resources) is not utilized all the time, and its CPU may be idle or underutilized as there are no (user-space) jobs running.

Let’s see another example of resource under-utilization: provisioning a web server for hosting only one gadget-review website. A reservation option (e.g. the 1-year option) would be considered for provisioning this server. But sometimes or probably many times, the web server is idle due to the smaller number of visitors e.g. a large number of visitors do not visit the gadget-news website during the Premier League and the World Cup (again, just an example). As a result, the server will be underutilized and will become a wasted resource.

If shutting down underutilized reserved servers/resources can save money during the idle stage, we just do it. For example, if we use either No-Upfront or Partial-Upfront reservation offered in AWS for provisioning servers, we can stop/terminate underutilized servers to save money. We also can reallocate such underutilized servers to  batch processing jobs such as web log analytics, social media analytics, image processing, any MapReduce jobs, etc. We may rent out them to other companies, if this will not violate any terms of services. If we really cannot benefit from the underutilized resources, we should analyze costs and benefits of both reservation and on-demand options more carefully before making the reservation upfront payment which is not refundable.

Simple Cost Analysis of Reservation and On-demand Options

We can conduct a simple cost analysis before making a resource provisioning decision. First, we can identify strengths and weaknesses of the two options.

For demonstrating how strength-and-weakness identification is performed, let’s draw a comparison between the AWS on-demand option and the AWS All-Upfront reservation option (which can be either 1-year or 3-year term). The table below shows the comparison. Bold letters in a cell indicate a strength. We can see that the on-demand option has more strengths. However, the zero cost (i.e. cheaper effective hour price) of the All-Upfront reservation option would yield more benefits. But, how can we know if the zero unit price of the reservation option can yield more benefits?

Comparison between the two options
Reservation On-demand
Upfront Payment Yes No
Unit Price Cheaper / Zero cost A due to the upfront payment Pay-per-use
Commitment Yes due to the non-refundable upfront payment No
Charge when stopping/terminating Already charged B No C
Capacity Reservation Yes D No

If we know the point at which the cost of running an on-demand resource equals the cost of the All-Upfront reservation option, we are able to determine whether the on-demand option or the All-Upfront reservation option can yield more benefits. See the following equation:

where  denotes the maximum number of hours that an on-demand resource can be spent within the fixed budget equaling the upfront cost which is denoted by , and again  denotes the hourly cost of the on-demand option. I prefer taking the floor function  as I want to neglect the fraction of an hour. divided by 720 yields the number of months [I assume that 1 month equals 720 hours].

Number of months that an on-demand resource can be spent within the same amount time of reservation term
Instance Type value for the 1-year term value for the 3-year term
t2.micro 7.99 months 14.35 months
c4.large 7.15 months 14.07 months
x1.16xlarge 7 months 10.21 months

The table above shows the   value (in months) given a different an EC2 Instance Type and a fixed-term option. With an   value, we can see how cost-effective or how valuable a reservation option is. For example, if we spend $49,036 for provisioning CPU-hours of an x1.16xlarge server by the on-demand option, the server can last for only 10.21 months. With the same amount of money, the x1.16xlarge server can last for 36 months or 3 years! So if our x1.16xlarge server will be needed longer than 10 months and we can afford the upfront cost, we would rather choose the 3-year reservation option.

Money always does matter! It’s the fact that our budget, our money, does matter. Absolutely, if we can’t afford the upfront payment of the 3-year term, the 1-year term is preferable. And.. if we can’t afford the 1-year term upfront payment, the on-demand option is preferable. The on-demand option is always preferable when the budget is tight. Lowering our resource specification or capacity requirement, i.e. choosing a cheaper resource type, to meet our budget is another solution which will be mentioned again later.

We can conduct deeper cost analysis by other cost-benefit analysis (CBA). I would not explain how the other CBA can be applied to the resource provisioning problem as it is out of scope of this post (and also out of scope of my thesis).

This post mainly uses All-Upfront reservation options offered by AWS to demonstrate the simple cost analysis. CBA is also recommended for analyzing Partial-Upfront, No-Upfront sub-options, and even other provisioning options offered in other CSPs.

A In AWS, when we pay for the All-Upfront reservation option, we do not need to pay the hourly-rate anymore as the upfront payment covers the entire reservation term (1 year-term or 3 year-term).  The effective hourly price of the All-Upfront reservation option is definitely cheaper than that of the on-demand option as discussed above.

B When we pay for the All-Upfront reservation option,  a reserved instance associated with this reservation option has been already charged although the instance is running, stopped, or terminated. Interesting fact: Amazon Reserved EC2 Instances are not actual instances/servers  but sort of offer that discounts usage of running EC2 instances.

C For stopped EC2 instances, AWS will not charge their hourly usage and network traffic but EBS storage used by the instances. Many cloud providers charge an hourly rate for the stopped on-demand servers.

D Capacity reservation guarantees availability of instances when needed and can be done by assigning the Reserved EC2 Instances to a specific Availability Zone.

Scenario – Provision of a server

We can apply the value discussed above to real-world scenarios. Let me use a very simple but common scenario — provisioning a server or a VM from AWS US-East Ohio. In this scenario, we want to know which provisioning option we should select for a single server.  Let’s consider on-demand, 1-year-term reservation, and also 3-year-term reservation options. If we exactly know that our server is needed for almost or at least one year, we would consider provisioning the server by the 1-year reservation option.

Let’s see a bit more challenging situation. Suppose we are going to launch a new online shopping project requiring a server that may or may not sustain in the next 12 months. Now we should determine the 1-year reservation option more carefully. If this new project is a short-term startup project or our budget is allocated to the project for only a few months for evaluating popularity of the online shop, we may not choose the reservation option. If the lifetime of the project is uncertain, we may estimate the expected lifetime (e.g. the mean or the average number of months that the project could last for) of other projects similar to our launching project. Without any historical data of the other similar projects, we may use our own judgement, a budget constraint E, a risk analysis tool, a predictive model, etc. to estimate the lifetime, or we can talk to an expert who can help us come up with a magic number exposing the project lifetime. If the expected lifetime is long enough for the on-demand option being more expensive, we would consider the reservation option. That is, the value can play its role i.e. if the lifetime is greater than , we should consider the reservation option.

For example, if we want to provision a single Linux server based on the AWS t2.micro in US-East (Ohio) for our new project and its expected lifetime is shorter than 7 months, we would rather choose the on-demand option according to the E values calculated. In addition, if the lifetime cannot be estimated, we just start with the on-demand option. If the lifetime is longer than 8 months but shorter than 14 months, we would rather choose the 1-year reservation. Last, if the lifetime is longer than 14 months, the 3-year one is preferred although the server may not last longer than 2 years. When any reservation term ends, we will plan on resource provisioning again.

If you like to see how a program of the resource-provisioning-option selection looks like, please refer the Java code as follows:

E The expected lifetime is directly governed by the limitation of the budget allocated to the project or the resources of the project. If we can afford the upfront cost of the 1-year or 3-year reservation, we can consider either reservation or on-demand option. If we cannot afford the upfront payment of both 1-year and 3-year terms, we should start with the on-demand option. Lowering our resource specification can accommodate to our budget, for example, we may replace the Instance Type t2.micro server by t2.nano server which is cheaper but comprised of smaller memory. Keep in mind that lowering resource specification can result in performance degradation of applications utilizing the resource.

Challenging Question : How many resources should we provision by the reservation option?

A major challenging question in my PhD thesis that I addressed is  “How many resources should we provision by the reservation option?”. It looks short and simple but why could it be a PhD thesis problem? Well, to get the best answer, or a nearly-best answer for the question is not easy.

Let’s focus on just servers as resources. In a private in-house IT system, a company might once try to answer this question “How many servers should we buy to meet our users’ demand?”. For a University, an IT support manager may ask this question “How many computers should we allocate to computer labs for serving all students who will enroll in courses using one of the labs?”. For a data center, a manager may ask this question “How many servers should we buy to serve cloud customers’ demand and maximize our profit”.

Simplified Question : How many EC2 Reserved Instances should we provision under a demand uncertainty?

Now, back to my thesis again – If resources are cloud servers e.g. AWS EC2 Instances, our challenging question can be “How many EC2 reserved instances or reserved VMs should we buy (i.e. provision by the reservation option)?”. Let’s simplify the question a bit more by assuming that there is only the 1-year reservation option and only one EC2 Instance Type that we are considering to buy.

If we perfectly know our resource demand impacting on the number of EC2 instances needed in the future, we just provision resources to exactly meet our demand. For example, if we perfectly know that only N VMs are enough based on the E value described in the previous section or N VMs are sufficient for the future demand within almost/at least a year, we would consider reserving only N VMs. Then, we can get the best provisioning result. Let me depict what this best provisioning looks like as follows:

The horizontal line represents a timeline. The whole timeline starting from the first vertical tally (|) to the last vertical tally (i.e. the third one)  represents the 1-year time. At the current point of time before the timeline starts (denoted by Current on top of the timeline), we have to plan on resource provisioning for identifying the number of reserved VMs to be purchased (again, the purchase of the reservation option has to be done in advance). If we provision N reserved VMs and in a future point of time (denoted by Future on top of the timeline) the actual demand is known to be N VMs, we do not need any additional on-demand VMs and we can definitely get the largest savings. We obtain the best provisioning!

Back to reality, the amount of resource demand in many systems, in many situations, is not perfectly known. Now it is not easy to answer “How many EC2 reserved instances or reserved VMs should we buy”. The question is challenging due to uncertainties, specifically a demand uncertainty in this simplified question.

Given our question, the demand uncertainty can cause one of three provisioning results: best provisioning (as discussed above), and the other two results as shown below, namely underprovisioning  overprovisioning.

Again, our simplified question is about finding the number of reserved VMs of one Instance Type to be provisioned by the 1-year reservation option. A basic rule or a constraint of this question is actually to match the reserved VMs to the actual demand. Let denote the number of reserved VM that we are going to provision and D denote the actual demand or the number of VMs that are actually needed.  To obtain the best provisioning result, we have to get equaling D i.e. X = D.

The underprovisioning problem occurs when we reserve resources (i.e. VMs in our question) less than the actual demand. The figure below shows what an underprovisioning problem looks like.

In this underprovisioning problem, we provision N reserved VMs (i.e. set X be N) but the actual demand is three times as large as N. That is, D = 3N = 3X, X < D. Then, we have to provision 2N on-demand VMs to serve all the demand. If the 2N VMs are not needed over the 1-year time or not needed longer than the E value, these 2N VMs can be terminated when they are unwanted anymore. But if the demands for the 2N on-demand VMs can last longer than a year or the E value, the cost of these 2N on-demand VMs will be more expensive than provisioning 2N reserved VMs which should be early done at the current point of time.

The overprovisioning problem occurs when we reserve resources (i.e. VMs in our question) larger than the actual demand. The figure below shows what an overprovisioning problem looks line.

In this overprovisioning problem, we provision N reserved VMs (i.e. set be N) but the actual demand is only half of N VMsThat is, D equals N/2, D = N/2 = X/2X > D. The first half of N VMs can be fully utilized. Neither on-demand VM nor reserved VM has to be additionally provisioned. But the other half of the reserved VMs can be wasted as we overspend our provisioning budget for the reservation option whose upfront fee is not refundable. If we can reassign the overprovisioned VMs for another work or rent them out to another organization, we would mitigate wastes of the overprovisioning problem.

Let me summarize all the 3 provisioning outcomes. Given the X reserved instances provisioned by the 1-year reservation option and then the actual demand, the number of demanded VMs, denoted by D is realized in the future,

  1. we will obtain the best provisioning result when X equals D i.e. X = D.
  2. we will obtain the underprovisioning result when X is less than D i.e. X < D.
  3. we will obtain the overprovisioning result when X is greater than D i.e. X > D.

Uncertainties

As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality. — Albert Einstein

I like the above quote although it is per se a paradox. A key term inside the quote is about uncertainties. Uncertainties are part of our lives. We face a variety of uncertainties all the time. We are not an oracle foreseeing what will exactly happen in the future. Although a thing is predictable, it may not happen in the way it is predicted or expected.

In cloud computing, there are a lot of uncertainties. As described in the previous section, a demand uncertainty is just one of them. When we do not know actual demands for cloud computing resources, we could not provision sufficient resources to accommodate to all the demands.

Prices of cloud resources can fluctuate too. This price uncertainty really happens in big cloud providers such as Amazon, Google, and Microsoft. In Amazon EC2, prices of on-demand VMs usually drop rather than increase. However, prices of spot VMs (i.e. spot instances) can go up and down according to demand and supply in Amazon EC2.

Resource availability is also uncertain. Availability of cloud resources is not always 100% up. Although a cloud provider defines a service level agreement (SLA) with 100% uptime for a cloud service, this SLA cannot ensure that the cloud service will be available all the time. Disruptions of cloud resources have really occurred.

I liked to bring  the Three Marks of Existence in Buddhism to explain uncertainties of cloud resources (or anything). These three marks include (1) impermanence, (2) unsatisfactoriness, and (3) non-self. I would say  the three marks exist in cloud computing. In my thesis, uncertainties of demands, prices, and availability of cloud computing resources are taken into account.

Contributions of My Thesis

 

 

 

 

 

 

 

My major thesis contributions  include resource provisioning algorithms and a framework that deal with the uncertainties for different cloud stakeholders including cloud consumers, cloud providers, and cloud retailers (as depicted in the above figure).

First, I proposed novel algorithms for a cloud consumer to provision resources from cloud providers. The algorithms can minimize the expected resource provisioning cost incurred by overprovisioning and underprovisioning of resources, while the uncertainties are taken into account. Optimization models based on stochastic programming were formulated to obtain the optimal solution for the algorithms. Robust optimization was also applied to handle impact of the uncertainties on the optimal solution. Performance evaluation shows that the proposed algorithms have the lowest resource provisioning cost when they are compared with other well-known algorithms.

Second, I proposed a novel resource provisioning framework for a cloud provider. The framework considers the cloud provider owning data centers where the smart grid technology is available. Inside the framework, a stochastic programming model with multi-stage recourse was derived. The model can jointly optimize the power and resource allocation costs, while uncertainties of power price and compute demand are addressed.

Finally, I investigated a cloud computing market where a cloud retailer sells value-added services on top of other cloud providers’ resources. A  resource provisioning algorithm based on stochastic programming was derived for provisioning resources from cloud providers to the cloud retailer such that the retailer’s profit can be maximized.

The proposed algorithms and framework will be useful for cloud providers who want to optimally operate the cloud computing business and cloud consumers who want to optimally utilize resources located in cloud computing.

Related Publications

I published contributions of my thesis in IEEE conferences and one IEEE journal. If you want to learn more about my research contributions, you may refer to these papers as your further readings. I expected that one day I would write an article to introduce some of these papers. If you do not have access to one of them, please ask for a copy from me by putting your comment and contact in this post.

  1. Chaisiri, S., Niyato, D., & Lee, B. S. (2014, July). Joint virtual machine allocation and power portfolio optimization for data centers in smart grid environment. In Computer Science and Engineering Conference (ICSEC), 2014 International (pp. 44-49). IEEE.
  2. Chaisiri, S., Niyato, D., & Lee, B. S. (2014, May). Capacity planning for data center to support green computing. In Computer Science and Software Engineering (JCSSE), 2014 11th International Joint Conference on (pp. 152-157). IEEE.
  3. Chaisiri, S., Lee, B. S., & Niyato, D. (2012). Optimization of resource provisioning cost in cloud computing. IEEE Transactions on Services Computing, 5(2), 164-177.
  4. Chaisiri, S., Kaewpuang, R., Lee, B. S., & Niyato, D. (2011, July). Cost minimization for provisioning virtual servers in amazon elastic compute cloud. In Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS), 2011 IEEE 19th International Symposium on (pp. 85-95). IEEE.
  5. Chaisiri, S., Lee, B. S., & Niyato, D. (2010, December). Robust cloud resource provisioning for cloud computing environments. In Service-Oriented Computing and Applications (SOCA), 2010 IEEE International Conference on (pp. 1-8). IEEE.
  6. Chaisiri, S., Lee, B. S., & Niyato, D. (2009, December). Optimal virtual machine placement across multiple cloud providers. In Services Computing Conference, 2009. APSCC 2009. IEEE Asia-Pacific (pp. 103-110). IEEE.

Leave a Reply

Your email address will not be published. Required fields are marked *

*