Subject: [tcpm] TCP Error recovery and efficiency

From: Anthony Sabatini <[email-masked]>
Date: Sun, 8 Jul 2012 23:55:09 -0400

All -

While data communications was constantly improving, due mostly to the wide adoption of fiber optics, the fact that TCP had an inferior recovery mechanism was moot as it came into play less and less often.  Sadly those days are now behind us and we face a world increasingly hostile to data transmission.  The sources of packet loss have grown legion, "traffic shapers", congested links to the subscibers, overloaded wifi bands, content monitor that can not keep up, rate caps on mobile phone data usage, the list goes on and on.  Complicating this is the increase in data rates and file sizes which allow many more packets and their acknowledgements to be inflight between two endpoints at once.  We as a community must move along the proliferation of SACK and if we are going to do that we should fix the underlying issues in the protocol first.

All current TCP recovery implementations are based on guessing the state at the remote node.  No recovery mechanism currently in place gives sufficient weight to in-flight or delayed messages.  This problem can be solved easily by transmitting a token related to the transmission state in each out going message which the destination node will return on its next transmission.  By having this token I know all of the messages the far end should have seen and if I do not have an acknowledgement for any of them, I know that those need to be retransmitted.

To start this discussion I have created an I-D "Highly Efficient Selective Acknowledgement (SACK) for TCP" - draft-sabatini-tcp-sack-00 which I hope will be accepted by the working group.

Note that even though no TCP implementation exists, the HDLC version I created for the financial community has 20 years of working history all over the world and the capability for being 100% efficient right down to one error per message no matter what the data rate or the delay (including multiple satellite hops).

Tony

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 11 Jul 2012 11:39:38 +0000

Hi Anthony,

first off, a quick observation: Modifying existing options, particularly their length or encoding, as you propose in that draft, will probably not work; there are many devices, which may react undefined (ignore the extended SACK permitted, accept it in the old way,...) which wouldn't be compatible.

Also, certain middleboxes do modify the contents of regular SACK blocks (rewriting TCP sequence numbers), and they would definitely interact very badly when a well-defined tcp option suddenly has different semantics.

Second, I try to understand your language around the token; I'm not sure I follow the reasoning around artificially delaying ACK / SACK updates on the receiver.

A worked out example as appendix would do good (showing which fields contain what when, and the exchange of these tokens between sender and receiver).

Third, the draft appears to propose sending multiple ACKs in response to a (receiver delay timeout), with varying SACK option contents between these ACKs (all having the same TCP header fields)? The purpose of these ACKs being to clock out the missing segments from the sender, if I read this correctly? However, no precaution is there to prevent a burst or train of ACKs (which would cause a transmit spike on the sender side), correct?

I'm not quite clear on the sender behavior; the text seems to imply that the SACK scoreboard should be deleted for each received ACK/SACK, and reconstructed anew?

The new "token" fields serving as secondary ACK counter to only resend those bytes that were not retransmitted by the time the receiver got that token?

Reconstructing the order in which packets arrive at the destination is, IMHO, a valuable goal to optimize the error recovery of TCP SACK.

So, to summarize, there are two main ideas in this draft:

a)      Use of a deterministically reflected token, that serves to reconstruct the exact order of packets received at the receiver (including retransmissions).

b)      Sending of unsolicidated ACKs based on a short timeout (1/4 RTT) in order to pull lost/delayed data from the sender without reverting to a sender-side RTO

c)       Modification of a well-known TCP option with new data fields

Please confirm that I have properly summarized your ideas in that draft.

I'm very much in favor of idea a). However, I still believe that the proper approach would be to synergistically use Timestamp together with SACK to achieve the same (which requires "only" a semantic/behavior change of the TS field in the presence of the SACK option, but doesn't alter the encoding/interpretation per se). With that modification to the Timestamp semantics, the timestamps can serve a "tokens" delivering the information you seek to better reconstruct the receiver state at the sender. Please have a look at http://tools.ietf.org/id/draft-scheffenegger-tcpm-timestamp-negotiation-03.txt.

I'm not so sure about idea b) since that would appear to violate the conservation of packets rule - even under optimal conditions (no packet loss, only very variable packet delay/reordering), a higher rate of ACKs would be sent back, potentially completely unnecessary.

With c)  - this will break this proposal. Please use experimental options in the draft (and newly assigned option numbers if adopted) so to avoid compatibility issues with existing deployed hardware in the internet.

Will you be present in Vancouver?

Best regards,

Richard Scheffenegger

From: [email-masked] [mailto:[email-masked]] On Behalf Of Anthony Sabatini
Sent: Montag, 09. Juli 2012 05:55
To: [email-masked]
Subject: [tcpm] TCP Error recovery and efficiency

All -

Tony

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 12 Jul 2012 13:18:23 +0000

Hello Anthony,

As a summary of our offline discussion, I believe I understand your loss recovery mechanism. Also, the really important signal that is missing from current TCP, to allow the implementation of this mechanism is the so-called "token".

I still believe that modifying the SACK signaling option is the wrong place to introduce this token.

SACK, as defined and implemented today, should keep the scoreboard in the sender in a very accurate state, with high reliability. And I think it performs this task very well.

>From the description so far, it's apparent that the tokens described are basically packet counters, that are monotonically increasing for each newly sent packet - regardless of original packet, or retransmission. With only 16 bits available for this counter, under extreme circumstances a BDP of ~100 MB could result in issues; However, the bounds for that token are not explicitly defined. I believe that it really only needs to increase once per RTT, or once per loss recovery epoch (resending any one segment anew starts one such epoch) - which can be considerably slower than a mere packet counter.

If the above observations hold, that your token has much more resemblance with the TCP timestamps. The major difference being, that timestamps are not immediately reflected when an ACK is sent -  particularly not during loss / reorder events.

