This paper studies basic properties of rate-based flow-control algorithms a
nd of the max-min fairness criteria. For the algorithms we suggest a new ap
proach for their modeling and analysis, which may be considered more "optim
istic" and realistic than traditional approaches. Three variations of the a
pproach are presented, and their rate of convergence to the optimal max-min
fairness solution is analyzed. In addition, we introduce and analyze appro
ximate rate-based now-control algorithms. We show that under certain condit
ions the approximate algorithms may converge faster. However, we show that
the resulting flows may be substantially different from the flows dictated
by the max-min fairness. We further demonstrate that the max-min fairness s
olution can be very sensitive to small changes, i.e., there are configurati
ons in which an addition or deletion of a session with rate delta may chang
e the allocation of another session by Omega(delta . 2(n/2)), but by no mor
e than O(delta . 2(n)). This implies that the max-min fairness criteria may
provide a bad estimate of how far a set of now allocations is from the opt
imal allocation. (C) 1999 Academic Press.