[Iccrg] LT-TCP followup

[Lachlan Andrew]

Greetings Michael,

Executive summary:
- The "loss additivity" approximation is conservative.  TCP is more agressive.
- Assuming equal loss on multiple links introduces the worst case
error to that assumption.
- The "equal rate through the flow" assumption is only made in my
claim that TCP is  alpha=2 fair, not in our analysis of high loss
networks
- To discuss fairness, we need to separate "cost" from "benefit".

On 06/08/07, Michael Welzl <michael.welzl at uibk.ac.at> wrote:
> > Applications certainly can produce variable rate data.
>
> ...the rate jumps to a higher value
> because the limit no longer exists". ... re-routing to a new path (which
> I'd consider a more reasonable example for a flow to suddenly cause
> a certain amount of congestion, as a congestion control mechanism would
> normally prevent an application from such "jumps").

Yes, rerouting could certainly cause that.  I wasn't meaning to imply
that the change was sudden -- I thought Jain's definition just refered
to the direction of the change.  But anyway, I think we roughly agree
here that TCP's current behaviour can (safely) induce what Jain called
congestion collapse.

> > For sources which produce congestion,  p  *is* very small.
> >  A window of a mere 10 packets needs roughly p = 10^-2.
>
> "For sources which produce congestion", p can be anything.

Ahh, yes.  If the flow doesn't follow TCP then  p  certainly can be
anything.  What I meant was "for a flow which reacts to congestion
(not corruption) like TCP does, any flow with a non-negligible  p
will be throttled to fewer than 10 packets, which will no longer cause
congestion".  On reflection, I agree 10 packets may still cause
congestion on a very slow link, or if enough flows do it.

However, that means that TCP is marginally *more* aggressive than what
I'm proposing.  It responds to the true aggregate receive loss rate,
and I'm suggesting responding to the (larger) sum of loss rates.  Of
course, when/if it comes to implementing this allocation, we may need
to revisit whether my suggestion of simply scaling the old TCP window
will be suitable.  It's not yet clear to me if that will be aggressive
or conservative.

> The larger p is, the more important I'd consider it to
> reasonably estimate it.

Agreed.  However, in "reasonable", I'd include a model more
conservative than the current Internet, which Kelly's sum model is.

> In the real Internet, p is very small indeed. However, p is
> also under the influence of your own flow, which will make
> the 2p estimate worse.

Yes, I was careless in how I listed "constant flow rate" in "assumptions".

It is one of the assumptions that I make in saying that TCP
corresponds to  alpha=2  fairness.  For the secnario in which TCP was
designed for, which assumes low-corruption, the influence of our own
flow will be the same on the two links, except for packets dropped due
to congestion.  Using ECN instead of dropping, those packets will also
influence the second link, and so this doesn't make  2p  any worse.

In the proposed high-corruption behaviour, we include the reduction in
load on later links the in model.  (That is why we only get "nice"
results for the case when corruption is only the last link, or only
before the first link.  The general case is still a work-in-progress,
but I expect it to be between these two extremes.)

> > > Since in fact p of the second hop will be less than
> > > p of the first hop
> >
> > a) Replace "loss" by "ECN" and this doesn't apply.
>
> Why? Just like packets can only be dropped once along
> a path, they can also only be ECN-marked once.

OK, I thought that you meant "the traffic will be reduced by the act
of congestion dropping", and so even in the symmetric case, there will
be marginally less congestion on the second link".  ECN will avoid
that one -- as mentioned above.

> > > with all these weird
> > > assumptions as a basis, it makes it hard for me to intuitively
> > > understand what you say.
> >
> > The assumptions are:
> > - flow rate is roughly constant through the life of the path -- which
> > is a 1% or better approximation for current networks
>
> Who says that?

Thanks for challenging me on this one.  It is worse than I had
expected.  I just checked <http://www.internettrafficreport.com/>  and
found that Australia (my home) has 0% loss, while the rest of the
world is hovering around an incredible 15%, meaning that TCP-compliant
windows are only about 4 packets!?!?

> Since the first hop is not unlikely to be the bottleneck,
> the outgoing rate after the first router can be significantly lower.

There can be transients while the queue is building, but in
equilibrium, ACK-clocking ensures that on average, what goes in either
goes on to the next hop, is dropped/marked due to congestion (which
adds to outgoing rate if ECN is used) or is corrupted (which the
design of the current TCP ignores, but is correctly handled as the
exception to this assumption in our model).

> parking lot scenario that we discussed, where you argue
> that the assumption that p of the two-hop flow is 2*p of
> the one-hop flows, we also have the assumption that p
> is constant throughout the network, which I absolutely
> don't believe to be true in reality.

Nor do I.  It is just the worst case.  Consider two links with  p_1
and  p_2 = k p_1, where  k<=1  without loss of generality.  Then
1-(1-p_1)(1-p_2) = (1+k)p_1 - k(p_1)^2.  The smaller  k  is (the less
equally the losses are shared), the smaller the error term is relative
to the sum term.  For example,
p_1 = 10%,  p_2 = 10%,  absolute error = 1%   relative error = 5%
p_1 = 10%,  p_2 = 4%, absolute error = 0.4%,  relative error = 3%
p_1 = 20%,  p_2 = 4%, absolute error = 0.8%,  relative error = 3%

> > - loss probability is cumulative through the network -- again 1% or better
>
> Who says that? Do you have measurements to back this up?

Before answering this:
1. Remember that this is conservative when modelling current TCP.  TCP
actually responds as if the loss probability is the  lower  of the two
values, while I'm proposing responding to the  higher  of the two
values.
2.  I was being slightly optimistic, and thinking of the *absolute*
error as being 1% loss or better.  The *relative* error could be up to
10% in some quite conceivable cases.

