An Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

One-line summary: Additive increase and multiplicative decrease for congestion control are necessary and sufficient conditions for convergence to an efficient and fair state regardless of the initial network state.

Overview/Main Points

• Assumptions: all users sharing same bottleneck link see same congestion feedback; control loop for all users is a synchronous discrete-time operation (all users see feedback and react to it, then more feedback comes)
• Discrete-time functions:
  • x_i(t): bandwidth demand of i'th user.
  • y(t): binary-valued congestion indication, sent to all users
  • u_i(t): user-effected change in demand based on y(t) feedback. u_i(t)=f(x_i(t), y(t)). Paper considers case where f is linear: f=A+Bx_i(t) for increase, f=a+bx_i(t) for decrease.
• Properties to optimize for:
  • Efficiency: how close is sum(x_i) to X_goal (the desired bandwidth of the link)?
  • Fairness: defined as sum(x_i)²/(n sum(x_i²)), so that:
    • fairness is in [0.0,1.0]
    • dimensionless
    • continuous function of allocations
    • if only k of n users share resource, fairness is k/n.
  • Distributedness: no user can know value of n.
  • Convergence: responsiveness measures latency of system to approach goal state, smoothness measures size of oscillations about the goal state.
• Graphical representation: in an n-dimensional space where each axis is one user's allocation. Example in 2D is explored.
  • y=x is the fairness line. (All points on any line passing through the origin have the same fairness, since multiplying both allocations by the same factor gives them the same share (fairness formula is invariant to multiplication)). In order to achieve fairness, system should converge to a point on this line.
  • Efficiency line is y+x=X_goal (maximum utilization). To get to efficiency, system must move toward this line.
  • Efficinecy and fairness lines intersect at a single point, the optimum operating point.
• Graphical representation of policy operations:
  • Additive increase corresponds to moving "outward" along a line of slope 1.
  • Multiplicative decrease corresponds to moving "inward" along a line connecting the point to the origin.
  • Etc.
• Development of constraints on A, B, a, b yields the following conclusions:
  • A,B,a,b cannot be of opposite signs and cannot be negative, therefore must all be >0
  • Specifically, must have A>=0, B>=0, a>=0, 0<=b<1, to insure that fairness goes up during utilization decrease and either goes down or stays the same during utilization increase
  • To guarantee convergence to efficiency in the face of distributedness (no user can know n), actually need the stronger conditions: A>0, B>=1, a=0, 0<=b<1.
• Proposition: in order to satisfy distributed convergence to efficiency and fairness without truncation (extreme backoff), we need mlutplicative decrease and additive increase, with the coefficients constrained as described above.
• Practical considerations:
  • allocations must be an integral number of packets. How are convergence conditions affected by rounding?
  • Reasonable to implement (amount of hardware, complexity of code, etc.)?
  • How does delayed feedback affect control?
  • What is marginal utility of multiple bits of feedback info?

Relevance

Flaws