A Random Online Algorithm for Reselling Reserved IaaS Instances in Amazon's Cloud Marketplace

When running applications in IaaS (Infrastructure as a Service) cloud platforms like Amazon EC2, cloud users can choose to purchase reserved instances instead of on-demand ones to save cost. However, if there are few workload arrivals after instance reservations, it will cause a waste of cost due to the idle reserved instances. At present, Amazon EC2 has launched a reserved instance market, in which cloud users can resell their idle reserved instances to avoid wastes. However, for IaaS users, it is difficult to make the optimal decisions on whether to resell idle reserved instances when they do not know the arrival situation of workloads in the future. This is because after the idle reserved instances are sold, if there arrive new workloads, additional cost for launching new reserved or on-demand instances will be incurred. In this paper, we propose a random online reselling algorithm to help cloud users make reasonable decisions on whether to sell their idle instances, while without requiring the knowledge of the future workload arrivals. We theoretically prove that our algorithm can achieve a bounded competitive ratio. Besides, we conduct extensive experiments using the real-world workload obtained from public clouds to validate our algorithm.