18.1.1 Dynamic Scheduling and Server Consolidation for Fixed Pricing Scheme

In the fixed pricing scheme, each VM type has a fixed price that does not fluctuate with the current supply and demand situation. Hence, the virtual machine revenue maximization problem (VRMP) can be modeled as a multiple knapsack problem (MKP) as follows: given a set of machines and resource types (differed in CPU, memory, and disk), where each machine has a capacity for each type of VM . The set of VMs to be scheduled is and each VM has a size for each and a value . To formulate the optimization problem, we would first choose the optimization variable (which is the VM scheduling parameter ), then define the objective and constraints. As we mentioned earlier, the objective is to maximize the total value, which is the summation of all of the chosen VMs(for a chosen VM, ; for an abandoned VM, ), which is . While the constraints for this goal is the machine capacity, that is, the summation of the size of all chosen VMs should be smaller than or equal to . On the basis of the intuition above, the problem can be formulated as

18.1

It can be noticed that this MKP formulation is an NP-hard combinatorial optimization problem, we propose a local search algorithm [14] that can approximate the optimal solutions, which is specified by Algorithm 18.1. In this algorithm, is the current set of VMs on machine , is the set of VMs chosen to maximize the total value, and isthe value of VM . As it is depicted, the algorithm proceeds in rounds. For each round, first maximize the total revenue among pending requests and current running VMs on machine ; then if there is a potential new configuration for by scheduling, first try to schedule all VMs using available free capacity and then preempt and migrate VMs when the total demand is reaching capacity. To achieve fast convergence rate, we require each local search operation to improve solution quality for each machine by at least .

18.1.2 Price Estimation for the Uniform Pricing Scheme

We now consider the case in which the price of each instance vary with the demand–supply curve and the resource availability. In this scenario, above all, we need to periodically analyzes the market situation and predict the demand and supply curves, on which the price of instances depend. The prediction of the demand curves can be constructed by capturing the relationship between the quantity of acceptable requests and the bidding price(as shown in Figure 18.2) over time period at sampling interval , where denotes the current time and denotes the prediction period. Then we can decide the expected price for each type of VM in each market based on the prediction. Finally, we will be able to make online scheduling decisions for revenue maximization.

Let denote the th bidding price in decreasing order, denote the demand that bids at price , and denote the demand that bids at price at least at time . As the spot instances mechanism allows requests with bidding prices higher than or equal to the spot price to be accepted, then when equals , we can schedule VM requests. (Demand curve as shown in Fig. 18.2.) As the bidding price of each individual VM request is independent of the current market situation, we can model the demand quantity to independently for each to predict the expected demand curve. Then we are able to predict the future demand for each from to . Our approach to do this is to adopt an autoregressive (AR) model [15] that estimates from the historical values as

where with is the set of parameters of the historical values and is uncorrelated white noise with mean 0 and standard deviation , and all these parameters can be obtained from historical demand data. This is an appropriate model because it is not only lightweight and easy to implement but also capable of capturing short-term trends to let us compute the expected demand curve.

Now we have the demand and supply curve, our objective is now to schedule requests of each spot market to maximize the expected revenue over the next prediction period. This dynamic revenue maximization with variable price (DRMVP) problem is identical to the former VRMP except that price of individual VMs is determined by the estimated demand curve . Again to formulate the optimization problem, first, we choose the same optimization variable as in Section 18.1.1, which is the scheduling vector of VMs. The difference is this time the variable varies with time because the price varies with time based on the demand curve, so it is defined as . And the objective is the sum of the revenue over demand prediction period , subject to the constraints that the total VMs scheduled during time should be smaller than or equal to the total number of VM requests in , and the total size of all chosen VMs should not exceed the machine capacity, noticed that each VM size here also varies with time because of demand curve prediction. Now we can model this problem as follows:

18.2

As the objective function of this optimization problem is nonlinear, the problem is even more difficult to solve that of the fixed priced case; however, the revenue function for a single VM type is a piecewise linear function, and it can be observed from the using examples in Figure 18.2. In some situations, scheduling a VM can cause the current market price to be lowered, resulting in a sharp drop in total revenue. Thus motivated by similar work on market clearing algorithms for piecewise linear objective functions, our approach to deal with this issue is to approximate using a concave envelope function , which is computed by constructing a upper convex hull using the extreme points in . has the following property.

18.3.1 Electricity Cost

