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

Dah-Ming Chiu and Raj Jain, Digital Equipment Corporation, 1989

B<Summary.> The key component in a congestion avoidance algorithm is the
I<control> formula for increasing or decreasing the user load (window or
rate). For both increasing and decreasing, the control formula can include
an I<additive> component, a I<multiplicative> component or both. This
paper shows that the optimal control formula uses I<additive increase>
and I<multiplicative decrease>.

=head1 More Detail

The control formula can be judged based on the following: 
	
=over 4

=item *

convergence - time to reach I<equilibrium>. Equilibrium is a steady
state where the total load oscillates around the optimal
state. Equilibrium can be characterized by I<responsiveness>, the time
to reach the I<Goal> state, and I<smoothness>, the amount of
oscillation around the Goal state once equilibrium is reached.

=item *

fairness - the maxmin model is used. Users are partitioned into groups based
on which resource is their primary bottleneck; all users in one group should
receive an equal share of the resource; i think what is left over is 
partitioned according to who needs the remaining (all users specify a min
& a max?); The I<fairness index> is the (sum of all the user's loads) squared
divided by the (sum of all the user's loads squared); the index's value
is between 0 and 1 with one being perfectly fair; completely unfair (one
user gets all of the resource) is 1/n which approaches 0 as n reaches 
infinity. 

=item *

efficient (the closeness of the total load to the knee). Efficiency
relates only to the total allocation so we can reach perfect
efficiency and not have fairness.

=item *

distributedness. The load should be determined by the individual sources
based on little feedback from the network. A centralized algorithm would
require complete knowledge of the system; to convey that information to 
each resource would produce considerable overhead. 

=back

They begin by describing the optimal load: the load at which throughput
is big and delay is small. When graphed as (throughput,delay), this is
the I<knee>. At loads greater than the knee, a small increase in throughput
results in a large increase in delay as queues build up. The point at which 
packets are lost is called the I<cliff>. 

Their model has 2 sources. The feedback & control loop is synchronous for 
all users (meaning that all receive feedback simultaneously and adjust
their loads simultaneously). The use a vector representation of loads. The
axes are the two sources' allocations. The I<efficiency line> is the line 
x+y = C. The I<fairness line> is the line x=y. The optimal point is where
the fairness line and the efficiency line intersect. An I<equifairness> line
is any 45-degree line parallel to the fairness line as all points on it
are equally fair. The I<underload> region is below the efficiency line. The 
I<overload> region is above the efficiency line. Multiplicative changes
move along the line between the current point and the origin. Additive 
changes move along the equifairness line through the current point. 

Immediately, we can see that an additive increase/ multiplicative decrease
coveerges to the optimal point. +/+ can converge to efficiency line but
cannot converge to optimal point as the fairness never improves. 

The analysis is based on these control coefficients:

=over 4

=item *

ai: additive increase constant

=item *

bi: multiplicative increase factor

=item *

ad: additive decrease constant

=item *

bd: multiplicative decrease factor

=back

B<Convergence to Efficiency.>
For a control condition to be feasible, it must adhere to the 
B<Principle of negative feedback>:  make sure that the system reacts correctly
to feedback. In other words, if we receive feedback saying the network
is congested, the controls should decrease the load and vice-versa. 

B<Convergence to Fairness.>
We can ensure non-decrease of fairness locally by ensuring that a/b >=
0. Therefore, the two cannot be of different signs so it follows that they
must all be positive. So, to converge to fairness we have the following 
set of conditions (10): 

=over 4

=item *

ai >= 0, bi >= 0

=item *

ad >= 0, 0 <= bd < 1

=back

B<Distributedness.> The conditions above for converging to fairness are
already distributed since they require no state information so we'll build
upon them. We must now try to satisfy the negative feedback requirement. 
This leads us to the following conditions (12):

=over 4

=item *

ai > 0, bi >= 0

=item *

ad = 0, 0 <= bd < 1

=back

Truncation: use (10) but take max of current and X(t(i+1)) if increasing,
min if decreasing. With trucation, have a set of conditions weaker than 12 but
stronger than 10. Based on these conditions:

=over 4

=item *

B<Proposition:> In order to satisfy reqs of distributed 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 (may have a multiplicative component with
a coefficient no less than one).

=back

B<Vectorial representation of the feasability conditions.> From 
awesome graphs in the paper, we see that for a point in the overloaded
area, if we take the intersection of the region where we are
guaranteed greater efficiency and the region where we are guaranteed
greater or equal fairness, the only options are along the vector going
through the point to the origin -- multiplicative decrease.

Likewise for the vectorial representation of the feasibility conditions
for increase, the intersection of the areas for greater efficiency and
fairness is the 45 degree line through the point -- additive increase. 

Note that there is a tradeoff between increasing responsiveness and 
increasing smoothness. 

B<Optimal convergence to fairness.> Through analysis, the 
multiplicative component in the increase policy falls out. This leads us
to:

=over 4

=item *

B<Proposition 3:> for *optimal* convergence to fairness (versus
proposition 1 which was not necessarily optimal convergence), we should
have additive increase and multiplicative decrease. 

=back

B<Nonlinear controls.> Their +/* control policy works on an example
that they give and nonlinear controls are more flexible in trying 
to achive fairness,  but they say that nonlinear controls usually depend 
on system parameters. For this reason, they would be difficult to 
configure and would require human intervention.