Subject: [tcpm] Fwd: New Version Notification for draft-flach-tcpm-fec-00.txt

From: Yuchung Cheng <[email-masked]>
Date: Mon, 15 Jul 2013 14:49:13 -0700

Hi

We are proposing an outrageous idea to send parity data in TCP
packet to promote sub 1-RTT loss recovery. This requires a separate
sequence space which we aren't quite sure how to do this yet without
upsetting middle-boxes. More data can be found in our new paper
"Reducing Web Latency: the Virtue of Gentle Aggression" sigcomm 2013
http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/41217.pdf

Comments are very welcome. Linux patches release are under way.

---------- Forwarded message ----------
From:  <[email-masked]>
Date: Sun, Jul 14, 2013 at 4:59 PM
Subject: New Version Notification for draft-flach-tcpm-fec-00.txt
To: Tobias Flach <[email-masked]>, Nandita Dukkipati
<[email-masked]>, Yuchung Cheng <[email-masked]>, Barath
Raghavan <[email-masked]>

A new version of I-D, draft-flach-tcpm-fec-00.txt
has been successfully submitted by Tobias Flach and posted to the
IETF repository.

Filename:        draft-flach-tcpm-fec
Revision:        00
Title:           TCP Instant Recovery: Incorporating Forward Error
Correction in TCP
Creation date:   2013-07-15
Group:           Individual Submission
Number of pages: 15
URL:             http://www.ietf.org/internet-drafts/draft-flach-tcpm-fec-00.txt
Status:          http://datatracker.ietf.org/doc/draft-flach-tcpm-fec
Htmlized:        http://tools.ietf.org/html/draft-flach-tcpm-fec-00

Abstract:
   Ordinary TCP loss recovery takes at least one round-trip time and as
   such can increase application-perceived latency, especially for short
   flows such as Web transactions.  TCP Instant Recovery (TCP-IR) is an
   experimental algorithm that allows a receiving end to recover lost
   packets without retransmissions, thus potentially saving at least one
   full round-trip time compared to standard TCP.  TCP-IR achieves this
   by judiciously injecting encoded data segments within a TCP stream.
   This document describes the TCP-IR algorithm at the sending and
   receiving ends, along with the required protocol changes.

The IETF Secretariat

---

From: Joe Touch <[email-masked]>
Date: Mon, 15 Jul 2013 14:58:59 -0700

You might take a look at TCP Boston, which is a much more elegant FEC 
than just parity.

