Strategy-Proof Mechanism for Time-Varying Fair Multi-resource Allocation with Placement Constraints in Clouds

Abstract Current cloud computing systems are committed to providing quality of service to users. However, one main problem is fairly and efficiently allocating resources to users with time-varying demands. This is mainly due to the mismatch between the heterogeneous hardware and software demands of users and the heterogeneity of resource deployment. This restricts users from running their jobs on servers that can match their demands. In this paper, we design a lexicographically max-min multiresource fair allocation mechanism called cumulative task share fairness (CTSF) based on historical allocations to ensure long-term fairness and efficiency. With CTSF, each user prefers their own allocation over that of another user; no user can increase their allocation without decreasing the allocation of others; the allocation of no user will decrease by sharing resources; and importantly, no user can benefit by misreporting their demands and/or placement constraints. We design a simple heuristic for implementing CTSF in real-world cloud computing systems, prototype CTSF in a 50-node simulation and demonstrate its service guarantees. Large-scale simulations driven by Alibaba cluster traces show that CTSF reduces the user's waiting, job queuing and job completion times.