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

[Peter Key]

Hi Wuwei,

You have described the "user optimisation", and one can show that under
certain assumptions (requiring  concave utility functions etc) that
these user  Optimisations also maximise the "social welfare" in a
network (for a single resource this defined  as $\sum_i U_i(x_i) -
C(\sum_i x_i)$), provided that the shadow prices (mark rates $p$)
represent  derivatives of the cost function $C()$.

Hence if different users use different (concave) utility functions, they
just share out the bandwidth according to these preferences, where the
marking algorithm determines the marking/price function $p$.  Different
utility functions can be engineered as different rate adaptation
algorithms.

Non-elastic traffic may have a convex or "s-shaped" utility function, in
which case traffic enters provided the marking rate or "price" "p" is
below some threshold.

Laurent Masssoulie & I looked at how these different types of utility
functions interact in a stochastic setting in an ISQE paper, "User
policies in a network implementing congestion pricing" 
http://research.microsoft.com/research/network/publications/ISQElm.ps
One of the interesting consequences  of looking at a large network limit
is that an optimal file transfer strategy does not correspond to a
concave rate utility function!

Best,

Peter



> -----Original Message-----
> From: Wuwei [mailto:wuwei at sdp.ee.tsinghua.edu.cn]
> Sent: 09 August 2001 02:51
> To: slow at caltech.edu; Saverio Mascolo
> Cc: Ramakrishna Gummadi; end2end-interest at postel.org
> Subject: Re: Fairness of TCP (was Re: [e2e] a new paper on Adaptive
RED)
> 
> 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
> 
>