PaperlayerView exact revision on arXiv

Source-linked AI summary

Energy-Aware Load Balancing in Content Delivery Networks

Vimal Mathew, Ramesh K. Sitaraman, Prashant Shenoy

arXiv:1109.5641v1cs.NIcs.DC

TL;DR

CDNs consume substantial energy, motivating energy-aware load balancing that balances energy reduction, service availability, and server-transition wear. The paper develops offline and online algorithms for local and global load balancing, finding more than 55% energy reduction while meeting customer SLAs and limiting transitions.

  • Problem

    CDNs operate hundreds of thousands of servers, and their energy costs are a significant fraction of total ownership costs.

  • Method

    The paper proposes optimal offline and online algorithms that save energy through local and global CDN load balancing while managing server transitions and availability.

  • Results

    More than 55% energy reduction is achieved while meeting customer SLA requirements, with 10% live spares absorbing global flash-crowd spikes and global load balancing substantially improving availability.

  • Takeaways & Limitations

    Keeping 10% of servers as hot spares provides a practical balance among energy reduction, five-nine availability, and at most one transition per server per day.

Abstract

from arXiv · show

Internet-scale distributed systems such as content delivery networks (CDNs) operate hundreds of thousands of servers deployed in thousands of data center locations around the globe. Since the energy costs of operating such a large IT infrastructure are a significant fraction of the total operating costs, we argue for redesigning CDNs to incorporate energy optimizations as a first-order principle. We propose techniques to turn off CDN servers during periods of low load while seeking to balance three key design goals: maximize energy reduction, minimize the impact on client-perceived service availability (SLAs), and limit the frequency of on-off server transitions to reduce wear-and-tear and its impact on hardware reliability. We propose an optimal offline algorithm and an online algorithm to extract energy savings both at the level of local load balancing within a data center and global load balancing across data centers. We evaluate our algorithms using real production workload traces from a large commercial CDN. Our results show that it is possible to reduce the energy consumption of a CDN by more than 55% while ensuring a high level of availability that meets customer SLA requirements and incurring an average of one on-off transition per server per day. Further, we show that keeping even 10% of the servers as hot spares helps absorb load spikes due to global flash crowds with little impact on availability SLAs. Finally, we show that redistributing load across proximal data centers can enhance service availability significantly, but has only a modest impact on energy savings.

I. INTRODUCTION

CDNs can reduce energy by turning off servers during low-load periods, but must balance energy savings against service availability and server-transition wear. The paper proposes offline and online load-balancing mechanisms and evaluates their tradeoffs on production CDN workloads.

  • Motivation: CDNs deploy hundreds of thousands of servers across thousands of data centers, making energy use a significant ownership cost and environmental concern.A 100,000-server platform is estimated to consume roughly 190,000 MWH annually.
  • Design objectives: Idle servers can consume more than 50% of full-load power, creating an opportunity to consolidate traffic and turn excess servers off.This optimization must preserve sufficient live capacity for incoming requests.
  • Design objectives: The design balances energy reduction, customer-SLA availability, and limited on-off transitions because load spikes and frequent cycling can respectively cause service failures and hardware wear.Turning servers back on takes time, while transitions can affect lifetime and reliability.
  • Approach: The offline algorithm varies the number of live servers using complete future load information, while Hibernate makes online decisions from past and current load.Both approaches target energy savings through local and global load balancing.
  • Results: 64.2% system-wide energy reduction is achieved offline, while 55.9% remains possible below 1 transition per server per day.The latter represents 87% of the maximum energy reduction.
  • Results: 60% energy reduction is achieved by Hibernate, within 94% of the offline optimum.The online algorithm uses no future-load information.
  • Results: With 10% live spares, Hibernate achieves 55% energy reduction, at least 99.999% availability, and at most 1 transition per server per day.The spare pool also supports five-nines availability during global flash crowds when load growth matches retained spare capacity.
  • Results: Global load balancing across proximal clusters has modest energy impact but can reduce server transitions by 10% to 25% and raise simulated availability to almost 100%.Redistribution can spread unexpected load increases to clusters with available live capacity.

II. BACKGROUND

The paper models CDN load balancing across servers and clusters, incorporating server power, transition energy, workload variability, and operational assumptions.

  • CDN Model: CDNs use global load balancing to select clusters and local load balancing to assign requests to individual servers.The model assumes load can be redistributed arbitrarily within and across clusters.
  • Energy Model: The server power model uses load ratio λ, with Ppeak = 92 Watts and Pidle = 63 Watts.The simulations use a linear model, while the algorithmic results also hold for convex power functions.
  • Energy Model: Server transitions consume fixed energy α, typically 37 kiloJoules, and take several minutes while servers cannot serve load.Shutdown and startup require traffic draining or migration and control-state migration.
  • Load Balancing: Local balancing keeps each live server at or below threshold Λ while deciding how many servers to activate or deactivate for the next interval.The incoming cluster load λt is divided among mt live servers, with λt ≤ Λmt.
  • Empirical Data: The evaluation uses 25-day traces from 22 US clusters containing 15,439 servers and reaching 800K requests/second peak traffic.The traces include 950 million delivered requests and cover the 2008–2009 holiday shopping season.

