Efficient Heuristics for Profit Optimization of Virtual Cloud Brokers

This article introduces a new kind of broker for cloud computing, whose business relies on outsourcing virtual machines (VMs) to its customers. More specifically, the broker owns a number of reserved instances of different VMs from several cloud providers and offers them to its customers in an on-demand basis, at cheaper prices than those of the cloud providers. The essence of the business resides in the large difference in price between on-demand and reserved VMs. We define the Virtual Machine Planning Problem, an optimization problem to maximize the profit of the broker. We also propose a number of efficient smart heuristics (seven two-phase list scheduling heuristics and a reordering local search) to allocate a set of VM requests from customers into the available pre-booked ones, that maximize the broker earnings. We perform experimental evaluation to analyze the profit and quality of service metrics for the resulting planning, including a set of 400 problem instances that account for realistic workloads and scenarios using real data from cloud providers.