Selling Reserved Instances in Cloud Computing

1 Introduction

Cloud computing becomes more and more popular nowadays because it can provide scalable and elastic access to IT resources and applications via the Internet [AWS, 2015; Azure, 2015; Google Cloud Platform, 2015]. Infrastructure as a service (IaaS), in which computing resources are mainly sold through instances (also referred to as virtual machines), is one of the several fundamental models of cloud computing. There are two main pricing models in today's IaaS market: the pay-as-you-go model (for on-demand instances), and the subscription model (for reserved instances). 1

1 There is a third one, the auction based pricing model for spot instances. However, it is supported by only one of the mainstream cloud provider.

The pay-as-you-go model is the most commonly used pricing mechanism, in which the cloud provider sets a fixed perinstance-hour price, and users pay for their utilization of instance hours. In the subscription model, a user should first pay some upfront fee 2 for the instances he/she is going to reserve for a pre-defined period of future time. Then the user can use the reserved resource whenever he/she wants during the subscription period, under a significantly discounted perinstance-hour usage price.

The pay-as-you-go pricing mechanism is easy to implement, since users do not need to specify the length of their jobs at the beginning. However, the pay-as-you-go price is usually higher than the subscription price for the same type of instances. Therefore, many users prefer to reserve some resources in the near future, if their demand is predictable. However, the options for buying reserved instances through the subscription model are very limited in today's cloud industry. For example, in Amazon EC2 users can only make a 1-year or 3-year reservation, and they cannot adjust their reservation according to their real demand.

To address the limitation of the current pricing model for reserved instances, in this work we design new pricing mechanisms which allow users reserve instances depending on their own need and offer them more flexibility. In particular, we allow a user i to specify the number of instances ni he/she needs, the start time ri, the end time di, and the time length li of his/her reservation. Note that the reservation can be tight (i.e., di - ri = li) or delayable (i.e., di - ri > li). For example, a user can submit a delayable reservation saying that he/she wants to reserve 5 instances for one week during next month. When the user submits his/her reservation to the cloud, the system will post the total price for the reservation immediately. If he/she is willing to pay the price, his/her reservation will be accepted. Otherwise, his/her reservation will be rejected. Once a reservation is accepted it will never be interrupted.

We focus on posted pricing mechanisms for selling reserved instances because posted pricing mechanisms have certain advantages. For instance, a user can adjust his/her reservation interval to minimize his/her cost. He/she may also have enough time to switch to other cloud providers if his/her value is lower than the price offered by a cloud provider, since posted pricing mechanisms provide immediate price response to his/her request. Another advantage of posted price is that users do not need to reveal their exact value to the mechanism, which is their private information.

2 The upfront fee could be zero depending on his/her choice.

Our goal is to maximize the social welfare. We propose two posted pricing mechanisms based on the utilization rate of the cloud. The main idea of the mechanisms is that the price of a reservation is positively correlated with the utilization rate of the cloud at its reservation period: When a reservation request arrives, if the cloud is heavily loaded (i.e. the available capacity is relatively small) during its reservation period, it needs to pay more to make it accepted; if its value is not large enough, it will be rejected, and the available capacity will be left to more valuable requests. This kind of pricing principle has already been used in many businesses such as air tickets selling, hotel reservation and so on. Different from those businesses, the cloud reservation faces more challenges. For example, the reservation may be quite flexible, starts at any time and the demands are hard to predict.

Our work can be summarized as follows:

• We first study the case in which all the reservations are tight. For this case, we propose a pricing mechanism which determines the price of a reservation based on the utilization rate of the cloud. The mechanism has a competitive ratio of 1 + 12 ln(3kT + 1) under a mild assumption, where k (res. T) is the maximum ratio between per-instance-hour valuation (res. length) of any two jobs.
• We then extend our result to a more general case where reservations can be delayable and have some flexibility. By slightly modifying the previous mechanism, we derive a new pricing mechanism that has the same competitive ratio.
• We also prove that no deterministic algorithm can obtain a competitive ratio less than ln(2kT) under the same assumption, which shows the optimality (within a constant factor) of our mechanisms.

2 RelatedWork

