TL;DR
This paper introduces competitive online algorithms for optimizing data center energy costs by combining geographical load balancing and energy storage. These algorithms offer worst-case performance guarantees against optimal offline solutions, outperforming traditional Lyapunov optimization methods, especially in scenarios with finite time horizons and limited storage.
What Problem Does This Paper Address?
Data centers are massive energy consumers, and their operational costs are escalating. To combat this, two strategies have emerged: geographical load balancing (shifting computing tasks to data centers with lower electricity prices) and energy storage management (storing energy when cheap and using it when expensive). While previous work has explored these individually or combined them using Lyapunov optimization, these approaches often rely on asymptotic analysis, assuming infinite time horizons and arbitrarily large energy storage. This paper addresses the practical limitations of these assumptions by developing online algorithms that work effectively with finite time horizons and smaller-to-medium energy storage capacities, providing robust performance guarantees.
Methods
The core contribution is the development of "competitive online algorithms." Unlike methods that predict future electricity prices or workloads, these algorithms make decisions in real-time based only on current and past information. They are designed to achieve a "competitive ratio," which is a worst-case measure of how close their performance is to the ideal solution that knows all future information.
The paper presents two main algorithms:
- Basic Online Algorithm (Algoth): This algorithm uses a "1-min search" approach. It prioritizes using energy from storage, then considers charging storage from the grid if prices are low, and finally satisfies remaining workload from the cheapest available grid source. A key element is a dynamically determined price threshold for charging the energy storage.
- Improved Online Algorithm (Algok): This algorithm builds upon the basic one by dividing the energy storage into k units. This allows for more granular control over charging and discharging, potentially leading to better utilization and cost savings. It also employs a threshold-based strategy for grid charging.
Both algorithms are analyzed using competitive analysis, providing theoretical bounds on their performance relative to an offline optimal solution.
Datasets
The paper uses real-world traces for evaluation:
- Workload Data: Website access traces from Wikipedia (September 2007) were used. The data was processed to derive workload for four data centers (Chicago, New York, Palo Alto, Houston) by counting web accesses every 10 minutes.
- Electricity Rates: Real-time locational marginal prices for the same four locations (Chicago, New York, Palo Alto, Houston) were used, sampled at 5-minute intervals.
The authors note that their model can incorporate QoS constraints but focus on energy storage management for clarity.
Key Insights and Ideas
- Competitive Analysis for Practical Scenarios: The paper demonstrates that competitive analysis, which provides worst-case guarantees, is a powerful tool for designing energy management algorithms that work reliably even with uncertain future inputs and limited resources (finite time, small storage).
- Energy Storage Utilization: The proposed algorithms show significantly better energy storage utilization compared to Lyapunov optimization. This suggests that Lyapunov's tendency to maintain a narrower fluctuation scope might lead to underutilization and missed cost-saving opportunities.
- Threshold-Based Decision Making: The use of dynamic price thresholds for charging energy storage is a crucial mechanism that balances the cost of grid electricity against the potential benefits of storing it for later use.
- Decomposition into One-Shot Workloads: The theoretical analysis leverages the concept of decomposing arbitrary workloads into "one-shot" workloads (a single burst of activity). This simplifies the analysis and allows the competitive ratio of the complex problem to be related to simpler, well-understood online search problems.
Key Results
- Significant Cost Savings: Simulations show that the proposed online algorithms (both basic and improved) outperform the Lyapunov optimization algorithm by approximately 40% and 50% in terms of cost savings, respectively.
- Theoretical Guarantees: The paper provides theoretical competitive ratios for the proposed algorithms, bounding their performance against the offline optimal solution. For the basic algorithm, the competitive ratio is bounded by $\frac{\sqrt{8Mm} + M^2 + M}{4m}$. The improved algorithm's ratio is more complex and depends on a parameter k and a fixed-point solution.
- Improved Storage Utilization: Visualizations (Figure 5) indicate that the proposed algorithms utilize a much larger portion of the energy storage capacity (up to 100%) compared to Lyapunov optimization (15-25%).
Limitations and Future Work
- QoS Constraints: While the paper mentions that QoS constraints can be incorporated, the primary focus and evaluation are on energy cost minimization. Future work could explore the trade-offs between cost savings and QoS guarantees more deeply.
- Simplified Energy Storage Model: The paper assumes ideal charging/discharging efficiencies ($n_c=n_d=1$) for simplicity in some analyses, though the algorithms are designed to handle non-ideal efficiencies. The impact of more complex battery degradation models or maintenance costs is not considered.
- Parameter Tuning: The improved algorithm introduces a parameter k (number of storage units). While the paper suggests a value of 40 for simulations, optimal tuning of k for different scenarios could be an area for further research.
- Real-world Deployment: The simulations are based on real-world data, but actual deployment in a live data center environment would involve additional complexities like network latency, communication overhead, and more dynamic workload patterns.
Summary updated