Rightsizing Clusters for Time-Limited Tasks

Cluster rightsizing facilitates cost-performance trade-off in resource-constrained clouds. Multidimensional bin-packing algorithms can address this rightsizing problem, but these assume that every task on the cluster is always active. In contrast, real-world tasks may be active only during specific time-periods, which allows reusing resources via time sharing and optimal packing. This motivates our generalized problem of rightsizing for time-limited tasks: given a timeline, time-periods and resource demands for tasks, the objective is to place the tasks on a minimum cost cluster of nodes without violating node capacities at any time instance. We design a baseline two-phase algorithm that performs penalty-based mapping of task to node-Type and then, solves each node-Type independently. We prove that the algorithm has an approximation ratio of O(D. min(m, T)), where D, m and T are the number of resources, node-Types and timeslots, respectively, We then present an improved linear programming based mapping strategy, enhanced further with a cross-node-Type filling mechanism. Our experiments on synthetic and real-world cluster traces show significant cost reduction by LP-based mapping compared to the baseline, and the filling mechanism improves further to produce solutions within 20% of (a lower-bound to) the optimal solution.