A distributed and quiescent max-min fair algorithm for network congestion control

- B-Neck is the first quiescent max-min fair distributed optimization algorithm.
- B-neck quiescence can be advantageous in energy efficiency scenarios.
- B-Neck correctness and quiescence are formally proved.
- A tight upper bound on the convergence time of B-Neck is formally proved.
- Experimental results encourage its use in anticipatory congestion control systems.

Given the higher demands in network bandwidth and speed that the Internet will have to meet in the near future, it is crucial to research and design intelligent and proactive congestion control and avoidance mechanisms able to anticipate decisions before the congestion problems appear. Nowadays, congestion control mechanisms in the Internet are based on TCP, a transport protocol that is totally reactive and cannot adapt to network variability because its convergence speed to the optimal values is slow. In this context, we propose to investigate new congestion control mechanisms that (a) explicitly compute the optimal sessions' sending rates independently of congestion signals (i.e., proactive mechanisms) and (b) take anticipatory decisions (e.g., using forecasting or prediction techniques) in order to avoid the appearance of congestion problems. In this paper we present B-Neck, a distributed optimization algorithm that can be used as the basic building block for the new generation of proactive and anticipatory congestion control protocols. B-Neck computes proactively the optimal sessions' sending rates independently of congestion signals. B-Neck applies max-min fairness as optimization criterion, since it is very often used in traffic engineering as a way of fairly distributing a network capacity among a set of sessions. B-Neck iterates rapidly until converging to the optimal solution and is also quiescent. The fact that B-Neck is quiescent means that it stops creating traffic when it has converged to the max-min rates, as long as there are no changes in the sessions. B-Neck reacts to variations in the environment, and so, changes in the sessions (e.g., arrivals and departures) reactivate the algorithm, and eventually the new sending rates are found and notified. To the best of our knowledge, B-Neck is the first distributed algorithm that maintains the computed max-min fair rates without the need of continuous traffic injection, which can be advantageous, e.g., in energy efficiency scenarios. This paper proposes as novelty two theoretical contributions jointly with an in-depth experimental evaluation of the B-Neck optimization algorithm. First, it is formally proven that B-Neck is correct, and second, an upper bound for its convergence time is obtained. In addition, extensive simulations were conducted to validate the theoretical results and compare B-Neck with the most representative competitors. These experiments show that B-Neck behaves nicely in the presence of sessions arriving and departing, and its convergence time is in the same range as that of the fastest (non-quiescent) distributed max-min fair algorithms. These properties encourage to utilize B-Neck as the basic building block of proactive and anticipatory congestion control protocols.