Subject: [tcpm] F-RTO and RFC 3517 interaction issues

From: Murari Sridharan <[email-masked]>
Date: Mon, 10 Mar 2008 10:05:46 -0700

I am seeing an inconsistency between FRTO and RFC 3517. May be the authors could clarify.

F-RTO defines recovery as follows

Set variable "recover" to
      indicate the highest segment transmitted so far.

RFC 3517 defines

"HighData" is the highest sequence number transmitted at a given

      point.

RFC 3517 clearly mandates that if RTO occurs during loss recovery new recovery phase MUST not be initiated until the RecoveryPoint is crossed.

"If an RTO occurs during loss recovery as specified in this document,

   RecoveryPoint MUST be set to HighData.  Further, the new value of

   RecoveryPoint MUST be preserved and the loss recovery algorithm

   outlined in this document MUST be terminated.  In addition, a new

   recovery phase (as described in section 5) MUST NOT be initiated

   until HighACK is greater than or equal to the new value of

   RecoveryPoint."

Now FRTO spec seems to violate the above rule with the following statement

If the algorithm exits with

   SpuriousRecovery set to SPUR_TO, "recover" is set to SND.UNA, thus

   allowing fast recovery on incoming duplicate acknowledgments.

This means that if we are in the middle of loss recovery and a real timeout occurs we save the recovery point per RFC 3517. At this point we continue with slow start and congestion avoidance, now say we are still below the earlier recovery point and a new timeout occurs. This time if the timeout is classified as SPUR_TO, then RecoveryPoint is set to SndUNA, overwriting the older value and a new recovery phase can begin, clearly violating RFC 3517.

Thanks

Murari
_______________________________________________
tcpm mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tcpm

---

From: Pasi Sarolahti <[email-masked]>
Date: Mon, 10 Mar 2008 20:08:26 -0400

Hi Murari,

Thanks for the careful reading! Clarification might indeed be in place.

 From quite early on when specifying the F-RTO algorithm we have  
thought it would be ok to allow fast recovery/SACK recovery  
immediately after detected spurious timeout, because then the TCP  
sender does not send the RTO retransmissions, and therefore the  
potential for RTO retransmissions triggering multiple fast  
retransmits should not exist (so the recover variable can be reset).  
For a case where spurious retransmission timeout follows the SACK  
recovery or fast recovery directly, this reasoning should be valid,  
do we agree?

In case where spurious timeout happens during an earlier RTO  
recovery, there could be potential for false fast retransmits to  
happen, as described in the original NewReno draft. (RFC 3517 does  
not describe it in such detail, but I assume the motivation for the  
text you quote is same also there). On the other hand, the draft says  
that F-RTO SHOULD NOT be applied when an earlier SACK recovery is in  
progress, as I think it was in the example you presented. Do you  
think this note is sufficient, or should it be clarified somehow?

- Pasi

On Mar 10, 2008, at 13:05, ext Murari Sridharan wrote:

> "HighData" is the highest sequence number transmitted at a  
> given      point.
>
> RFC 3517 clearly mandates that if RTO occurs during loss recovery  
> new recovery phase MUST not be initiated until the RecoveryPoint is  
> crossed.
> “If an RTO occurs during loss recovery as specified in this  
> document,   RecoveryPoint MUST be set to HighData.  Further, the  
> new value of   RecoveryPoint MUST be preserved and the loss  
> recovery algorithm   outlined in this document MUST be terminated.   
> In addition, a new   recovery phase (as described in section 5)  
> MUST NOT be initiated   until HighACK is greater than or equal to  
> the new value of   RecoveryPoint.”  Now FRTO spec seems to violate  
> the above rule with the following statementIf the algorithm exits  
> with   SpuriousRecovery set to SPUR_TO, "recover" is set to  
> SND.UNA, thus   allowing fast recovery on incoming duplicate  
> acknowledgments. This means that if we are in the middle of loss  
> recovery and a real timeout occurs we save the recovery point per  
> RFC 3517. At this point we continue with slow start and congestion  
> avoidance, now say we are still below the earlier recovery point  
> and a new timeout occurs. This time if the timeout is classified as  
> SPUR_TO, then RecoveryPoint is set to SndUNA, overwriting the older  
> value and a new recovery phase can begin, clearly violating RFC  
> 3517.  ThanksMurari

---

From: Murari Sridharan <[email-masked]>
Date: Tue, 11 Mar 2008 09:47:34 -0700

The main issue I see is that without maintaining extra state how do you know which situation you are in? I think the draft should clarify how exactly this should be done to avoid incorrect implementations. Here are the cases as I see it broadly there are two cases but its really 3 sub-cases. The cases are as FRTO sees the TCP state when it is about to classify a timeout.

a) This is the simplest case when timeout has happened without any prior recovery attempt. Setting Recover = SndUna works fine here.
b) Recovery in progress. Fast retransmit is triggered, 3517 may be active, now the timeout happens. If SPUR_TO, Recover = SndUna is ok for the reasons you outline below.
c) Recovery in progress like (b), timeout happens but this is a real timeout. Now next phase starts with valid Recover value based on 3517. Another timeout happens before Recover is crossed, now *without any additional state* there is no way to differentiate this from case (b).

