Learning to Optimize Resource Utilization with QoS Guarantees

Resource allocation optimization is crucial in cloud computing platforms, which need to support a heterogeneous set of users sharing the same physical computing resource. Without prior knowledge of fluctuating user demands, existing methods often result in inefficient resource utilization (low system utility) or fail to meet Quality of Service (QoS) guarantees for users. Motivated by this, we present a feedback-limited online resource allocation model for a divisible resource shared among multiple users, each with specific QoS requirements and fluctuating demands. Using only binary feedback on the queue status of each user, we propose an efficient online algorithm that balances resource utilization and adherence to users' QoS requirements. Our algorithm ensures nearly optimal resource utilization, even when compared to the omniscient offline dynamic optimum. Also, it concurrently meets all individual users' QoS requirements with minimal error. The core algorithmic technique involves a multiplicative weight update strategy and a primal-dual approach to secure these guarantees. Furthermore, we present numerical results to validate the effectiveness of the algorithm.