Subject: [Tsvwg] Eifel-Response-03

From: Reiner Ludwig <[email-masked]>
Date: Wed, 05 Mar 2003 12:51:52 +0100

we have updated the draft that specifies the Eifel response algorithm:
http://www.ietf.org/internet-drafts/draft-ietf-tsvwg-tcp-eifel-response-03.txt

We have followed Pasi Sarolahti's suggestion and made the Eifel response 
algorithm independent of any particular detection algorithm. I.e., it 
should now be possible to also "plug" the Eifel response onto a number of 
alternative detection algorithms including DSACK-based solutions and/or F-RTO.

We would greatly welcome more feedback.

Otherwise, we believe that this draft is ready for WG-last-call to become 
an experimental RFC.

///Reiner

_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Yogesh Prem Swami <[email-masked]>
Date: 05 Mar 2003 11:49:47 -0600

Reiner,

I didn't see anything fundamentally different (apart from the timer
calculation) in this draft from the -01 draft, so all my previous
comments about not restoring the congestion window are still valid. The
rationale behind the timer calculation is also not clear to me. But let
me begin with congestion issues. 

-- The bottom line for a spurious timeout is that a spurious timeout is
spurious ONLY in terms of what packets to resend; its not spurious in
terms of congestion. Congestion is not a property of one particular
connection, but its a property of the *entire* system. So the response
algorithm MUST follow the same congestion principles as a normally
timeout connection.

Restoring congestion window after a timeout is WRONG. Just because a
particular TCP connection was waiting for some new ACK does not mean
that rest of the connections in the system would leave the congestion
state of that connection intact. The competing TCP connections will eat
up all the unused resources (buffer space). Do some analysis or run some
tests and see for yourself.

All the papers and documents that you pointed out shows only a SINGLE
TCP connection in the system (there are other CBR traffic, but CBR does
not compete like TCP does. With CBR the congestion state remains
unaltered). Unless you own an ISP, a Backbone, and the  server, you will
have more than one connection in the system.

Conceptually, the *least* a spurious timed out connection can do is to
follow RFC-2861 (and I don't know why it's not a standards track
RFC)--and that is after you discount subnet change causing spurious
timeout. Also, just see how TRFC behaves if it does not receive an ACK
for some time. Why is Eifel response exempted from all these
considerations.

Eifel response will create a havoc in case of subnet change with present
Inter Protocols (specific networks with hop-by-hop flow control may not
have this problem, but such networks are not part of IP). Again, run
some simulations (let me know if you cannot setup a test scenario with
subnet change).

-- In step ReCC, why should the sender stop processing spurious timeout 
response after 3 timeouts. Why the magic number 3? I guess a better
scheme is to just follow RFC-2861 with some modifications.

-- The timer calculation in STO.2:

SRTT <- SRTT + 1/FlightSize * (RTT-SAMPLE - SRTT)

is most disconcerting. Why should SRTT have a component of FLIGHT_SIZE.
BTW, just to refresh your memory, the RTT samples are the round trip
time for the *entire* congestion window--the samples are taken once
every window--and not for every packet. 

Are you implicitly assuming that RTT is a linear function of window
size. Well, RTT is a linear function only if you have a single queue
(one hop); for the rest of the cases, it increases non-linearly
depending upon the queuing discipline of individual router.

Besides, if you are restoring the window which you are, there is no need
to take FlightSize into consideration.

Also, in the later two steps, aren't the values of SRTT and RTTVAR
reset. Could you explain these three steps:

	SRTT <- SRTT + 1/FlightSize * (RTT-SAMPLE - SRTT)
              and set
        SRTT <- RTT-SAMPLE
        
	RTTVAR <- RTT-SAMPLE/2,

Isn't my value of SRTT same as RTT_SAMPLE after all this fancy
calculation? What am I missing here?

-- yogesh

PS:  Folks, there are many more comments in the DCLOR draft 
(draft-swami-tsvwg-tcp-dclor-00.txt) which I cannot possibly write down
here, but please read it for more arguments why Eifel response is not
right.

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 06 Mar 2003 16:23:59 +0100

At 18:49 05.03.2003, Yogesh Prem Swami wrote:
>The
>rationale behind the timer calculation is also not clear to me.

That point is taken. In the meantime, we have had discussions offline from 
this list about "making the retransmission timer more conservative in 
response to a detected spurious timeout".

Yes, we are convinced. That part needs to be changed.

>Restoring congestion window after a timeout is WRONG.

We have had that discussion before, and you won't convince us just because 
you get more excited about this. Our views and arguments about this issue 
are presented in section 3.4 of the Eifel response draft. You and I have 
different views on this, and that's fine. Let's hear from others instead of 
restating the same opinions over and over again.

The interworking with Congestion Window Validation (CWV) [RFC2861] that you 
brought up, I find relevant, though ...

CWV kicks in if
- the connection has been *idle* for longer than one RTO, or
- the connection has been *application-limited* for longer than one RTO.

