Cost Minimizing Reservation and Scheduling Algorithms for Public Clouds

Cloud Service Providers offer various pricing schemes to charge for their computational resources. Cloud Service Users can opt for on-demand, reserved, or spot instances for their requirements. The overall cost of an application depends on the instances chosen to execute the job. Finding the optimal reservation amount is a significant research problem, and it is more challenging when one uses spot instances with unpredictable prices. We have proposed two algorithms to determine the reservation amount, and for both algorithms, the future spot prices are unknown. But the first algorithm assumes that future demands are known. The second algorithm does not make any such assumption and yet can ensure that the cost of reservation and usage of cloud resources is within a factor 2 - u(h)/e(c) of the optimal cost where u(h) is the usage cost per hour of the reserved instance and e(c) is the average cost per hour for unreserved instances. We have compared our findings with that of some recent works in the literature. We have also given an Integer Linear Programming (ILP) formulation of the problem. Experimental results show that our algorithm differs in cost from ILP by less than 21%.

Automated summary

Cloud Service Providers offer different pricing schemes and Cloud Service Users can choose on-demand, reserved, or spot instances. The optimal reservation amount is a significant research problem, especially when using spot instances with unpredictable prices. We proposed two algorithms to determine the reservation amount without knowing the future spot prices. Our algorithm ensures a cost within a factor 2 - u(h)/e(c) of the optimal cost, where u(h) is the usage cost per hour of the reserved instance and e(c) is the average cost per hour for unreserved instances. Experimental results show that our algorithm differs from ILP by less than 21% in cost.