OTOH, using both SACK and TS synergistically, could retain the wire encoding and signaling, and existing mechanisms using these options, while allowing new features, such as a more efficient loss recovery scheme as proposed.

I'm looking forward to a lively discussion around these topics in Vancouver, if no one wants to share his views on list.

Richard Scheffenegger

From: Anthony Sabatini [mailto:[email-masked]]
Sent: Mittwoch, 11. Juli 2012 18:47
To: Scheffenegger, Richard; tcpm; [email-masked]
Subject: RE: [tcpm] TCP Error recovery and efficiency (updated reply)

Sorry - previous message sent in error.
Richard -

First off thank you for taking the time to read the draft.

With respect to the option numbers, as I wrote to the tcpm chairs - I can not presume in a draft what option numbers will be assigned in a standard but I needed a place holder for illustration.  I therefore used the ones in SACK to show how they relate and to guarantee in the final document they will be corrected to the assigned appropriate values.

With respect to sending multiple ACKs and what is contained in those ACKs - in IPv4 the TCP options fields are very limited and I have had to steal four more of them.  Fortunately SACK uses 8 byte pairs so I have not decreased the number of pairs sent, but in order to render a complete state I may need to send a multiple number of ACKs.  Like SACK, I have to lay out at least a framework of what pairs get transmitted in what order with how many repeats.  Like SACK the first pairs have to be any blocks which have changed sizes since my last acknowledgement.  The next most important block is the oldest since it defines the oldest, and thus the most important, missing segment.  The rest of the blocks are then transmitted, oldest first.  Repeating this sequence of ACKs is an homage to any of the various TCP fast recovery mechanisms, they are right in that you are as likely to lose the ACK as you are to lose the message.  Two things I am sure of, 1) someone is going to do a masters thesis on what is the optimal order to send the blocks in and how many repeats are best and 2) someone is going to suggest compressing the segment limits in the TCP options (and we might want to make that change in this standard).  Note that the 1/4 RTT time was a restatement of a SACK philosophy to which I personally find of minimal value.  An immediate repeat of the ACK set insures against transient packet loss, the 1/4 RTT only adds robustness where the link drops a burst of segments such as happens in an overloaded content inspector.  Note that unless you have a SACK situation, normal TCP acknowledgement rules apply, even if you have a couple of SACK segments, normal TCP acknowledgement rules apply.  In both cases the only thing that changed was there are options in the ACK.  It is  only when we are fairly far down into the weeds that either the original SACK or my version changes anything and mostly it is to generate multiple ACKS so we can get the state out.  Thus I change nothing and violate no rules on a clean link or even a slightly dirty one.  The violation that occurs is in the original, approved, SACK RFC.

 With respect to timestamps - having written many network drivers with many operating systems, I have tried to avoid them on a driver level if possible as calling one device driver from within another can lead to unintended consequences.  For example many clocks lock a call when they are processing a time increment so that yo do not get a ripple effect of half an updated timestamp.  This lead to an all block at the network level for that period of time which is not good.  It also means that you have to timestamp every outgoing message in the transmit queue.  By using as your token the current index into the transmitted segment queue you can immediately work forward in that queue to see what segments have been retransmitted but not yet received, regardless of timestamp.

With respect to the scoreboard - the acknowledgement in the TCP header forms a floor for the scoreboard, all entries with segment finishes prior to that are released when this value is updated (others are retained as not yet complete).  With respect to selective acknowledgements, a SACK is permanent, it creates a begin/end pair in the scoreboard, as subsequent SACKs come in entries may be inserted, added to the end, or merged with one or more of the existing entries.  The holes between these entries represent the segments (and between the floor and the first) that must be retransmitted.  Likewise in the reciever the TCP acknowledgement rules, the receiver must remove all SACK blocks on its side which are now below the updated floor.

With respect to the delay returning a received token - we as a group take too little time understanding why a protocol works.  TCP is tolerant of out of sequence packet arrivals because it saves segments beyond the one it expects and will fill in when they arrive out of order.  Since the proposed change will tightly monitor missing segments, if the far end updated its returned token immediately then any out of order packets would be considered permanently lost.  By delaying the update of the returned token I allow time for the out of order packet to arrive and be processed.  Yes this hurts efficiency and yes the delay should be set to zero in a point to point environment but having this feature means that the modified protocol has all of the robustness of the original.  A seconday important feature of the delay is that it insures that all of the ACKs that comprise the receiver state have been received and processed.

With respect to Vancouver - I will go if anyone cares about this - since you do, I could be easily convinced.  I have asked the tcpm chairs for 15 minutes to explain myself but have not heard from them as of yet.

Note for the record - I am probably not the best person to rewrite this draft as I am too close to the issue,  if anyone wants to co-author it and rewrite it please let me know, we will then, at least, have one other person who understands what I am trying to express.

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

________________________________
From: [email-masked]<mailto:[email-masked]>
To: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: [tcpm] TCP Error recovery and efficiency
Date: Wed, 11 Jul 2012 11:39:38 +0000

Hi Anthony,

Best regards,

Richard Scheffenegger

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]<mailto:[mailto:[email-masked]]> On Behalf Of Anthony Sabatini
Sent: Montag, 09. Juli 2012 05:55
To: [email-masked]<mailto:[email-masked]>
Subject: [tcpm] TCP Error recovery and efficiency

All -

Tony

---

From: Yuchung Cheng <[email-masked]>
Date: Thu, 12 Jul 2012 08:06:06 -0700

Hi Anthony,

