TL;DR
This paper argues that Dominant Resource Fairness (DRF), a popular objective for sharing multiple resources, is suboptimal. The authors propose "Bottleneck Max Fairness" (BMF) as a more efficient alternative, demonstrating through simulations that BMF and Proportional Fairness (PF) offer better performance, especially under dynamic workloads, without sacrificing strategyproofness in realistic scenarios.
What Problem Does This Paper Address?
In modern computing and networking, systems often need to share multiple resources simultaneously. Examples include compute clusters where jobs require CPU, RAM, and other resources, and network routers that must manage bandwidth alongside specialized processing units (middleboxes) for different types of traffic. The challenge lies in designing fair and efficient allocation mechanisms. Dominant Resource Fairness (DRF) has emerged as a leading objective, aiming to ensure that no user is deprived of their "dominant" resource (the one they need most relative to others). However, this paper questions whether DRF truly offers the best balance between fairness and overall system efficiency, particularly when considering real-world scenarios with dynamic demands.
Methods
The authors introduce and analyze three multi-resource fairness objectives: Dominant Resource Fairness (DRF), Proportional Fairness (PF), and their proposed Bottleneck Max Fairness (BMF). They first define these objectives in an abstract "fluid model" where resources are infinitely divisible. Then, they develop practical, packet-based algorithms for realizing PF and BMF, drawing inspiration from existing algorithms like DRFQ for DRF. These algorithms are designed for both compute cluster task scheduling and network flow management. The core of their evaluation involves simulating these algorithms under a "Markovian demand model" to compare their performance in terms of completion times for dynamic workloads.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and simulation-based performance evaluation using a synthetic demand model.
Key Insights and Ideas
- DRF is Misguided: The paper's central claim is that DRF, despite its popularity, is not the optimal objective for multi-resource fairness.
- Efficiency-Fairness Tradeoff: PF and BMF offer a better balance between maximizing overall system throughput (efficiency) and ensuring equitable resource distribution (fairness) compared to DRF.
- Dynamic Demand Matters: The performance advantage of PF and BMF over DRF becomes particularly pronounced when dealing with dynamic workloads (jobs or flows arriving over time), leading to significantly smaller completion times.
- Strategyproofness Re-evaluated: The paper argues that the strategyproofness property, often cited as a key advantage of DRF, is less critical in dynamic environments. Users are unlikely to have perfect knowledge of competitors' needs and system state to effectively manipulate the system, making PF and BMF effectively strategyproof in practice.
- BMF as a Practical Alternative: Bottleneck Max Fairness (BMF) is presented as a viable and simpler alternative to PF, especially for network resource sharing, as it doesn't require knowledge of per-flow queue lengths.
Key Results
- Simulations show that under balanced and unbalanced loads, both PF and BMF achieve higher service rates (meaning faster completion times) than DRF, especially at higher load levels.
- The performance difference is accentuated under unbalanced load, where PF and BMF provide a better efficiency-fairness tradeoff, yielding significant gains for some classes with only negligible reductions for others.
- Packet-based algorithms for PF and BMF closely approximate the performance of their ideal fluid model counterparts, validating their practical applicability.
- The paper suggests that BMF is particularly well-suited for network integration scenarios, including wireless access networks, due to its simplicity and effectiveness.
Limitations and Future Work
- Realistic Constraints: The authors acknowledge that their models simplify real-world scenarios by assuming homogeneous resource pools and ignoring compatibility constraints in task placement. Future work should incorporate these practical considerations.
- Algorithm Convergence and Stability: While algorithms are proposed, a deeper theoretical analysis of their convergence properties and the stability of supposed equilibria is needed.
- Demand Models: The current evaluation relies on a specific Markovian demand model. Further evaluation with more realistic and diverse demand models is suggested.
- Resource Usage Constraints: The paper mentions the need to analyze algorithms under practical resource usage constraints, which were not fully explored.
Summary updated