PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Power Cost Management Using Stored Energy in Data Centers

Rahul Urgaonkar, Bhuvan Urgaonkar, Michael J. Neely, Anand Sivasubramaniam

arXiv:1103.3099v2cs.PFeess.SYmath.OC

TL;DR

Data centers face substantial electricity costs, motivating opportunistic use of UPS batteries as energy storage rather than only outage bridges. The paper develops a Lyapunov-optimization online controller that uses UPS storage and delay-tolerant workload without process statistics, with cost approaching optimality as battery capacity increases.

  • Problem

    The paper addresses how to reduce a data center’s time-average electricity bill by opportunistically using UPS storage amid time-varying workloads and prices.

  • Method

    Lyapunov optimization is used to design an online control algorithm that exploits UPS storage and delay-tolerant workloads without requiring workload or cost statistics.

  • Results

    The dynamic algorithm’s average cost approaches the optimal value as battery capacity increases and performs close to the corresponding offline optimum even for smaller capacities.

  • Takeaways & Limitations

    UPS units can serve as energy-storage devices for data-center electricity-bill management, extending their role beyond transitional outage support.

Abstract

from arXiv · show

Since the electricity bill of a data center constitutes a significant portion of its overall operational costs, reducing this has become important. We investigate cost reduction opportunities that arise by the use of uninterrupted power supply (UPS) units as energy storage devices. This represents a deviation from the usual use of these devices as mere transitional fail-over mechanisms between utility and captive sources such as diesel generators. We consider the problem of opportunistically using these devices to reduce the time average electric utility bill in a data center. Using the technique of Lyapunov optimization, we develop an online control algorithm that can optimally exploit these devices to minimize the time average cost. This algorithm operates without any knowledge of the statistics of the workload or electricity cost processes, making it attractive in the presence of workload and pricing uncertainties. An interesting feature of our algorithm is that its deviation from optimality reduces as the storage capacity is increased. Our work opens up a new area in data center power management.

I. INTRODUCTION

Data-center electricity costs vary over time, while workload and pricing uncertainty constrain conventional demand-response strategies. The paper proposes using UPS batteries as storage and Lyapunov optimization for online, near-optimal cost management.

  • Motivation: Electricity bills account for 30-50% of data-center operational expenses, and minimizing energy consumption need not minimize the electricity bill.A 15MW data center may spend about $1M monthly on electricity; prices vary across time, geography, and utility providers.
  • Motivation: Demand-response methods shift power draw across times, locations, or utilities, but workload performance requirements can limit their cost-reduction benefits.Energy storage provides a complementary mechanism for moving power needs without relying solely on workload scheduling or shifting.
  • UPS-Based Storage: UPS units can bridge utility outages for 10-20 seconds while retaining enough battery capacity to power a data center at maximum demand for 5-30 minutes.The paper exploits these reserves by charging when prices are low and augmenting utility power when prices are high.
  • Problem: The paper targets an online control policy that uses UPS storage and delay-tolerant workload to minimize the time-average electricity bill under unknown workload and price statistics.Dynamic programming faces curse-of-dimensionality and re-computation challenges as system size or statistics change.
  • Approach and Contribution: Lyapunov optimization yields an online algorithm that requires no system statistics, is easy to implement, and approaches optimality as battery capacity increases.The algorithm is within O(1/V) of optimal, with the maximum V limited by battery capacity; the gap decreases as capacity grows.
  • Model Scope: The basic model uses time slots, requires each slot’s workload to be served immediately, and models UPS and battery interchangeably.The model assumes bounded workload, allows either recharge or discharge in a slot but not both, and initially omits charging, discharging, and leakage losses.

C. Cost Model

