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

[Wuwei]

Hi,Steven Low

Yes, there have been numerous works made in the context of flow optimization, such as 
Kelly's, Kunniyur and Srikant's, La nad Anantharam's,Mo and Walrand's and some guys
in MS Research in London.But i think the works are focusing on the case of single 
utility function in a network, such as proportional fairness (U=log x) and more 
generally (p,alpha)-proportional fairness (U=x_^(1-alpha)/(1-alpha)). What is the 
case when different utility function is used? From my understanding, a user's utility
function only determine his equilibrium rate by optimizing U(x_i)-px_i (x_i=U_^(-1)(p)) 
where p denotes the end-to-end price or can be interpreted to mark/loss rate. 

Another question is how to describe non-elastic traffic in the "utility". Obviously,
many of them will not be concave. It seems that Shenker's Sigcomm98 paper made some
preliminary work on it, but no fairness issues have ever been found. 

BTW: I remember in Kunniyur and Srikant's Infocom2000 paper has proved TCP reno et al
has the utility function U=-1/x. I wonder whether it is U=-1/x_i or U=arctan(rtt_i x_i).

Thanks 

Best Regards
Wei Wu
wuwei at sdp.ee.tsinghua.edu.cn
|=====================================================================|
| Wei Wu, Complexity Engineering System Labs (CESL)                   |
| Electronics Engineering Department, Tsinghua University             |
| Beijing, P.R.China                                                  | 
|                                                                     | 
| Office:Room 401 Division 10,Eastern Main Building of Tsinghua Univ. |
|       (tel) 86 10 6277 3228                                         |
| Dorm  :Room 300 Apartment 14, Tsinghua Univ.                        |
|       (tel) 86 10 6277 8632                                         |
|=====================================================================| 

In your letter 2001-8-8 16:52:00 
>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