A Restless Bandit Model for Energy-Efficient Job Assignments in Server Farms

We aim to maximize the energy efficiency, gauged as average energy cost per job, in a large-scale server farm with various storage or/and computing components, which are modeled as parallel abstracted servers. Each server works in multiple power modes characterized by potentially different service and energy consumption rates. The heterogeneity of servers and multiple power modes significantly complicate the maximization problem, where optimal solutions are generally intractable. Relying on the Whittle relaxation technique, we resort to a near-optimal and scalable job-assignment policy. Under certain conditions including the assumption of exponentially distributed job sizes, we prove that our proposed policy approaches optimality as the size of the entire system tends to infinity; that is, it is asymptotically optimal. Nevertheless, we demonstrate by simulations that the effectiveness of our policies is not significantly limited by the conditions used for mathematical rigor and that our model still has wide practical applicability. In particular, the asymptotic optimality is very much relevant for many real-world large-scale systems with tens or hundreds of thousands of components, where conventional optimization techniques can hardly apply. Furthermore, for non-asymptotic scenarios, we show the effectiveness of the proposed policy through extensive numerical simulations, where the policy substantially outperforms all the tested baselines, and we especially demonstrate numerically its robustness against heavy-tailed job-size distributions.