A Theory of Load Adjustments and its Implications for Congestion Control

Multiplicative Increase (MI), Additive Increase (AI), and Multiplicative Decrease (MD) are linear adjustments used extensively in networking. However, their properties are not fully understood. We analyze responsiveness (time for the total load to reach the target load), smoothness (maximal size of the total load oscillations after reaching the target load), fairing speed (speed of convergence to equal individual loads) and scalabilities of MAIMD algorithms, which generalize AIMD algorithms via optional inclusion of MI. We prove that an MAIMD can provide faster asymptotic fairing than a less smooth AIMD. Furthermore, we discover that loads under a specific MAIMD converge from any initial state to the same periodic pattern, called a canonical cycle. While imperfectly correlated with smoothness, the canonical cycle reliably predicts the asymptotic fairing speed. We also show that AIMD algorithms offer the best trade-off between smoothness and responsiveness. Then, we introduce smoothness-responsiveness diagrams to investigate MAIMD scalabilities. Finally, we discuss implications of the theory for the practice of congestion control