On Sun, Jul 8, 2012 at 8:55 PM, Anthony Sabatini <[email-masked]> wrote:
> All -
>
> While data communications was constantly improving, due mostly to the wide
> adoption of fiber optics, the fact that TCP had an inferior recovery
> mechanism was moot as it came into play less and less often.  Sadly those
> days are now behind us and we face a world increasingly hostile to data
> transmission.  The sources of packet loss have grown legion, "traffic
> shapers", congested links to the subscibers, overloaded wifi bands, content
> monitor that can not keep up, rate caps on mobile phone data usage, the list
> goes on and on.  Complicating this is the increase in data rates and file
> sizes which allow many more packets and their acknowledgements to be
> inflight between two endpoints at once.  We as a community must move along
> the proliferation of SACK and if we are going to do that we should fix the
> underlying issues in the protocol first.
>
> All current TCP recovery implementations are based on guessing the state at
> the remote node.  No recovery mechanism currently in place gives sufficient
> weight to in-flight or delayed messages.  This problem can be solved easily
> by transmitting a token related to the transmission state in each out going
> message which the destination node will return on its next transmission.  By
What exactly do sender and receiver put in the sender/receiver state field?
Maybe we can have an example? say senders send 1,2,3,4 packets,
receiver receives only first 2nd then 4th packets.

The state you described resembles sack scoreboard in RFC 3517, which
is implemented
in all major operating systems. Can you compare your approach to that RFC?

> having this token I know all of the messages the far end should have seen
> and if I do not have an acknowledgement for any of them, I know that those
> need to be retransmitted.
>
> To start this discussion I have created an I-D "Highly Efficient Selective
> Acknowledgement (SACK) for TCP" - draft-sabatini-tcp-sack-00 which I hope
> will be accepted by the working group.
>
> Note that even though no TCP implementation exists, the HDLC version I
> created for the financial community has 20 years of working history all over
> the world and the capability for being 100% efficient right down to one
> error per message no matter what the data rate or the delay (including
> multiple satellite hops).
>
> Tony
>
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>

---

From: Anthony Sabatini <[email-masked]>
Date: Wed, 11 Jul 2012 11:35:06 -0400

Richard -

With respect to sending multiple acks and what is contained in those acks - in IPv4 the TCP options fields are very limited and I have had to steal four more of them.  Fortunately SACK uses 8 byte pairs so I have not decreased the number of pairs sent, but in order to render a complete state I may need to send a multiple number of ACKs.  Like SACK, I have to lay out at least a framework of what pairs get transmitted in what order with how many repeats.  Like SACK the first pairs have to be any blocks which have changed sizes since my last acknowledgement.  The next most important block is the oldest since it defines the oldest, and thus the most important, missing segment.  The rest o the blocks are then transmitted, oldest first.  Repeating this sequence of ACKs is an homage to any of the various TCP fast recovery mechanisms, they are right in that you are as likely to lose the ACK as you are to lose the message.

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

From: [email-masked]
To: [email-masked]; [email-masked]; [email-masked]
Subject: RE: [tcpm] TCP Error recovery and efficiency
Date: Wed, 11 Jul 2012 11:39:38 +0000

Hi Anthony,
 
first off, a quick observation: Modifying existing options, particularly their length or encoding, as you propose in that draft, will probably
 not work; there are many devices, which may react undefined (ignore the extended SACK permitted, accept it in the old way,…) which wouldn’t be compatible.
 
Also, certain middleboxes do modify the contents of regular SACK blocks (rewriting TCP sequence numbers), and they would definitely interact very
 badly when a well-defined tcp option suddenly has different semantics.

Second, I try to understand your language around the token; I’m not sure I follow the reasoning around artificially delaying ACK / SACK updates
 on the receiver.

Third, the draft appears to propose sending multiple ACKs in response to a (receiver delay timeout), with varying SACK option contents between
 these ACKs (all having the same TCP header fields)? The purpose of these ACKs being to clock out the missing segments from the sender, if I read this correctly? However, no precaution is there to prevent a burst or train of ACKs (which would cause a transmit
 spike on the sender side), correct?
 
I’m not quite clear on the sender behavior; the text seems to imply that the SACK scoreboard should be deleted for each received ACK/SACK, and
 reconstructed anew?
 
The new “token” fields serving as secondary ACK counter to only resend those bytes that were not retransmitted by the time the receiver got that
 token?

 

 
a)     
Use of a deterministically reflected token, that serves to reconstruct the exact order of packets received at the receiver (including
 retransmissions). 
 
b)     
Sending of unsolicidated ACKs based on a short timeout (1/4 RTT) in order to pull lost/delayed data from the sender without reverting
 to a sender-side RTO
 
c)      
Modification of a well-known TCP option with new data fields

I’m very much in favor of idea a). However, I still believe that the proper approach would be to synergistically use Timestamp together with SACK
 to achieve the same (which requires “only” a semantic/behavior change of the TS field in the presence of the SACK option, but doesn’t alter the encoding/interpretation per se). With that modification to the Timestamp semantics, the timestamps can serve a “tokens”
 delivering the information you seek to better reconstruct the receiver state at the sender. Please have a look at http://tools.ietf.org/id/draft-scheffenegger-tcpm-timestamp-negotiation-03.txt.
 
I’m not so sure about idea b) since that would appear to violate the conservation of packets rule – even under optimal conditions (no packet loss,
 only very variable packet delay/reordering), a higher rate of ACKs would be sent back, potentially completely unnecessary.
 
With c)  - this will break this proposal. Please use experimental options in the draft (and newly assigned option numbers if adopted) so to avoid
 compatibility issues with existing deployed hardware in the internet.

Best regards,

Richard Scheffenegger

From: [email-masked] [mailto:[email-masked]]
On Behalf Of Anthony Sabatini

To: [email-masked]

 

All -