In RFC2861, the term *application-limited* is well defined ("When TCP sends 
a packet that does not fill the congestion window, and the TCP send queue 
is empty, then the sender is application-limited."), but unfortunately the 
term *idle* is not so well defined; also not in the CWV pseudo-code. What 
is missing is that *idle* means: "no data is outstanding". This is how V. 
Jacobson defined it in his '92 revision of his SIGCOMM '88 paper (appendix 
C), and that's also how it's implemented in BSD.

With the Eifel response algorithm the situation is different. Once a 
spurious timeout has been detected, the connection had apparently *not* 
been idle before.
Thus, that part of the CWV algorithm should not kick in. The second part of 
the CWV algorithm that deals with *application-limited* connections is 
already implicitly included in the Eifel response algorithm: cwnd is at 
most restored to the current flightsize + IW. This basically follows the 
spirit and intention of the CWV algorithm.

So, I think you have a valid point. In the next revision of the Eifel 
response draft, we should say that the CWV algorithm should be "reset". For 
example, by setting the CWV variables T_last and T_prev to tcpnow.

///Reiner

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 11:28:19 -0500 (EST)

> restating the same opinions over and over again.

I was ready to say that I agree with Yogesh, but...

> spirit and intention of the CWV algorithm.

If cwnd restoration is as explained above, then I think "restoring cwnd"
is fine.

I quickly skimmed the draft and saw on page 5, the step for reverting cwnd
includes the following text:

              If the acceptable ACK has the ECN-Echo flag [RFC3168] set
              OR the TCP sender has already taken more than three
              timeouts for the oldest outstanding segment, then proceed
              to step (DONE),

How was the value three chosen?

~armando

0--                                                  --0
| Armando L. Caro Jr.      |  Protocol Engineering Lab |
| www.cis.udel.edu/~acaro  |    University of Delaware |
0--                                                  --0

---

From: Yogesh Prem Swami <[email-masked]>
Date: 06 Mar 2003 10:30:51 -0600

Hello Reiner, all,

On Thu, 2003-03-06 at 09:23, ext Reiner Ludwig wrote

> are presented in section 3.4 of the Eifel response draft. You and I have 

Here's the excerpt from 3.4:

	"When a TCP sender enters loss recovery, it also assumes that is 	has
received a congestion indication. In response to that it 	reduces cwnd,
and ssthresh. However, once the TCP sender detects 	that the loss
recovery has been falsely triggered, this 	reduction was unnecessary. In
fact, no congestion signal has 	been received. We therefore believe that
it is safe to revert to 	the previous congestion control state."

If I go by this logic, then why shall I start with a small window size
at the start of the connection? At the start of the connection I have no
congestion indication, so I should be able to send what ever amount of
data I want? 

Are you suggesting we should start with a window of say 10M bytes and
wait until we receive congestion indication? Your logic seems to imply
that.

> term *idle* is not so well defined; also not in the CWV pseudo-code. What 

idle is any time period greater than RTO. RTO is an statistical upper
bound during which the *end to end state of the network* will remain
*roughly* (no guarantees) the same as far as congestion is concerned.
Beyond that, there is no reason to believe that network will be in the
same state.

> C), and that's also how it's implemented in BSD.

Congestion control is about the state of the network, not about how you
define certain things. If the state of the network changes because the
sender was not sending data for more than RTO, then that is a valid
candidate for CVW--regardless of the definition used.

In addition, CVS works only when there is no host mobility.

> spurious timeout has been detected, the connection had apparently *not* 

The connection is not idle, but the network has been. Beyond RTO you
don't know what happened in the network.

> spirit and intention of the CWV algorithm.

It doesn't matter whether it's application limited or idle. The simple
rule is: if you have used your share of network resources within RTO,
you can continue using that share. If you have not, you are required to
start from scratch.

But I think it will be good to get some feedback from other people too. 

I strongly disagree with the present response algorithm because it
reduces the over all throughput of the system. Again, I emphsize "the
system" and not one particular TCP connection. We have also put the
results in appendix of the DCLOR draft to see the difference. 

--yogesh

---

From: Yogesh Prem Swami <[email-masked]>
Date: 06 Mar 2003 10:44:17 -0600

Hi,

>               timeouts for the oldest outstanding segment, then proceed

The ECN-ECHO doesn't say anything. Consider this case

		 Part-A			        Part-B
	Sender ----------> pkt stalling node ----------> receiver

The Congestion Experience could have been set either on Part-A or on
Part-B, but the ACKs received after the spurious timeout only tell the
state of the network either

a) for the entire path but before RTO, or
b) only Part-B.

In either case, the sender does not know what the current state of
network is on Part-A. It's possible that Part-B was not congested but
Part-A got congestion during the RTO period and you will not receiver
any ECN-Echo in that case.

On the other hand, if the network did get better during the stalling
period, it's better that the sender should start using the resources at
a faster rate. 

Eifel response fails in both the cases. 

--yogesh

---

From: Ethan Blanton <[email-masked]>
Date: Thu, 6 Mar 2003 12:20:02 -0500

Yogesh Prem Swami spake unto us the following wisdom:
>        "When a TCP sender enters loss recovery, it also assumes
>        that is has received a congestion indication. In response to
>        that it reduces cwnd, and ssthresh. However, once the TCP
>        sender detects that the loss recovery has been falsely
>        triggered, this reduction was unnecessary. In fact, no
>        congestion signal has been received. We therefore believe
>        that it is safe to revert to the previous congestion control
>        state."
> 

I don't think this is equivalent at all to what Reiner's draft is
saying.  His draft is more equivalent to saying "As long as I am
continuing with normal TCP transmission and getting normal
acknowledgements, it's OK to use congestion avoidance as usual."  The
basic point here is that we *thought* we saw congestion, but we didn't
-- we busted our own connection by using an apparently bogus RTO
timer.  As another message in this thread indicated, perhaps finding a
way to fix that RTO is called for, but that is orthogonal to the point
you are questioning here.

> wait until we receive congestion indication? Your logic seems to imply

I'm suggesting (as I agree with Reiner, and I think this is what his
text says) that we should use the accepted TCP congestion avoidance
and congestion control routines, and take advantage of the fact that
we can detect when we made a mistake.

> results in appendix of the DCLOR draft to see the difference. 

I think saying it reduces the overall throughput of every system is a
bold claim ... I would believe that it reduces throughput in some
circumstances, but I would like to believe that it improves the
throughput for the connection in question without adversely affecting
the rest of the network in many or most circumstances.

Ethan