Because of its popularity and great impact to IT industry, cloud computing has attracted a lot of attention from research community [Abhishek et al., 2012; Fox et al., 2009; Funke et al., 2012; Jain et al., 2014; Vinothina et al., 2012]. We only review those papers closely related to our work.

Our work is part of the large body of literature on designing truthful online mechanisms [Friedman and Parkes, 2003; Parkes et al., 2004; Hajiaghayi, 2005; Parkes, 2007]. However, most mechanisms in these papers are auction-based mechanisms, in which the payment of each agent is determined at the (reported) deadline of his/her job, while in our mechanisms, the payment is determined right upon the arrival of the agent (i.e., posted price). In this sense, our setting is more suitable for cloud computing because if an agent immediately gets notified upon his arrival that his job cannot be completed, he can switch to other cloud computing platforms with minimum time cost.

The online resource allocation problem for cloud computing has been investigated in many papers [Mashayekhy et al.,

2014; Zaman and Grosu, 2012; Zhang et al., 2013]. A closely related work is [Zhang et al., 2013], in which the authors propose an online mechanism framework for cloud resource allocation. Different from our work, agents' valuation functions are continuous and concave in their model: An agent will get a positive value even if his/her demand is only partially satisfied, and the more resources he/she is allocated, the more value he/she will get. In our model, the valuation function of an agent is binary: He/she gets a positive value if and only if his/her reservation is accepted and fully satisfied.

Azar and Khaitsin [2011] consider an online ad placement problem which is similar to our problem. Each ad has an arrival time, a deadline, a length and a value. Similar to our work, they are interested in truthful "prompt" mechanism where the payment is determined for an agent at the very moment of his/her arrival. The difference is that the jobs (ads) in their setting are of the same length, while jobs (reservation) in our model are of different length. That is, their problem can be regarded as a special case of our problem.

Chakrabarty et al. [2013] consider the online version of knapsack problem. Both their work and our work belong to a class of online decision problem: whether to accept an item (reservation) at its arrival. The difference is that their problem is much simpler than ours. Once an item is accepted in the online knapsack problem, it will be in the knapsack forever and one does not need to concern whether to pack the item inside the knapsack. In contrast, in our model, once a reservation is accepted, we need to find a time interval for the reservation (and determine its payment), and the resources can be re-used by other jobs when the time interval of the reservation has passed.

The reservation problem of perishable products originates from the airline industry [Williamson, 1992], and then draws a lot of attention in hotel industry [Baker and Collier, 1999; Bitran and Gilbert, 1996; Bitran and Mondschein, 1995; Goldman et al., 2002; McMahon-Beattie, 2002; Sch¨utze, 2008]. Comparing to the airline reservation, the hotel reservation problem is more closely related to ours since the hotel booking requests can occur for different lengths and can therefore overlap. Bitran and Mondschein [1995] consider the room allocation problem, and formulate this problem as a stochastic and dynamic programming model. Baker and Collier [1999] compare the performances of five booking control policies. Our work has obvious differences with these work on hotel reservation. First, all these work focuses on the revenue maximization, while our goal is to maximize the social welfare. Second, they empirically evaluate the performance of their algorithms by simulation, while we theoretically study the performance of our pricing mechanisms by competitive analysis.

3 ProblemFormulation

In this section, we formally setup the problem of designing pricing mechanisms for instance reservation in cloud.

Let C denote the capacity of a cloud provider, i.e., the cloud provider has C instances (virtual machines) for reservation. Customers/agents arrive sequentially and submit their reservation requests. For simplicity, we also call a reservation j a job, which is characterized by (rj , dj , lj , nj , vj ), where rj is the earliest start time of the reservation, dj is the latest end time of the reservation, lj(≤ dj -rj) is the time length of the reservation, nj (≪ C) is number of instances to reserve, and vj is the value of the reservation. We call a job tight (resp. delayable) if lj = dj - rj (resp. lj < dj - rj ). For any job set S, we use v(S) to denote ∑j∈S vj .

