Fairness of TCP (was Re: [e2e] a new paper on Adaptive RED)
peterkey at microsoft.com
Fri Aug 10 02:21:29 PDT 2001
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
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"
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!
> -----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
> 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
> some guys
> in MS Research in London.But i think the works are focusing on the
> utility function in a network, such as proportional fairness (U=log x)
> generally (p,alpha)-proportional fairness (U=x_^(1-alpha)/(1-alpha)).
> 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
> where p denotes the end-to-end price or can be interpreted to
> Another question is how to describe non-elastic traffic in the
> many of them will not be concave. It seems that Shenker's Sigcomm98
> 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
> 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).
> 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,
> >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
> >utility. Moreover, the utility functions associated with different
> >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
> >of (roughly) arctan(rtt_i x_i), which equalizes window for sources
> >*see the same loss probability in their paths*. This is the same as
> >1/sqrt(p) model when p is small. This utility function determines
> >equilibrium rate vector, and hence fairness among different sources
> >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,
> >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
> >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.
> >ps. I'd cover the equilibrium and dynamic (stability) properties
> >of TCP/AQM in a Sigcomm tutorial later this month:
> >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
> >> > what the original RED and adaptive RED assume), random dropping
> >> guarantee
> >> > fairness. Under this assumption, adaptive RED is no more or no
> >> > 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
> >> > 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
> ( 100
> >> Mbps link).
> >> In my opinion, main reason because RED does not work is that queue
> >> introduces delay for which the discard is no more early as it
> >> Using a simple constant dropping rate, related to instantaneous
> >> 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
More information about the end2end-interest