Paper review: Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

Reviewer: Mike Liu

  1. State the problem the paper is trying to solve.
  2. The main problem the paper is trying to analyze is congestion avoidance algorithms, namely increase/decrease algorithms, and tries to solve the problem by devising a solution using simple additive increase and multiplicative decrease.
  3. State the main contribution of the paper: solving a new problem, proposing a new algorithm, or presenting a new evaluation (analysis). If a new problem, why was the problem important? Is the problem still important today? Will the problem be important tomorrow?  If a new algorithm or new evaluation (analysis), what are the improvements over previous algorithms or evaluations? How do they come up with the new algorithm or evaluation? 
  4. The main contribution of this paper is that it documents and characterizes abstractly the a wide class of increase/decrease algorithms and compares them using several different performance metrics. The key metrics it defines are efficiency, fairness, convergence time, and size of oscillations. This is a very novel analysis because it give some way to measure the effectiveness of future algorithms that are used to solve this general problem of congestion avoidance. It will still be important tommorow since as new algorithms are introduced, their effectiveness and strengths will be measure by these elegant metrics. This paper provided a way to classify and test all such algorithms.
  5. Summarize the (at most) 3 key main ideas (each in 1 sentence.) 
  6. The three 3 key main ideas are: (1) In order to satisfy the requirements of distribued convergence to efficiency and fairness without truncation, the linear decrease policy should be multiplicative, and the linear increase policy should always have an additive component, and optimally it may have a multiplicative component with the coefficient no less than one. (2) For the linear controls with truncation, the increase and decrease policies can each have both additive and multiplicative components. (3) For both feasibility and optimal convergence to fairness, the increase policy should be additive, and the decrease policy should be multiplicative.
  7. Critique the main contribution
  8. What lessons should researchers and builders take away from this work. What (if any) questions does this work leave open?
  9. The key lesson that researcher and builders should take away from this work is that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for convergence to an efficient and fair state regardless of the starting state of the network. The questions it leaves open are: How does delayed feedback affect the control? What is the marginal utility of increase bits of feedback? Is it worthwhile to guess the current number of users n? What is the impact of asynchronous operation? Finally, perhaps most importantly, how well does this algorithm fare when implemented in the real world? What is its performance when implemented on the Internet?