There should be some additional state associated with the value stored in Recover which is if FRTO declared a real timeout. Now you can say only reset Recover = SndUna only if Recover is not associated with a real timeout. If we want to avoid implementation bugs we need to be prescriptive here so it may not be enough to say " On the other hand, the draft says
that F-RTO SHOULD NOT be applied when an earlier SACK recovery is in
progress" Because it doesn't clarify how case (b) is different from (c). In both cases an earlier SACK recovery is in progress.

Hope this helps.

Murari

-----Original Message-----
From: Pasi Sarolahti [mailto:[email-masked]]
Sent: Monday, March 10, 2008 5:08 PM
To: Murari Sridharan
Cc: [email-masked]; [email-masked]
Subject: Re: F-RTO and RFC 3517 interaction issues

Hi Murari,

- Pasi

On Mar 10, 2008, at 13:05, ext Murari Sridharan wrote:

> "If an RTO occurs during loss recovery as specified in this
> the new value of   RecoveryPoint."  Now FRTO spec seems to violate

---

From: Murari Sridharan <[email-masked]>
Date: Thu, 13 Mar 2008 13:30:02 -0700

Pasi any updates on this? I'd like to try out a fix to address this issue.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Murari Sridharan
Sent: Tuesday, March 11, 2008 9:48 AM
To: Pasi Sarolahti
Cc: [email-masked]; [email-masked]
Subject: Re: [tcpm] F-RTO and RFC 3517 interaction issues

Hope this helps.

Murari

-----Original Message-----
From: Pasi Sarolahti [mailto:[email-masked]]
Sent: Monday, March 10, 2008 5:08 PM
To: Murari Sridharan
Cc: [email-masked]; [email-masked]
Subject: Re: F-RTO and RFC 3517 interaction issues

Hi Murari,

- Pasi

---

From: Pasi Sarolahti <[email-masked]>
Date: Thu, 13 Mar 2008 21:35:34 -0400

Hi Murari,

Yes, I think your reasoning below is basically right, except that I  
think case (b) should not happen, because F-RTO is not allowed during  
earlier recovery (I had this mistake also in my earlier mail). We'll  
revise the draft ASAP, but before that I'd like to think a bit more  
about what is the minimal state needed at the sender, and if it was  
possible to do something without adding extra state or too much extra  
complexity.

I wonder if rephrasing the "This algorithm SHOULD NOT be applied if  
the TCP sender is already in SACK loss recovery when retransmission  
timeout occurs." condition in the following way would help:

when timeout occurs:
if (RecoveryPoint <= snd.una) then
    execute F-RTO
else
    follow normal RTO recovery procedure directly (e.g., set  
RecoveryPoint = HighData)

in addition setting RecoveryPoint = HighData in F-RTO algorithm  
should be postponed to step 2 to allow F-RTO for cases where delay  
causes multiple consecutive timeouts. I need to think about this a  
bit more, but wouldn't this solve the case (c) below? It would also  
prevent F-RTO during recovery from earlier genuine timeout, but I  
think this should be ok.

What do you think? Does this seem like a way forward?

- Pasi

On Mar 13, 2008, at 16:30, ext Murari Sridharan wrote:

> The main issue I see is that without maintaining extra state how do  
> you know which situation you are in? I think the draft should  
> clarify how exactly this should be done to avoid incorrect  
> implementations. Here are the cases as I see it broadly there are  
> two cases but its really 3 sub-cases. The cases are as FRTO sees  
> the TCP state when it is about to classify a timeout.
>
> a) This is the simplest case when timeout has happened without any  
> prior recovery attempt. Setting Recover = SndUna works fine here.
> b) Recovery in progress. Fast retransmit is triggered, 3517 may be  
> active, now the timeout happens. If SPUR_TO, Recover = SndUna is ok  
> for the reasons you outline below.
> c) Recovery in progress like (b), timeout happens but this is a  
> real timeout. Now next phase starts with valid Recover value based  
> on 3517. Another timeout happens before Recover is crossed, now  
> *without any additional state* there is no way to differentiate  
> this from case (b).
>
> There should be some additional state associated with the value  
> stored in Recover which is if FRTO declared a real timeout. Now you  
> can say only reset Recover = SndUna only if Recover is not  
> associated with a real timeout. If we want to avoid implementation  
> bugs we need to be prescriptive here so it may not be enough to say  
> " On the other hand, the draft says
> progress" Because it doesn't clarify how case (b) is different from  
> (c). In both cases an earlier SACK recovery is in progress.
>

---

From: Murari Sridharan <[email-masked]>
Date: Fri, 14 Mar 2008 11:24:09 -0700

I agree that this approach would solve the problem I mentioned below but this will prevent FRTO recovery for case (b) isn't that too restrictive? Would it negate some of the benefits of FRTO? The reason I ask is that packet reordering may be very common and we might very well be in recovery when a timeout happens. The case is that we see some dupacks indicating out of order packets may be during some mobility handoff, we enter recovery but the delay spike causes a timeout. This timeout is possibly spurious. I think the question really is how often does recovery precede a spurious timeout in the real world? Do you have any data from your testing. I know you discuss some of this in the appendix section of the draft as possible extensions, however it may be simple to fix if we maintain the extra bit that says that a real timeout occurred during earlier loss recovery so FRTO cannot begin till the recovery point is crossed.

-----Original Message-----
From: Pasi Sarolahti [mailto:[email-masked]]
Sent: Thursday, March 13, 2008 6:36 PM
To: Murari Sridharan
Cc: [email-masked]; [email-masked]
Subject: Re: F-RTO and RFC 3517 interaction issues

Hi Murari,

when timeout occurs:

- Pasi