Optimal Capacity Provisioning for Online Job Allocation with Hard Allocation Ratio Requirement

The problem of allocating jobs to appropriate servers in cloud computing is studied in this paper. We consider that the jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. In order to meet the hard allocation ratio requirement in the presence of unknown arrival patterns, one can increase the capacity of servers by expanding the size of data centers. We then aim to find the minimum capacity needed to meet a given allocation ratio requirement. We study this problem for both systems with persistent jobs, such as video streaming, and systems with dynamic jobs, such as database queries. For both systems, we propose online job allocation policies with low complexity. For systems with persistent jobs, we prove that our policies can achieve a given hard allocation ratio requirement with the least capacity. For systems with dynamic jobs, the capacity needed for our policies to achieve the hard allocation ratio requirement is close to a theoretical lower bound. Two other popular policies are studied, and we demonstrate that they need at least an order higher capacity to meet the same hard allocation ratio requirement. Simulation results demonstrate that our policies remain far superior than the other two even, when the jobs arrive according to some random process.