The cost model defines grid power, battery actions, workload, and system state within a constrained time-slotted optimization problem. A relaxed stationary benchmark enables construction of a dynamic Lyapunov policy that meets battery constraints without requiring process statistics.

  • Cost Definition: Per-unit grid cost C(t) depends on grid power P(t) and auxiliary state S(t), and is non-decreasing in P(t) for each fixed state.S(t) can capture time of day or utility identity, while the cost function need not be convex, strictly monotonic, or continuous.
  • Constraints and Information: The model bounds grid draw by Ppeak and assumes the current state S(t), cost function, and incoming workload are known at the beginning of each slot.The auxiliary state and workload are modeled as i.i.d. processes in the basic analysis, with unknown distributions.
  • Optimization Objective: The control objective is to minimize time-average cost while satisfying the model’s workload, battery, and grid-power constraints.The controller observes workload and makes decisions about grid draw, recharge, and discharge; recharge and discharge indicators contribute fixed battery-operation costs.
  • Relaxation and Benchmark: A relaxed problem removes battery-level dependence and admits a stationary randomized policy based only on current workload and system state.Any feasible solution to the original problem also satisfies the relaxed problem, so the relaxed optimum lower-bounds the original optimum.
  • Dynamic Policy: Lyapunov optimization constructs a dynamic policy using a queueing state variable X(t) to track battery charge and approximately solve the original constrained problem.The policy does not require statistical descriptions of workload or cost processes, and its approximation improves with battery capacity.

V. OPTIMAL CONTROL ALGORITHM

The paper presents an online dynamic control algorithm that uses a shifted queueing state to manage UPS charging and discharging under current system conditions. In the example, increasing battery capacity brings its average cost toward the offline optimum, despite no future-process knowledge.

  • Algorithm design: The algorithm uses control parameter V and queueing state X(t) to approximately solve the constrained optimization problem P1.X(t) tracks the battery charge level in the algorithmic formulation.
  • Algorithm design: At each slot, the dynamic algorithm chooses P(t) by solving an optimization problem and then derives recharge and discharge decisions.The feasible grid-power interval is bounded by Plow = max[0, W(t) − Dmax] and Phigh = min[Ppeak, W(t) + Rmax].
  • Algorithm design: The algorithm uses only current system-state values and does not require workload or unit-cost statistics.Its slot-by-slot optimization is therefore myopic and greedy in nature.
  • Illustrative example: In the periodic example, the offline strategy recharges at Clow and discharges at Chigh, achieving 87.0 dollars/slot versus 94.0 dollars/slot without battery use.The example sets Wlow = 10, Wmid = 15, Whigh = 20, and Clow = 2, Cmid = 6, Chigh = 10 dollars.
  • Illustrative example: As Ymax increases, the dynamic algorithm’s time average cost approaches the optimal value.With Ymax = 100, its decisions initially perform suboptimally but eventually become close to optimal.
  • Illustrative example: The example also shows that a price-threshold policy is not always optimal, because the dynamic algorithm can outperform such a policy.This comparison is introduced for random workload and price processes with Rmax = Dmax = 10 and Ppeak = 90.

A. Solving P3

P3 minimizes a per-slot objective balancing grid power, battery charging, and battery discharging. Depending on the shifted cost state and battery constraints, its solution has threshold or convex-optimization structure with feasibility and O(1/V) cost guarantees.

  • Solving P3: When C(t) depends only on S(t), the objective separates into grid, recharge, and discharge terms and yields a threshold structure.The no-storage objective is θ(t) = W(t)(X(t) + V C(t)).
  • Solving P3: If X(t) + V C(t) > 0, the algorithm does not recharge and either discharges as much as possible or draws all power from the grid.Discharge occurs when Plow(X(t) + V C(t)) + V Cdc < θ(t).
  • Solving P3: If X(t) + V C(t) ≤ 0, the algorithm does not discharge and either recharges as much as possible or draws all power from the grid.Recharge occurs when Phigh(X(t) + V C(t)) + V Crc < θ(t).
  • Performance: The resulting solution is feasible under the finite battery constraint, and larger V moves time-average cost closer to the optimum within B/V.V is restricted by Vmax, so the parameter cannot increase without bound.
  • Solving P3: P3 becomes a single-variable convex optimization when C(t) is convex and increasing in P(t).An example cost is ˆC(S(t), P^2(t)) = α(S(t))P^2(t), with α(S(t)) > 0.