In the electricity market of North America, Regional Transmission Organization (RTO) is responsible for transmit electricity over large interstate areas and electricity prices are regionally different. Electricity prices remain the same for a relatively long period in some regions, whereas they may change every hour, even 15 min in the regions who have wholesale electricity markets [9, 17, 18]. In this paper, we consider cloud computing services consisting of distributed regional data centers, which are subject to different electricity prices. When servers at each data center are homogeneous, the total electricity consumption at each data center over period can be calculated directly by multiplying the number of active servers and the electricity consumption per server . Let be the electricity price of data center at time . We also assume that for is known noncausally at the beginning of each billing cycle. In practice, this can be achieved by stochastic modeling of electricity prices [24, 25] or by purchasing forward electricity contracts in the whole sale market [26, 27]. Thus the total electricity cost for data centers over the next cycle is given as

18.6

18.3.2 Workload Constraints

We denote the number of VM instances received by job from data center at period as . We consider two types of jobs: divisible jobs and indivisible jobs. An indivisible job that requires VM instances and a subscription time cannot be interrupted and must have VM running continuously for periods, whereas a divisible job can be partitionedarbitrarily into any number of portions, as long as the total VM instance hour is equal to the demand . Each portion of a divisible job can run independently from other portions. Examples of applications that satisfy this divisibility property include image processing, database search, Monte Carlo simulations, computational fluid dynamics, and matrix computations [28]. Given the scheduling decisions of all jobs, the aggregate workload for each regional data center must satisfy a service rate constraint

18.7

where is the service rate per server at regional data center and is the number of active server at time . There is also a limitation on the number of servers at each location. Therefore, we have

18.8

All user requests for the next cycle are collectively handled by a job scheduler, which decides the location and time for each job to be processed in a judiciary manner. This scheme can be viewed as a generalization of existing on-spot VM instances in Amazon EC2, which allows users to bid for multiple periods and different job deadlines (or job completion times). The system model is illustrated in Figure 18.5. Let denote the scheduled completiontime of job , the total revenue received by the cloud provider over the next cycle is given as

18.9

The goal of this paper is to design a job scheduler that maximizes the net profit over feasible scheduling decisions , subject to the workload constraints. For a given job completion time , we denote the set of all feasible job scheduling decisions by a set . In particular, for a divisible job, a user is only concerned with the total VM instance hour received before time . This implies

18.10

where is the total demand of job . On the other hand, an indivisible job must be assigned to a single regional data center and run continuously before completion. It will have a feasible scheduling set as

18.11

where is an indicator function and equals to 1 if belongs to the scheduled execution interval and 0 otherwise. We suppress the positivity constraints of for simplicity of expressions.

We formulate the data center NPO problem as follows:

18.12

18.13

18.14

18.15

18.16

The above problem can be looked at graphically as illustrated in Figure 18.5. It requires a joint optimization of revenue and electricity cost, which is a mixed-integer optimization because the scheduling decisions are discrete for indivisible jobs. Further, because of our deadline-dependent pricing mechanism, the maximization of revenue over completion time is coupled with the minimization of electricity cost over feasible scheduling decisions . However, there is no closed-form, differentiable function that represents by . Therefore, off-the-shelf optimization algorithms cannot be directly applied.

It is worth noticing that our formulation of Problem NPO in Eq. (18.12 ) also incorporates sharp job deadlines. For instance, if job must be completed before time , we can impose a utility function with , for all , so that scheduling decisions with a completion time later than becomes infeasible in Problem NPO.

Problem NPO is a complex joint optimization over both revenue and electricity cost, whose optimization variables; scheduling decisions and job completion time are not independent of each other. There is no closed-form, differentiable function that relates the two optimization variables. Let be the aggregate service rate received by job at time . For given scheduling decisions , we could have replaced constraint (18.15 ) by a supremum

18.17

where is the total demand of job . However, it still requires evaluating supremum and inequalities and, therefore, does not yield a differentiable function to represent by scheduling decisions .

To overcome this difficulty, an approximation of the job completion time function in Eq. (18.17 ) by a differentiable function is proposed in Reference [12]:

18.18

where is a positive constant and normalizes the service rate . The accuracy of this approximation is given as follows.