We consider an online setting, in which jobs arrive online and the provider has no knowledge about future jobs. The agents are self-interested and may misreport the attributes of their reservations to be better off. Once a job j arrives, the agent (the owner of the job) submits its attributes ˆ rj, ˆ dj, ˆlj and ˆnj to the cloud system (note that ˆ rj is not necessarily equal rj, so are ˆ dj etc.), the system immediately calculates the price pj of the reservation, and then the agent decides whether to accept the price. The utility of j is vj - pj if he/she accepts the price, and 0 otherwise. We assume each agent is rational: he/she will accept the price and buy the reserved instances if vj ≥ pj, and reject the price and give up the reservation otherwise. Note that the agent does not need to reveal his/her value vj to the system. Similar to [Hajiaghayi, 2005], we restrict the misreports of agents, i.e., ˆ rj ≥ rj, ˆ dj ≤ dj, ˆlj ≥ lj and ˆnj ≥ nj.

In consideration of the potential misreport of agents, we are concerned with incentive compatible (also truthful) mechanisms. Amechanism is incentive compatible (IC) if, for any agent j, regardless of the behaviors of other agents, truthful reporting his/her job maximizes his/her utility.

The goal of the system is to design mechanisms that can maximize the social welfare (the total value of the accepted jobs). Once a job is accepted, it cannot be rejected or interrupted in the future. We use the competitive ratio [Parkes, 2007] to evaluate the performance of a mechanism, i.e., to compare the mechanism against the optimal offline solution.

Definition 1. A mechanism M is β-competitive in terms of social welfare if for any job sequence θ, we have SW(M, θ) ≥ 1/βOPT(θ), where SW(M, θ) denotes the social welfare achieved by M over θ and OPT(θ) denotes the optimal social welfare over θ.

It is easy to verify that no mechanism can achieve a constant competitive ratio if there is no restriction on lengths or value density of jobs. Therefore, we make the following assumptions.

• We assume the per-instance-hour valuation ρj = vj nj lj of every job is supported in [ρmin, ρmax].
• The length of every job falls in a known interval [lmin, lmax].

Denote k := ρmax ρmin and T := lmax lmin . Without loss of generality, we further assume ρmin = 1 and lmin = 1.

4 The Mechanisms

In this section, we design mechanisms for selling reserved instances. To warm up, we first consider a special case where all the jobs are tight. This case reflects the way that current clouds provide reserve services. Therefore it is helpful to study it separately to provide theoretical guideline to real applications. In addition, this case is much easier and can help to demonstrate the idea of our proposal.

We then extend our result to the general case in which jobs may be delayable.

In our mechanisms, when a job j arrives, we will set a pj for its request (ˆ rj, ˆ dj, ˆlj, ˆnj). If the job (agent) accepts the price and pays for it for its reservation, then we say our mechanism accepts the job.

4.1 A Simple Case with Tight Jobs

In this subsection, we consider a simple case that all jobs are tight, i.e. lj = dj - rj, ∀j. In other words, [rj, dj] is the exact reservation time period for request j. In the following, we first present our post-price mechanism and then prove that the competitive ratio of the mechanism is O(ln(kT )).

Let γj(t) denote the utilization rate of the cloud at time t when job j arrives, i.e.

where Sj denotes the set of jobs that come earlier than j and are accepted by the cloud.

Our proposed mechanism is shown in Mechanism 1, in which f(x) is an auxiliary function defined as below.

The intuitive requirement on the auxiliary function is that the price monotonically depends on the cloud utilization rate x: the higher the utilization rate, the higher the price. With this in mind, one can actually choose different forms of auxiliary functions, and will correspondingly obtain different competitive ratios. We show that this specific form can lead to a good competitive ratio.

Mechanism 1

Pricing rule:

When job j arrives,

• If j does not overfill the system (i.e. ∀t ∈ [⌊rj⌋, ⌈dj⌉), γj(t) + nj C ≤ 1), set price

• Otherwise, set price pj = +∞.

Allocation rule:

If j accepts the price pj and pays for it, allocate nj instances to j from rj to dj.

Note that when calculating the payment in the mechanism, we round the start time downwardly and the end time upwardly to integers. For example, for a job with rj = 0.5 and dj = 1.5, we will treat it as rj = 0 and dj = 2; if it is accepted, we will assume it occupies the allocated instances for the time interval [0, 2) while computing the utilization rate of the cloud, even if its actual reservation interval is [0.5, 1.5).

The purpose of such an operation is to ease the theoretical analysis.