While data communications was constantly improving, due mostly to the wide adoption of fiber optics, the fact that TCP had an inferior recovery mechanism was moot as it came into play less and less often.  Sadly those days are now behind us and we face a world
 increasingly hostile to data transmission.  The sources of packet loss have grown legion, "traffic shapers", congested links to the subscibers, overloaded wifi bands, content monitor that can not keep up, rate caps on mobile phone data usage, the list goes
 on and on.  Complicating this is the increase in data rates and file sizes which allow many more packets and their acknowledgements to be inflight between two endpoints at once.  We as a community must move along the proliferation of SACK and if we are going
 to do that we should fix the underlying issues in the protocol first.

All current TCP recovery implementations are based on guessing the state at the remote node.  No recovery mechanism currently in place gives sufficient weight to in-flight or delayed messages.  This problem can be solved easily by transmitting a token related
 to the transmission state in each out going message which the destination node will return on its next transmission.  By having this token I know all of the messages the far end should have seen and if I do not have an acknowledgement for any of them, I know
 that those need to be retransmitted.

Note that even though no TCP implementation exists, the HDLC version I created for the financial community has 20 years of working history all over the world and the capability for being 100% efficient right down to one error per message no matter what the
 data rate or the delay (including multiple satellite hops).

Tony

---

From: Anthony Sabatini <[email-masked]>
Date: Wed, 11 Jul 2012 12:47:26 -0400

Richard -

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

From: [email-masked]

Hi Anthony,

 

 

 

 
a)     
 
b)     
 
c)      

 

 
Best regards,

Richard Scheffenegger

To: [email-masked]

 

All -

Tony

---

From: Anthony Sabatini <[email-masked]>
Date: Fri, 13 Jul 2012 12:11:52 -0400

Yuchung -

> in all major operating systems. Can you compare your approach to that RFC?

The sender puts into the send state token the actual ordinal representing this message's sequence in the transmission stream regardless of whether the message is new or a retransmission and then uses that ordinal to save the information about the segment that was sent.

When the transmit side receives a sack block it inserts it into the list of acknowledged blocks, merging them or adding to the end of the list as needed as with the current RFC.  It also removes or modifies entries in the retransmit queue as needed. Each time the transmitter receives a change to its token that was returned to it, it regenerates the retransmission queue based on what segments are missing from the sack receive list  and the ages it forward (starting at the returned transmit token plus one) by removing all entries which correspond to segments that have been sent since then.  This new list is the used as the retransmission queue, all entries in the retransmission queue must be transmitted before new segments are transmitted.

Thus (p = packet, t = token) -
Transmit - Network   -    Recvieve
P1T0       -->
P2T1       -->
P3T2       -->
P4T3       -->
(Waits for work)
           --X              (first packet lost)   
           P2T1             -->
           <--              SACK T1P2
           --X              (third packet lost)
           P4T3             -->
           <--              SACK T3P2P4
                            (Waits for work)
<--        SACK T1P2  
P1T4       -->
<--        SACK T3P2P4
P3T5       -->
(It knows P1 is "inflight")
           P1T4             -->
           <--              ACK 2 SACK T4P4
           P3T5             -->
           <--              ACK 4 SACK T5
<--        ACK 2 SACK T4P2 
(Moves new floor to 2)
(It knows P3 "inflight")
<--        ACK 4 SACK T5
(Moves new floor to 4)

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

> From: [email-masked]
> Date: Thu, 12 Jul 2012 08:06:06 -0700
> Subject: Re: [tcpm] TCP Error recovery and efficiency
> To: [email-masked]
> CC: [email-masked]
> 
> Hi Anthony,
>

---

From: Anthony Sabatini <[email-masked]>
Date: Sun, 15 Jul 2012 15:59:40 -0400

All -

First off a thank you to Richard Scheffenegger for his comments but most importantly when he asked whether the number of ACKs being sent was excessive (since we are trying for efficiency unnecessary ACKs diminish that efficiency).  When I first wrote this RFC six years ago for my thesis, my concern was with my extensions not in reanalyzing the base protocol.  This turns out to be a mistake because, by moving the retransmission process farther away from using timers and changing it to purely a state basis, a number of statements/features of the base protocol no longer work the same.

As a statement of policy SACK should send no more ACKs then a current modern version of TCP does.  For the most part SACK only adds from 2 to 34 bytes in the options area of existing messages.  Even with this change we are only talking 6 to 38 bytes.  It is only in extreme situations where there are more than four gaps in the acknowledged data that SACK requires additional ACKs.  As to when these ACKs are sent again normal TCP practice applies for the most part (as long as all SACK blocks occupy a single ACK).

The recovery basis in Enhanced SACK (E-SACK) except for the "Link Broken" disaster timer is entirely state driven on the transmit side.  Since timers by their very nature, must be set to the worst case value, this automated retransmission is much quicker and more accurate.  The combination of TCP ACKs, SACK block changes and Returned Transmit Token changes form the triggers that guide the recovery and transmission processes.  In order to insure the proper flow of those signals the receiver is running three classes of timer - Returned Transmit Token delay timer, Second ACK timer and the "I did not receive what I needed" keep alive timer.  More about those in the commentary.

The principle that all state changing information should be sent twice (second ACK) from TCP is a good one and should be preserved in this protocol since the loss of an ACK is as disastrous as the loss of a message, we just need to be cognizant that there are now three state change elements, any of which triggers the ACK pair, specifically the TCP ACK (acknowledging a change in the TCP transmit floor), a change to a SACK block, and finally a change to one of the tokens (note I Include both Transmit and Returning here).  The question then becomes how do we implement this.  The underlying reality here is that on a link with even moderate activity a second intentional ACK is not needed since the ACK triggered by the next arriving message would replace it.  The problem we encounter is that ACK messages are significantly shorter than full data messages so we would always send a second ACK if we send it immediately after the first since nothing has changed.  The thought is then to delay the second ACK until the link goes idle (1.3 times the length of time to receive a full packet on the fast side to 2.6 x the length of time to receive a full packet on the slow side).  Note that this delay has a direct effect on the Returned Transmit Token delay timer as that timer can not be less than this delay plus the amount of time to transmit all of the ACKs to hold the complete list of SACK blocks in order to insure that state information is up to date before the token changes, thus possibly degrading link efficiency.