But what use is parity? If a packet is corrupted, most link layers will 
drop it anyway (esp. because you don't even know if the packet header is 
correct, thus whether you're sending it to the right connection).

Joe

On 7/15/2013 2:49 PM, Yuchung Cheng wrote:
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>

---

From: Tobias Flach <[email-masked]>
Date: Mon, 15 Jul 2013 20:49:32 -0400

There are indeed far more elegant and sophisticated coding schemes out
there than the XOR approach we used. TCP Boston as well as other published
approaches like "Network Coded TCP" (http://arxiv.org/abs/1212.2291) are
capable to mask losses better than XOR, but XOR has the advantage that it
is easy to implement and results in a relatively low computational
overhead. In addition, we do not limit our proposal to XOR, but rather use
it to demonstrate how TCP-IR works in general, and we can easily extend the
module to support other coding schemes in the future.

Regarding the second question: Regular payloads and parity data are not
mixed in the same packet. Parity data is sent separately which enables
immediate recovery if only one packet in the encoding range is lost. As
said, more sophisticated coding schemes might do better here, but our
experiments have shown that even simple XOR can improve latency a lot -
especially for short flows.

- Tobias

On Mon, Jul 15, 2013 at 5:58 PM, Joe Touch <[email-masked]> wrote:

> You might take a look at TCP Boston, which is a much more elegant FEC than
> just parity.
>
>> http://static.**googleusercontent.com/**external_content/untrusted_**
>> dlcp/research.google.com/en/**us/pubs/archive/41217.pdf<http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/41217.pdf>
>>
>> URL:             http://www.ietf.org/internet-**
>> drafts/draft-flach-tcpm-fec-**00.txt<http://www.ietf.org/internet-drafts/draft-flach-tcpm-fec-00.txt>
>> Status:          http://datatracker.ietf.org/**doc/draft-flach-tcpm-fec<http://datatracker.ietf.org/doc/draft-flach-tcpm-fec>
>> Htmlized:        http://tools.ietf.org/html/**draft-flach-tcpm-fec-00<http://tools.ietf.org/html/draft-flach-tcpm-fec-00>
>>
>>
>> Abstract:
>> ______________________________**_________________
>> tcpm mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/**listinfo/tcpm<https://www.ietf.org/mailman/listinfo/tcpm>
>>
>>  ______________________________**_________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/tcpm<https://www.ietf.org/mailman/listinfo/tcpm>
>

---

From: Joe Touch <[email-masked]>
Date: Mon, 15 Jul 2013 18:32:23 -0700

Well, FEC-style redundant transmission is fine so long as you subtract 
those XOR packets from your congestion window. I.e., either you send 10 
data packets, or 5 data and 5 XOR.

If you're just pumping data into the net in the hope that something 
makes it, we've seen that before too - Roadrunner tried it 15 years ago. 
We all know it works, but I hope we all know why it's not a good idea.

BTW, these sorts of tricks are a LOT older than 1-2 years.

Joe

On 7/15/2013 5:49 PM, Tobias Flach wrote:
> there than the XOR approach we used. TCP Boston as well as other
> published approaches like "Network Coded TCP"
> (http://arxiv.org/abs/1212.2291) are capable to mask losses better than
> XOR, but XOR has the advantage that it is easy to implement and results
> in a relatively low computational overhead. In addition, we do not limit
> our proposal to XOR, but rather use it to demonstrate how TCP-IR works
> in general, and we can easily extend the module to support other coding
> schemes in the future.
>
> On Mon, Jul 15, 2013 at 5:58 PM, Joe Touch <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     You might take a look at TCP Boston, which is a much more elegant
>     FEC than just parity.
>
>     But what use is parity? If a packet is corrupted, most link layers
>     will drop it anyway (esp. because you don't even know if the packet
>     header is correct, thus whether you're sending it to the right
>     connection).
>
>     Joe
>
>
>         http://static.__googleusercontent.com/__external_content/untrusted___dlcp/research.google.com/en/__us/pubs/archive/41217.pdf
>         <http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/41217.pdf>
>
>         From:  <[email-masked] <mailto:[email-masked]>>
>         To: Tobias Flach <[email-masked] <mailto:[email-masked]>>, Nandita
>         Dukkipati
>         <[email-masked] <mailto:[email-masked]>>, Yuchung
>         Cheng <[email-masked] <mailto:[email-masked]>>, Barath
>         Raghavan <[email-masked] <mailto:[email-masked]>>
>
>
>
>         URL:
>         http://www.ietf.org/internet-__drafts/draft-flach-tcpm-fec-__00.txt
>         <http://www.ietf.org/internet-drafts/draft-flach-tcpm-fec-00.txt>
>         Status: http://datatracker.ietf.org/__doc/draft-flach-tcpm-fec
>         <http://datatracker.ietf.org/doc/draft-flach-tcpm-fec>
>         Htmlized: http://tools.ietf.org/html/__draft-flach-tcpm-fec-00
>         <http://tools.ietf.org/html/draft-flach-tcpm-fec-00>
>
>
>         Abstract:
>         _________________________________________________
>         tcpm mailing list
>         [email-masked] <mailto:[email-masked]>
>         https://www.ietf.org/mailman/__listinfo/tcpm
>         <https://www.ietf.org/mailman/listinfo/tcpm>
>
>     _________________________________________________
>     tcpm mailing list
>     [email-masked] <mailto:[email-masked]>
>     https://www.ietf.org/mailman/__listinfo/tcpm
>     <https://www.ietf.org/mailman/listinfo/tcpm>
>
>

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Tue, 16 Jul 2013 14:29:52 +0000

Hi,

After a quick scan through the draft, some initial questions...

>   1.  Periodically in every round-trip time, a TCP-IR sender places the
>   XOR of newly transmitted segments into a single MSS-length checksum
>   packet.  The XOR is only computed for new segments not previously
>   included in checksums.

Is it correct that there are more than one XOR packets per RTT if there are more than 8 or 16 outstanding packets, i.e., CWND>8 or 16?

>   3.  The encoded XOR packet uses the same sequence number as the first
>   segment it encodes.  The encoded packet carries a flag in the TCP-IR
>   option signaling that the payload is encoded.  A receiver uses the
>   flag to disambiguate an encoded packet from a regular
>   (re)transmission, since both segments carry the same sequence number.
>   The option also includes the number of bytes that the payload
>   encodes.

So, on the wire there are different bytes for the same sequence number, right?

I recall lengthy discussions on that in the MPTCP WG.

BTW: Have you thought of using MPTCP, i.e., sending the XOR packets on a separate MPTCP subflow between the same IP addresses? This could be an interesting application of MPTCP. MPTCP already allows today sending packets redundantly on two subflows - adding coding to MPTCP seems doable.

>   4.  For the purpose of recovering lost segments, a receiver buffers
>   the last fifteen in-order MSS blocks that it ACKed, even if the
>   application layer has already consumed these blocks.  Because an
>   encoded packet is the XOR of at most sixteen MSS segments, the
>   receiver can recover any single lost packet by computing the XOR of
>   the encoded payload and the buffered data in the encoding range.

What about TCP flow control? Are those 15 packets reduced from the advertised RWND?

>   6.  TCP-IR does not circumvent congestion control.  If the receiver
>   [...]

As already pointed out by Joe, not circumventing congestion control implies to me that XOR packets are substracted from CWND. I wonder why this is not explicitly mentioned in the draft. Since packet loss is mainly due to congestion in most parts of the Internet, increasing the transmission rate on a congested link beyond what is allowed by congestion control is a no-go.

>   TCP-IR adds a short delay in the transmission of encoded packets to
>   the reduce the probability of losing both the original transmission
>   and the encoded packet in the same loss burst.

So, the recovery delay is actually not too different to TLP?

>   The last 15 ACKed MSS length segments remain in the buffer, even if
>   the application layer has already consumed these segments.  Segments
>   received out-of-order are already buffered by default and cannot be
>   consumed by the application layer.  Since a single TCP-IR packet
>   encodes at most 8 (interleaved XOR) or 16 (basic XOR) MSS length
>   segments, any single segment loss (up to MSS length) in the encoding
>   range can be recovered by the decoder.

With this scheme, can a malicious sender attack a receiver so that it runs out of buffer space? For instance, what does a receiver do if a sender sends only one out of 16 packets?

>   Some problems caused by middlebox interference (and their solutions
>   in TCP-IR) are not discussed in the current version of this draft:
>
>   o  Rewriting of the acknowledgement number if the acknowledged
>      segment was not observed by the middlebox.  With TCP-IR this can
>      occur after recovering a lost segment.  This issue can be
>      circumvented by retransmitting the recovered segment, even though
>      it is not needed by the other endpoint anymore.  This plugs the
>      "sequence hole" in the state of the middlebox.
>   o  Rewriting payloads of previously seen segments.
>   o  Packet coalescing and splitting.

Out of my head, these were major design constraints for MPTCP. This is why I wonder if transfering the XOR packets over a separate MPTCP subflow could maybe help.

>   We conducted two kinds of experiments.  The first was in an emulated
>   setting using loss patterns similar to those observed in our
>   measurement of real traffic.  We used the netem module to emulate a
>   200 ms RTT and both random and correlated loss rates of 2%. TCP-IR
>   reduced the latency for short transfers in lossy environments by 28%
>   in the 90th percentile.  The benefits diminish as the minimum number

Could you comment on the transmission overhead or goodput?

At first sight, the amount of sent bytes is increased by at least 1/16 = 6% (or 1/8 = 12% with interleaving) even if a connection faces no congestion at all. Plus the per-packet overhead of the TCP option and the consumption of scarce SYN bytes.

Of course, one could reduce the overhead by selectively activating the FEC scheme only if a link is congested. But this still means that the goodput on a congested link is reduced.

>   of RTTs necessary to complete the transaction increases (due to the
>   message size) because the time to recover from losses no longer
>   dominates the overall transmission time.  TCP-IR is better suited for
>   small transfers common in today's Web.

Really? If a sender only has, say, 4 KB to send, i.e., about 3 packets for MTU 1500 byte, sending an additional coded packet results in an overhead of about 25%, right?

And if an app only transfers a single byte, is the overhead then MSS / 1byte = 150000%?

With such an overhead, is TCP-IR really well-suited for small transfers?

>   The two Options for TCP-IR used during negotiation and subsequently
>   in every packet of the connection require IANA allocate one value
>   from the TCP option Kind namespace.  Experimentation prior to the
>   allocation SHOULD follow [EXPOPT] and use experimental option kind
>   254 and two magic bytes 0xDC60, and migrate to the new option after
>   the allocation accordingly.

If experiments are performed over Internet paths, a registration at http://www.iana.org/assignments/tcp-parameters/tcp-parameters.xhtml#tcp-exids would be highly welcome.

Sorry if I missed something in my first reading.

Thanks

Michael

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Yuchung Cheng
> Sent: Monday, July 15, 2013 11:49 PM
> To: [email-masked] Extensions
> Subject: [tcpm] Fwd: New Version Notification for 
> draft-flach-tcpm-fec-00.txt
> 
> Hi
> 
> We are proposing an outrageous idea to send parity data in 
> TCP packet to promote sub 1-RTT loss recovery. This requires 
> a separate sequence space which we aren't quite sure how to 
> do this yet without upsetting middle-boxes. More data can be 
> found in our new paper "Reducing Web Latency: the Virtue of 
> Gentle Aggression" sigcomm 2013 
> http://static.googleusercontent.com/external_content/untrusted
> _dlcp/research.google.com/en/us/pubs/archive/41217.pdf
> 
> <[email-masked]>, Yuchung Cheng <[email-masked]>, 
> Barath Raghavan <[email-masked]>
> 
> 
> 
> A new version of I-D, draft-flach-tcpm-fec-00.txt has been 
> successfully submitted by Tobias Flach and posted to the IETF 
> repository.
> 
> http://www.ietf.org/internet-drafts/draft-flach-tcpm-fec-00.txt

---

From: Tobias Flach <[email-masked]>
Date: Wed, 17 Jul 2013 10:03:38 -0400

I agree that if we introduce a significant amount of redundant
transmissions, these packets need to be accounted for by the congestion
window. However, the way we designed our algorithm, the amount of
redundancy is relatively small (usually 16 data packets are encoded by 1
XOR packet), which is why in our prototype the XOR packets are transmitted
outside of the window.

And you are right that these schemes in general are pretty old, but to our
knowledge no one has actually thought about the protocol level details of
incorporating FEC into TCP before, including all the trouble middleboxes
are causing.

- Tobias

On Mon, Jul 15, 2013 at 9:32 PM, Joe Touch <[email-masked]> wrote:

> If you're just pumping data into the net in the hope that something makes
> it, we've seen that before too - Roadrunner tried it 15 years ago. We all
> know it works, but I hope we all know why it's not a good idea.
>
>> (http://arxiv.org/abs/1212.**2291 <http://arxiv.org/abs/1212.2291>) are
>> capable to mask losses better than
>>         http://static.__googleusercont**ent.com/__external_content/**
>> untrusted___dlcp/research.**google.com/en/__us/pubs/**archive/41217.pdf<http://googleusercontent.com/__external_content/untrusted___dlcp/research.google.com/en/__us/pubs/archive/41217.pdf>
>>
>>         <http://static.**googleusercontent.com/**
>> external_content/untrusted_**dlcp/research.google.com/en/**
>> us/pubs/archive/41217.pdf<http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/41217.pdf>
>> >
>>
>>         From:  <[email-masked] <mailto:internet-drafts@ietf.**
>> org <[email-masked]>>>
>>         http://www.ietf.org/internet-_**_drafts/draft-flach-tcpm-fec-_**
>> _00.txt<http://www.ietf.org/internet-__drafts/draft-flach-tcpm-fec-__00.txt>
>>         <http://www.ietf.org/internet-**drafts/draft-flach-tcpm-fec-**
>> 00.txt <http://www.ietf.org/internet-drafts/draft-flach-tcpm-fec-00.txt>>
>>         Status: http://datatracker.ietf.org/__**doc/draft-flach-tcpm-fec<http://datatracker.ietf.org/__doc/draft-flach-tcpm-fec>
>>         <http://datatracker.ietf.org/**doc/draft-flach-tcpm-fec<http://datatracker.ietf.org/doc/draft-flach-tcpm-fec>
>> >
>>         Htmlized: http://tools.ietf.org/html/__**draft-flach-tcpm-fec-00<http://tools.ietf.org/html/__draft-flach-tcpm-fec-00>
>>
>>         <http://tools.ietf.org/html/**draft-flach-tcpm-fec-00<http://tools.ietf.org/html/draft-flach-tcpm-fec-00>
>> >
>>
>>
>>         Abstract:
>>         ______________________________**___________________
>>         tcpm mailing list
>>         https://www.ietf.org/mailman/_**_listinfo/tcpm<https://www.ietf.org/mailman/__listinfo/tcpm>
>>         <https://www.ietf.org/mailman/**listinfo/tcpm<https://www.ietf.org/mailman/listinfo/tcpm>
>> >
>>
>>     ______________________________**___________________
>>     tcpm mailing list
>>     https://www.ietf.org/mailman/_**_listinfo/tcpm<https://www.ietf.org/mailman/__listinfo/tcpm>
>>     <https://www.ietf.org/mailman/**listinfo/tcpm<https://www.ietf.org/mailman/listinfo/tcpm>
>> >
>>
>>
>>

---

From: Tobias Flach <[email-masked]>
Date: Wed, 17 Jul 2013 10:57:03 -0400

Thanks for your comments.
Responses inline:

On Tue, Jul 16, 2013 at 10:29 AM, Scharf, Michael (Michael) <
[email-masked]> wrote:

> Is it correct that there are more than one XOR packets per RTT if there
> are more than 8 or 16 outstanding packets, i.e., CWND>8 or 16?
>

That is correct. If there are more than 8 (or 16) unencoded packets in the
queue when the timer fires, multiple XOR packets are generated.
Additionally, if new packets are transmitted after the timer fired, the
timer is armed again (set to RTT/4), so for a sender transmitting data
continuously the timer would fire up to four times per RTT.

> So, on the wire there are different bytes for the same sequence number,
Yes.

> BTW: Have you thought of using MPTCP, i.e., sending the XOR packets on a
> separate MPTCP subflow between the same IP addresses? This could be an
> interesting application of MPTCP. MPTCP already allows today sending
> packets redundantly on two subflows - adding coding to MPTCP seems doable.
>

We thought about MPTCP in our initial design phase but our take was that
MPTCP has too much complexity for our purpose. The question we tried to
answer was: How would we augment TCP in the simplest possible way to inject
FEC packets within the data stream. Once MPTCP implementations are more
mature and widely deployed we certainly have to revisit this question.

> What about TCP flow control? Are those 15 packets reduced from the

Yes. In the draft and prototype we do not mention this yet, but will
include it in future revisions.

> As already pointed out by Joe, not circumventing congestion control
> implies to me that XOR packets are substracted from CWND. I wonder why this
> is not explicitly mentioned in the draft. Since packet loss is mainly due
> to congestion in most parts of the Internet, increasing the transmission
> rate on a congested link beyond what is allowed by congestion control is a
> no-go.
>

By not circumventing CC, we mean reducing cwnd in the event that a loss is
transparently recovered at the receiver using FEC segments.
The next version of the draft will include a clarification on whether FEC
segments should be within or outside of cwnd. Both are viable options.

> So, the recovery delay is actually not too different to TLP?

The delay added for FEC segments is only a 1/4 RTT. While TLP waits for 2
RTTs before sending a new or retransmitted segment. Besides that, you are
right that there is some similarity between the two schemes. TLP could be
considered an additional encoding type, which only "encodes" the last
packet in flight.

> With this scheme, can a malicious sender attack a receiver so that it runs
> out of buffer space? For instance, what does a receiver do if a sender
> sends only one out of 16 packets?
>

I might not follow this correctly, but XOR packets are always transmitted
after the original data segments, and right now they are discarded if there
is not enough data buffered data at the receiver to recover segments. So if
a sender sends 1 out of 16 packets, and then the XOR for these 16 packets,
the receiver will not recover any data, and respond with an ACK having the
R_FAIL flag set. Does that answer your question?

> Out of my head, these were major design constraints for MPTCP. This is why
> I wonder if transfering the XOR packets over a separate MPTCP subflow could
> maybe help.
>

I am sure it will work if FEC segments are transferred over an MPTCP
subflow. The downside is this is not immediately deployable. Therefore, we
are interested in investigating extensions to TCP to accommodate simple XOR
segments.

> At first sight, the amount of sent bytes is increased by at least 1/16 =
> 6% (or 1/8 = 12% with interleaving) even if a connection faces no
> congestion at all. Plus the per-packet overhead of the TCP option and the
> consumption of scarce SYN bytes.
>
> Of course, one could reduce the overhead by selectively activating the FEC
> scheme only if a link is congested. But this still means that the goodput
> on a congested link is reduced.
>

That is correct. For longer flows, or flows which usually don't see
congestion, FEC is only causing performance degradation. We don't envision
that every flow uses this, but rather have it as a tuning knob for
scenarios where a reduction in throughput is acceptable if that reduces
overall latency (by reducing the probability of an RTO).

> Really? If a sender only has, say, 4 KB to send, i.e., about 3 packets for
> MTU 1500 byte, sending an additional coded packet results in an overhead of
> about 25%, right?

Yes. The key is that a loss of the third packet can take a very long time
to recover from. With TLP we need to wait at least 2 RTTs thus completing
the transmission after 3 RTTs. With TCP-IR we are done after 1.25 RTTs. Now
it is up to the user whether avoiding a 25% overhead or reducing latency by
58% in the event of a tail loss is more important.

> And if an app only transfers a single byte, is the overhead then MSS /

We have not specified this yet, but if there is less than MSS data to
encode, the encoded packet does not need to use padding to fill up unused
space. So in this particular case the encoding range would be 1, and the
encoded packet would carry a 1-byte payload. Overhead can therefore be 100%
in the worst case.

> If experiments are performed over Internet paths, a registration at
> http://www.iana.org/assignments/tcp-parameters/tcp-parameters.xhtml#tcp-exidswould be highly welcome.
>

Thanks for the pointer!

- Tobias

---

From: Joe Touch <[email-masked]>
Date: Wed, 17 Jul 2013 09:32:38 -0700

On 7/17/2013 7:03 AM, Tobias Flach wrote:
> XOR packet), which is why in our prototype the XOR packets are
> transmitted outside of the window.

There's no rule in TCP congestion control that says "oh, it's OK to send 
one more packet if that's a small increase vs. what CWND says".

I appreciate that this extension considers that extra packet "not new 
information", but to the rest of the network it's one extra packet.

> And you are right that these schemes in general are pretty old, but to
> our knowledge no one has actually thought about the protocol level
> details of incorporating FEC into TCP before,

That's incorrect.

> including all the trouble middleboxes are causing.

I haven't seen anything in TCP Boston or other similar approaches that a 
middlebox would interfere with.

Joe

>
> - Tobias
>
> On Mon, Jul 15, 2013 at 9:32 PM, Joe Touch <[email-masked]
>     Well, FEC-style redundant transmission is fine so long as you
>     subtract those XOR packets from your congestion window. I.e., either
>     you send 10 data packets, or 5 data and 5 XOR.
>
>     makes it, we've seen that before too - Roadrunner tried it 15 years
>     ago. We all know it works, but I hope we all know why it's not a
>     good idea.
>
>         (http://arxiv.org/abs/1212.__2291
>         <http://arxiv.org/abs/1212.2291>) are capable to mask losses
>         better than
>         <mailto:[email-masked]>
>         <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>
>         http://static.__googleusercont__ent.com/__external_content/__untrusted___dlcp/research.__google.com/en/__us/pubs/__archive/41217.pdf
>         <http://googleusercontent.com/__external_content/untrusted___dlcp/research.google.com/en/__us/pubs/archive/41217.pdf>
>
>
>         <http://static.__googleusercontent.com/__external_content/untrusted___dlcp/research.google.com/en/__us/pubs/archive/41217.pdf
>         <http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/41217.pdf>>
>
>                  From:  <[email-masked]
>         <mailto:[email-masked]>
>         <mailto:[email-masked]
>         <mailto:[email-masked]>>>
>                  To: Tobias Flach <[email-masked] <mailto:[email-masked]>
>         <mailto:[email-masked] <mailto:[email-masked]>>>, Nandita
>                  Dukkipati
>                  <[email-masked] <mailto:[email-masked]>
>         <mailto:[email-masked] <mailto:[email-masked]>>>, Yuchung
>                  Cheng <[email-masked] <mailto:[email-masked]>
>         <mailto:[email-masked] <mailto:[email-masked]>>>, Barath
>                  Raghavan <[email-masked] <mailto:[email-masked]>
>         <mailto:[email-masked] <mailto:[email-masked]>>>
>
>
>
>         http://www.ietf.org/internet-____drafts/draft-flach-tcpm-fec-____00.txt
>         <http://www.ietf.org/internet-__drafts/draft-flach-tcpm-fec-__00.txt>
>
>         <http://www.ietf.org/internet-__drafts/draft-flach-tcpm-fec-__00.txt
>         <http://www.ietf.org/internet-drafts/draft-flach-tcpm-fec-00.txt>>
>                  Status:
>         http://datatracker.ietf.org/____doc/draft-flach-tcpm-fec
>         <http://datatracker.ietf.org/__doc/draft-flach-tcpm-fec>
>                  <http://datatracker.ietf.org/__doc/draft-flach-tcpm-fec
>         <http://datatracker.ietf.org/doc/draft-flach-tcpm-fec>>
>                  Htmlized:
>         http://tools.ietf.org/html/____draft-flach-tcpm-fec-00
>         <http://tools.ietf.org/html/__draft-flach-tcpm-fec-00>
>
>                  <http://tools.ietf.org/html/__draft-flach-tcpm-fec-00
>         <http://tools.ietf.org/html/draft-flach-tcpm-fec-00>>
>
>
>                  Abstract:
>                       Ordinary TCP loss recovery takes at least one
>         round-trip
>                  time and as
>                       such can increase application-perceived latency,
>         especially
>                  for short
>                       packets without retransmissions, thus potentially
>         saving at
>                  least one
>                       by judiciously injecting encoded data segments
>         within a TCP
>                  stream.
>                  ___________________________________________________
>                  tcpm mailing list
>         [email-masked] <mailto:[email-masked]> <mailto:[email-masked]
>         <mailto:[email-masked]>>
>         https://www.ietf.org/mailman/____listinfo/tcpm
>         <https://www.ietf.org/mailman/__listinfo/tcpm>
>                  <https://www.ietf.org/mailman/__listinfo/tcpm
>         <https://www.ietf.org/mailman/listinfo/tcpm>>
>
>              ___________________________________________________
>              tcpm mailing list
>         [email-masked] <mailto:[email-masked]> <mailto:[email-masked]
>         <mailto:[email-masked]>>
>         https://www.ietf.org/mailman/____listinfo/tcpm
>         <https://www.ietf.org/mailman/__listinfo/tcpm>
>              <https://www.ietf.org/mailman/__listinfo/tcpm
>         <https://www.ietf.org/mailman/listinfo/tcpm>>
>
>
>

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 17 Jul 2013 17:05:47 -0700

On Wed, Jul 17, 2013 at 9:32 AM, Joe Touch <[email-masked]> wrote:
> There's no rule in TCP congestion control that says "oh, it's OK to send one
> more packet if that's a small increase vs. what CWND says".
>
Good point. We'll reconsider that.

>> details of incorporating FEC into TCP before,
I think what Tobias meant was there were no real implementation of FEC
in TCP itself.
There are many designs of similar sort (e.g. boston), but we are not
aware of any publicly accessible real stack

> middlebox would interfere with.
This calls for more information to compare other works in the mtg (and
in the draft).

>>                       flows such as Web transactions.  TCP Instant
>> Recovery
>>                  (TCP-IR) is an
>>                       experimental algorithm that allows a receiving end
>> to
>>                  recover lost
>>                       full round-trip time compared to standard TCP.
>> TCP-IR
>>                  achieves this

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 18 Jul 2013 20:14:41 +0000

Hi Nandita,

> Thanks for your comments, Richard. do you mind if I cc the list?

Not really, if you think they are valuable :)

>> Why use a ECN-like handshake for the recovery signal? This 
>> limits your reactions to one bit per RTT, but a RTT could 
>> cover many FEC "episodes" (consecutive segments all covered 
>> by a single FEC).
> 
> The analogy to ECN's mechanism is only in the context of 
> sender reducing congestion window just once per RTT, for 
> segments recovered silently at the receiver.

I understand. My context was in the area of adaptive FEC episodes... Perhaps an example helps:

Say the window is 12(+3) segments [as I believe Joe has a very valid point with the FEC segments need to be accounted for against CWND], and the FEC episode is 4 segments. With a single handshake-like mechanism, the sender will not know if each of the three in-flight FEC episodes had to be recovered, or only the first... Of course, the CC reaction will be identical (just like having experienced one, two or three losses in the same window - all leading to a single CC reaction). But for an adaptive FEC episode, you don't have a good signal to decrease, or increase the FEC episode length. I.e. if only one of the three FEC episodes had to be recovered, a three-time larger FEC episode would be just as good (or a slight increase in the current one would have done), reducing the relative overhead from, say, 4+1 to 6+1 or 8+1; in the opposite case, where each episode had to be recovered, a decrease in the episode length would be advisable to maintain the FEC properties...

In that scenario, your current handshake mechanism seems to fail to deliver a good signal to differentiate between these cases. 

Of course, if the FEC episode length (do you have a name for that) is fixed (socket option) and not dynamic (even though the draft seems to allow for that), you wouldn't need a more fine-grained feedback...

Richard Scheffenegger

From: Nandita Dukkipati [mailto:[email-masked]] 
Sent: Mittwoch, 17. Juli 2013 21:13
To: Scheffenegger, Richard
Cc: Tobias Flach
Subject: Re: [tcpm] Fwd: New Version Notification for draft-flach-tcpm-fec-00.txt

Thanks for your comments, Richard. do you mind if I cc the list?

> On Tue, Jul 16, 2013 at 6:40 AM, Scheffenegger, Richard <[email-masked]> wrote:
> Hi Tobias, Nandita,
 
> Two observations:
> 
> Why use a ECN-like handshake for the recovery signal? This limits your reactions to one bit per RTT, but a RTT could cover many FEC "episodes" (consecutive segments all covered by a single FEC).

The analogy to ECN's mechanism is only in the context of sender reducing congestion window just once per RTT, for segments recovered silently at the receiver.

> I'm wondering, if a unilateral feedback like we propose in AccECN wouldn't yield more informantion, ie. to let the sender reduce the FEC episodes  before an actual R_FAIL occurs (covering less than 16 segments per FEC). You'd need a counter of some width for this, but as it would count up by one only once per FEC episode (1/1 to 1/16 segments), I would think a small number of bits (4-6) would be sufficient.

What you are proposing makes sense to me. While our focus for the first cut was to come up with the simplest design that achieves most of the performance benefits, extensions such as what you propose should certainly be on the table. I think the key is to weigh in the complexity versus the benefit...

> Second, you state that FEC has to be disabled when MSS changes.. But you don't explicitly state, how to do this (apparently, the FEC option would still need to be sent, but no FEC packets anymore). But is this really necessary on shrinking MSS?  I can see, that supporting increases in MSS would be difficult to support (but MSS shouldn't be growing after 3WHS), but for a shrinking MSS the effect would be the same as sending a couple non-MSS sized packets, that are FEC-covered. AS you cann't assume that all (but the last) segment is MSS sized, and padding the payload with zero up to MSS size is mentioned for smaller segments, why not have this on shrinking MSS too - keep the padding, but expand this to FEC segments as well. Of course, this is easy with XOR encoding, other encoding schemes might not work so well.

Nice! I like this idea of handling the shrinking MSS - should include in the next draft version.

> Finally, I have mentioned this earlier, we (NetApp) might want to have our RAID-DP scheme in there as well. It does have a few drawbacks operationally and functionally (larger FEC episode - longer latency until recovery; functionally - only prime-1 FEC episodes can natively be supported (formally, there can be "unsent" "padding" segments, to arrive at FEC episodes of length prime-1 though). 
>  
> In that light, it might be interesting to dynamically switch between encodings (non-interleaved xor, interleaved xor, double-xor), just as the sender is free to choose the FEC episode length dynamically.

The way it stands now is the encoding scheme negotiation is done in 3WHS, and this is stuck with for the rest of the connection. But if the encoding type is carried in the option on every segment, I think it's feasible to switch between encodings during the connection course.

> BTW: are overlapping FECs (up to the limit of 16 segments) allowed? Ie, send one FEC covering 1-4 as the 5th packet; 1-8 as the 10th packet, 1-16 as the 20th packet? Just asking because I have recently read a paper showing such overlapped FEC schemes to subsequently cover more and more data.

Yes, the current design allows this. Although we haven't actually tried this in our implementation.

Nandita

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Thu, 18 Jul 2013 20:24:28 +0000

Hi Tobias,

> Is it correct that there are more than one XOR packets per
> RTT if there are more than 8 or 16 outstanding packets,
> i.e., CWND>8 or 16?
>
> That is correct. If there are more than 8 (or 16) unencoded
> packets in the queue when the timer fires, multiple XOR packets
> are generated. Additionally, if new packets are transmitted after
> the timer fired, the timer is armed again (set to RTT/4), so for
> a sender transmitting data continuously the timer would fire up
> to four times per RTT.

So, you are ONLY sending with the RTT/4 timer? Wouldn't it be more useful to send the FEC segments immediately following the segments that are covered by it?

1 2 3 4 Xa 5 6 7 [pause] Xb

Vs 

1 2 3 4 5 6 7 [pause] Xa Xb

(FEC episode of 4; as the client only captures up to 16 segment - i assume of the first episode that cann't be recovered? - for larger windows, where a whole bunch of XOR segment will get sent out at the RTT/4 timer, most of them will be pretty useless, even if they could theoretically could have recovered some loss... Or am I getting something wrong here?

Best regards,

Richard Scheffenegger

---

From: Tobias Flach <[email-masked]>
Date: Thu, 18 Jul 2013 17:26:52 -0400

Right now FEC packets are only transmitted when the timer fires but your
proposal sounds interesting. As long as there is more outstanding data
which would be transmitted right after an FEC packet, it might be okay to
transmit the FEC packet immediately. And we would still delay if there is
no more data to send, e.g.

1 2 3 4 Xa 5 6 7 8 [pause] Xb

The only disadvantage I see is that having FEC packets in the middle of the
burst, is that the burst size increases, which might be okay.

Regarding your second question, let's use the example above. If we set the
maximum encoding range to 4, the receiver only needs to keep the last 3
in-order packets buffered.

Examples (* denotes loss of the packet):
* 2 3 4 Xa --> 1 can be recovered, because 2 - 4 remained in the OOO queue
1 2 3 * Xa --> 4 can be recovered, because 1 - 3 remained in the in-order
queue (because they are the last 3 in-order packets)
1 2 3 * 5 6 7 * Xa Xb --> 4 can be recovered by Xa, because packets 1 - 3
are the last three 3 in-order packets buffered, 8 can be recovered by Xb
because 5 - 7 are in the OOO queue.
1 2 * * 5 6 7 * Xa Xb --> 3 and 4 cannot be recovered by Xa, but 8 can
still be recovered and goes into the OOO queue.

Any FEC packet which would require earlier segments for a recovery, is
actually only encoding packets which have already been received.
Does this answer your question?

- Tobias

On Thu, Jul 18, 2013 at 4:24 PM, Scheffenegger, Richard <[email-masked]>wrote:

> So, you are ONLY sending with the RTT/4 timer? Wouldn't it be more useful
> to send the FEC segments immediately following the segments that are
> covered by it?
>
> (FEC episode of 4; as the client only captures up to 16 segment - i assume
> of the first episode that cann't be recovered? - for larger windows, where
> a whole bunch of XOR segment will get sent out at the RTT/4 timer, most of
> them will be pretty useless, even if they could theoretically could have
> recovered some loss... Or am I getting something wrong here?
>
> Best regards,
>
>
> Richard Scheffenegger
>
>
>

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 19 Jul 2013 08:57:00 +0000

Hi Tobias,

> The only disadvantage I see is that having FEC packets 
> in the middle of the burst, is that the burst size 
> increases, which might be okay.

True, with the relative probabilities which packets get dropped in a burst, you want to unmangle them; with TSO, you probably want to send the FEC segment at the beginning of the next TSO burst (or actually in between, since you need individual TCP options for each segment anyway). 

And again, FEC segments need to account against CWND. I consider a (useful) 6.25% (16:1) to 50% (2:1) increase in traffic volume not insignificant that TCP CC should not apply to these segments. 

But again, the receivers FEC queue will need to hold on to the full window of segments. I made myself not clear enough in the examples, if the OOO queue is also only 4 deep (not 16):

> 1 2 3 * 5 6 7 * Xa Xb --> 4 can be recovered by Xa, 
> because packets 1 - 3 are the last three 3 in-order 
> packets buffered, 8 can be recovered by Xb because 
> 5 - 7 are in the OOO queue.

Only 4 can be recovered; not all (most) stacks are segment oriented - this appears to be a silent assumption in your draft that should be made explicit (or have I missed that part?)...

Best regards,

Richard Scheffenegger

From: [email-masked] [mailto:[email-masked]] On Behalf Of Tobias Flach
Sent: Donnerstag, 18. Juli 2013 23:27
To: Scheffenegger, Richard
Cc: [email-masked] Extensions
Subject: Re: [tcpm] Fwd: New Version Notification for draft-flach-tcpm-fec-00.txt

Right now FEC packets are only transmitted when the timer fires but your proposal sounds interesting. As long as there is more outstanding data which would be transmitted right after an FEC packet, it might be okay to transmit the FEC packet immediately. And we would still delay if there is no more data to send, e.g.

The only disadvantage I see is that having FEC packets in the middle of the burst, is that the burst size increases, which might be okay.

Regarding your second question, let's use the example above. If we set the maximum encoding range to 4, the receiver only needs to keep the last 3 in-order packets buffered.

Examples (* denotes loss of the packet):
* 2 3 4 Xa --> 1 can be recovered, because 2 - 4 remained in the OOO queue
1 2 3 * Xa --> 4 can be recovered, because 1 - 3 remained in the in-order queue (because they are the last 3 in-order packets)
1 2 3 * 5 6 7 * Xa Xb --> 4 can be recovered by Xa, because packets 1 - 3 are the last three 3 in-order packets buffered, 8 can be recovered by Xb because 5 - 7 are in the OOO queue.
1 2 * * 5 6 7 * Xa Xb --> 3 and 4 cannot be recovered by Xa, but 8 can still be recovered and goes into the OOO queue.

Any FEC packet which would require earlier segments for a recovery, is actually only encoding packets which have already been received.
Does this answer your question?

- Tobias

On Thu, Jul 18, 2013 at 4:24 PM, Scheffenegger, Richard <[email-masked]> wrote:
Hi Tobias,

Vs

Best regards,

Richard Scheffenegger

---

From: Yuchung Cheng <[email-masked]>
Date: Fri, 19 Jul 2013 08:49:29 -0700

> But again, the receivers FEC queue will need to hold on to the full window of segments. I made myself not clear enough in the examples, if the OOO queue is also only 4 deep (not 16):
why is OOO queue max length limited to 4? FECs are accounted in the
receiver buffer autotuning, i.e., the sender won't send us FEC packet
unless the receiver told him it can take that.

> Only 4 can be recovered; not all (most) stacks are segment oriented - this appears to be a silent assumption in your draft that should be made explicit (or have I missed that part?)...

I am not sure what's a segmented oriented stack. are you referring to
segment or byte-based congestion control?