Efficient Online Strategies for Renting Servers in the Cloud

Abstract. In Cloud systems, we often deal with jobs that arrive and depart in an online manner. Upon its arrival, a job should be assigned to a server. Each job has a size which defines the amount of resources that it needs. Servers have uni-form capacity and, at all times, the total size of jobs assigned to a server should not exceed the capacity. This setting is closely related to the classic bin packing problem. The difference is that, in bin packing, the objective is to minimize the total number of used servers. In the Cloud, however, the charge for each server is proportional to the length of the time interval it is rented for, and the goal is to minimize the cost involved in renting all used servers. Recently, certain bin pack-ing strategies were considered for renting servers in the Cloud [Li et al. SPAA’14]. There, it is proved that all Any-Fit bin packing strategy has a competitive ratio of at least µ, where µ is the max/min interval length ratio of jobs. It is also shown that First Fit has a competitive ratio of 2µ+ 13 while Best Fit is not competitive at all. We observe that the lower bound of µ extends to all online algorithms. We also prove that, surprisingly, Next Fit algorithm has competitive ratio of at most 2µ + 1. We also show that a variant of Next Fit achieves a competitive ratio of K ×max{1, µ/(K − 1)}+ 1, where K is a parameter of the algorithm. In par-ticular, if the value of µ is known, the algorithm has a competitive ratio of µ+2; this improves upon the existing upper bound of µ + 8. Finally, we introduce a simple algorithm called Move To Front (MTF) which has a competitive ratio of at most 6µ+7 and also promising average-case performance. We experimentally study the average-case performance of different algorithms and observe that the typical behaviour of MTF is distinctively better than other algorithms.