-- 
Happiness is a belt-fed weapon.

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 12:31:40 -0500 (EST)

> wait until we receive congestion indication? Your logic seems to imply

I agree with you on principal, but I think you are missing something. From
section 3.1 (The Algorithm), the cwnd restoration algorithm is:

		  cwnd <- min (pipe_prev, (FlightSize + IW))
                  ssthresh <- pipe_prev

So this algorithm does use the CWV principles from RFC 2861.

I would suggest to Reiner to reword text references to cwnd restoration so
that the text better reflects the actual algorithm.

(FYI: I will read the response drafts in more detail soon and give my
comments.)

~armando

0--                                                  --0

---

From: Yogesh Prem Swami <[email-masked]>
Date: 06 Mar 2003 11:51:34 -0600

Hi,

> acknowledgements, it's OK to use congestion avoidance as usual."  The

That's precisely the point. During the spurious timeout period, the
sender is not getting the ACKs in the regular fashion, so congestion
avoidance makes no sense.  During that period the other TCP connections
in the system were still doing fine and they will use up all the
resources of the network. Please see section 2.2 of DCLOR draft
(draft-swami-tsvwg-tcp-dclor-00.txt) for an analysis.

> basic point here is that we *thought* we saw congestion, but we didn't

we cannot claim that we *didn't see* congestion; the congestion
informaiotn on the first part (the part between the sender and stalling
node) is more than an RTO old so its of little use. All we can claim is
that we don't know what happened during that idle period. 

> we can detect when we made a mistake.

Yes we can detect congestion after losing packets, but that would be too
late. Consider the case where there are repeated spurious timeouts
(which will happen if there are many mobile users moving from one subnet
to another). In that case, the network will keep losing packets from
random set of senders.

As long as spurious timeouts happen once in a while, it might be
acceptable to restore the window. But once the number of spurious
timeouts increases, the system will the hardly hit.

> bold claim ... I would believe that it reduces throughput in some

Indeed it's a bold claim, and that's why I am asking the working group
to define a test environment which will consider all possible causes of
spurious timeouts. This will also allow an independent observer to test
each of these schemes.

I think this should be acceptable to everyone.

> the rest of the network in many or most circumstances.

Could you please provide some data of these circumstances. From my
experiments, I have found the performance to go down (I used the Linux
distribution of Eifel.) in almost all cases except where there are just
one or two TCP connections in the system.

--yogesh

---

From: Randall Stewart <[email-masked]>
Date: Thu, 06 Mar 2003 11:43:24 -0600

> I was ready to say that I agree with Yogesh, but...
I like Armando was ready to agree with Yogesh.. then at the
prompting of this set of exchanges I went and read the draft ;->

>>spirit and intention of the CWV algorithm.

I think FWIW I am ok with restoring to min(prevfs, (currfs+IW))

But I do have one question..

Would this ever other return anything but currfs+IW?

R

-- 
Randall R. Stewart
[email-masked] 815-342-5222 (cell phone)

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 13:04:08 -0500 (EST)

> Would this ever other return anything but currfs+IW?

Yeah, I don't see how prev_flight is ever achieved... unless the
spurious rtx detection is REALLY late.

~armando

0--                                                  --0

---

From: Ethan Blanton <[email-masked]>
Date: Thu, 6 Mar 2003 13:06:49 -0500

> timeouts increases, the system will the hardly hit.

Now on this point, I *completely* agree.  Our experiments with DSACK
suggested that if these bogus retransmissions (of any kind) are not
curbed, they will become a significant problem in and of themselves.
However, as Reiner has I believe pointed out in another part of this
thread, this is a known problem ... and I would agree with you that it
needs a little bit of face time in this draft or any other draft
addressing the issue of allowing congestion state reversion.
Obviously we do not want to continually take false timeouts and spew
unnecessary retransmits into the network in any event.

If this is the crux of your position, then I am in agreement.

Ethan

---

From: Mark Allman <[email-masked]>
Date: Thu, 06 Mar 2003 14:02:50 -0500

> Now on this point, I *completely* agree.  Our experiments with
> DSACK suggested that if these bogus retransmissions (of any kind)
> are not curbed, they will become a significant problem in and of
> themselves.  However, as Reiner has I believe pointed out in
> another part of this thread, this is a known problem ... and I
> would agree with you that it needs a little bit of face time in
> this draft or any other draft addressing the issue of allowing
> congestion state reversion.  Obviously we do not want to
> continually take false timeouts and spew unnecessary retransmits
> into the network in any event.
> 

I agree that spuriously retransmitting continuously is a Bad Thing.
But, I want to note that Reiner's draft (& our draft on what to do
in the face of reordering) takes action to attempt to avoid this
situation in the future (i.e., so it doesn't happen continuously).
That is, the RTO or the dupthresh is adjusted in an effort to
prevent continuous bogosity.  And, so I think it is a bit unfair to
argue against Reiner's intent here (if you want to claim that his
algorithms do not go far enough, I think that is fine -- but, I
think that is a different argument all together).

allman

--
Mark Allman -- BBN/NASA GRC -- http://roland.grc.nasa.gov/~mallman/
_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Mark Allman <[email-masked]>
Date: Thu, 06 Mar 2003 14:20:08 -0500

> If I go by this logic, then why shall I start with a small window
> size at the start of the connection? At the start of the
> connection I have no congestion indication, so I should be able to
> send what ever amount of data I want?
> 
> Are you suggesting we should start with a window of say 10M bytes
> and wait until we receive congestion indication? Your logic seems
> to imply that.

I disagree with the above analysis.  I hope the following is very
neutral -- I mean it to neither support nor refute your overall
argument (I am still rolling that around in my head).

