Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2006-01-01

Filename

wucse-2006-40.pdf

Technical Report Number

WUCSE-2006-40

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K71V5C69

Download

Share

COinS