Abstract

We study the Renting Servers in the Cloud problem (\RSiC), which addresses the need for efficient job allocation in cloud computing applications. Jobs arrive in an online manner and need to be assigned to servers. The size of each job is known at the time of arrival. If the duration of the jobs is also known, the scenario is termed clairvoyant; if the duration is unknown, it is non-clairvoyant. An infinite supply of identical servers is available, each providing one unit of computational capacity per unit of time across all dimensions. A server can be rented at any time and remains rented until all assigned jobs are completed. The cost of an assignment is the sum of the rental periods of all servers. The objective is to allocate jobs to servers in a way that minimizes the overall cost while adhering to server capacity constraints.

We first focus on a scenario where all jobs have equal durations and analyze the performance of two natural algorithms, \NF and \FF. We establish a tight bound of $2$ on the competitive ratio of \NF. For \FF, we also prove bounds under several restrictions. Next, we conduct a parameterized analysis of \FF, examining inputs where it utilizes at most $k$ servers simultaneously. We support the theoretical analysis with extensive experimental studies. Then, we show for a large class of well-known algorithms for \RSiC, none of them always outperforms the others.
We study the multi-dimensional \RSiC setting, where jobs/servers have multi-parameter resource demands/capacities (e.g., cores, memory). We demonstrate a direct sum property of \RSiC. We also propose a novel clairvoyant algorithm called \Greedy; our experiments demonstrate its superiority over existing algorithms in most scenarios. We introduce and analyze performance of a new sub-family of \AF algorithms termed monotone \AF, which includes \Greedy, \FF, \LF, and \MTFtext.
Finally we evaluate both clairvoyant and non-clairvoyant algorithms for \RSiC on real-world data using the Azure dataset. The results are sometimes different from those previously obtained on synthetic data. We also proposed some new algorithms that are combinations of known algorithms and outperform all existing algorithms in our experiments.