Since Mechanism 1 gives a take-it-or-leave-it price, it is obviously truthful about user's private value. Recall that we restrict the misreports of each agent j to ˆ rj ≥ rj, ˆ dj ≤ dj, ˆlj ≥ lj and ˆnj ≥ nj. It is easy to check that Mechanism 1 is also truthful about other attributes.

By the definition of γj(t) we have the following observation.

Observation 1. For any tz ∈ Z+ and any j, the utilization rate γj(t) during [tz , tz + 1) is a constant.

Theorem 1. Mechanism 1 is IC, and its competitive ratio is at most 1 + 12 ln(3kT + 1) if all the jobs are tight and nj C ≤ ln(3/2) ln(3kT+1) , ∀j.

For any job sequence, denote S as the set of jobs accepted by Mechanism 1 and S∗ as the set of jobs accepted by the optimal offline algorithm. We need to prove

Since v(S ∩ S∗ ) ≤ v(S), we only need to prove

Let γ(t) be the utilization rate of time t after all the jobs in S have been accepted. We will prove the following inequalities separately (Lemmas 1-2), and then Theorem 1 follows directly.

Proof. Note that we assume all the jobs are rational. For any job j ∈ S∗ \ S, its rejection by the mechanism due to one of the two reasons: vj < pj or the system will over fill if accepting j. We show that in both cases,

If vj < pj , then by the definition of pj and the monotonicity of f(x), we have

If it is the over-fill case, by Observation 1, there must exist some time interval [t1, t2) ⊆ [⌊rj⌋, ⌈dj⌉) such that t2 -t1 ≥

1 and γj(t) + nj C > 1 for any t ∈ [t1, t2). According to the assumptions on job's attributes, we have

which combines with γj(t) + nj C > 1 for any t ∈ [t1, t2) implying

With all the above facts, we have

Recall that nj C ≤ ln(3/2) ln(3kT+1) . Thus we get (3kT + 1) nj C ≤ 3 2 . Furthermore,

The last inequality is from the fact that lj ≥ 1 and vj ≥ lj nj ρmin.

Therefore,

This completes the proof.

Proof. Since all the jobs in S are accepted by the mechanism and all the jobs are rational, we obtain

Since for any job j, lj = dj - rj ≥ 1 and its per-instancehour value is at least ρmin, we have

Using (3) and (4), we have

Thus we derive

This completes the proof.

4.2 The General Case with Delayable Jobs

In this subsection, we consider the general case that lj ≤ dj - rj for any job j. For this general case, we show that with a slight modification on Mechanism 1, we obtain a new mechanism with the same competitive ratio for the general case.

In our mechanism, for every job j, we will only consider allocating it to time interval [rj , rj +lj) or [tz , tz +lj), where tz ∈ Z and ⌈rj⌉ ≤ tz ≤ ⌊dj - lj⌋. Let a∗j denote the start time of the interval allocated to j if j is accepted by our mechanism. Apparently,

We still use γj(t) to denote the utilization rate of every time t according to the allocation of the mechanism when j arrives, i.e.

where Sj denotes the set of jobs that come earlier than j and are accepted by the cloud. Define AFj ⊆ Aj to be the set of feasible start time that if allocate j from this time, the system will not overfill, i.e.,

Besides, the auxiliary function f(x) is the same as that in the previous subsection.

Mechanism 2

Pricing rule:

When job j arrives,

• If AFj ̸= ∅, set price

• Otherwise, set price pj = +∞.

Allocation rule:

If j accepts the price pj, allocate j to time interval [a∗j , a∗j + lj), where

Note in Mechanism 2, an agent still does not need to reveal its private value. Now we show the competitive ratio of Mechanism 2 is also O(ln(kT)) for the case with delayable jobs.

Theorem 2. Mechanism 2 is IC, and its competitive ratio is at most 1+12 ln(3kT +1) if nj C ≤ ln(3/2) ln(3kT+1) , ∀j.

Proof. We still use S and S∗ to denote the sets of jobs that are accepted by Mechanism 2 and the optimal offline algorithm respectively. For any job j ∈ S∗ \ S, denote its allocated time interval by the optimal offline algorithm as [tj , tj + lj) ⊆ [rj, dj). Since j is rational and not accepted by our mechanism, it must be one of the following cases:

• The following inequality holds.

