A practical algorithm for balancing the max-min fairness and throughput objectives in traffic engineering

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.

• Networking

• Responsible AI