Skip to Main content Skip to Navigation
New interface
Conference papers

Allocating jobs with periodic demand variations

Olivier Beaumont 1, 2 Ikbel Belaid 3, 2 Lionel Eyraud-Dubois 1, 2 Juan-Angel Lorenzo-Del-Castillo 2, 3 
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : In the context of service hosting in large-scale datacenters, we consider the problem faced by a provider for allocating services to machines. Based on an analysis of a public Google trace correspond-ing to the use of a production cluster over a long period, we propose a model where long-running services experience demand variations with a periodic (daily) pattern and we prove that services following this model acknowledge for most of the overall CPU demand. This leads to an allo-cation problem where the classical Bin-Packing issue is augmented with the possibility to co-locate jobs whose peaks occur at different times of the day, which is bound to be more efficient than the usual approach that consist in over-provisioning for the maximum demand. In this paper, we provide a mathematical framework to analyze the packing of services exhibiting daily patterns and whose peaks occur at different times. We propose a sophisticated SOCP (Second Order Cone Program) formula-tion for this problem and we analyze how this modified packing constraint changes the behavior of standard packing heuristics (such as Best-Fit or First-Fit Decreasing). We show that taking periodicity of demand into account allows for a substantial improvement on machine utilization in the context of large-scale, state-of-the-art production datacenters.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Lionel Eyraud-Dubois Connect in order to contact the contributor
Submitted on : Wednesday, February 18, 2015 - 3:42:09 PM
Last modification on : Saturday, June 25, 2022 - 7:41:21 PM
Long-term archiving on: : Sunday, April 16, 2017 - 9:36:13 AM


Files produced by the author(s)




Olivier Beaumont, Ikbel Belaid, Lionel Eyraud-Dubois, Juan-Angel Lorenzo-Del-Castillo. Allocating jobs with periodic demand variations. Euro-Par 2015, Träff, Jesper Larsson, Hunold, Sascha, Versaci, Francesco, 2015, Vienna, Austria. ⟨10.1007/978-3-662-48096-0_12⟩. ⟨hal-01118176⟩



Record views


Files downloads