C. Proof of Theorem 1

Theorem 1 is proved by establishing queue bounds, translating them into battery bounds and feasibility, and applying Lyapunov drift-plus-penalty analysis. The analysis compares the dynamic decisions with a stationary randomized policy to derive the cost guarantee.

  • Queue bounds: The proof initializes X(0) through the shifted battery state and establishes its lower and upper bounds inductively.The induction considers separate ranges of X(t), using the algorithm’s recharge or discharge decisions and maximum rate bounds.
  • Battery feasibility: The bounds on X(t) imply Ymin ≤ Y(t) ≤ Ymax for every slot, and therefore all control decisions are feasible.Feasibility follows from the battery bound together with the constraint on P(t).
  • Cost analysis: Lyapunov analysis uses L(X(t)) = 1/2 X^2(t) and adds a V-weighted cost penalty to the conditional one-slot drift.The resulting drift-plus-penalty expression is rewritten using W(t) = P(t) − R(t) + D(t).
  • Cost analysis: For each queue state, the dynamic algorithm minimizes the drift-plus-penalty right-hand side over all feasible policies, including the optimal stationary randomized policy.Expectation and time summation then yield the asymptotic performance bound.
  • Extended model: Figure 6 depicts the extended model’s block diagram with delay-tolerant and delay-intolerant workloads.The delay-tolerant workload can be buffered, while the delay-intolerant workload must be served immediately.

VI. EXTENSIONS TO BASIC MODEL

The extended model separates workload into delay-tolerant and delay-intolerant components, allowing some work to be buffered while requiring the rest to be served immediately. It targets minimum time-average cost subject to battery, service, and finite-delay constraints.

  • Workload model: The total workload is divided into delay-tolerant W1(t) and delay-intolerant W2(t) components.Delay-tolerant work may be postponed without affecting utility, whereas delay-intolerant work cannot be buffered.
  • Optimization objective: The extended objective minimizes time-average cost while meeting finite battery and service constraints and ensuring finite average delay for W1(t).The formulation explicitly includes the finite-average-delay requirement.
  • Relaxation: A relaxed problem is less constrained than the original problem, so its optimal value ˆφext is no greater than φext.The comparison parallels the basic model’s relaxation argument.
  • Reference policy: Under i.i.d. workload and auxiliary-state processes, a stationary randomized policy can make decisions from the current state while satisfying the model constraints.Its guarantees are evaluated with respect to the stationary state distribution and randomized decisions.
  • Delay guarantee: The initial queueing condition guarantees stability but not bounded worst-case delay, motivating a dynamic algorithm with average cost within O(1/V) of ˆφext.The paper separately develops bounded-delay guarantees for buffered workload.

A. Delay-Aware Queue

The delay-aware algorithm augments the battery queue with workload and persistent queues, then solves a per-slot optimization using the current system state. Queue bounds support finite worst-case delay while preserving online operation without process statistics.

  • Delay-Aware Queue: The virtual queue Z(t) is introduced to provide worst-case delay guarantees for buffered workload.If U(t) and Z(t) remain bounded, the delay-tolerant workload has a bounded worst-case delay.
  • Delay-Aware Queue: If U(t) ≤ Umax and Z(t) ≤ Zmax, any delay-tolerant workload waits at most δmax slots.The proof uses FIFO service, the workload backlog bound, and the persistent-queue evolution.
  • Online algorithm: The dynamic algorithm tracks U(t), Z(t), and X(t), and chooses P(t), R(t), D(t), and γ(t) by solving a constrained per-slot optimization.X(t) tracks battery charge, while U(t) and Z(t) represent workload and auxiliary queues.
  • Online algorithm: The optimizer allocates (1−γ*(t))(P*(t)−R*(t)+D*(t)) to delay-intolerant work and the remainder to delay-tolerant work.The algorithm repeats this process every slot using current state values.
  • Structural properties: The optimal solution has threshold properties: X(t) > −V Cmin prevents recharge, while X(t) < −Qmax prevents discharge.These structural properties support the subsequent performance analysis.

