Subject: [Tsvwg] WG last call on draft-ietf-tsvwg-tcp-eifel-alg-04.txt

From: Scott Bradner <[email-masked]>
Date: Fri, 9 Aug 2002 08:30:20 -0400 (EDT)

this message starts a WG last call on draft-ietf-tsvwg-tcp-eifel-alg-04.txt
for publication as an experimental RFC - please send any comments
to the tsvwg list

please send comments before Aug 30 (3 weeks instead of two because
its vacation time for many people)

Scott & Allison

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

---

From: Pasi Sarolahti <[email-masked]>
Date: Fri, 9 Aug 2002 18:25:22 +0300

Hi,

On Friday 09 August 2002 15:30, Scott Bradner wrote:
> this message starts a WG last call on
> draft-ietf-tsvwg-tcp-eifel-alg-04.txt for publication as an
> experimental RFC - please send any comments to the tsvwg list

I have a couple of small comments/questions.

First, variable "SpuriousRecovery" in the algorithm description is 
undefined and unreferenced anywhere in the text. I assume it is left 
there for the purposes of future recovery algorithms, but wouldn't it 
be worth of small description? <nit>Btw, is "SpuriousRecovery" boolean, 
enum, or integer?</nit>

Second, Eifel detection cannot see the possible loss of the (spurious) 
retransmission. Maybe this is a minor concern, since the retransmission 
was spurious anyway, but nevertheless, it is a loss caused by network 
congestion, so in principle the congestion window should have been 
reduced in that case. I would be interested to hear opinions about this 
issue in general from this community, because this was one of the 
reasons we decided not to undo congestion window in our related work 
(draft-sarolahti-tsvwg-tcp-frto-00.txt). D-SACK does not have this 
problem, but on the other hand, it reacts one RTT later on the spurious 
retransmission than Eifel does. Maybe the draft could notify the 
response algorithm implementors about this.

