Additive Increase Appears Inferior
Sergey Gorinsky, Harrick M. Vin · 2000
Feedback-based adjustment of load is a common mechanism for resource allocation in computer networks. This paper disputes the popular beliefs that the additive-increase multiplicative-decrease adjustment policy is optimal or even necessary for convergence to fair resource sharing. We demonstrate that, in the classic synchronous model, additive increase does not guarantee the quickest convergence of fairness. Moreover, not only fairness but also efficiency converges very slowly under additive increase. For an asynchronous model, we show that the additive-increase multiplicative-decrease algorithm fails to converge to optimal fairness. We observe that the TCP congestion control algorithm suffers from the problems detected by our analysis and is unfair. 1 Introduction Plenty of congestion control schemes rely on feedback to achieve efficient and fair resource allocation among network users. Since networks are large distributed systems with dynamic load on resources, feedback is often bin...