Upward Max-Min Fairness in Multipath High-Speed Networks

Abstract

To take full advantage of the available network capacity, connections need to be able to use multiple paths to route their packets. Max-min fairness (MMF) can be effectively applied to single-path networks, but computing MMF rates in multipath networks requires solving a series of linear programming (LP) problems with high computational cost. Thus, a relaxation of MMF has been proposed, namely, upward max-min fairness (UMMF), which can be solved by simple combinatorial algorithms. Current proposals carry out incremental approximations emulating the waterfilling algorithm, which inherently establishes a dependency between the time required to achieve the optimal solution and the capacity of the links. Thus, the more capacity the network has, the less efficient the algorithms are. We defined the concept of the saturation level as the basis for the computation of fair shares. We developed the first centralized algorithm based on this concept, which we call c-SLEN. Unlike its predecessors, its convergence time does not depend on network capacity, and it does not incur link oversaturation. Based on c-SLEN, we derived d-SLEN, a distributed protocol that does not need to maintain per-subflow information in routers and guarantees constant processing time for control packets, making it a good candidate for practical use. Finally, through extensive simulations, we showed that d-SLEN is faster, lighter, and more accurate than its counterparts. Owing to its accuracy and convergence speed, it is able to maintain the size of link queues at minimal values at all times, thus proactively avoiding network congestion.

Keywords

• ERC algorithms
• multipath networks
• upward max-min fairness
• high-speed networks
• proactive congestion control