Online Fault-Tolerant Bin Packing for Server Consolidation Revisited

The server consolidation problem, which aims to allocate services into fewer servers, is one of the main concerns in cloud computing. In the online setting where services are released sequentially, we study this problem by modeling it as an online fault-tolerant bin packing problem: Bins and items respectively represent servers with uniform capacity and services with heterogeneous workloads. To tolerate up to [Formula: see text] faulty servers, each service is replicated into [Formula: see text] replicas including one primary and [Formula: see text] standby replicas. The target of the considered bin packing problem is to minimize the total number of required bins while ensuring that each service retains at least one available replica despite faults in any [Formula: see text] bins. [Formula: see text]Our main work is to propose a Harmonic-based algorithm and prove that this algorithm achieves an asymptotic competitive ratio less than 1.694. This performance surpasses the previous best ratio of 1.75 and closely approaches the theoretical lower bound of 1.691 for classic Harmonic algorithm.