One note of clarification, if a state change triggers another pair of ACKs, this takes precedence over completing the remainder of the ACK group if multiple ACKs are required to transmit the SACK blocks.

The reason we trigger an ACK on either token changing is to get around the dreaded "last character hang" of very early TCP implementations.  If the transmitter sends an ACK with the updated Transmit Token from the last outgoing segment when the link goes idle it insures the receiver has the updated value of that Transmit Token which will lead to the retransmission of that last missing segment.

We delay the return of the received Transmit Token for two reasons, first it allows packets that got out of order to be received and put back in order before being declared missing and secondly, because a group of SACK blocks might span multiple ACKs, to make sure that state information is up to date before we declare a segment as missing.

This leads the to a discussion of very bad burst mode errors.  If the receiver has not received the segments it requires and has not sent out an ACK for RTT*1.3 then the receiver needs to send another ACK pair.  Note this applies to the transmitter also in that if its Returned Transmit Token does not equal Last Transmit Token after the same RTT*1.3 it is obligated to send an ACK pair to the receiver to prompt it to restart.  Obviously RTT*1.3 is a long time on transcontinental or satellite links which is why 1/4 RTT for an ACK pair from the receiver as a keep alive is under consideration, the maximum length of time to cover the burst error without degrading efficiency too badly.

In filling the outgoing ACKs with SACK blocks at the receiver, the list is maintained in the order oldest (smallest segment start) to the youngest.  The list is queried three times when building the ACK group, first for all blocks that just changed and thus have the most critical information (ACK NEEDED = 2), then a scan for those blocks which already had their first ACK (ACK NEEDED = 1) and then for the blocks which have already been transmitted twice (ACK NEEDED = 0).  The ACK NEEDED count is then decremented. 

To make E-SACK work three lists must be maintained, one at the receiver and two at the transmitter.  The one in the receiver is identical in concept to the one in the original RFC with the addition of ACK NEEDED and the proviso that it be in oldest to youngest order.  At the transmitter an identical list is maintained built from the recovered SACK blocks.  When a changed Returned Transmit Token is received, the recovered SACK block list is used to construct a retransmit queue of all unacknowledged segments.  Then starting at the transmit queue entry plus one derived from the Returned Transmit Token, and proceeding forward until all transmitted segment extents have been processed, entries are removed or modified in the new retransmit queue to compensate for segments sent after the time of the Returned Transmit Token.  The adjusted new transmit queue replaces the existing queue and the transmission process is started again starting at the first entry on the queue, not proceeding with new transmission until the queue is completed.  Please note that incoming SACK blocks must be checked against the retransmit queue in order to remove segments that have been subsequently correctly received.

Noto Bene - This protocol is an update to RFC 2018.  It is not compatible with nor do I believe in the philosophy of RFC2883/RFC3708 as the whole purpose of this change is to eliminate duplicate segments and increase efficiency and reliability where the changes outlined in those RFCs degrade efficiency (especially by generating extra SACK blocks) without substantially improving anything.  Also as adopted in the RFC there is a major fallacy, it assumes that there can be only one SACK block with a status change where in reality, due to processing considerations, there can be two or even more blocks with changes before an ACK can be sent.

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

---

From: Joe Touch <[email-masked]>
Date: Mon, 16 Jul 2012 10:04:31 -0700

On 7/11/2012 8:35 AM, Anthony Sabatini wrote:
> With respect to the option numbers, as I wrote to the tcpm chairs - I
> can not presume in a draft what option numbers will be assigned in a
> standard but I needed a place holder for illustration.  I therefore used
> the ones in SACK to show how they relate and to guarantee in the final
> document they will be corrected to the assigned appropriate values.

You should be using either "TBD" or a number that won't fit (256). You 
should NEVER use an existing assignment unless you intend to be 
compatible with that assignment.

You should NEVER use a currently unassigned value.

Specific values will be determined by IANA in the late stages of 
publication, not before.

Joe

---

From: Anthony Sabatini <[email-masked]>
Date: Mon, 16 Jul 2012 13:37:37 -0400

Joe -

As I mentioned this will be addressed in the next release of the draft, this draft was there to get a discussion going and to work out the final implementation details, I used the same numbers in the discussion document to correspond them to the existing RFC2018 for comparison, that as previously stated was probably a mistake.  What are your comments on the mechanics of the protocol?

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

> Date: Mon, 16 Jul 2012 10:04:31 -0700
> From: [email-masked]
> CC: [email-masked]; [email-masked]; [email-masked]

---

From: Joe Touch <[email-masked]>
Date: Mon, 16 Jul 2012 10:46:05 -0700

I haven't looked at the protocol; there are others more familiar with 
SACK thank I.

Joe

On 7/16/2012 10:37 AM, Anthony Sabatini wrote:
> Joe -
>
> As I mentioned this will be addressed in the next release of the draft,
> this draft was there to get a discussion going and to work out the final
> implementation details, I used the same numbers in the discussion
> document to correspond them to the existing RFC2018 for comparison, that
> as previously stated was probably a mistake.  What are your comments on
> the mechanics of the protocol?
>
> Tony
>
> Anthony Sabatini
> 200 West 20th Street
> Apt. 1216
> New York, NY 10011
>
> Phone: (212) 867-7179
> Mobile: (917) 224-8388
>
>
>
>

