Algorithms for right-sizing heterogeneous data centers

Susanne Albers, Jens Quedenfeld

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Power consumption is a dominant and still growing cost factor in data centers. In time periods with low load, the energy consumption can be reduced by powering down unused servers. We resort to a model introduced by Lin, Wierman, Andrew and Thereska (23,24) that considers data centers with identical machines, and generalize it to heterogeneous data centers with d different server types. The operating cost of a server depends on its load and is modeled by an increasing, convex function for each server type. In contrast to earlier work, we consider the discrete setting, where the number of active servers must be integral. Thereby, we seek truly feasible solutions. For homogeneous data centers (d=1), both the offline and the online problem were solved optimally in (3,4) In this paper, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach which achieves a competitive ratio of 2d + 1 + ϵ for any ϵ > 0. For time-independent operating cost functions, the competitive ratio can be reduced to 2d + 1. There is a lower bound of 2d shown in (5), so our algorithm is nearly optimal. For the offline version, we give a graph-based (1+ϵ)-approximation algorithm. Additionally, our offline algorithm is able to handle time-variable data-center sizes.

Original languageEnglish
Title of host publicationSPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages48-58
Number of pages11
ISBN (Electronic)9781450380706
DOIs
StatePublished - 6 Jul 2021
Event33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021 - Virtual, Online, United States
Duration: 6 Jul 20218 Jul 2021

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021
Country/TerritoryUnited States
CityVirtual, Online
Period6/07/218/07/21

Keywords

  • Approximation algorithm
  • Competitive analysis
  • Discrete setting
  • Energy conservation
  • Heterogeneous machines
  • Online algorithm

Fingerprint

Dive into the research topics of 'Algorithms for right-sizing heterogeneous data centers'. Together they form a unique fingerprint.

Cite this