17 - Convex Optimization (Server Provisioning in Cloud Computing)

Summary

Introduction

In this chapter, we consider an important practical problem in modern data centres: how many servers to provision, given the uncertain demand, in the presence of a switching cost incurred in increasing or decreasing the number of active servers over time.

At a data centre, let the demand at time t be D(t) that is revealed causally over time. Dedicating S(t) number of servers at time t to support this demand, two types of costs are incurred; the quality of service cost depending on D(t), S(t) and the energy cost required to run the S(t) servers. The two costs are combined to produce a single cost function ft(St, Dt). In addition, because of obvious practical limitations, there is a penalty in changing the number of servers across time slots, captured by cost function c(S(t − 1), S(t)), where c is a specific function that increases with |S(t − 1) − S(t)|. Overall, the optimization problem is to choose S(t) with uncertain demand D(t) so as to minimize ft(St, Dt) + c(S(t − 1), S(t)) summed across time. This problem is popularly known as server provisioning for power-proportional data centers.

To model this popular and important problem, in this chapter, we consider a general framework of online convex optimization (OCO) with switching cost, where at each discrete time t, a convex function ft : d → + is revealed, and an algorithm has to choose an action xt knowing all f, ≤ t. The cost of choosing action xt at time t is the sum of the suboptimality/ hitting cost ft(xt), and the switching cost c(xt−1, xt). The goal is to choose xt, 1 ≤ t ≤ T such that the overall cost summed over T slots is minimized. Note that for the server provisioning problem, d = 1.

Problem Formulation

At each discrete time 1 ≤ t ≤ T, a non-negative convex function ft arrives such that ft : d → +. Let x⋆t = arg minx ft(x). Let x0 be fixed for time 0. On the arrival of the function ft at time t, the decision is to move from the current action xt−1 to a new action xt, where the total cost is the sum of two types of costs: (i) hitting cost ft(xt) and (ii) switching cost c(xt−1, xt).