Fairness of TCP (was Re: [e2e] a new paper on Adaptive RED)

[Steven Low]

By "fairness", we typically mean some property about the equilibrium
rate vector.   An insight suggested by recent work (e.g. Kelly, Srikant,
Walrand, Anatharam, and ours, etc) is that
TCP/AQM can be thought of as carrying out a distributed computation
over the internet to solve an optimization problem - maximizing
aggregate
utility.  Moreover, the utility functions associated with different
protocols
can be explicitly derived.   Within this context, then, the unique
equilibrium rate vector is determined solely by TCP protocol (or its
utility function), and *not* by AQM (but see below).

For example, Reno (& its variants such as NewReno, SACK) has a utility
of (roughly) arctan(rtt_i x_i), which equalizes window for sources that
*see the same loss probability in their paths*.  This is the same as the
1/sqrt(p) model when p is small.   This utility function determines the
equilibrium rate vector, and hence fairness among different sources in
a well-known way.

The only way AQM can alter fairness, without changing TCP Reno, is to
tinker with loss probability as seen by the sources.  For example, the
above models assume all sources see the same loss probability at a 
common bottleneck node, because each packet, regardless of which flow
it belongs, is dropped with the same probability in RED.   In principle,
one can manipulate loss probability on a per-flow basis to steer the
equilibrium rate vector to satisfy any fairness relation.

Btw, the utility function of TCP Vegas is log, and hence Vegas
achieves (weighted) proportional fairness.

Steven

ps. I'd cover the equilibrium and dynamic (stability) properties
of TCP/AQM in a Sigcomm tutorial later this month:
http://www.acm.org/sigs/sigcomm/sigcomm2001/tutorials.html
Comments/suggestions will be appreciated.






Saverio Mascolo wrote:
> 
> ----- Original Message -----
> From: "Ramakrishna Gummadi" <ramki at aciri.org>
> To: "Saverio Mascolo" <mascolo at poliba.it>
> Cc: "Sally Floyd" <floyd at aciri.org>
> Sent: Friday, August 03, 2001 5:07 PM
> Subject: Re: [e2e] a new paper on Adaptive RED
> >
> > 1) As long as end users are assumed to be behaving correctly (which is
> > what the original RED and adaptive RED assume), random dropping can
> guarantee
> > fairness. Under this assumption, adaptive RED is no more or no less fair
> > than RED. That is why we say---"We do not discuss the fairness behavior of
> > Adaptive RED, since this is quite similar to the fairness behavior of
> > RED."
> 
> Actually what I have found is that RED/Gentle RED do not improve fairness in
> a significant way but they reduce the throughput over high speed links ( 100
> Mbps link).
> 
> In my opinion, main reason because RED does not work is that queue average
> introduces delay for which the discard is no more early as it should be.
> Using a simple constant  dropping rate, related to instantaneous queue
> level, makes things much more easy and  effective.
> 
> Thanks,
> Saverio

-- 
__________________________________________________________________
Steven Low, Assoc Prof of CS & EE 
slow at caltech.edu			netlab.caltech.edu
Tel: (626) 395-6767			Caltech MC256-80
Fax: (626) 792-4257			Pasadena CA 91125