From: Susumu Harada (harada@cs.washington.edu)
Date: Sun Oct 17 2004 - 22:34:53 PDT
"Analysis of the Increase and Decrease Algorithms for Congestion Avoidance
in Computer Networks"
Dah-Ming Chiu and Raj Jain
This paper presents a mathematical framework for analyzing the
effectiveness of various algorithms used by the hosts to modify the
window-size (increase/decrease algorithms) in a congestion avoidance
scheme, in this case the binary feedback scheme presented in the other
paper by Ramakrishnan and Jain ("A Binary Feedback Scheme for
Congestion Avoidance in Computer Networks with a Connectionless Network
Layer").
The authors define four criterias upon which the algorithms are compared.
They are 1) efficiency, 2) fairness, 3) distributedness, and 4)
convergence. Efficiency represents how close the total allocation of the
router resource is to the "knee" of the load-throughput curve.
Measure of convergence includes the combination of the time it takes to
reach convergence (responsiveness) and the size of oscillation about the
point of convergence (smoothness).
One very unique aspect of the paper that distinguishes it from the
original paper by Ramakrishnan and Jain is its representation of the
system state transition as "a trajectory through n-dimensional vector
space", where n represents the number of users with each axix representing
the corresponding user's allocation of network bandwidth. Using this
representation, the authors define two reference "hyperplanes". One is
the fairness "line", which represents points with equal distribution of
resources among all users. The other is an efficiency "line", which
represents the allocation of resources at the "knee" of the
load-throughput curve of the router. Using this representation and the
mathematical representation of the desired system behavior, the author
shows that the linear decrease policy should be multiplicative in order to
converge to optimal efficiency and fairness, and that the increase policy
must be additive in order to optimize the convergence.
I found the paper to be very insightful in its approach to represent the
constraint problem as a geometric representation in multi-dimensional
space, and also for its presentation of the further questions that remain
from their discussion of the congestion avoidance problem. In particular,
I was particularly interested in finding out the impact of using multiple
bits instead of just one to encode various other information such as the
guess at the number of users contending for the resource.
This archive was generated by hypermail 2.1.6 : Sun Oct 17 2004 - 22:34:53 PDT