## 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 [17, 19] 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. [17, 19] 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. Hence, while LCP does not attain an optimal competitiveness in the continuous setting, it does so in the discrete problem examined here. We prove that the lower bound of 3 also holds in a problem variant with more restricted operating cost functions, introduced by Lin et al. [17]. Finally, we address the continuous setting and give a lower bound of 2 on the best competitiveness of online algorithms. This matches an upper bound by Bansal et al. [5]. A lower bound of 2 was also recently shown by Antoniadis and Schewior [3]. We develop an independent proof that extends to the scenario with more restricted operating cost.

Original language | English |
---|---|

Title of host publication | SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures |

Publisher | Association for Computing Machinery |

Pages | 363-372 |

Number of pages | 10 |

ISBN (Electronic) | 9781450357999 |

DOIs | |

State | Published - 11 Jul 2018 |

Event | 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 - Vienna, Austria Duration: 16 Jul 2018 → 18 Jul 2018 |

### Publication series

Name | Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|

### Conference

Conference | 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 |
---|---|

Country/Territory | Austria |

City | Vienna |

Period | 16/07/18 → 18/07/18 |

## Keywords

- Discrete setting
- Homogeneous servers
- Lower bounds
- Online algorithm
- Polynomial-time offline algorithm