Abstract
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 (DRF) has a significantly less favorable efficiency-fairness tradeoff than alternatives like Proportional Fairness (PF) and our proposal, Bottleneck Max Fairness (BMF). In addition to other desirable properties, these objectives are equally strategyproof in any realistic scenario with dynamic demand.
Introduction
In modern data centers and high-speed routers, "fairness" is no longer just about sharing a single resource like link bandwidth. A single job might require a specific mix of CPU, RAM, and specialized processing. This paper challenges the current industry standard for multi-resource allocation—Dominant Resource Fairness (DRF)—arguing that it sacrifices too much efficiency for a theoretical "strategyproofness" that doesn't hold up in the real world. The authors demonstrate that Proportional Fairness (PF) and their own proposal, Bottleneck Max Fairness (BMF), provide significantly better performance and lower completion times in dynamic environments where jobs arrive and depart over time.
Methodology
The authors evaluate three primary allocation objectives using both a theoretical fluid model and a practical packet-based simulation:
- Dominant Resource Fairness (DRF): Equalizes the share of the most heavily used resource for each user.
- Proportional Fairness (PF): Maximizes the sum of the logarithms of the allocation rates, balancing total throughput with user fairness.
- Bottleneck Max Fairness (BMF): A novel proposal that ensures every transaction receives a "maximal" share of at least one bottleneck resource.
To bridge theory and practice, they adapt Start-time Fair Queuing (SFQ)—a standard scheduling algorithm—to implement these multi-resource objectives in routers. Performance was tested using synthetic Markovian models (Poisson arrivals and exponential task sizes) and specific requirement vectors to simulate heterogeneous resource demands.
Key Insights
- The Strategyproofness Myth: DRF’s strategyproofness is an "academic" benefit. In a dynamic system, a user would need perfect knowledge of every other user's current and future demands to successfully "game" Proportional Fairness. In reality, such manipulation is just as likely to hurt the malicious user as help them.
- Efficiency-Fairness Tradeoff: DRF is "too fair" in a way that hurts everyone. By forcing strict equality on dominant resources, it often prevents the system from utilizing secondary resources that are currently idle, leading to "resource strandedness."
- BMF as a Pragmatic Middle Ground: BMF generalizes the well-known "max-min fairness" to a multi-resource context and is particularly well-suited for networks where propagation delays are non-negligible.
Performance Results
In scenarios with unbalanced loads, PF and BMF consistently achieved higher "relative service rates" than DRF. This translates directly to shorter job completion times. Under heavy load, DRF’s performance dropped significantly compared to PF and BMF because it could not effectively "fill the gaps" in resource usage.
As illustrated in the figure above, BMF and PF maintain much higher service rates as system load increases, whereas DRF's performance degrades sharply. The authors showed that their packet-based SFQ implementations for PF and BMF closely match the ideal theoretical performance, proving they are computationally feasible for real-world routers and schedulers.
Conclusion
While DRF remains a popular choice due to its theoretical properties, this research highlights its limitations in dynamic, real-world settings. Proportional Fairness and Bottleneck Max Fairness offer a more favorable balance of efficiency and fairness, leading to better resource utilization and faster service. Future work will address placement constraints in physical clusters and the stability of these algorithms under more complex, fluctuating demands.
Summary updated