At the beginning of a connection you have no congestion indication,
indeed.  But, also you have no indication of what the cwnd ought to
be.  When we spuriously timeout we have a cwnd that has been
validated by the network path.  Now, that might or might not be
valid after the suprious timeout--- rather my point si that we have
*some notion* about what cwnd ought to be, as opposed to the start
of a connection when we have none.

allman

---

From: Yogesh Prem Swami <[email-masked]>
Date: 06 Mar 2003 13:59:56 -0600

Hi Marc, all,

> of a connection when we have none.

Yes, I agree that the sender has a some stale information about the
state of the network, but that information, as you note, might not be of
any use. The answer to the question of how good the information actually
is, depends on the how long the spurious timeout lasted

Let us do some simplified calculations (I am using the same calculation
in my DCLOR draft; I apologize if you have already seen this). Lets say
there are M competing connection (apart from the connection which was
interrupted) and each of them has a Round Trip Time or R (this is a
simplifying assumption; I am by no means suggestion it's the case).
Let's also say that that the stalling duration is K*R, where K is some
integer constant (again just a simplified case to the feel for things).
Let's also assume that all the competing connections were doing
congestion aovidance.

In this case while the stalled connection was waiting for
acknowledgements, rest of the M competing connections would increase
their congestoin window 1 segment per RTT. So by the end of the spurious
timeout, the effective buffer space for the defaulting connection will
become:

	cwnd - M*K 

As we can see this number grows linealy with K (that is the stalling
period) and with the number of competing connections. There is NO way
for a TCP sender to know how many competing connections are there in the
system.

Now if I restore the window (in this idealized scenario) then there will
be M*K packet loss. In reality this is not so direct due to
retransmissions etc, but it's close (at least in our emulation which had
differnet uniform distributed RTT values)

All this analysis is true as long as the spurious timeout is not caused
due to user's mobility. With user's mobility, things are worse.

In the DCLOR draft we take the most conservative approach to start with
a small window size and run slow-start. This prevents from packet loss,
and also improves thoughput. This approach is also in sync with RFC-793
which recommends "being conservative in what you send, and liberal in
what you accept."

BTW, it's useful to point out that fast-retransmit, fast-recovery
recovers one packet per RTT. On the other hand, Slow start can recover
packet at a much faster rate if the number of lost packets is large.
There is a lot more information in Janey C. Hoe's MS thesis (Strart Up
dynamics of TCP's congestion control and avoidance schemes)

So coming back to the argument of initial window, a spurious timeout is
no different from a new connection. The information that the sender has
is too old and has no value.

--yogesh

---

From: Yogesh Prem Swami <[email-masked]>
Date: 06 Mar 2003 14:17:50 -0600

Marc,

> in the face of reordering) takes action to attempt to avoid this

One can avoid (although I'm still skeptical how this can be done without
hurting the thoughput in case of real timeouts) spurious timeouts if the
same sender keeps timing out over and over again. But if the sender's
are new each time--which is most likey the case--then one cannot do
anything. The effect on the network is, however, still the same.

--yogesh

---

From: Mark Allman <[email-masked]>
Date: Thu, 06 Mar 2003 15:34:08 -0500

> > I agree that spuriously retransmitting continuously is a Bad
> > Thing.  But, I want to note that Reiner's draft (& our draft on
> > what to do in the face of reordering) takes action to attempt to
> > avoid this
> 
> One can avoid (although I'm still skeptical how this can be done
> without hurting the thoughput in case of real timeouts) spurious
> timeouts if the same sender keeps timing out over and over
> again.

You want to eat your cake, too?

> But if the sender's are new each time--which is most likey the
> case--then one cannot do anything. The effect on the network is,
> however, still the same.

Good point.

(A theoretical argument is that we could share this information
between connections.  That might help some.  But, in practice we
don't share information -- and, I am not even sure how much it would
help in this case.)

allman

---

From: Mark Allman <[email-masked]>
Date: Thu, 06 Mar 2003 15:11:09 -0500

> -- The bottom line for a spurious timeout is that a spurious
> timeout is spurious ONLY in terms of what packets to resend; its
> not spurious in terms of congestion.
>
> [...]
> 

I think you bring up an interesting thought.  I am not sure we have
ever actually defined what "congestion" means in an RFC (and, if we
have someone please correct me).  We use drops as implicit
indications of "congestion".  We use ECN bits as explicit
indications of "congestion".  However, that does not preclude the
use of other indications, I would say.

So then the question is: when the retransmission timer fires what
part of that process is the congestion indication?

  * Is it the unexpectedly long time we spent waiting for feedback
    (an ACK) for some segment?

  * Or, is it that we believe something has been dropped (and, so we
    are now retransmitting)?

I *think* I have a hit on this.  But, I am going to roll it around
my head a bit so I can be coherent when I try to explain it.  But,
I'd be interested in hearing other's thoughts, too.

allman

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 20:17:34 -0500 (EST)

> for a TCP sender to know how many competing connections are there in the

I think you have a flaw in your analysis. You are assuming that the
competing flows are synchronized, which is not the case in a real
networks.  I agree with you that the "available bandwidth" for a flow does
fluctuate, but you cannot simply say that one TCP connection reducing its
sending rate will cause others to increase x amount in y amount of time.
The congestion state at routers is bursty... connections may get drops
just because of coincidental burst at the time it decided to send.

~armando

0--                                                  --0

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 20:26:04 -0500 (EST)

> don't share information -- and, I am not even sure how much it would

I don't think sharing this information makes much sense. My understanding
is that detecting spurious timeouts is useful in wireless scenarios where
RTTs may fluctuate much more due to L2 rtxs. In these cases, spikes in
RTTs are probably due noise, which is temporary. Thus, it is not something
meaningful to convey to other new connections. For wired netwoks, RTT
spikes are less frequent, but still not meaningful to share.

PLEASE correct me if I am totally off here...

