Coalition formation for deadline-constrained resource procurement in cloud computing

Abstract To attract more customers, a cloud provider tends to give some discounts to a customer if he/she rents a plenty of resources. Under this situation, a group of customers who need homogeneous cloud instances with various deadlines are prone to purchasing resources in a collaborative manner, i.e., using a coalition game, to reduce purchase costs. It is essential to design a mechanism that enables all customers to voluntarily and happily collaborate while ensuring that each customer pays at the lowest cost possible. To address this issue, we propose a mechanism to show collaborative interactions between customers and determine the number of service programs purchased from each provider to charge each cloud customer a minimum cost. We establish a coalition game based on multi-customer resource procurement and prove that there exists a unique optimal solution in the coalition game, while satisfying individual stability and group stability. In addition, the optimal solution is a solution in which the selected service program of each coalition optimizes the cost per customer and maximizes resource utilization. We propose a heuristic Deadline-constrained Resource Coalition Allocation (DRCA) algorithm to calculate the near-optimal solution. A backtracking algorithm is proposed to calculate the pseudo maximum resource utilization of the provided programs by improving the rectangular packing. Extensive experiments are performed to verify the feasibility and effectiveness of the proposed algorithm.