Designing efficient and fair algorithms for sharing multiple resources between heterogeneous demands is becoming increasingly important. Applications include compute clusters shared by multi-task jobs and routers equipped with middleboxes shared by flows of different types. We show that the currently preferred objective of Dominant Resource Fairness has a significantly less favorable efficiency-fairness tradeoff than alternatives like Proportional Fairness and our proposal, Bottleneck Max Fairness. In addition to other desirable properties, these objectives are equally strategyproof in any realistic scenario with dynamic demand.
We limit the present discussion to the most relevant related work. DRF @cite_5 and no justified complaints'' @cite_3 were placed in a more general economics framework in the work of Gutman and Nisan @cite_15 . Joe-Wang al also generalized DRF by introducing two families of allocations that allow a controlled tradeoff between efficiency and fairness @cite_6 . All these objectives are evaluated assuming a fixed set of transactions. The serve the most deprived job'' approach introduced in @cite_5 proves very versatile. It is used by Zeldes and Feitelson @cite_12 to implement bottleneck-based fairness and by Ghodsi and co-authors @cite_19 to account for compatibility constraints in task placement. Our proposed implementations of PF and BMF for sharing cluster resources are further illustrations of this versatility.
@cite_6 @cite_3 @cite_19 @cite_5 @cite_15 @cite_12
1890643295 2962701284 1996998821 2129996460
We consider the problem of fair resource allocation in a system containing different resource types, where each user may have different demands for each resource. To address this problem, we propose Dominant Resource Fairness (DRF), a generalization of max-min fairness to multiple resource types. We show that DRF, unlike other possible policies, satisfies several highly desirable properties. First, DRF incentivizes users to share resources, by ensuring that no user is better off if resources are equally partitioned among them. Second, DRF is strategy-proof, as a user cannot increase her allocation by lying about her requirements. Third, DRF is envy-free, as no user would want to trade her allocation with that of another user. Finally, DRF allocations are Pareto efficient, as it is not possible to improve the allocation of a user without decreasing the allocation of another user. We have implemented DRF in the Mesos cluster resource manager, and show that it leads to better throughput and fairness than the slot-based fair sharing schemes in current cluster schedulers. Abstract The performance of cluster computing depends on how concurrent jobs share multiple data center resource types such as CPU, RAM and disk storage. Recent research has discussed efficiency and fairness requirements and identified a number of desirable scheduling objectives including so-called dominant resource fairness (DRF). We argue here that proportional fairness (PF), long recognized as a desirable objective in sharing network bandwidth between ongoing data transfers, is preferable to DRF. The superiority of PF is manifest under the realistic modeling assumption that the population of jobs in progress is a stochastic process. In random traffic the strategy-proof property of DRF proves unimportant while PF is shown by analysis and simulation to offer a significantly better efficiency–fairness tradeoff. We present a model for fair strategyproof allocations in a realistic model of cloud computing centers. This model has the standard Leontief preferences but also captures a key property of virtualization, the use of containers to isolate jobs. We first present several impossibility results for deterministic mechanisms in this setting. We then construct an extension of the well known dominant resource fairness mechanism (DRF), which somewhat surprisingly does not involve the notion of a dominant resource. Our mechanism relies on the connection between the DRF mechanism and the Kalai-Smorodinsky bargaining solution; by computing a weighted max-min over the convex hull of the feasible region we can obtain an ex-ante fair, efficient and strategyproof randomized allocation. This randomized mechanism can be used to construct other mechanisms which do not rely on users' being expected (ex-ante) utility maximizers, in several ways. First, for the case of @math identical machines one can use the convex structure of the mechanism to get a simple mechanism which is approximately ex-post fair, efficient and strategyproof. Second, we present a more subtle construction for an arbitrary set of machines, using the Shapley-Folkman-Starr theorem to show the existence of an allocation which is approximately ex-post fair, efficient and strategyproof. This paper provides both a rigorous foundation for developing protocols that explicitly utilize the detailed structure of the modern cloud computing hardware and software, and a general method for extending the dominant resource fairness mechanism to more complex settings. Spectral efficiency, fairness and user satisfaction are crucial aspects for resource allocation in multi-user Orthog- onal Frequency Division Multiplexing (OFDM)-based cellular networks. Classical Radio Resource Allocation (RRA) strategies, such as Max-Rate (MR), Proportional Fairness (PF) and Max- Min Fairness (MMF), show different performances regarding the three aforementioned aspects. In this work, we present an adap- tive RRA framework that joins the criteria of the three classical strategies in a unified manner and can be dynamically configured according to the cellular operator's objectives. We exemplify the flexible use of this general framework by proposing two adaptive RRA algorithms that provide strict fairness among users and maximizes the users' satisfaction, respectively. Simulation results show that the two proposed algorithms can efficiently achieve their respective objectives by means of the adaptation of the general RRA framework.