~armando

0--                                                  --0

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 20:27:56 -0500 (EST)

On Thu, 6 Mar 2003, Mark Allman wrote:

> be.

Now THIS information would be a good idea to share :-)

(Yeah, I know... people have already thought of that)

~armando

0--                                                  --0

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 6 Mar 2003 20:35:04 -0500 (EST)

>   * Or, is it that we believe something has been dropped (and, so we

Both :-)  It's just that the drop is a clearer indiation (in wired
networks) that there is congestion. Without the loss, a long delay does
imply congestion, but the question is how to act on it. I believe that TCP
Westwood and TCP Vegas provide some direction here.

~armando

0--                                                  --0

---

From: Pasi Sarolahti <[email-masked]>
Date: 07 Mar 2003 10:20:04 +0200

> Westwood and TCP Vegas provide some direction here.

I agree. We were suggesting in the F-RTO draft that cwnd & ssthresh
would be reduced by some amount (halving was suggested) after detecting
spurious RTO. Some problem cases were pointed out with that approach
(possible underutilization of the pipe in congestion avoidance,
especially when RTO occurs in the beginning of connection) but I still
think it could be one way to go, at least with some modifications. One
alternative could be, for example, reducing only cwnd and keeping
ssthresh at a higher level, which starts to be quite close to RFC2861, I
think.

In any case, I think it might be useful to have the different potential
response alternatives documented with some background why the particular
response is justifiable. From the reader's perspective it might be
better to have them all in the same covers, but I don't know if folks
here are willing to go that way.

- Pasi

---

From: Pasi Sarolahti <[email-masked]>
Date: 07 Mar 2003 10:37:26 +0200

> don't share information -- and, I am not even sure how much it would

Btw, that is not necessarily so theoretical. E.g. Linux stores the
recent values of ssthresh, rto-related parameters, observed reordering,
etc. per destination and reuses them as initial values when new
connections start up shortly.

- Pasi

---

From: Mark Allman <[email-masked]>
Date: Fri, 07 Mar 2003 07:34:29 -0500

> Let us do some simplified calculations 

I'm not yet convinced that your analysis is right because...

  + If the delay spike is on a shared portion of the network then
    chances are multiple connections will suffer the effects.  You
    assume only one connection will.

  + If the delay spike is on a non-shared network then your notion
    that other connections will take the resources once used by the
    transfer that spuriously retransmitted is right, I think.  But,
    in that case, when the transfer that spuriously retransmitted
    figures it out and reverts the CC state, isn't that OK?  That
    is, the other connections have more than their share and the
    connection in question has less than its fair share of the
    shared network resources.  (And, also note that the increased
    traffic is not introduced as a huge burst.)

  + Unfortunately, real networks are not quite as static as you have
    sketched - with connections coming and going, and connections
    experiencing loss (from the non-shared network), and apps
    limiting the sending, and a thousand other things.  So, I think
    it is pretty hard to use a back-of-the-envelope calculation to
    argue that the eifel-response is going to hurt the overall
    system.

> recovers one packet per RTT. On the other hand, Slow start can
> recover packet at a much faster rate if the number of lost packets
> is large.  There is a lot more information in Janey C. Hoe's MS
> thesis (Strart Up dynamics of TCP's congestion control and
> avoidance schemes)

Or in RFC 2582.

> So coming back to the argument of initial window, a spurious
> timeout is no different from a new connection. The information
> that the sender has is too old and has no value.

So, I am still unconvinced that these two cases are the same.

I might be happy with a scheme that sort of followed RFC 2861 --
i.e., when we detect a spurious retransmit via the RTO we look at
the elapsed time between when sending that retransmit and sending
whatever data segment we sent prior to that.  For each RTO seconds
that have elapsed we reduce cwnd_prev by half.  That places some
value on the previous CC state, but at the same time takes into
account that the connection has not been validating its cwnd for
some time.  (And, if enough time passes the old cwnd information
will be "too old" and have "no value", but that case does not happen
immediately and simply by virtue of the fact that the RTO fired.)

allman

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 07 Mar 2003 14:26:41 +0100

>How was the value three chosen?

Out of the hat. It's up for debate.

The question is: How many spurious timeouts in a row, i.e., for the same 
outstanding sequence number, are OK to still restore congetsion control state?

