Back to index
An Analysis of the Increase and Decrease Algorithms for
Congestion Avoidance in Computer Networks
Dah-Ming Chiu and Raj Jain, DEC
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.
- Assumptions: all users sharing same bottleneck link see same
congestion feedback; control loop for all users is a synchronous
(all users see feedback and react to it, then more
- Discrete-time functions:
- xi(t): bandwidth demand of i'th user.
- y(t): binary-valued congestion indication, sent to all
- ui(t): user-effected change in demand based on
y(t) feedback. ui(t)=f(xi(t),
y(t)). Paper considers case where f is linear:
f=A+Bxi(t) for increase, f=a+bxi(t)
- Properties to optimize for:
- Efficiency: how close is sum(xi) to Xgoal
(the desired bandwidth of the link)?
- Fairness: defined as sum(xi)2/(n
sum(xi2)), so that:
- fairness is in [0.0,1.0]
- 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=Xgoal (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
- Multiplicative decrease corresponds to moving "inward"
along a line connecting the point to the origin.
- Development of constraints on A, B, a, b yields the following
- 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
- How does delayed feedback affect control?
- What is marginal utility of multiple bits of feedback
Mathematical (and nice graphical) treatment of fairness and efficiency
that yields a nice and intuitively satisfying result.
As pointed out by the authors. Also, the graphical "proofs" are nice
but not clear how some of them extend to multiple dimensions.
Back to index