C. Solving P6

P6 is solved by evaluating closed-form objective values for no battery action, recharge, and discharge, then selecting the mode with the highest value. Under stated parameter conditions, the resulting dynamic algorithm provides queue, feasibility, delay, and time-average-cost guarantees.

  • Closed-form solution: P6 can admit closed-form real-time solutions when the unit cost function C(t) has suitable structure.The paper considers the case where C(t) does not depend on P(t).
  • Operating modes: The no-recharge/no-discharge case computes θ1(t) by comparing U(t) + Z(t) with V C(t).The resulting value uses either Ppeak or W2(t), depending on that comparison.
  • Operating modes: Recharge and discharge cases compute θ2(t) and θ3(t) through piecewise conditions on Q1(t) and Q2(t).The expressions incorporate recharge and discharge limits and costs, including Rmax, Dmax, Crc, and Cdc.
  • Mode selection: The controller selects the mode with the highest objective value after computing θ1(t), θ2(t), and θ3(t).This choice determines the corresponding control solution implemented in the slot.
  • Performance guarantees: For admissible ϵ and V, the algorithm guarantees deterministic queue bounds, feasible controls, a bounded battery level, and time-average cost within Bext/V of optimum under i.i.d. processes.Increasing V moves cost closer to the minimum but increases the worst-case delay; Vmax limits how large V may be chosen.

VII. SIMULATION-BASED EVALUATION

The evaluation uses synthetic and six-month real pricing data to study online control under varying workload, price, and battery-capacity settings. Results show that combining battery use with workload postponement yields the greatest cost savings, while increasing battery capacity lowers average cost toward an optimum.

  • Results: Average cost reduces as Ymax increases and converges to $33.23 per hour, compared with $39.90 per hour without a battery.The convergence matches the behavior suggested by Theorem 1 in the simple example.
  • Evaluation setup: The evaluation combines a simple periodic workload-and-price model with six months of Los Angeles Zone LA1 spot-market prices from CAISO.The real dataset covers 01/01/2005–06/30/2005; hourly prices are held fixed within each hour while decisions occur every five minutes.
  • Results: The study also examines total cost over six months under i.i.d. workloads and different battery capacities.The corresponding plots include total cost over six months and average cost per hour versus Ymax.
  • Evaluation setup: Four schemes compare grid-only operation, battery use, workload postponement, and the complete algorithm across Ymax ∈ {15, 30, 50} MW-slot.The complete scheme combines both battery storage and workload postponement; the baseline uses neither.
  • Results: Scheme (D), the complete algorithm, provides the most cost savings relative to the no-battery, no-workload-postponement baseline over six months.Table II reports ratios for schemes (B), (C), and (D) relative to scheme (A).
  • Future work: The authors identify extensions involving multiple utilities, peak-dependent tariffs, reduced battery-capacity dependence, investment trade-offs, and realistic workloads.They also propose using the technique as a design tool for battery sizing, usage rules, and decision timescales.

APPENDIX A -PROOF OF LEMMA 2

The proof establishes threshold behavior for the per-slot control problem by comparing battery charging or discharging decisions with serving demand directly from the grid. Feasibility and queue-drift arguments support the resulting exclusions of suboptimal actions.

  • Threshold cases: When X(t) > −V Cmin, charging the battery is not optimal because serving demand from the grid yields a smaller objective.The comparison uses nonnegative, non-decreasing grid cost C(t) and the condition X(t)+V C(W(t)) > 0.
  • Threshold cases: When X(t) < −V χmin, discharging the battery is not optimal because serving all demand from the grid yields a smaller objective.The proof invokes property (10) together with the stated threshold condition.
  • Feasibility: At most one of R(t) and D(t) can be nonzero, while their magnitudes are bounded by Rmax and Dmax.These feasibility bounds are used in the Lyapunov-drift calculation.
  • Extended problem: For the extended control problem, charging is also ruled out when X(t) exceeds −V Cmin, including the case where delay-tolerant workload is present.The proof compares the candidate objective with a feasible policy that draws the remaining power from the grid.
  • Extended problem: For X(t) below −Qmax, discharging is not optimal in both cases P*(t)+D*(t) ≤ Ppeak and P*(t)+D*(t) > Ppeak.The proof constructs feasible alternatives with no discharge and uses bounds on X(t), U(t), Z(t), and W2,max.
  • Extended problem: When P*(t)+D*(t) > Ppeak, choosing P(t)=P*(t) and D(t)=0 remains feasible because W2,max ≤ Ppeak−Dmax.This establishes that discharge cannot improve the objective in that case.