By the approximation in Eq. (18.18 ), we obtain a closed-form, differentiable expression for , which guarantees an approximated completion of job off by a logarithmic term in the worst case. The approximation becomes exact as approaches infinity. However, often there are practical constraints or overhead concerns on using large . We choose an appropriate such that the resulting optimality gap is sufficiently small.

An algorithmic solution for Problem NPO with divisible jobs is derived in Reference [12]. The problem has a feasible set:

18.20

In order to solve the problem, we leverage the approximation of job completion time in Eq. (18.18) to obtain an approximated version of Problem NPO. The resulting problem has an easy-to-handle analytical structure and is convex for certain choices of functions. Further, when the problem is nonconvex, we then convert it into a sequence of linear programming and solve it using an efficient algorithm. It provides useful insights for solving Problem NPO with indivisible jobs.

Rewriting Eq. (18.15 ) in Problem NPO using the approximation in Eq. (18.18 ) and the feasible set in Eq. (18.20 ), we obtain a net profit optimization problem for divisible jobs (named Problem NPOD) as follows:

18.21

18.22

18.23

18.24

18.25

18.26

18.27

where completion time becomes a differentiable function of . The optimization variables in Problem NPOD may still be integer variables, that is, the number of active servers and the number of demanded VM instances . We can leverage rounding techniques (e.g., [29]) to relax Problem NPOD so that its optimization variables become continuous.

As inequality constraints in Eqs. (18.23 ), (18.24 ), and (18.26 ) are linear, we investigate the convexity of the optimization objective in Eq. (18.22 ), which is a function of and , by plugging in the equality constraint (18.25 ). It is shown [12] that for in Eq. (18.25 ) and a positive differentiable , the objective function of Problem NPOD is convex if for all and concave if for all . The two conditions of capture a wide range of functions in practice. Let and be arbitrary constants. Examples of that result in a concave objective function include certain exponential and logarithmic functions. Examples that result in a convex objective function include linear and logarithm . We remark that when for all , Problem NPOD is a concave maximization. It can be solved efficiently by off-the-shelf convex optimization algorithms, for example, primal-dual algorithm and interior point algorithm [30].

On the other hand, when Problem NPOD maximizes a convex objective, an iterative solution based on difference of convex programming is proposed [12]. Relying on a linearization of the objective, the following iterative algorithm is used to solve Problem NPOD via a sequence of linear programming. It starts at some random initial point , solves the linear programming with , and, therefore, generates a sequence . This procedure is indeed a special case of the difference of convex programming and has been extensively used in solving many nonconvex programs of similar forms in machine learning [31]. It is shown that the sequence converges to a local minimum or a saddle of Problem NPOD, as in Theorem 18.2. We further apply a primal-dual algorithm [30] to obtain a distributed solution to each linear programming. The algorithm is summarized in Fig. 18.6.

Finally, we evaluate our algorithmic solution for Problem NPOD over a 24-h cycle, divided into 10-min periods. The goal is to obtain empirically validated insights about the feasibility/efficiency of our solution using synthesized data from a recent study [9]. We construct regional data centers, which reside in different electricity markets and have electricity prices $ , $ , and $ . The data centers host , , and servers. Each server is operating at W with VMs per server for .

We construct two types of jobs: elephant jobs that subscribes VMs for periods and mice jobs that subscribes VMs for periods. In our simulations, both and areuniformly randomly generated from their ranges. We fix the total workload to be jobs, each being an elephant job with probability and a mice job with probability . Job is associated with a nonlinear bid function, given by

18.28

where and are uniformly distributed. Using this nonlinear bid function, the approximation of job completion time will result in a convex objective function in Eqs. (18.12 ) and (18.22 ). All numerical results shown in this section are averaged over five realizations of random parameters.

To provide benchmarks for our evaluations, we also implement a greedy algorithm that sequentially schedules all jobs with a largest job first (LJF) policy and a heuristic algorithm NPOI (net profit optimization problem for indivisible jobs) by assuming indivisible jobs in problem NPOI. Figure 18.7 compares the optimized net profit of NPOD, NPOI, and LJF algorithms. When jobs are indivisible, our NPOI algorithm improves the net profit by over the baseline LJF algorithm (from $1868 to $2095), while an additional increment (to $2394) can be achieved by NPOD if all jobs are divisible. We also notice that our NPOI algorithm is able to simultaneously improve total revenue and cut down electricity cost, compared to the baseline LJF algorithm. This is achieved by the joint optimization over job completion time and scheduling decisions .