In an earlier proposal, we suggested "full restore" for the first spurious 
timeout, "half restore" for the second spurious timeout, etc.
(see http://iceberg.cs.berkeley.edu/papers/Ludwig-Eifel-Alg/index.html)

///Reiner

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 07 Mar 2003 14:41:45 +0100

>Would this ever other return anything but currfs+IW?

Yes, it can. If the TCP sender was in congestion avoidance (FlightSize >= 
ssthresh) when a spurious timeout occurs, no data segments and no ACKs get 
lost, then cwnd == pipe_prev (== value of FlightSize when the timeout 
occurs) after step (ReCC) of the algorithm.

///Reiner

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 07 Mar 2003 15:08:26 +0100

>I'd be interested in hearing other's thoughts, too.

RFCs 2309, and 2914 only talk about "packet drop" as the congestion signal. 
On the other hand, I certainly agree that the we cannot fully reverse 
congestion control state when the sender hasn't probed the network for some 
time. We thought 3 timeouts in a row should be an OK time. But maybe we 
should go back to the previous approach of halving pipe_prev for every RTO 
(backed-off or not?).

///Reiner

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 07 Mar 2003 15:22:07 +0100

... at least compared to the current TCP that after a spurious timeout 
sends (often) useless go-back-Ns in slow-start, and thereby breaking 
'packet conservation'.

With the Eifel-Response + advanced loss recovery, 'packet conservation' is 
preserved *and* useful restransmits are sent.

You make it look as if the Eifel-Response was aggressive. This is not the 
case. For example, if the TCP sender was in congestion avoidance before the 
spurious timeout, then it will simply return to that state with the Eifel 
response. I.e., each of the (late) original ACKs will nicely clock out one 
or two (in case of delayed ACKs) new data segment(s).

///Reiner

---

From: Yogesh Prem Swami <[email-masked]>
Date: 07 Mar 2003 10:14:07 -0600

> just because of coincidental burst at the time it decided to send.

Armando,

There is no flaw in the analysis, although I do agree that the number
M*K is the upper bound--asuuming no non TCP connections. TCP has such a
choatic behavior it's impossible to have a realistic analysis on paper.

The idea behind the analysis is to demonstrate that the congestion state
in the network is not going to remain the same after an RTO, so the
sender cannot start from it left. The analysis also gives a good idea
how the number of connections affects the overall process. If you have
too many connections in the system, chances are your old congestion
state will be of no value at all.

This is also one of the reasons why I asked for a standarad simulation
environment against which we can evaluate different schemes. 

--yogesh

---

From: Yogesh Prem Swami <[email-masked]>
Date: 07 Mar 2003 10:36:15 -0600

Mark,

>     assume only one connection will.

Well the argument in my analysis assumes that the bottle neck router
(the router that has minumum buffer_space/|different in outgoing link
speed and incoming| ratio on the end to end path) and the point where
packets are stalled are different. That's why there is just one TCP
conenction. This is a very realistic scenario.

Here is figure from the DCLOR draft:

                      C(1) C(2)... C(M)
                        |  |   ... |
                        |  |   ... |
                        |  |   ... |
                        V  V   ... V
                        \  \      /
                         \  \    /
                          \  \  /
                    +------X--X--X---+       +------------------+
        Defaulting  |                |       |                  |
   C(0) ----------->|   Bottleneck   |------>|Buffered packets  |--->
        connection  |   router       |       |                  |
                    +-----X--X----X--+       +------------------+
                          |  |    |
                          |  |    |
                        c(1)c(2) C(M)

The M connections I was talking about go through the bottle neck router.

>     traffic is not introduced as a huge burst.)

Yes the increased traffic has not introduced the burst, but the Eifel
response has. 

Also, why should the other traffic which didn't go through spurious
timeout suffer because of the burst caused by Eifel response. Problem
with such bursts is that some connections might get unnecessarily
penalized (for example a connection which was just starting). 

>     argue that the eifel-response is going to hurt the overall

Completely agree. I won't bet a penny on that analysis. But the point is
that the congestion state of the system is not going to remain the same.
I gess I got that idea across so the analysis has served its purpose.

> immediately and simply by virtue of the fact that the RTO fired.)

That's precisely my point. Except, this scheme will not work when there
are spurious timeouts due to subnet change. Not compaining too much
though.

I hope we (except Reiner) agree that Eifel Response is Myopic in it's
approach.

--yogesh

---

From: Yogesh Prem Swami <[email-masked]>
Date: 07 Mar 2003 10:47:29 -0600

> time. We thought 3 timeouts in a row should be an OK time. But maybe we

3 timeouts are too long--it roughly (1+2+4)*(3*RTT) = 21*RTT (I have
replaced RTO with 3RTT for simplicity; that's ofcourse not always the
case). The best approach is to 1/2 the data rate every RTO as Mark (and
RFC 2861) pointed out in his last e-mail.

--yogesh

---

From: Yogesh Prem Swami <[email-masked]>
Date: 07 Mar 2003 11:05:54 -0600

Reiner,

> preserved *and* useful restransmits are sent.

Hate to repeat myself,  but Packet conservation is meaningless after a
timeout. To quote from VJ's paper--congestion control and avoidance
(page 2, paragraph 4):

	"By  conservation of packets  we mean that for a connection  in 	
equilibrium , i.e., running stably with a full window of data 	 	 in
transit, the packet flow is what a physicist would call  	 	
conservative ..."

After a timeout, the sender is not "running stably with a full window of
data."

> You make it look as if the Eifel-Response was aggressive. This is not the 

I am not making Eifel Response "look" aggressive--it *is* agressive. And
it's WRONG.

--yogesh

---

From: Mark Allman <[email-masked]>
Date: Fri, 07 Mar 2003 12:16:05 -0500

I understand the scenario you are assuming now.  Thanks.

> Yes the increased traffic has not introduced the burst, but the
> Eifel response has.

The eifel response calls for sending based on the ACK clock.  And,
the ACKs should be coming back at the rate the bottleneck link can
support (in the return direction).  So, we should not be sending a
huge burst, but rather ACK clocking things out.  (The ACK clock
could be a bit off, I suppose.  But it has to be better than a big
line-rate burst.)

> Also, why should the other traffic which didn't go through
> spurious timeout suffer because of the burst caused by Eifel
> response. Problem with such bursts is that some connections might
> get unnecessarily penalized (for example a connection which was
> just starting).

To flip this around: Why should the connection through the link with
the delay spike have to give up share through the bottleneck?  Why
does the fact that one of the links it traverses uses LL retransmits
(that worked!) mean that it should get less resources through the
bottleneck?  These seem like orthogonal issues to me.

> > i.e., when we detect a spurious retransmit via the RTO we look
> > at the elapsed time between when sending that retransmit and
> > sending whatever data segment we sent prior to that.  For each
> > RTO seconds that have elapsed we reduce cwnd_prev by half.  That
> > places some value on the previous CC state, but at the same time
> > takes into account that the connection has not been validating
> > its cwnd for some time.  (And, if enough time passes the old
> > cwnd information will be "too old" and have "no value", but that
> > case does not happen immediately and simply by virtue of the
> > fact that the RTO fired.)
> 
> That's precisely my point. Except, this scheme will not work when
> there are spurious timeouts due to subnet change. Not compaining
> too much though.