• There exists some time period [t1, t2) ⊆ [ ⌊tj ⌋, ⌈sj+lj⌉) such that γj(t) + nj C > 1, ∀t ∈ [t1, t2) and t2 - t1 ≥ 1.

Then similar to the proof of Theorem 1, we can still prove

and

where γ(t) is the final utilization rate after all jobs in S are accepted by Mechanism 2. Thus

This completes the proof.

4.3 Optimality of Our Mechanisms

One may wonder whether the competitive ratio bound of our mechanisms depends on the assumption that nj C ≤ ln(3/2) ln(3kT+1) , ∀j. In fact, without any restriction on nj and C, no deterministic algorithm can obtain a competitive ration better than C · kT . This can be seen from the following example.

Example 3. Consider two jobs. The first job has unit length, unit demand, unit value, and its reservation interval is [0, 1]. For the second job, its length is T, its number of machines is C, its value is C · kT and its reservation interval is [0, T], i.e., their types are (0, 1, 1, 1, 1) and (0, T, T, C, C · kT), respectively. The first job comes earlier than the second one. If an algorithm accepts the first job, the second job will not be accepted, and then the competitive ratio is at least C · kT. If the mechanism does not accept the first job, the second job will not show up, and then the competitive ratio is ∞.

Besides, in today's cloud industry, the capacity C is very large, e.g., a provider usually hosts tens of thousands of servers which can serve even more virtual instances. Therefore, our assumption holds in practice.

In the following, we give a lower bound Ω(ln(kT)) on the competitive ratio of any deterministic algorithm for the case nj = 1, ∀j. This bound shows that our mechanisms are optimal within a constant factor.

Theorem 3. The competitive ratio of any deterministic algorithm for this problem is at least ln(2kT).

Proof. We prove the theorem by constructing an example and show that no deterministic algorithm performs well for this example.

In this example we assume nj = 1 for any job j. Therefore the maximum value of any job j is at most kT .

Given any parameter η > 0. Let

Suppose there are M + 1 bundles of jobs. For i = 0, 1, . . . ,M ′ , the i-th bundle consists of C tight jobs with value (1 + η)i , and all the C jobs' reservation periods include a same time interval [t, t+1]. For i =M ′ +1, . . . ,M, the i-th bundle consists of 2C tight jobs with value 12 (1+η)i , half of which end at t+0.5, and the others start at t+0.5. Besides, the i-th bundle comes earlier than the (i +1)-th bundle for i = 1, 2, . . . ,M - 1.

Given any online algorithm. For i = 1, 2, . . . ,M ′ , let xi be the number of jobs in the i-th bundle accepted by the algorithm. For i =M ′ +1, . . . ,M, let yi (resp. zi) be the number of accepted jobs in i-th bundle that end at t + 0.5 (resp. start at t+0.5), and xi be yi+zi 2 . Since we can only accept at most C jobs that reserving a same time interval, thus we have

Adding the above two inequalities, we have

We first prove that there always exists some h (1 ≤ h ≤ M) such that

Denote Sj = ∑ji=0 xi ·(1+η)i (1+η)j . Then we have

Since all Sj ≥ 0, thus there must exist some h ∈ [1,M] such that Sh ≤ C(η+1) ηM .

If we only use the first h + 1 bundles as input, then the jobs that are accepted by the algorithm must be the same as the previous one (M + 1 bundles), and the total value of the accepted jobs is

However, apparently the optimal offline algorithm is to accept all the jobs in the h-th bundle whose social welfare is C · (1 + η)h . Then the competitive ratio of the given online algorithm is at least

Since limη→0 η ln(1+η) = 1, we derive the conclusion by setting η → 0.

5 FutureWork

In this work, we have designed two mechanisms with worstcase performance guarantee for selling reserved instances in cloud. There are multiple aspects to investigate to make the mechanisms practically useful.

First, we have assumed that the agents know the lengths of their reservations and required them to report their job lengths. It is possible that they do not have this knowledge. The cloud provider may need to take this responsibility. How to estimate the length of a job is an independent research topic.

Second, we have considered only one cloud provider. In today's cloud market, there are usually multiple providers offering the same or similar service. It is interesting to consider the competition between cloud providers.

Third, we have focused on social welfare maximization. Another research topic is revenue maximization for the cloud provider.