---

From: Matt Mathis <[email-masked]>
Date: Thu, 19 Jul 2012 13:02:43 -0700

I don't understand what problem you are trying to solve: As written 2018
provides the sender with perfect information about the state of the
receivers reassembly queue (e.g. which data is still missing) as long as
most ACKs are delivered, mostly in order.   The minimum cases which causes
the sender to send duplicate data are timeouts (but see the errata against
2018), or fairly complicated patterns of sustained losses on both sides of
the link.

In fact, if there is no loss or reordering on the return path, a single
SACK block is sufficient to give the sender perfect information.

With classic TCP timestamps (not for PAWS) it is even possible to
disambiguate between holes that were filled by ooo data or retransmissions.
 Due to the TS echo rules for PAWS, it actually does less well.  I am not
the expert here, but Richard Scheffenegger has explored this problem
extensively.   But the ambiguity is whether congestion control undo is
permitted, not which data is still needed at the receiver.

If you look at 2018, (and 2883) the first SACK block is described as MUST
be the chronologically newest.  The rest of the option is described with
SHOULDs, because we knew that SACK could theoretically be improved by
dithering the rest of the SACK option across all past SACK blocks.   Such a
scheme would make SACK work well with unreasonable levels of loss on the
ACK path.  (e.g. the 2nd SACK block could alternate between the two most
recent prior 1st blocks, the 3rd across all earlier blocks).

But now, would that really a feature for TCP to work well on the forward
path, while the (low bandwidth) return path is being mauled by SACK?

Thanks,
--MM--
The best way to predict the future is to create it.  - Alan Kay

On Sun, Jul 15, 2012 at 12:59 PM, Anthony Sabatini <[email-masked]>wrote:

>  All -
>
> First off a thank you to Richard Scheffenegger for his comments but most
> importantly when he asked whether the number of ACKs being sent was
> excessive (since we are trying for efficiency unnecessary ACKs diminish
> that efficiency).  When I first wrote this RFC six years ago for my thesis,
> my concern was with my extensions not in reanalyzing the base protocol.
> This turns out to be a mistake because, by moving the retransmission
> process farther away from using timers and changing it to purely a state
> basis, a number of statements/features of the base protocol no longer work
> the same.
>
> As a statement of policy SACK should send no more ACKs then a current
> modern version of TCP does.  For the most part SACK only adds from 2 to 34
> bytes in the options area of existing messages.  Even with this change we
> are only talking 6 to 38 bytes.  It is only in extreme situations where
> there are more than four gaps in the acknowledged data that SACK requires
> additional ACKs.  As to when these ACKs are sent again normal TCP practice
> applies for the most part (as long as all SACK blocks occupy a single ACK).
>
> The recovery basis in Enhanced SACK (E-SACK) except for the "Link Broken"
> disaster timer is entirely state driven on the transmit side.  Since timers
> by their very nature, must be set to the worst case value, this automated
> retransmission is much quicker and more accurate.  The combination of TCP
> ACKs, SACK block changes and Returned Transmit Token changes form the
> triggers that guide the recovery and transmission processes.  In order to
> insure the proper flow of those signals the receiver is running three
> classes of timer - Returned Transmit Token delay timer, Second ACK timer
> and the "I did not receive what I needed" keep alive timer.  More about
> those in the commentary.
>
> The principle that all state changing information should be sent twice
> (second ACK) from TCP is a good one and should be preserved in this
> protocol since the loss of an ACK is as disastrous as the loss of a
> message, we just need to be cognizant that there are now three state change
> elements, any of which triggers the ACK pair, specifically the TCP ACK
> (acknowledging a change in the TCP transmit floor), a change to a SACK
> block, and finally a change to one of the tokens (note I Include both
> Transmit and Returning here).  The question then becomes how do we
> implement this.  The underlying reality here is that on a link with even
> moderate activity a second intentional ACK is not needed since the ACK
> triggered by the next arriving message would replace it.  The problem we
> encounter is that ACK messages are significantly shorter than full data
> messages so we would always send a second ACK if we send it immediately
> after the first since nothing has changed.  The thought is then to delay
> the second ACK until the link goes idle (1.3 times the length of time to
> receive a full packet on the fast side to 2.6 x the length of time to
> receive a full packet on the slow side).  Note that this delay has a direct
> effect on the Returned Transmit Token delay timer as that timer can not be
> less than this delay plus the amount of time to transmit all of the ACKs to
> hold the complete list of SACK blocks in order to insure that state
> information is up to date before the token changes, thus possibly degrading
> link efficiency.
>
> One note of clarification, if a state change triggers another pair of
> ACKs, this takes precedence over completing the remainder of the ACK group
> if multiple ACKs are required to transmit the SACK blocks.
>
> The reason we trigger an ACK on either token changing is to get around the
> dreaded "last character hang" of very early TCP implementations.  If the
> transmitter sends an ACK with the updated Transmit Token from the last
> outgoing segment when the link goes idle it insures the receiver has the
> updated value of that Transmit Token which will lead to the retransmission
> of that last missing segment.
>
> We delay the return of the received Transmit Token for two reasons, first
> it allows packets that got out of order to be received and put back in
> order before being declared missing and secondly, because a group of SACK
> blocks might span multiple ACKs, to make sure that state information is up
> to date before we declare a segment as missing.
>
> This leads the to a discussion of very bad burst mode errors.  If the
> receiver has not received the segments it requires and has not sent out an
> ACK for RTT*1.3 then the receiver needs to send another ACK pair.  Note
> this applies to the transmitter also in that if its Returned Transmit Token
> does not equal Last Transmit Token after the same RTT*1.3 it is obligated
> to send an ACK pair to the receiver to prompt it to restart.  Obviously
> RTT*1.3 is a long time on transcontinental or satellite links which is why
> 1/4 RTT for an ACK pair from the receiver as a keep alive is under
> consideration, the maximum length of time to cover the burst error without
> degrading efficiency too badly.
>
> In filling the outgoing ACKs with SACK blocks at the receiver, the list is
> maintained in the order oldest (smallest segment start) to the youngest.
> The list is queried three times when building the ACK group, first for all
> blocks that just changed and thus have the most critical information (ACK
> NEEDED = 2), then a scan for those blocks which already had their first ACK
> (ACK NEEDED = 1) and then for the blocks which have already been
> transmitted twice (ACK NEEDED = 0).  The ACK NEEDED count is then
> decremented.
>
> To make E-SACK work three lists must be maintained, one at the receiver
> and two at the transmitter.  The one in the receiver is identical in
> concept to the one in the original RFC with the addition of ACK NEEDED and
> the proviso that it be in oldest to youngest order.  At the transmitter an
> identical list is maintained built from the recovered SACK blocks.  When a
> changed Returned Transmit Token is received, the recovered SACK block list
> is used to construct a retransmit queue of all unacknowledged segments.
> Then starting at the transmit queue entry plus one derived from the
> Returned Transmit Token, and proceeding forward until all transmitted
> segment extents have been processed, entries are removed or modified in the
> new retransmit queue to compensate for segments sent after the time of the
> Returned Transmit Token.  The adjusted new transmit queue replaces the
> existing queue and the transmission process is started again starting at
> the first entry on the queue, not proceeding with new transmission until
> the queue is completed.  Please note that incoming SACK blocks must be
> checked against the retransmit queue in order to remove segments that have
> been subsequently correctly received.
>
> Noto Bene - This protocol is an update to RFC 2018.  It is not compatible
> with nor do I believe in the philosophy of RFC2883/RFC3708 as the whole
> purpose of this change is to eliminate duplicate segments and increase
> efficiency and reliability where the changes outlined in those RFCs degrade
> efficiency (especially by generating extra SACK blocks) without
> substantially improving anything.  Also as adopted in the RFC there is a
> major fallacy, it assumes that there can be only one SACK block with a
> status change where in reality, due to processing considerations, there can
> be two or even more blocks with changes before an ACK can be sent.
>
>
> Tony
>
> Anthony Sabatini
> 200 West 20th Street
> Apt. 1216
> New York, NY 10011
>
> Phone: (212) 867-7179
> Mobile: (917) 224-8388
>
>

