Rightsizing Clusters for Time-Limited Tasks

Abstract

Cost-performance trade-off is critical in constructing a cluster of compute nodes for hosting an application with multiple tasks on a cloud environment, where each task can demand multiple resources, and the cloud offers nodes with different capacity and cost. Multidimensional bin-packing algorithms can address this rightsizing problem, but these assume that every task is always active. In contrast, real-world tasks (e.g. load bursts, batch jobs) may be active only during specific time periods and the cluster cost can be reduced by reusing resources. 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 time slots, 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 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.