We consider the problem of optimal bid pricing in an auction for cloud computing resource allocation. The multistage model connected with the full-information best-choice problem is investigated. In this model, users set bids as a sequence of thresholds at each step to minimize the expected resource rent price. A form of the spot price distribution function is proposed based on real-life Amazon EC2 spot price dynamics. The optimal bid values, mean instance rent price and average step for buying the resource were found through simulations.
Cloud computing has a leading position in the IT-market, and is constantly increasing its market share. Public cloud computing resources are accessible, and allow users who require complex computing or other hardware and software tools to avoid software and hardware expenses and other costs. Also, these services respond exibly and quickly to the changing computing needs of the users. Cloud services have also become increasingly popular in the modern world, where it became necessary to work remotely. Therefore, the demand for such resources has lately increased signi cantly. With cloud services available, a user only has to pay the rent of the computing resource he/she needs and can then start using it immediately.
One of the major computing resources providers on the web is the cloud
computing platform Amazon EC2 [
In this paper, the following model of an auction for renting a spot resource
(see Ivashko et al. [
This paper is structured as follows. Section 2 o ers a brief review of related works. In Section 3, we outline the spot auction mechanism. The mathematical model of spot instance auctions is considered, and the strategy for minimizing the expected spot price is described in Section 4. Next, in Section 5, we investigate the spot price dynamics and conduct parameter tting for the distribution function of real data from real-like Amazon SI auctions. Finally, in Section 6, we present the ndings and conclusions, and draft plans for the future. 2
Di erent schemes based on competitive prices are used when buying/selling or renting resources. One can name various auctions and tenders, competition for computing resources or storage capacity. Cloud computing resources are gaining signi cance in the IT world. Therefore, a lot of research is going on in the area.
Research papers are dedicated to both exploring the existing pricing
mechanisms and behavior of real data, and proposing new mechanisms. There are
various approaches to analyzing cloud resource pricing. Di erent probabilistic
and statistical pricing models are considered in papers by Kumar et al. [
An important task is to model the competitive behavior of participants in various types of auctions. Online auction is the best example of modern markets. In an auction, it is necessary for a participant to determine his/her optimal strategy in order to increase the chance of winning.
Auction designs vary. Mechanisms for bidding in auctions for a computing resource are proposed in papers by Karunakaran et al. [9], Sowmya, Sundarraj [10], Tang et al. [11], and Wang et al. [12].
Optimal stopping models are often used to study the behavior of participants in socio-economic systems. The optimal stopping problems where the participants have to take the decision about choosing an item that ful lls certain criteria are also known as best-choice problems. One of the rst to describe the classical statement of the best-choice problem was Moser [13]. Such problems often arise in economics, nance, sociology and politics.
The users' optimal strategies are often derived using the dynamic programming method, in which a complex problem can be solved by breaking it down into simpler sub-problems represented as a recursive sequence. This method has various applications in di erent spheres, such as the house-selling problem, the job-search problem, or the mate-choice problem, and is successfully used in economic contexts for best-choice problems and auctions.
In some schemes of online auctions for buying an item or resource participants do not know in advance the exact current price. Each customer can set the threshold price value (bid) at which he/she agrees to buy the resource. During the auction the deal is made if the price o ered by a customer exceeds the current price. An important task is to analyze the behavior of participants in this type of auction. The optimal behavior of participants of various online auctions has been studied by the best-choice problem in papers by Harrall et al. [14], Mazalov, Ivashko [15], Babaio et al. [16].
Ivashko et al. [
In this paper, we use the model proposed by Ivashko et al. [
Elastic Compute Cloud platform (Amazon EC2) [
SIs are in high demand among users who do not need to use the resources continuously. SIs are well-suited for data analysis, batch jobs, background processing, and optional tasks. SIs are rented through an auction for unused capacity. Customers bid the maximum cost of instance per hour of use they would be ready to pay. If their bids exceed the spot price, they win the auction. All winning customers pay the same price, which is equal to the value of the lowest winning bid. This closed auction is a Vickrey auction. 4
This paper examines SIs and the auction for their allocation. The mathematical
best-choice model proposed by Ivashko et al. [
The optimal stopping theory deals with the problems of choosing the time to make a decision based on observing sequentially the random values. The aim is to maximize the expected payo . In the optimal stopping theory there is a class of best-choice problems. They arise from real choice processes. The best-choice problem with full-information is directly related to the problem of optimal bid pricing in a spot auction.
We describe the best-choice model as follows [
Full-information best-choice problems with nite horizon are solved by the dynamic programming method. Let us nd the optimal behavior of a customer. If the customer does not win a SI within the period n, he/she will have to buy it for the maximum price pmax. It makes sense for the customer to buy the SI at any price below or equal to pmax. So, the bid at the last step is n = pmax.
Because spot prices are independent and identically distributed random variables with a continuous cumulative distribution function F (x), the expected SI n price at the last step n is equal to R xdF (x). At the step n 1 the customer's pmin bid n 1 is the minimum between the current SI price and the expected cost at the n-th step: n 1 = E[minfX; ng] =
minfx; ngdF (x) = pmax
Z pmin
Z n pmin xdF (x) + pmax Z n ndF (x): Here, E[X] is the expectation of the random variable X.
Continuing the process, we get that the optimal bid value i at each step i is rendered by the system of recurrent equations: i = n = pmax; pmax
R pmin minfx; i+1gdF (x) =
Ri+1 xf (x)dx + pmRax pmin i+1 i+1f (x)dx; i = 1; :::; n where f (x) is the probability density function of the distribution F (x).
If the customer's bid 1 at the rst step does not win, the next bid 2 is used at the second step. Continuing this process, the customer is guaranteed to get an instance during the time period n with the minimum expected spot price. 1; (1) 5
We describe a method to derive the strategy for optimal bid pricing. We use real Amazon EC2 spot prices data [18]. Based on this history, we build the prices' probability density function and derive the optimal threshold bids using formula (1). Wolfram Mathematica platform is used for modelling.
Price histograms are plotted using spot price statistics. Figure 1 shows examples of price histograms for the instances us-east-1b m4.xlarge linux/UNIX and us-east-1b m4.2xlarge linux/UNIX.
Analyzing the data one can construct the prices probability density function, see Figure 1. We used the following truncated mixture of Gaussian distributions: b1
Take for example the optimal strategy modelling for the us-east-1e p2.8xlarge Linux/UNIX instance over the period of July12{August 30, 2019. We have N = 200 values of spot prices (see Figure 2).
Having the data we construct the histogram of prices (Figure 3). The step in the histogram is 1 + [log2 N ], N = 200.
Using the data we get in formula (2) b1 = pmin = 2:216; b2 = pmax = 3:048, where pmin corresponds to the minimum price over the entire period of time, and pmax corresponds to the maximum price.
We tested the statistical hypothesis using Pearson's chi-squared test ( 2). The null hypothesis H0 stated that the frequency distribution of certain events observed in a sample (using histogram) is consistent with a mixture of two Gaussian distributions. The alternative hypothesis H1 is that the frequency distribution does not have the form of a mixture of two Gaussian distributions. Having run the 2 test at a signi cance level = 0:05, we got P -V alue = 0:801189. As P -V alue > , so normally we would not reject the null hypothesis.
We estimate the unknown distribution parameters a1; 1; a2; 2; !1; !2 using an Expectation Maximization (EM) algorithm. The EM-algorithm is used to nd maximum likelihood parameters of a statistical model in cases where the equations cannot be solved directly.
We consider the vector of the estimated parameters = (!1; !2; a1; a2; 1; 2): The density function of the normal distribution has the form:
N (x; aj; j) = p 1 2 j e (x aj)2 2 j2 ; j = 1; 2: Let us consider two steps of the EM-algorithm: The expectation (E) step: gij = 2!jN(xi;aj; j) , i = 1; :::; m;
sP=1 !sN(xi;as; s) The maximization (M) step:
m !j = m1 iP=1 gij;
1 Pm gijxi; aj = m!j i=1
j2 = m1!j iP=m1 gij(xi aj)2; j = 1; 2; here, m is the number of elements in the sample, gij is the probability that the observation xi comes from the component j of the mixture of two Gaussian distributions.
We should iterate the steps E and M until convergence: until the value difference between a1, a2 at step h and a1, a2 at step h 1 is less than 10 4.
The application of the EM-algorithm yielded the estimations shown in Table 1.
Next, we get the optimal threshold values (bids) for n = 15 steps of the model using formula (1) (Table 2). As one can see, the sequence of bids is increasing with i, i = 1; :::; n.
To illustrate the optimal behavior let us consider the time period September 5 { 28, 2019 with the number of steps n = 15. In Figure 4 the optimal thresholds !1 !2 0.0701 0.9299 2.2404 2.6492 0.0149 0.1707 (grey line) and spot prices (black line) are presented at each step. Here, the acceptance step is i = 13, and the bid value which exceeded the spot price is equal to 2:5828.
In Table 3 the results on the optimized mean spot price and mean acceptance step are given for n = 5, n = 10, n = 15, and for 90 price values from time period September 7, 2019 { October 2, 2019.
As illustrated by Table 3, if the number of steps available in an auction increases, the mean acceptance step also grows, while the mean spot price decreases. As a result, the more steps are available for participating in the auction, the lower is the price at which a user can rent the resource.
n 5 10 15 This paper examines the problem of optimal bid pricing by cloud service users. The problem is connected with the full-information best-choice problem. Based on real data dynamics, the spot price distribution is modeled as a mixture of Gaussian distributions. Thus, we apply the theoretic model to real spot price dynamics. The optimal bid values, mean instance rent price and the acceptance step for buying the instance were found through simulations. These values allow winning the auction while minimizing the expected SI rent price.
In the future, new models for optimal bid pricing in spot auctions can be proposed. Various strategies can be compared to identify their respective bene ts and limitations. We collected the price history during one year and we can use these data to further research. Also the model where the prices are dependent random variable can be considered. For this case a new model can be constructed.