---

From: Anthony Sabatini <[email-masked]>
Date: Fri, 20 Jul 2012 14:16:20 -0400

Matt -
 
First off I would like to thank you for your excellent work on RFC2018, the purpose of this update is not to diminish your work but rather extend and expand on it.  Without your lead I would never have had the impetus to extend my work from HDLC into the TCP domain.  Please understand that the first draft was a trial draft to toss around and get essential comments.  Also please understand that it was originally written as part of a thesis presentation on adapting token, state driven recovery to TCP, not as an RFC per se.
 
1) A problem with RFC2018 is that it provides no real information with respect to the receivers reassembly queue at the time the transmitter receives the acknowledgement.  The protocol presupposes conditions often not present in the real world, that the information transfer is near instantaneous and that a rather low number of messages can be in-flight i.e. 7 SACK blocks total combined in both directions (i.e. messages for which SACK blocks have not yet been received).  The RFC2018 DOES NOT send information about messages that were lost (nor can it with the implied requirement of packet fragmentation or out of order delivery), it can only say what it has seen.
 
2) On an active link SACK goes into the weeds whenever noise bursts affecting receipt of SACK blocks exceed approximately 100,000 bit times, a 10 ms noise burst at 10 mbps or 1 ms at 100 mbps causing a rollover of the active three SACK block window.  At that point SACK goes into timer based recovery. The problem with time based recovery is that timers must always be set to the maximum possible delay, destroying efficiency.  The purpose of this change is to take recovery from timer based to state based so that it is maximally responsive.
 
3) SACK presupposes a relatively stable link with a relatively low random packet drop.  Neither are true anymore and it is why you need only to look at RFC2883 to realize that SACK sends a lot of duplicate segments destroying efficiency.  I am simply trying to reduce that number.
 
4) SACK has an implicit "last character problem"; normally you would get multiple confirmation SACK blocks as additional messages arrive equal to the number of SACK blocks.  This is not true if the link goes idle where the next to last only has two acknowledgements and the last only has one.  If the last transmit segment is dropped and the link goes idle or the last ACK packet from the receiver is lost you are now into a condition where it takes a major link timeout to recover it.  The changes in the revised draft reduce the pssibility of that occurrence.
 
5) I admit the current draft does not properly express my views.  In the current RFC2018 we normally have three SACK blocks, in this version normally four.  What I was basically saying is that UNUSED SACK blocks should be filled with older, still not completed SACK blocks rather than transmit the same set of SACK blocks five, six or more times.  This will be clarified in the next revision.
 
6) Note that the argument has moved to whether we need to allow more that 16,000 messages to be in process during any particular second in the face of 10 Gbps links, proposal is on the table to expand that to 4,000,000.  Also there is a proposal on SACK block compression in process (RFC1072 was not wrong in concept only in implementation) so that we can include more segments.
 
I do appreciate your comments and feedback.
 
Tony 

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

Date: Thu, 19 Jul 2012 13:02:43 -0700
Subject: Re: [tcpm] TCP Error recovery and efficiency
From: [email-masked]
To: [email-masked]
CC: [email-masked]