APPENDIX D - PROOF OF THEOREM 2, PARTS 2-6

The proof establishes bounded queue and battery-related state evolution by induction and then uses a quadratic Lyapunov function to derive the drift-plus-penalty bound. These bounds support the algorithm’s comparison with an optimal stationary randomized policy.

  • Queue stability: The queue bounds use workload and service limits to show that arrivals cannot exceed available service for U(t) and Z(t).The argument relies on W1(t)+W2(t) ≤ Wmax ≤ Ppeak−Rmax and analogous bounds for W2(t).
  • State bounds: The proof initializes X(0) within −Qmax−Dmax ≤ X(0) ≤ Ymax−Ymin−Qmax−Dmax.The bounds follow from the definition of X(0), Ymin ≤ Y(0), and Y(0) ≤ Ymax.
  • State bounds: The induction maintains X(t) ≤ Ymax−Ymin−Qmax−Dmax for all slots.The proof separately handles X(t) above and below −V Cmin and bounds the largest possible increase.
  • State bounds: The induction also maintains X(t) ≥ −Qmax−Dmax for all slots.The proof uses the absence of discharge in one region and the bound Dmax on the maximum decrease in the other.
  • Battery feasibility: The bounds on X(t) translate through Y(t)=X(t)+Qmax+Dmax+Ymin into corresponding bounds on the battery state.Parts 3 and 4 of Theorem 2 follow directly from these transformed inequalities and the constraint on P(t).
  • Lyapunov analysis: The proof uses the quadratic Lyapunov function L(Q(t)) = 1/2(U^2(t)+Z^2(t)+X^2(t)) and a conditional one-slot drift.The resulting drift-plus-penalty expression includes grid cost and charging or discharging costs.
  • Lyapunov analysis: Because the algorithm minimizes the drift-plus-penalty right-hand side for each queue state, it can be compared with the optimal stationary randomized policy.Taking expectations, summing over slots, dividing by VT, and letting T approach infinity yields the performance bound.

INCREASING C(t)

For increasing power-cost functions, the optimal per-slot decision is characterized by the derivative-based candidate P′ and the feasible interval defined by Plow and Phigh. Threshold comparisons determine whether the battery is charged, discharged, or unused.

  • Decision rule: P′ is defined by C′(S,P)=0 with C(P′)=Ĉ(S,P′), providing the derivative-based candidate for the optimal power draw.The subsequent cases compare P′ with workload and feasible power limits.
  • Decision rule: If Plow ≤ P′ ≤ W(t), the policy either discharges to use P′ or serves all demand from the grid.Discharge occurs when P′(X(t)+V C(P′))+V Cdc < θ(t).
  • Decision rule: If W(t) < P′ ≤ Phigh, the policy either charges up to P′ or serves all demand from the grid.Charging occurs when P′(X(t)+V C(P′))+V Crc < θ(t).
  • Boundary cases: If P′ exceeds Phigh, the policy either discharges to Phigh or serves all demand from the grid.The discharge threshold uses Phigh(X(t)+V C(Phigh))+V Cdc < θ(t).
  • Boundary cases: If P′ is below Plow, the policy either charges to Plow or serves all demand from the grid.The charging threshold uses Plow(X(t)+V C(Plow))+V Crc < θ(t).
  • Fallback action: When the relevant threshold is not satisfied, the policy sets battery charging or discharging to zero and uses P*(t)=W(t).This fallback appears in each of the four cases.
Loading 1103.3099v2…