Paper Info
Title
Optimal Algorithms for Right-Sizing Data Centers - Extended Version.
Abstract
Electricity cost is a dominant and rapidly growing expense in data centers. Unfortunately, much of the consumed energy is wasted because servers are idle for extended periods of time. We study a capacity management problem that dynamically right-sizes a data center, matching the number of active servers with the varying demand for computing capacity. We resort to a data-center optimization problem introduced by Lin, Wierman, Andrew and Thereska that, over a time horizon, minimizes a combined objective function consisting of operating cost, modeled by a sequence of convex functions, and server switching cost. All prior work addresses a continuous setting in which the number of active servers, at any time, may take a fractional value. In this paper, we investigate for the first time the discrete data-center optimization problem where the number of active servers, at any time, must be integer valued. Thereby we seek truly feasible solutions. First, we show that the offline problem can be solved in polynomial time. Our algorithm relies on a new, yet intuitive graph theoretic model of the optimization problem and performs binary search in a layered graph. Second, we study the online problem and extend the algorithm Lazy Capacity Provisioning (LCP) by Lin et al. to the discrete setting. We prove that LCP is 3-competitive. Moreover, we show that no deterministic online algorithm can achieve a competitive ratio smaller than 3. We develop a randomized online algorithm that is 2-competitive against an oblivious adversary and prove that 2 is a lower bound for the competitive ratio of randomized online algorithms. Finally, we address the continuous setting and give a lower bound of 2 on the best competitiveness of online algorithms. All lower bounds mentioned above also holds in a problem variant with more restricted operating cost functions, introduced by Lin et al.
Year
Venue
Field
2018
arXiv: Data Structures and Algorithms
Online algorithm,Time horizon,Upper and lower bounds,Server,Algorithm,Binary search algorithm,Time complexity,Optimization problem,Mathematics,Competitive analysis
DocType
Volume
Citations 
Journal
abs/1807.05112
0
PageRank 
References 
Authors
0.34
10
2
Name
Order
Citations
PageRank
Susanne Albers11538107.42
Jens Quedenfeld201.35