III. LOCAL LOAD BALANCING

The paper develops optimal offline and practical online algorithms for energy-aware local load balancing, evaluating practical performance against theoretical baselines.

  • Algorithmic Approach: The study first derives optimal offline algorithms and then develops online algorithms for realistic CDN load traces.The online algorithms are compared with the energy reductions achievable by the offline baselines.
  • Algorithmic Approach: The algorithms target energy savings while accounting for server transitions and load-balancing feasibility.This frames local load balancing as a comparison between implementable policies and theoretically optimal schedules.
  • Evaluation: The evaluation uses realistic CDN traces to quantify how closely online policies approach the offline optimum.The offline algorithms provide theoretical baselines for assessing practical online performance.

A. An Optimal Offline Algorithm

The offline algorithms optimize CDN energy use subject to load-feasibility and transition constraints, then quantify achievable reductions and availability on production traces.

  • Optimization Formulation: The offline schedule selects live-server counts mt satisfying λt ≤ Λmt while minimizing server and transition energy.The schedule is converted into an on-off plan for the cluster’s servers.
  • An Optimal Offline Algorithm: Dynamic-programming algorithm OPT finds the minimum-energy schedule in O(nM^2) time and O(nM) space.Its state records the minimum energy through time t for each possible number of live servers.
  • Bounded Transitions: Algorithm OPT(k) minimizes energy while allowing no more than k total server transitions.It extends the dynamic-programming state with a transition-budget dimension and runs in O(nM^2K) time.
  • Empirical Results: 64.2% system-wide energy reduction is achieved by OPT across the 22-cluster trace, with individual clusters ranging from 50% to 87%.The experiments use a load threshold of Λ = 75%.
  • Empirical Results: 55.9% system-wide energy reduction is achieved with an average of 1 transition per server per day, exceeding 87% of the unbounded-transition benefit.The unbounded case asymptotically reaches 64.2% reduction.
  • Availability: OPT and OPT(k) achieve 100% availability because complete load-sequence knowledge lets them provision live servers before each time slot.Their schedules never drop load under the offline model.

B. Online Algorithms

Hibernate is an online load-balancing algorithm that manages live spare servers to trade off energy reduction, availability, and server transitions. Its behavior varies with utilization thresholds and spare capacity, including during simulated global flash crowds.

  • Hibernate uses past and current load, not future load, to estimate server transitions and balance energy, availability, and transition frequency.
  • Hibernate maintains spare capacity to absorb unpredictable traffic surges while turning off servers that remain spare for τ consecutive time slots.The algorithm uses spare threshold κ and time threshold τ.
  • Typical workload fluctuations: Increasing Λ raises energy reduction and generally lowers transitions, but decreases availability by reducing headroom for temporary load spikes.
  • Global flash crowds: A simulated global flash crowd applies a 30% capacity spike for one hour simultaneously across 22 clusters during a low-traffic period.
  • Global flash crowds: With spare capacity sized to the load-increase rate, Hibernate maintains five-nine availability and customer SLAs during global flash crowds.

IV. GLOBAL LOAD BALANCING

The paper evaluates whether redistributing requests across geographically proximal clusters improves energy-aware CDN load balancing. Global balancing adds modest energy savings, reduces transitions, and substantially improves availability through cross-cluster averaging.

  • The evaluation groups clusters in the same metropolitan area so global load balancing can redistribute requests between locations with roughly equivalent performance.
  • Global load balancing adds 4% to 6% energy savings because clusters in each set have broadly similar peak and off-peak load patterns.
  • Global load balancing reduces average transitions by 10% to 25% by serving spikes in one cluster with spare capacity in another.
  • Availability was nearly 100% in all simulated cluster sets because load fluctuations could be averaged across clusters.

V. RELATED WORK

Prior work addresses data-center energy management and server activation, while this paper focuses on CDN workloads and explicitly incorporates SLA constraints into energy-aware load balancing.

  • Earlier data-center studies use techniques including DVFS, low-power servers, energy-price-aware routing, and dynamic node activation.
  • A related study also develops offline and online server on-off algorithms, but targets clustered mail servers rather than CDN workloads.
  • Unlike the related study, this work emphasizes SLA issues because CDN violations can cause revenue losses.

VI. CONCLUSIONS

The paper presents energy-optimization techniques for CDNs that balance energy reduction, SLA availability, and server-transition frequency. Evaluation on production traces shows substantial energy savings with SLA compliance, while future work targets prediction, global balancing, and disk-state management.

  • Contributions: The proposed offline and online algorithms optimize CDN energy use through local and global load balancing while balancing availability and server-transition objectives.They turn off servers during low-load periods and operate within and across data centers.
  • Results: More than 55% energy reduction was achieved while meeting customer SLA requirements with only a modest number of daily on-off transitions per server.The evaluation used real production workload traces from a large commercial CDN.
  • Results: Keeping 10% of servers as hot spares helped absorb global flash-crowd load spikes with little impact on availability SLAs.
  • Future work: Future work includes workload prediction, energy optimization of global load balancing, and management of customer disk footprints during server transitions.
Loading 1109.5641v1…