>From <http://www.icir.org/floyd/ccmeasure.html>, the global loss rate
was 4% in 2000.  If  that comes from  p = 4% on one link and none
elsewhere, then the sum rule is exact.  Otherwise, the worst case is
p_1 = 2%, p_2 = 2%, giving an absolute error of 0.04%, and a relative
error of 1%.

Of course, many individual flows will have higher loss rates.
However, as you pointed out, most flows (especially low rate = high
loss ones) have only one significant bottleneck at some point in the
access network.  In that case, the approximation is even better

> > - each "lost packet" causes one "loss event"
>
> Quite improbable. Losses are typically clustered in the
> Internet;

Granted.  In the theory community, it has been a "standard"
assumption, but on reflection I don't think I need it (see the better
approximation below).

> > - packet loss probability is equal for all flows
>
> I could live with this one if you'd assume that all
> flows traverse exactly the same path.

You're absolutely right.  I meant "packet loss probability   at a
given link   is equal for all flows".  Obviously if different flows
use different links then they can have totally unrelated loss rates :)


> > I believe they're all pretty standard...
>
> No, I think they're all completely wrong

*grin*  OK.  David and I will keep looking for evidence.

> > ...and more intuitive than
> > replacing the last two by something more accurate.

Actually, I take that back.  The last two can be replaced by:
- Each loss event is caused by a congestion event at a single queue
- Each flow using a queue has an equal probability of observing a
congestion event at that queue.

(I think the first of these actually also makes the "sum of loss
probabilities" point moot too, so that leaves us with these two plus
"- The total reduction in load due to congestion loss is small".)

The first is hard to verify because "congestion event" at a queue is
hard to define, and harder to measure.  However, I believe it is more
accurate than what I originally said, if most queues are droptail.  It
is certainly compatible with your observations, and it is also
compatible with the intuition of a queue which is almost overflowing
"bumping up against being full" several times before subsiding
appreciably.

I agree that the second isn't exact but this assumption, or some
variant, is the basis for any notion that it is even possible
loss-based congestion control to be fair.  It isn't quite accurate
when, for example, TFRC flows share with non-TFRC flows, but has only
recently been recognised as being an approximation rather than fact.
As evidence, I'd cite every paper that shows Reno over one link is
fair.


> Note that I'm not playing devil's advocate - I honestly
> believe that they're completely wrong. For instance,
> you'll probably lose some packets at some bottleneck
> along the path, and lose nothing in most other routers,
> as opposed to losing the same amount everywhere - if
> that's the case, this renders some of your assumptions
> above wrong.

OK.  The assumptions that I meant to say (as opposed to what I did
say...) are fairly standard.  I agree that you'll generally only have
one major bottleneck; if that seems to violate one of the assumption,
then I didn't explain the assumption clearly.  Which does it violate?

> > If we suddenly cause 10 times the congestion
> > per received packet, TCP would start giving us
> > data at about 1/3  ( 1/sqrt(10) ) the rate.
> >
> > If we want to have the same response when we suddently cause 10 times
> > the congestion per received packet because of 90% corruption, then we
> > need to send at a rate about 10/3 higher, so we still get data at a
> > rate of about 1/3 the original.
>
> I'm honestly very sorry, but I still don't get it. Why 10/3?

If you're happy that we want to *receive* at the same rate in the two
cases  (1/3 of the original short-route/corruption-free rate) then
sending at rate 10/3  times the original corruption-free rate follows
from the fact that we need to  send  at 10 times the rate that we
receive.

> > TCP originally specified sending rates because it specified an
> > algorithm run at the sender, not a fairness paradigm.  In a
> > non-collapsed world with reliable links, sending rate is approximately
> > receiving rate, so TCP essentially specifies both sending rates and
> > receiving rates.
>
> I can't live with the "non-collapsed world with a reliable links"
> assumption here. We're talking about severe cases in our examples -
> severe corruption, possibly severe congestion.

True.  I was talking about the world that VJ was trying to create, not
the one he was trying to avoid.  If everyone followed his TCP, then in
the "loss = congestion" world view, he was specifying the rate that
flow would achieve.

You're absolutely right that we're looking at a different case here,
which is why we need to revisit the principles rather than the
specifics.  To me, the principle is "everyone should get fair benefit,
balanced by how much congestion they cause".  Neither side of that
balance directly corresponds to sending rate, although it is related
to both.  VJ used send rate as a surrogate for both benefit and
congestion-causing, because Kelly hadn't come along yet to show us how
they relate.

> > Sending rate:  reflects actual harm done to the network.
> > Receiving rate:  determines actual benefit done to the user.
> >
> > In the tradeoff between congestion caused and data delivered,
> > the sensible (to me) "rate" of the flow is the data delivered.
>
> As a measure of "harm done to the network", I agree, but not
> as the rate that we want to control.

Sorry, I'm not sure what you mean.  It sounds like you think I'm
saying that "data delivered is a measure of harm done to the network",
which isn't what I meant.  The way I see it, we have
  Cost:    measured by corruption loss (or ECN, or ...)
  Benefit: data received by a flow
I believe we should decide how to balance these two (in a way which is
fair to existing flows) and then choose the sending rate to achieve
that.

> If you want to match the
> receive rate of TCP, I'd suggest to invent a new term  :)

OK, I'm happy to do that.  "TCP-fair" comes to mind.  The term
"minimum expected delay" has been used for this type of fairness, but
"square-root formula fair" may sound more familiar.  I'll call it
whatever is most likely to get it adopted :)

Cheers,
Lachlan

-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603