[Iccrg] Re: TCP requirements

[S. Keshav]

/* 'm ccing ICCRG on this discussion because it touches on a point  
that Michael brought up in his mail to the group */

Lachlan,

>>         Well, in general, simultaneously achieving Pareto  
>> optimality and
>> fairness is hard. Pareto optimality is easy to achieve when you only
>> consider scheduling, because all work-conserving disciplines are
>> Pareto optimal. However, once you take transport effects into
>> account, especially congestion signals, achieving the Pareto frontier
>> is not a given. Consider a bit-setting scheme such as DECbit. If you
>> have a long RTT flow, you could set bits on an over-limit flow, that
>> would take effect only after a while, and then would persist for 2
>> RTTs (because DECbit takes control actions once every 2 RTTs).
>
> Thanks for your explanation, but I don't quite understand it.  In that
> situation, with dynamics, it isn't clear what quantity we are being
> Pareto or max-min with respect to; time average rates? instantaneous
> rates at some time?  I'm only used to thinking of a single average
> rate per (long lived) flow.
>
We can consider the Pareto frontier with respect to at least two  
quantities:

1. Instantaneous (or short-term) rates, measured say, over the time  
scale of a few ms:
We can achieve Pareto optimality at this time scale with any work- 
conserving scheduling discipline. A (max-min) fair scheduling  
discipline can achieve both Pareto optimality and fairness.

2. Time-average rates, measured over several RTTs (10s to 100s of ms):
Here, things are harder because of feedback at the transport layer.  
When modulated by a transport layer, the sum of time average rates of  
all the flows at a bottleneck link may not sum up to the link rate  
(especially with small buffers and long RTTs). Then, Pareto  
optimality will not be achieved. As a thought experiment, consider a  
WFQ scheduler with only 1 packet of buffering per flow, which drops  
packets whenever a flow has more than one packet in its queue. If you  
send TCP over this, you are going to achieve short-term Pareto  
optimality trivially. However, over the long term, you may achieve  
max-min-fair-share, but *not* Pareto optimality.

>> Clearly, to achieve max-min fairness, the control mechanism will lead
>> you to a non-Pareto allocation.

> Perhaps I'm misunderstanding either max-min fairness or
> Pareto-optimality, but I thought that definition of max-min implied
> Pareto-optimality.  If a particular DECbit solution is non-Pareto,
> then one user can increase without hurting any other (definition of
> non-Pareto); hence it can increase without hurting any worse-off user,
> which I thought was the definition of being not max-min.

I think the confusion arises from the fact that there are two time- 
scales of interest. I hope my example above clarifies the situation.  
In particular, I could have a scheduling discipline that does not  
have one buffer statically allocated per flow,but pools buffers and  
serves FIFO. With TCP, my guess is that you will do *better* than WFQ  
(in terms of sum of average rates).

regards
keshav