chiu_jain.increase_decrease_analysis
Dah-Ming Chiu and Raj Jain, Digital Equipment Corporation, 1989
Summary. The key component in a congestion avoidance algorithm is the
control formula for increasing or decreasing the user load (window or
rate). For both increasing and decreasing, the control formula can include
an additive component, a multiplicative component or both. This
paper shows that the optimal control formula uses additive increase
and multiplicative decrease.
The control formula can be judged based on the following:
- convergence - time to reach equilibrium. Equilibrium is a steady
state where the total load oscillates around the optimal
state. Equilibrium can be characterized by responsiveness, the time
to reach the Goal state, and smoothness, the amount of
oscillation around the Goal state once equilibrium is reached.
- 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 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.
- 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.
- 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.
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 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 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 efficiency line is the line
x+y = C. The fairness line is the line x=y. The optimal point is where
the fairness line and the efficiency line intersect. An equifairness line
is any 45-degree line parallel to the fairness line as all points on it
are equally fair. The underload region is below the efficiency line. The
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:
- ai: additive increase constant
- bi: multiplicative increase factor
- ad: additive decrease constant
- bd: multiplicative decrease factor
Convergence to Efficiency..For a control condition to be feasible, it must adhere to the
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.
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):
- ai >= 0, bi >= 0
- ad >= 0, 0 <= bd < 1
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):
- ai > 0, bi >= 0
- ad = 0, 0 <= bd < 1
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:
- 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).
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.
Optimal convergence to fairness. Through analysis, the
multiplicative component in the increase policy falls out. This leads us
to:
- Proposition 3: for *optimal* convergence to fairness (versus
proposition 1 which was not necessarily optimal convergence), we should
have additive increase and multiplicative decrease.
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.