I presume you mean because the new cwnd could have no resemblence to
the previous cwnd.  Is that right?

This is a more general problem though -- if you switch to a subnet
with drastically different properties then I think you're likely to
get into some TCP ugliness whether there are spurious retransmits or
not.

allman

---

From: Ethan Blanton <[email-masked]>
Date: Fri, 7 Mar 2003 13:16:00 -0500

> I hope we (except Reiner) agree that Eifel Response is Myopic in it's

I'm not sure who "we" is at this point, but I do not agree.  I think
the basic plan of attack is valid.

Ethan

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Fri, 7 Mar 2003 14:08:39 -0500 (EST)

> the basic plan of attack is valid.

I too think the Eifel Response is fine. As Mark said in a previous mail,
the cwnd is restored, but the acks are clocking out the data. The ack
clock never went away... just delayed.

~armando

0--                                                  --0

---

From: Yogesh Prem Swami <[email-masked]>
Date: 07 Mar 2003 13:37:35 -0600

> clock never went away... just delayed.

The ACK clock is how you send new data into the network. Congestion
response is about how you prevent unnecessary packet loss. These two are
different issues. Ack clocking *can* be used to prevent congestion if
these ACKs arrive in a regular fashion. If the ACKs don't arrive in a
regular fashion, as in case of spurious timeout, they don't convey any
information.

If I go back to my previous figure

		Part-A		      Part-B
	sender-------> stalling node -------> receiver

The ACKs are telling me that congestion on Part-B is fine. But is that
sufficient to conclude that congestion on the entire Part-A + Part-B is
fine? To me the answer seems to be no. 

In addition, the ACKs on Part-B will all arrive as a burst--depending
upon how many hops are between stalling node and receiver (stating from
my simulations). 

I still think that a well defined test can help. Based on the
simulations, we can decide the right thing to do. After the tests, the
working group might decide not to give so much importance to congestion
after all, if something else of an algorithm is important.

--yogesh

---

From: Mark Allman <[email-masked]>
Date: Fri, 07 Mar 2003 14:44:00 -0500

> The ACK clock is how you send new data into the
> network. Congestion response is about how you prevent unnecessary
> packet loss. These two are different issues. Ack clocking *can* be
> used to prevent congestion if these ACKs arrive in a regular
> fashion. If the ACKs don't arrive in a regular fashion, as in case
> of spurious timeout, they don't convey any information.

I would phrase it "they may not convey any useful information".  On
the other hand, they will serve to prevent a complete line-rate
burst (e.g., send N packets as fast as you can) even in the worst
case.

> simulations, we can decide the right thing to do. 

I bet that with the right simulation I could make either case.
That's the nice thing about simulations! :)