I don't understand what problem you are trying to solve: As written 2018 provides the sender with perfect information about the state of the receivers reassembly queue (e.g. which data is still missing) as long as most ACKs are delivered, mostly in order.   The minimum cases which causes the sender to send duplicate data are timeouts (but see the errata against 2018), or fairly complicated patterns of sustained losses on both sides of the link.

In fact, if there is no loss or reordering on the return path, a single SACK block is sufficient to give the sender perfect information.

With classic TCP timestamps (not for PAWS) it is even possible to disambiguate between holes that were filled by ooo data or retransmissions.  Due to the TS echo rules for PAWS, it actually does less well.  I am not the expert here, but Richard Scheffenegger has explored this problem extensively.   But the ambiguity is whether congestion control undo is permitted, not which data is still needed at the receiver.

If you look at 2018, (and 2883) the first SACK block is described as MUST be the chronologically newest.  The rest of the option is described with SHOULDs, because we knew that SACK could theoretically be improved by dithering the rest of the SACK option across all past SACK blocks.   Such a scheme would make SACK work well with unreasonable levels of loss on the ACK path.  (e.g. the 2nd SACK block could alternate between the two most recent prior 1st blocks, the 3rd across all earlier blocks).

But now, would that really a feature for TCP to work well on the forward path, while the (low bandwidth) return path is being mauled by SACK?

Thanks,

--MM--

On Sun, Jul 15, 2012 at 12:59 PM, Anthony Sabatini <[email-masked]> wrote:

All -

Tony

Anthony Sabatini
200 West 20th Street
Apt. 1216
New York, NY 10011

Phone: (212) 867-7179
Mobile: (917) 224-8388

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 20 Jul 2012 21:20:28 +0000

Hi Tony,

I think you need to clarify more the issues you see in the current signaling of SACK; 2018 SACK gives the most complete view of the receiver state at the time when the ACK carrying the SACK was sent... I don't quite follow the argument around larger window links...

Ad 1)

Your point here seems to indicate that the receiver is supposed to extrapolate the (then future) state of the receiver at the time, when the sender (in your notion, transmitter) is receiving an ACK.. But to make that extrapolation, the receiver has to run a model of the path, which is much more complex in a packet switched network than on p2p links (over "simple" media). 

Also, in the real world of TCP/IP, one cannot know if a packet was lost or delayed; this is also a major differentiating factor to P2P links (HDLC, SDLC etc., where you seem to be coming from). Therefore, the receiver cannot deduce that Packet 1 was lost, once it has received Packet 2 (with these packet numbers encoded in the tokens). It can merely state that Packet 1 was either delayed (any may be received still), or lost - less information here than in a P2P link!

In accordance with the principles of TCP, though, the sender could make the deduction that if the 1st retransmission of packet 1 was not received by the time packet 3 - sent out after the retransmission of 1 - was confirmed on the receiving side, that a 2nd retransmission is in order. 

And this really is a undefined space so far (linux does some tricks that are not in the IETF specs, but in the spirit).

Your token scheme (making each packet uniquely identifiable) would also go a long way to enable this.

Ad 2)

Burst loss of the ACKs: True; but burst loss of ACKs of that severity has other implications in TCP, e.g. the ACK clock will fail (or SACK without PRR-RB/Laminar TCP will send out burst of new packets, very possibly making things worse).

As Matt mentioned in his reply, a receiver is free to dither the returned SACK blocks from the available SACK blocks. This could address this contingency to some point. But I figure it's not trivial to figure out an optimal dithering strategy - e.g. blocks could also be repeated with varying probability to indicate their "importance". As indicated earlier, you place a very high value at the oldest block, to facilitate some forward progress on the receiver side as soon as possible (and to reset the RTO timer?) Thus the oldest block could be included in a certain fraction of ACKs, overriding the current LIFO ordering scheme...

Ad 3)

I don't buy this one; you proposed to send ACKs multiple times over and over - clearly much less efficient than establishing reliability by sending the same SACK block at least 3 times (thus covering at least 2 consecutive ACK losses).

Ad 4)
See the rescue retransmission in RFC3517bis and draft-dukkipati-tcpm-tcp-loss-probe; but having a fast re-ACK timer (~ inter packet interval) on the receiver appears to be quicker and possibly more efficient (often, tx power < rx power on mobile devices; smaller packets don't use up too much bandwidth as simply resending the last packet after a ~RTO timer).

Ad 5)

> 5) I admit the current draft does not properly express
> my views.  In the current RFC2018 we normally have
> three SACK blocks, in this version normally four. 
> What I was basically saying is that UNUSED SACK blocks
> should be filled with older, still not completed SACK
> blocks rather than transmit the same set of SACK blocks
> five, six or more times.  This will be clarified in the
> next revision.

SACK usually has 4 too - it's just often deployed/enabled together with Timestamps that take away option space. A combined SACK+TS (SACK+token) option could yield 4 SACK block plus the two Tokens / Timestamps. (2 + 2x(4) + nx(4+4)).

In 2018, there are no unused SACK blocks - whenever the receiver has discontinuous data, it makes it into a SACK block until all available SACK blocks are used up... usually from most recently received to least recently received... And as Matt mentioned, a receiver is free to cycle periodically through all the discontinuous blocks except for the first SACK block (it's just not implemented today; 

The resiliency achieved by the redundant sending of SACK blocks is viewed to be sufficient. If you have data to the contrary, please share.

Richard Scheffenegger

From: [email-masked] [mailto:[email-masked]] On Behalf Of Anthony Sabatini
Sent: Freitag, 20. Juli 2012 20:16
To: [email-masked]
Cc: tcpm
Subject: Re: [tcpm] TCP Error recovery and efficiency

Matt -