Subject: A Radical Idea ( RE: [Tsvwg] new version of early retransmit )

From: [email-masked]
Date: Thu, 14 Dec 2006 11:52:19 -0500

Apologies if this has already been researched, or if there
are obvious flaws, but it struck me as interesting.

TCP and SCTP fast retransmission algorithms seem based on the
following assumptions.

1.  The receiving end gives the sending end information
    about what data has and has not been received using
    SACK and other mechanisms.

2.  The sending end uses this information to determine if
    and when data should be retransmitted.

3.  The algorithms used by the sending end to determine
    when data is retransmitted should be standardized and
    agreed upon.

I would suggest violating all these assumptions and replacing
with some very different assumptions.

1.  The receiving end makes a determination as to whether
    data has been lost and must be retransmitted.

2.  SACK goes away and is replaced by a "retransmit request"
    option that notifies the sender to retransmit specified
    data.

3.  The receiving end must keep track of any unnecessary
    retransmit requests as evidenced by receiving both
    the original data and the retransmitted data.

4.  The receiving end MUST NOT issue any retransmit
    requests if it has exceeded its budget of 
    unnecessary retransmit requests, but as long
    as it stays within budget, it may issue retransmit
    requests whenever it wants based on whatever 
    algorithm it chooses.

Potential advantages are that the protocol is less chatty,
and algorithms can evolve over time and be experimented with
without adversely affecting the network or requiring 
standards work.

Also, the receiving end has access to much useful information
which is not currently factored into retransmission decisions
such as a history of reordering (or lack thereof) on the 
particular path.  Over time, more information can be 
factored into the retransmit decision without needing
to create new protocol extensions to carry this information from 
the receiving end to the sending end.

-----Original Message-----
From: Mark Allman [mailto:[email-masked]] 
Sent: Thursday, December 14, 2006 9:05 AM
To: [email-masked]
Subject: [Tsvwg] new version of early retransmit

We recently re-submitted the early retransmit I-D that we pushed along a
while back:
 
        Title           : Early Retransmit for TCP and SCTP
        Author(s)       : M. Allman, et al.
        Filename        : draft-allman-tcp-early-rexmt-04.txt
        Pages           : 10
        Date            : 2006-11-26
 
http://www.ietf.org/internet-drafts/draft-allman-tcp-early-rexmt-04.txt

---

From: Fred Baker <[email-masked]>
Date: Thu, 14 Dec 2006 12:36:40 -0800

in short, instead of SACK, send a NACK.

In my mind, there are two fundamental thoughts here. An ACK or SACK  
says what one knows ("I know that I have received this") while a NACK  
says what one conjectures ("I know that received A and C, I infer  
that there must be a B, and I wonder whether you might be interested  
to know that this happened"). It also depends on an assumption that  
isn't generally true: that the receipt of C before B implies that B  
should be retransmitted. RFC 4588 makes the same assumption, and I  
would opine that in the cases where it is useful the probability of  
misordering is probably very low.

I'm not sure I see a big difference between a NACK and a duplicate  
ACK in the case that one retransmits on receipt of a duplicate ACK.  
There is a special case - if I am receiving a stream {A, B, C, D, E,  
F, G} and miss E, and sent an ACK in response to A and C but not D,  
the ACK I send in response to F acknowledges D and is therefore not  
duplicate, while a NACK of E would acknowledge D *and* state that E  
had not arrived. But in that case, the ACK sent on receipt of G would  
be a duplicate ACK. So it resolves to a similar case if not  
identical. But there is a reason that we don't trigger a  
retransmission on the first dup-ACK - misordering has a non-trivial  
rate of occurrence in the real backbone.

So in the real backbone, I think we would wind up with a similar  
heuristic. On receipt of an out of order packet, we might for example  
set a timer for a delayed NACK and send it if the timer expires and  
the segment has still not been received. We would also have to wonder  
aloud whether the NACK arrived or itself was lost in the network, and  
in the latter case what should be done about that.

Don't let me throw water on your research. But let me say that in my  
mind it isn't an obvious improvement. It's another way of doing about  
the same thing.

On Dec 14, 2006, at 8:52 AM, [email-masked] wrote:

> Apologies if this has already been researched, or if there are  
> obvious flaws, but it struck me as interesting.
>
> 1.  The receiving end gives the sending end information about what  
> data has and has not been received using SACK and other mechanisms.
>
> 2.  The sending end uses this information to determine if and when  
> data should be retransmitted.
>
> 3.  The algorithms used by the sending end to determine when data  
> is retransmitted should be standardized and agreed upon.
>
> I would suggest violating all these assumptions and replacing with  
> some very different assumptions.
>
> 1.  The receiving end makes a determination as to whether data has  
> been lost and must be retransmitted.
>
> 2.  SACK goes away and is replaced by a "retransmit request" option  
> that notifies the sender to retransmit specified data.
>
> 3.  The receiving end must keep track of any unnecessary retransmit  
> requests as evidenced by receiving both the original data and the  
> retransmitted data.
>
> 4.  The receiving end MUST NOT issue any retransmit requests if it  
> has exceeded its budget of unnecessary retransmit requests, but as  
> long     as it stays within budget, it may issue retransmit  
> requests whenever it wants based on whatever algorithm it chooses.
>
> Potential advantages are that the protocol is less chatty, and  
> algorithms can evolve over time and be experimented with without  
> adversely affecting the network or requiring  standards work.
>
> Also, the receiving end has access to much useful information which  
> is not currently factored into retransmission decisions such as a  
> history of reordering (or lack thereof) on the  particular path.   
> Over time, more information can be  factored into the retransmit  
> decision without needing to create new protocol extensions to carry  
> this information from  the receiving end to the sending end.
>
> We recently re-submitted the early retransmit I-D that we pushed  
> along a while back:
>

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Thu, 14 Dec 2006 13:51:34 -0700

Jim.Williams,

In SCTP at least, sending a GAP report in a SACK is a negative
acknowledgement.  In cases where many gaps occur (e.g. CMT SCTP),
advantage is gained by suppressing expessive GAP reports using
multi-queue analysis at the receiver; however, in SCTP sending
gap reports is largely optional.  So under the existing SCTP
protocol, a receiver can already request a fast retransmission
by issuing 4 gap reports for the "missing" TSNs (or not, by not
issuing gap reports).  Controlled gap reports is already in use
for CMT SCTP and mostly has a positive effect as reordering of
packets trasnmitted by on alternate multi-homed paths is common
place for CMT SCTP.

--brian

[email-masked] wrote:          (Thu, 14 Dec 2006 11:52:19)

-- 
Brian F. G. Bidulock
[email-masked]
http://www.openss7.org/