(It's just a damn hard problem to come up with *the* simulation
harness -- probably because there isn't one, IMO.)

allman

---

From: Randall Stewart <[email-masked]>
Date: Fri, 07 Mar 2003 13:54:04 -0600

> the basic plan of attack is valid.
Count me NOT in the "we" catagory... I am ok with Eifel's basic
plan of attack as well..

R

---

From: Yogesh Prem Swami <[email-masked]>
Date: 10 Mar 2003 10:10:27 -0600

Hello Mark,

[I am quite backlogged on this list; please bear with me]
 
> I would phrase it "they may not convey any useful information".  On

Agreed, that's the right wording. But, the fact that a TCP sender will
have the right information will only be a coincidence. 

One cannot design a congestion response based on coincidences. If that
weren't the case then AIAD (.. additive decrease) would have been
sufficient since in some sunny day scenarios we don't need AIMD. 

> burst (e.g., send N packets as fast as you can) even in the worst

Could you please justify your claim for the above scenario. What happens
if all ACKs except the first and the last get lost into the network. Or,
what happens if all the ACKs--instead of the data packets--were stalled
on the first router connected to the sender.

I think in the worst case the sender will still send data at the line
rate. 

Besides, the comparison with line speed is not of relevance here. If
someone had used line-rate that would have been worse, but that does not
tell the sender that using the old data is correct. I never drive my car
faster than a flying airplane, but does that guarantee that I will not
get a speeding ticket. The speeding ticket in this case is posted by the
routers on the e2e path, and the sender does not know anout these speed
limits.

After a spurious timeout, a TCP sender does not have any information
about the state of the network. The only information it has is that the
longer it waits, the lesser it can rely on the old data rate. In my
opinion, an appropriate congestion response will take this into
consideration.

A congestion response must work in all the cases. Put differently, a
congestoin response needs to be slow enough so that even in the worst
case where the network is already congested, the response algorithm will
not add a single bit to the existing level of congestion.

> That's the nice thing about simulations! :)

Not if everyone agrees that a particular scenario is the one that most
resembles a real scenario. But I do agree it's a hard problem.

What other options are there? One cannot analyze the problem
mathematically; one cannot run simulation; so shall we have two
experimental RFCs (I don't like this idea more than anyone else), but
I'm running out of options here.  

--yogesh

---

From: Ethan Blanton <[email-masked]>
Date: Mon, 10 Mar 2003 11:31:20 -0500

> I think in the worst case the sender will still send data at the line

No.  Because the algorithm sets ssthresh to the previous value of cwnd
... therefore cwnd can open up only as acks arrive, as in initial slow
start.

> opinion, an appropriate congestion response will take this into

So, let me put this in perspective ... an RTO causes the connection to
go into slow start, Reiner's draft causes the connection to go into
slow start.

> resembles a real scenario. But I do agree it's a hard problem.

Never going to happen.  What sort of real scenario?  That's just far
too wide a question.

> I'm running out of options here.  

If you mean an experimental RFC for Eifel and an experimental RFC for
DCLOR, I think it's a fantastic solution.

Ethan

---

From: Mark Allman <[email-masked]>
Date: Mon, 10 Mar 2003 11:51:20 -0500

> Agreed, that's the right wording. But, the fact that a TCP sender
> will have the right information will only be a coincidence.

Um.  Not sure I would phrase it that way, but OK.

> One cannot design a congestion response based on coincidences. 

OK.

So, I agree that the worst case is a fairly substantial bursting
behavior (whether it is line rate or slightly less or a lot
less... point is we can burst in a fairly significant way).  And, we
should look at the worst case.

> After a spurious timeout, a TCP sender does not have any
> information about the state of the network. The only information
> it has is that the longer it waits, the lesser it can rely on the
> old data rate. In my opinion, an appropriate congestion response
> will take this into consideration.

I agree with the statement "the longer it waits, the less[er] it can
rely on the old data rate".  But, I do not agree with the first
statement that says just because we RTO means that the previous CC
state information is useless.

And, so, while I am not convinced that Reiner's scheme of reverting
the entire cwnd is right, I do not think that disallowing all
reversion is right either.

But, now I am just repeating...

allman

---

From: Mark Allman <[email-masked]>
Date: Mon, 10 Mar 2003 11:52:31 -0500

> > experimental RFCs (I don't like this idea more than anyone
> > else), but I'm running out of options here.
> 
> If you mean an experimental RFC for Eifel and an experimental RFC
> for DCLOR, I think it's a fantastic solution.

Agreed.
(modulo WG consensus on each independently, of course)

allman

---

From: Mark Allman <[email-masked]>
Date: Mon, 10 Mar 2003 11:57:13 -0500

> So, let me put this in perspective ... an RTO causes the
> connection to go into slow start, Reiner's draft causes the
> connection to go into slow start.

Right.  The difference is in the length of this slow start (from
cwnd_prev/2 (std case) to cwnd_prev (when allowing state reversion))
(and hence the length of the potentially bursty behavior).

allman

---

From: Yogesh Prem Swami <[email-masked]>
Date: 10 Mar 2003 10:59:23 -0600

Agreed. 

--yogesh

---

From: Reiner Ludwig <[email-masked]>
Date: Tue, 11 Mar 2003 10:45:23 +0100

>(and hence the length of the potentially bursty behavior).

Just to make it precise. After a spurious timeout the Eifel response will 
make the TCP sender either resume transmission in congestion avoidance if 
it had been in congestion avoidance before the timeout, or in slow start if 
it had been in slow start before the timeout. From the draft:
    "We suggest to restore cwnd to the minimum of the previous FlightSize,
    and the current FlightSize plus IW.
    [...]
    In addition, we suggest to restore ssthresh to pipe_prev, i.e., the
    maximum of the previous value of ssthresh and the value that
    FlightSize had when loss recovery was unnecessarily entered. As a
    result, the TCP sender either immediately resumes probing the network
    for more bandwidth in congestion avoidance, or it first slow starts
    until it has reached its previous share of the available bandwidth."

But, yes, Mark is right in what he says about the "difference in the length 
of the slow start" for the case where the TCP sender had been in slow start 
before the timeout.

The motivation for our choice are scenarios of high BxD connections and a 
spurious timeout early in the initial slow start. Note, that such spurious 
timeout is at least not unlikely since in the beginning of a connection, 
SRTT and RTTVAR have not yet converged to "good" values (unless they had 
been initialized from previous or concurrent connections).

In the standard case, ssthresh is "clamped" at a low value. As a result the 
TCP sender is forced to climb up to BxD in congestion avoidance.

With the Eifel response, ssthresh is restored to its previous value (likely 
its initialization value). As a result the TCP sender can resume slow 
starting to ssthresh which ideally is higher than BxD.

///Reiner

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Wed, 12 Mar 2003 16:08:02 -0500 (EST)

> sufficient since in some sunny day scenarios we don't need AIMD.

To me, it seems like you are arguing against TCP's feedback mechanism.
Yes, the feedback mechanism _may_ be too slow to convey good/bad
information at times. But the feedback mechanism seems to work fine, and
it is what we have to work with.

Let me flip the perspective on spurious timeouts. Suppose that a spurious
timeout occurs when the RTO is 1 sec. Since the timeout was in fact
spurious, all we can REALLY infer from this is that the RTO was too low.
Ok, that's obvious. Now suppose that instead of the RTO being 1 sec, it
was actually 2 secs. Then the spurious timeout would probably not occur at
all. Thus, we wouldn't be concerned with the cwnd being stale, would we?
The acks would continue clocking out new data as normally done and nobody
would complain because maybe the RTT is really just THAT long.

The fact that as the RTT increases, the feedback mechanism becomes "less
realiable" is a different problem altogether I think. But flows with long
or even highly variable RTTs should not be penalized.

~armando

0--                                                  --0

---

From: Mark Allman <[email-masked]>
Date: Mon, 17 Mar 2003 13:09:49 -0500

> The question is: How many spurious timeouts in a row, i.e., for
> the same outstanding sequence number, are OK to still restore
> congetsion control state?

My vote would be <= 1 RTO for a full restore.

> In an earlier proposal, we suggested "full restore" for the first
> spurious timeout, "half restore" for the second spurious timeout,
> etc.  (see
> http://iceberg.cs.berkeley.edu/papers/Ludwig-Eifel-Alg/index.html)

I like this.  But, as I offered before the starting point might need
to be variable...  If it has been >= RTO since we last sent
something then you get to restore to only half the previous value.
If it has been <= RTO seconds then you can start by fully
restoring.  (Followed by having on each subsequent RTO.)

allman

--
Mark Allman -- NASA GRC/BBN -- http://roland.grc.nasa.gov/~mallman/
_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg