A practical algorithm for balancing the max-min fairness and throughput objectives in traffic engineering
Venue
INFOCOM (2012)
Publication Year
2012
Authors
Emilie Danna, Subhasree Mandal, Arjun Singh
BibTeX
Abstract
One of the goals of traffic engineering is to achieve a flexible trade-off between
fairness and throughput so that users are satisfied with their bandwidth allocation
and the network operator is satisfied with the utilization of network resources. In
this paper, we propose a novel way to balance the throughput and fairness
objectives with linear programming. It allows the network operator to precisely
control the trade-off by bounding the fairness degradation for each commodity
compared to the max-min fair solution or the throughput degradation compared to the
optimal throughput. We also present improvements to a previous algorithm that
achieves max-min fairness by solving a series of linear programs. We significantly
reduce the number of steps needed when the access rate of commodities is limited.
We extend the algorithm to two important practical use cases: importance weights
and piece-wise linear utility functions for commodities. Our experiments on
synthetic and real networks show that our algorithms achieve a significant speedup
and provide practical insights on the trade-off between fairness and throughput.
