[2011 NSDI] Dominant Resource Fairness: Fair Allocation of Multiple Resource Types
DRF is a generalization of max min fairness for multiple resources. Each user has a demand vector (containing multiple resources; for one task of the user) and a dominant resource (xxx-bound) -- calculated using the demand vector and total resources available -- and DRF tries to equalize the dominant share (fraction of the dominant resource user is allocated) for all users.
- 1.Introduction
- 2.Motivation
- 3.Allocation Properties
- 4.Dominant Resource Fairness (DRF)
- 1.An Example
- 2.DRF Scheduling Algorithm
- 3.Weighted DRF
- 5.Alternative Fair Allocation Policies
- 1.Asset Fairness
- 2.Competitive Equilibrium from Equal Incomes
- 3.Comparison with DRF
- 6.Analysis
- 1.Fairness Properties
- 1.Properties Violated by Asset Fairness
- 2.Properties Violated by CEEI
- 3.Resource Monotonicity vs. Sharing Incentives and Pareto efficiency
- 2.Discrete Resource Allocation
- 7.Experimental Results
- 1.Dynamic Resource Sharing
- 2.DRF vs. Alternative Allocation Policies
- 3.Simulations using Facebook Traces
- 8.Related Work
- 9.Conclusion and Future Work
- 10.Acknowledgments
- Desired properties for resource allocation policies
- Sharing incentive: Each user should be better off sharing the cluster, than exclusively using her own partition of the cluster. Consider a cluster with identical nodes and n users. Then a user should not be able to allocate more tasks in a cluster partition consisting of 1/n of all resources.
- Strategy-proofness: Users should not be able to benefit by lying about their resource demands. This provides incentive compatibility, as a user cannot improve her allocation by lying.
- The paper included two really interesting examples of users benefitting from lying
- Pareto efficiency: It should not be possible to increase the allocation of a user without decreasing the allocation of at least another user. This property is important as it leads to maximizing system utilization subject to satisfying the other properties.
- Envy freeness: A user should not prefer the allocation of another user.
- Four other nice properties that are nice-to-have
- Single resource fairness: For a single resource, the solution should reduce to max-min fairness.
- Bottleneck fairness: If there is one resource that is percent-wise demanded most of by every user, then the solution should reduce to max-min fairness for that resource.
- Population monotonicity: When a user leaves the system and relinquishes her resources, none of the allocations of the remaining users should decrease.
- Resource monotonicity: If more resources are added to the system, none of the allocations of the existing users should decrease.
- Existing (fair) allocation policies
- Equal share: Not work conserving
- Max min fairness: Maximize the allocation for most poorly-treated users
- Asset fairness: Equalizes each user's sum of resource shares (violates sharing incentive)
- (Microeconomic theory) Competitive Equilibrium from Equal Incomes (CEEI): (not strategy-proof)
- Previous work on fair allocation focuses on one single resource type
Pseudo-code for DRF