Abstract
An online non-convex optimization problem is considered where the goal is to minimize the flow time (total delay) of a set of jobs by modulating the number of active servers, but with a switching cost associated with changing the number of active servers over time. Each job can be processed by at most one fixed speed server at any time. Compared to the usual online convex optimization (OCO) problem with switching cost, the objective function considered is non-convex and more importantly, at each time, it depends on all past decisions and not just the present one. Both worst-case and stochastic inputs are considered; for both cases, competitive algorithms are derived.
Introduction
In modern data center management, capacity provisioning—the process of dynamically adjusting the number of active servers—is a critical operational challenge. Operators must navigate a fundamental trade-off: keeping many servers active minimizes job latency (flow time) but incurs high energy and switching costs (the overhead of toggling server states). While this problem is often framed within the framework of Online Convex Optimization with Switching Costs (OCO-S), traditional models frequently overlook two physical realities: the non-convex nature of discrete server allocation and the "memory" effect inherent in queueing systems, where past decisions directly impact current backlogs.
Problem Formulation: Beyond Standard OCO-S
The authors identify two primary limitations in existing OCO-S literature when applied to capacity provisioning.
1. The Memory Effect
In standard OCO-S, the cost at time $t$ typically depends only on the current action $x_t$ and the immediate transition from $x_{t-1}$. However, in a queueing system, if the number of active servers at time $t-1$ was insufficient to handle the arrival rate, the remaining work carries over. This creates a cumulative effect where the current cost (flow time) is a function of the entire history of server allocations. This "unbounded memory" significantly complicates the derivation of competitive ratios because an algorithm's current state is tied to every previous decision.
2. Non-Convexity
Queueing dynamics are inherently non-linear. Because the number of servers and jobs are discrete integers, and the relationship between service rate and delay is non-linear, the resulting objective function—minimizing the sum of flow times and switching costs—is non-convex. This prevents the direct application of standard convex optimization tools and gradient-based online learning methods.
Methodology and Algorithmic Framework
The paper investigates two distinct switching cost structures: linear (proportional to the magnitude of change) and quadratic (proportional to the square of the change).
Potential Function Analysis
For linear switching costs, the researchers utilize a potential function approach. They construct functions that track both the number of active servers and the volume of outstanding work. This allows them to bound the online algorithm's performance against an optimal offline adversary that has full knowledge of future job arrivals, effectively "charging" the online algorithm for its deviations from the optimal state.
Primal-Dual Technique for Non-Convexity
One of the paper's most significant contributions is the application of a Lagrangian primal-dual analysis to the quadratic switching cost scenario. Primal-dual methods are standard in convex optimization but are rarely successfully applied to non-convex problems with memory. The authors overcome this by introducing a "work neutrality" constraint. This constraint ensures the offline optimal solution cannot achieve artificially low costs by idling servers in a way that an online algorithm (which cannot see the future) could never replicate.
Key Results and Competitive Analysis
The performance of the proposed algorithms is measured by their competitive ratio—the ratio between the cost incurred by the online algorithm and the cost incurred by an optimal offline algorithm.
Linear Switching Costs
The results for linear costs depend on the weighting parameter $\alpha$, which represents the relative importance of switching costs versus flow time:
- Low Switching Cost ($\alpha \leq 1$): A simple "match the queue" strategy, where the number of servers is proportional to the current backlog, is shown to be 2-competitive.
- High Switching Cost ($\alpha > 1$): The authors develop an "aggressive" algorithm ($ALG_{LG}$) that scales the server count by $\alpha^{1/4}$, achieving a competitive ratio of $4\alpha^{1/4}$. This growth in the ratio marks a distinct departure from 1D OCO-S theory, where constant ratios are typically expected regardless of $\alpha$.
Quadratic Switching Costs
For quadratic costs, the proposed algorithm maintains a constant competitive ratio of at most 20, regardless of the value of $\alpha$. This provides a robust guarantee for systems where frequent, small changes are preferred over large, abrupt shifts in capacity.
Stochastic Performance
Under a Markovian arrival model (Poisson arrivals and exponential service times), the authors prove that a policy setting the number of servers equal to the number of outstanding jobs is $(1+2\alpha)$-competitive. They also observe that in "heavy traffic" scenarios, "gated" policies—which allow a small buffer of jobs to accumulate before activating servers—can achieve significantly lower costs than purely reactive policies.
Discussion and Insights
The paper's "zoomed-in" view of queueing dynamics reveals that explicit memory fundamentally alters the optimization landscape. The discovery that the competitive ratio must scale with $\alpha^{1/4}$ in the linear case suggests that capacity provisioning is inherently more difficult than standard OCO-S problems. Furthermore, the success of the "aggressive" scaling strategy highlights that when memory is involved, over-provisioning slightly in the present can lead to significant long-term savings by preventing backlog accumulation.
Limitations and Future Directions
While the paper provides a rigorous foundation, several avenues for future research remain. Much of the worst-case analysis assumes uniform job sizes; extending these bounds to jobs with varying processing requirements remains an open challenge. Additionally, the current analysis often treats server counts as continuous rates before applying a ceiling function; a more direct discrete analysis could yield tighter bounds. Finally, extending this model to multi-dimensional systems, such as geographically distributed data centers with routing costs, would represent a significant step toward real-world implementation.
Summary updated