Maximizing Utilization under Time-Varying Resource Requirements

Low utilization has been one of the key limiting factors for the continued scaling of today's computing systems. One main reason for the low utilization is the temporal variation in the actual resource requirements of jobs, because reserving resources for jobs based on the peak requirements then results in idle resources for non-peak time. To increase utilization, in practice, resources are often overcommitted, so jobs may need to contend for resources at times and experience performance degradation, incurring a cost. To make use of the flexibility in resource allocation provided by overcommitment to the best advantage, it is critical to answer the following fundamental question that has not been well studied: given an acceptable budget for the cost associated with resource contention, how can we achieve the maximum utilization of the system? In this paper, we propose a job model that captures the time-varying resource requirement of each job by a Markov chain. We consider a stochastic formulation of the job dispatch problem in an infinite-server system. Our goal is to maximize system utilization by minimizing the number of active servers (servers running at least one job), subject to a budget on the cost of resource contention. Our main result is the design of a job dispatch policy that is asymptotically optimal as the job arrival rate increases. The novel technical framework that we develop reduces the policy design problem under study to that in a single-server system through policy conversions, which may be of independent interest. The framework allows us to design the asymptotically optimal policy by solving a linear program.