Finally, I am still not 100% convinced that RTO due to loss of ACKs 
should be interpreted as spurious timeout. If there are data packets 
lost in the same window when Eifel is applied due to lost ACKs, the 
resulting recovery can be quite ineffective, as we have experienced. 
This assumes that the response to Eifel-detected spurious 
retransmission is to continue sending new data right away. By 
inspecting the next couple of acks following the RTO this problem could 
be avoided (as described in tech. report at 
http://www.cs.Helsinki.FI/research/iwtcp/papers/f-rto.ps). Of course, 
this does not concern the detection algorithm, but again, maybe the 
draft should notify the implementors of the response algorithms about 
this.

- Pasi

---

From: Pasi Sarolahti <[email-masked]>
Date: Wed, 14 Aug 2002 15:21:52 +0300

Hi,

On Tuesday 13 August 2002 15:05, ext Reiner Ludwig wrote:

> >there for the purposes of future recovery algorithms, but wouldn't
> > it be worth of small description? <nit>Btw, is "SpuriousRecovery"
> > boolean, enum, or integer?</nit>
>
> I think it's common practice in IETF documents to specify algorithms
> using pseudo code. My understanding is that variable definitions are
> then left to the implementors.

Sure, the point was mainly editorial: variable "SpuriousRecovery" 
suddenly appears in Section 3.2, it is specifically used in the 
algorithm, and then it just disappears without being used again in the 
rest of the document. I was looking for some kind of definition. The 
same goes for "RetransmitTS". Not a major point, but comments were 
asked and one was given.

> >Second, Eifel detection cannot see the possible loss of the
> > (spurious) retransmission. Maybe this is a minor concern, since the
> > retransmission was spurious anyway, but nevertheless, it is a loss
> > caused by network congestion, so in principle the congestion window
> > should have been reduced in that case.
>
> We see your point: All original packets arrive at the receiver, i.e.,
> no congestion losses, but the sender still spuriously retransmits the
> oldest packet, and that retransmit gets lost.
>
> Yes, the Eifel algorithm ignores that case, but we think that's OK.
> First, this seems like a pretty pathological case. But even so, one
> could argue that a TCP sender (e.g., one with a more conservative
> retransmission timer) that would not have spuriously retransmitted
> would not have triggered loss recovery / congestion control either.

I don't think so. If a buffer was full somewhere, the next incoming 
packet is dropped, regardless of whether it is a retransmission or a 
new segment, and congestion window should be decreased. I agree, if the 
pipe capacity is large enough, the probability that this dropped packet 
was the spurious retransmission is pretty small. But as I said, I was 
interested to hear what's the general opinion about taking the small 
risk of a congestion control violation under these circumstances, since 
I have been thinking about this problem in my own work.

> The Eifel algorithm basically asks the following question: Was the
> oldest outstanding segment really lost?
> If yes, it does nothing.
> If no, it declares that the loss recovery phase was unnecessarily
> entered.

Yes, Eifel can answer the question, but in my opinion the rest of the 
no-part given above is not always true: even if the oldest outstanding 
segment was not really lost, loss recovery might still be needed. For 
example, a burst loss that triggers RTO is likely to be such a case. 
I.e., Eifel can reliably detect whether the oldest outstanding segment 
was really lost, but it cannot reliably say whether loss recovery was 
unnecessary entered, unlike the draft states.

Eifel surely helps significantly in improving performance when spurious 
retransmissions are present, and I believe for most users Eifel is 
harmless even if there were no spurious retransmissions. But isn't it 
possible, that a host is behind a lossy link, and its user would want 
to disable Eifel detection since it leads to unnecessarily leaving the 
retransmission phase, in worst case resulting in additional timeout? 
That's why I was suggesting that maybe it would be fair if the draft 
informed about these kind of known problems instead of saying things 
like "the TCP sender must have entered loss recovery unnecessarily.", 
no matter how corner cases they may look like from our viewpoint.

- Pasi

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 15 Aug 2002 14:19:28 +0200

At 14:21 14.08.2002, Pasi Sarolahti wrote:
>segment was not really lost, loss recovery might still be needed.

True, loss recovery (LR) might *later* be needed when the TCP sender finds 
that another segment from that flight was really lost (dropped in the 
network).

But why should a TCP sender be required to stay in LR when it has just 
detected that the segment for which it had enetered LR was in fact not lost?

Example:
Segments 1, 2, and 3 are sent. 2 and 3 are really lost (dropped in the 
network), and 1 arrives at the TCP receiver, but the TCP sender still gets 
a spurious timeout for 1 and retransmits 1. Then the *original* ACK for 1 
arrives at the TCP sender.

In this example, one could say that the TCP sender entered loss recovery 
too early: it entered LR when it (falsely) thought that 1 was lost, but 
really should have entered LR when it finds that 2 was lost. The latter is 
exactly what will happen using Eifel detection & response.

The Eifel detection algorithm will declare that the loss recovery was 
entered unnecessarily when the *original* ACK for 1 arrives at the TCP 
sender. Consequently the Eifel response algorithm will terminate loss 
recovery. Rightfully I would say, since when the *original* ACK for 1 
arrives, the TCP sender has no information to believe otherwise. Clearly, 
the TCP sender will then immediately re-enter LR again when it finds out 
that 2 was lost.

>For

I don't follow. Please, give me an example.

>unnecessary entered, unlike the draft states.

I believe that we have different philosophies about what to do when the 
first acceptable ACK that arrives after a spurious retransmit is an 
original ACK.

- You seem to say: "let's do nothing right away, but wait for more ACKs to 
arrive to hopefully derive more information about what's going on in the 
network."
- We say that the TCP sender may at any point in time decide and act upon 
the fullness of information it has gathered about network/receiver state.

At this point, I believe that both approaches are fine, and both comply 
with congestion control principles (RFC2914).

>harmless even if there were no spurious retransmissions.

Just to avoid confusion: as long as a TCP sender does not send a spurious 
retransmit, Eifel detection/response doesn't get triggered.

>But isn't it

I don't think so. With Eifel the TCP sender enters loss recovery exactly at 
that point in time when a segemnt is really lost.

Another example: 1000 segments are outstanding, spurious timeout, but only 
the second segment from that flight was really lost. What should the TCP 
sender do?

>informed about these kind of known problems

So far, I haven't heard about "known problems".

///Reiner

---

From: Pasi Sarolahti <[email-masked]>
Date: Thu, 15 Aug 2002 17:27:19 +0300

Hi again,

On Thursday 15 August 2002 15:19, ext Reiner Ludwig wrote:

> True, loss recovery (LR) might *later* be needed when the TCP sender
> finds that another segment from that flight was really lost (dropped
> in the network).
>
> But why should a TCP sender be required to stay in LR when it has
> just detected that the segment for which it had enetered LR was in
> fact not lost?

I'm not saying that TCP sender should stay in loss recovery without 
reason. My thinking is that looking at the timestamp of the first 
segment after RTO is irrelevant, because deciding whether to skip slow 
start retransmission based on that information might lead to 
inefficient behaviour. An example is given below.

The alternative solution I'm suggesting would be to continue sending 
new data and go to slow start retransmission only if the sender has 
seen indication of lost data, i.e. it received duplicate ACK. This is 
little bit like fast retransmit, but it only needs to modified slightly 
to make it work efficiently in cases where the pipe was drained out of 
packets.

I'm not saying that Eifel would not be needed, either. It surely gives 
additional information which might be useful for some clever response 
algorithm, and is needed for detecting reordering and false fast 
retransmits anyway.

> I don't follow. Please, give me an example.

Ok, we were making performance tests quite a while ago with different 
TCP alternatives, including Eifel. We generated different link 
scenarios with a network emulator, of which one was a simple two-state 
good link-bad link scenario, where the link occasionally entered into a 
short state when it dropped all packets in both directions. We noticed 
that Eifel triggers about twice the number of RTOs than TCP without 
Eifel in this case.

The following simplified example is copied from 
draft-sarolahti-tsvwg-tcp-frto-00.txt, which tries to illustrate what 
the problem is:

         ...                (cwnd = 6, ssthresh = 4, FlightSize = 5)
         1.  SEND(10) ->    (ts 110>
         2.  ACK(6) <-      <tsecr 105>
         3.  SEND(11) ->    <ts 111>
         4.  <data segment 7 is lost, ACKs for 6-11 are lost>
         5.  <RTO>          (cwnd <- 1, ssthresh <- 3)
         6.  SEND(6) ->     <ts 116>
         7.  ACK(7) <-      <tsecr 106> (undo: cwnd <- 6, ssthresh <- 4)
         8.  SEND(12) ->    <ts 117>
         9.  ACK(7) <-      <tsecr 106>
         10. <RTO>
         11. SEND(7) ->     <ts 120>
         12. ACK(8) ->      <tsecr 120>
         ...

The sender retransmits one segment after RTO, which comes as an 
out-of-order segment at the receiver. According to RFC 1323, the 
receiver is required to echo the last timestamp that advanced the 
window in this case, which points to time before RTO. The Eifel sender 
goes back transmitting new data in congestion avoidance. Since segment 
7 is missing, the receiver generates one dupack. Then the pipe runs out 
of segments and the sender has to wait for another RTO, which may take 
time.

See? The first retransmission was unnecessary, but that information did 
not help very much.

> - You seem to say: "let's do nothing right away, but wait for more
> ACKs to arrive to hopefully derive more information about what's
> going on in the network."
> - We say that the TCP sender may at any point in time decide and act
> upon the fullness of information it has gathered about
> network/receiver state.

No, I say: Let's try to transmit new data after RTO, but still keep 
eyes open for the case there really was serious data loss.

> >But isn't it
> >possible, that a host is behind a lossy link, and its user would
> > want to disable Eifel detection since it leads to unnecessarily
> > leaving the retransmission phase, in worst case resulting in
> > additional timeout?
>
> I don't think so. With Eifel the TCP sender enters loss recovery
> exactly at that point in time when a segemnt is really lost.

If I was suffering from network behaviour like shown above, I would 
want to disable Eifel, even if it would mean disabling timestamps 
entirely.

> Another example: 1000 segments are outstanding, spurious timeout, but
> only the second segment from that flight was really lost. What should
> the TCP sender do?

Yes, I get your point. But I also think that doing no worse than 
standard TCP is better than taking the risk of killing the performance 
under certain network conditions, even though they were rare.

- Pasi

---

From: Reiner Ludwig <[email-masked]>
Date: Tue, 13 Aug 2002 14:05:07 +0200

Hi Pasi,

>be worth of small description? <nit>Btw, is "SpuriousRecovery" boolean,

I think it's common practice in IETF documents to specify algorithms using 
pseudo code. My understanding is that variable definitions are then left to 
the implementors.

>reduced in that case.

We see your point: All original packets arrive at the receiver, i.e., no 
congestion losses, but the sender still spuriously retransmits the oldest 
packet, and that retransmit gets lost.

Yes, the Eifel algorithm ignores that case, but we think that's OK. First, 
this seems like a pretty pathological case. But even so, one could argue 
that a TCP sender (e.g., one with a more conservative retransmission timer) 
that would not have spuriously retransmitted would not have triggered loss 
recovery / congestion control either.

The Eifel algorithm basically asks the following question: Was the oldest 
outstanding segment really lost?
If yes, it does nothing.
If no, it declares that the loss recovery phase was unnecessarily entered.

The case you brought is a second order problem that is outside of the IDs 
scope. But, if you believe it helps, we can add a note in the next revision 
of the ID.

>should be interpreted as spurious timeout.

I think you can view it one way or the other. We have chosen to consider 
this as a spurious timeout. True, when no packet was lost in the data path 
but all ACKs are lost then the timeout is unavoidable. But, the resulting 
retransmit will be spurious since the original transmit did arrive, and 
really there was no congestion in the data path. That's why the Eifel 
algorithm again declares that the loss recovery phase was unnecessarily 
entered.

>If there are data packets

Probably true. But if no data packets are lost from the same window for 
which at that point in time we have no indication than no recovery is 
needed, anyway.

In more general terms, I believe that you can always find situations where 
an algorithm does not perform optimal. The question is then whether such 
situations are common or only rare corner cases.

>By
>be avoided

I believe you're right, but that's not the philosophy of the Eifel 
detection algorithm. The Eifel detection algorithm makes its decision on 
the *first* acceptable ACK that arrives after loss recovery was entered. 
And, I believe that we have shown that this decision is reliable. That is, 
if the algorithm declares that a loss recovery phase was unnecessarily 
triggered then this in fact true.

I'm sure that one could devise schemes that wait for more than just the 
first acceptable ACK to hopefully derive further information about what 
happened in the network.

///Reiner & Michael

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 16 Aug 2002 13:46:33 +0200

Hi Pasi,

In http://iceberg.cs.berkeley.edu/papers/Ludwig-Eifel-Alg/index.html we had 
shown how TCP breaks packet conservation after a spurious timeout. In our 
view, any proposal that addresses spurious timeouts needs to fix this 
misbehavior of TCP; ideally under all circumstances. That's what Eifel does.

We know that Eifel does perform worse than TCP-Reno (without Eifel) in the 
face of burst losses. We had already shown that in this paper: 
http://www.cs.Helsinki.FI/u/gurtov/papers/ew02.html. This is the reason why 
we recommend combining Eifel with either NewReno or preferably SACK-based 
loss recovery. This is also stated in 
draft-ietf-tsvwg-tcp-eifel-response-00.txt.

However, TCP-Reno (or any TCP without Eifel or something equivalent) only 
has this performance advantage in this case because it is unfair: it breaks 
packet conservation after a spurious timeout. That is all packets 
outstanding are retransmitted *in slow start* (!!!) although the sender 
does not know whether those packets are lost or not.

So, by disabling Eifel in the example you gave, you would see better 
performance in the face of spurious timeouts combined with burst losses, 
*but* only because your TCP sender is breaking packet conservation. That 
doesn't go so well with RFC2914.

///Reiner

---

From: Pasi Sarolahti <[email-masked]>
Date: Fri, 16 Aug 2002 16:34:20 +0300

Hi,

On Friday 16 August 2002 14:46, ext Reiner Ludwig wrote:

> We know that Eifel does perform worse than TCP-Reno (without Eifel)
> in the face of burst losses. We had already shown that in this paper:
> http://www.cs.Helsinki.FI/u/gurtov/papers/ew02.html. This is the
> reason why we recommend combining Eifel with either NewReno or
> preferably SACK-based loss recovery. This is also stated in

Here is a modified example with SACK. There is a imaginary link outage 
that causes a moment of packet loss in both uplink and downlink data 
loss.

        ...                (cwnd = 6, ssthresh = 4, FlightSize = 5)
         1.  SEND(10) ->    (ts 110>
         2.  ACK(6) <-      <tsecr 105>
         3.  SEND(11) ->    <ts 111>
         4.  <data segments 7-11 is lost, ACKs for 6-11 are lost>
             <RTO>          (cwnd <- 1, ssthresh <- 3)
         6.  SEND(6) ->     <ts 116> (cwnd = 1, pipe = 1)
         7.  ACK(7) <-      <tsecr 106> (undo: cwnd <- 6, ssthresh <- 4)
         8.  SEND(12) ->    <ts 117> (pipe = 6)
         9.  ACK(7, S: 12) <-  <tsecr 106> (cwnd = 6, pipe = 6)
         10. SEND(13) ->
         11. ACK(7, S: 12-13) <- (cwnd = 6, pipe = 6)
         12. SEND(14) ->
         13. ACK(7, S: 12-14) <- (cwnd = 6, pipe = 6)
             <fast retransmit>  (cwnd <- 3, pipe = 6)
         14. SEND(7) ->
         15. ACK(8, S: 12-14) <- (cwnd = 3, pipe = 5, cannot send)
             <RTO>
        ...

I hope my presentation format is not too unclear... After (falsely) 
skipping the go-back-N retransmissions, SACK sender gets to transmit 
one segment for each ACK after the RTO, because "pipe" is in balance 
with cwnd. Since the window was lost, it generates SACKs and the sender 
goes to recovery phase and reduces congestion window. Because the 
"pipe" variable remains at higher level, the sender cannot transmit and 
the real pipe runs out of packets.

I hope I have read the SACK recovery draft correctly, but in this case 
the definition of pipe variable causes problems with Eifel, since it 
becomes far above the true number of packets in the real pipe.

So, the problem still is, that output of the Eifel detection algorithm 
does not help to make the correct decission on whether to retransmit, 
even though the segment that triggered RTO was properly received.

> performance in the face of spurious timeouts combined with burst
> losses, *but* only because your TCP sender is breaking packet
> conservation. That doesn't go so well with RFC2914.

You have some kind of misunderstanding. There was no delay spike or 
spurious timeout in either of these two examples I gave. The first RTO 
occurred because the pipe got out of packets, so it was not spurious by 
any means. Since there was no packets on the pipe, there was no packet 
conservation to break. In both examples the second RTO occurred because 
the sender did not retransmit segments, as it should have done.

- Pasi

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 19 Aug 2002 14:43:43 +0200

>          15. ACK(8, S: 12-14) <- (cwnd = 3, pipe = 5, cannot send)

I'm not so familiar with SACK-based loss recovery, but I would think that 
in step 15, pipe should be equal 4 since from the sender's perspective 
segments 8, 9, 10, and 11 are still in the network.

But apart from that, I don't see anything wrong in this example. For 
SACK-based loss recovery one could maybe think about retransmitting old 
data after an acceptable ACK has arrived while pipe > cwnd. So, in the 
above example it should be OK if the sender retransmitted 8 right in 
response to ACK(8, S: 12-14).

>After (falsely)
>skipping the go-back-N retransmissions,

We disagree about the "falsely", but I think we had that.

>spurious timeout in either of these two examples I gave.

If you read our definition of spurious timeout, you would see that, in 
fact, we do consider the timeout in step 4 of your example as a spurious 
timeout. From our draft:
   "We also speak of a
    spurious timeout when the timeout occurred because an entire flight
    of ACKs was lost while in fact the original transmit of the oldest
    outstanding segment had arrived at the TCP receiver.
    [...]
    Such a timeout is certainly unavoidable, i.e., it would not
    have made a difference if the TCP sender had "waited longer". Still,
    the triggering of loss recovery was spurious since that original
    transmit was not lost, i.e., there had been no congestion in the data
    path. Hence, we use the term 'spurious timeout' in the sense that
    initiating the associated loss recovery was unnecessary."

>Since there was no packets on the pipe, there was no packet
>conservation to break.

Even though you - as a global observer - know that segments 7-11 were lost, 
the sender doesn't know that. So, after step 15 in your example, the sender 
must be conservative and assume that segments 8, 9, 10, and 11 are still in 
the network (packet conservation).

///Reiner