5 ms·

Forward error correction in QUIC

62 points by jsnell 11y ago

muhic 11y ago
It is worth noting that this document reads more like a first draft, in fact the document title is 'QUIC FEC v1'. No details/illustration of the implementation and experimental results are given, instead you find statements like 'Median and mean join latency increased'.
- jsnell 11y ago
  It's not academic writing, just a short explanation on why something that was expected to be a major advantage of QUIC is being removed from the spec for now, due to having a negative impact on Youtube. (Of course that shows that they're able to revert bad decisions, which is definitely an advantage over TCP...) Though there is an interesting rebuttal in the related mailing list thread [1] suggesting that the feature is sound as-is, but was being applied in the wrong way in these experiments. Specifically, that the largest expected gain is for the client-sent packets very early during the connection setup. [1] https://groups.google.com/a/chromium.org/forum/#!topic/proto-quic/Z5qKkk2XZe0 https://groups.google.com/a/chromium.org/forum/#!topic/proto...
ycmbntrthrwaway 11y ago
Similar idea (coded TCP) is patented: http://www.codeontechnologies.com/technology/use-cases/coded-tcp/ http://www.codeontechnologies.com/technology/use-cases/coded... They are selling licenses to Cisco: http://www.codeontechnologies.com/partners/ http://www.codeontechnologies.com/partners/ The idea is simple: XOR random combinations of packets and use gaussian elimination to restore them. Google uses simplest version of it, where they XOR together groups of N packets and send them as N+1 packets, so they can recover one packet if it is lost.
- justicezyx 11y ago
  That sounds like network coding
  - colanderman 11y ago
    Ya, I don't understand how that's patented. It must be a very specific patent. A few years ago when I first learned of the woes of TCP over lossy links literally the first thought that popped into my head was "why not code N packets into M>N and recover using Gaussian elimination over GF-2"? Such an idea could have passed for non-obvious maybe 50 years ago but it's a pretty basic idea in the 21st century. To be clear, you can trivially apply any technique here: https://en.wikipedia.org/wiki/Erasure_code https://en.wikipedia.org/wiki/Erasure_code across packets in a channel.
  - ycmbntrthrwaway 11y ago
    The goal of network coding is increased throughput, and it is only possible in multicast case. Authors of CTCP also call it "network coding", but in their case they just decrease delay in the case of loss. Throughput of normal TCP is lower, but only because it reacts to loss by decreasing throughput, so the same throughput can be obtained by using more aggressive congestion control.
Nrsolis 11y ago
I've often wondered why not implement G.709 on the packet payload (as opposed to the whole frame) and see how that compares to TCP retransmission. https://en.wikipedia.org/wiki/G.709 https://en.wikipedia.org/wiki/G.709
- ycmbntrthrwaway 11y ago
  I don't know about G.709, but in general coding, including FEC, is used on link layer, as there it is possible to finely adjust it to achieve throughput close to channel capacity and nearly zero packet loss ratio. It is the problem of channel estimation and rate control. In ideal world where users don't contend and always transmit at the same rate, it would be enough. TCP solves another problem: it adjusts source rate. It assumes that link layer works correctly and packets are not lost because incorrect rate (aka MCS) is used. Instead, packet loss is used as the indicator of congestion: users send data faster then it is possible to transmit it through bottleneck. It is hard to predict and packets are not lost with the same probability on the TCP timescale (RTT, around 50ms), so TCP can't react in time and select the code that would correct losses without adding too much overhead. Thus, coding is not used on TCP layer. That is why Google focuses on latency, not throughput. It is the area where you can benefit from FEC on transmission layer. Another problem QUIC can solve is bad rate control, such as Wi-Fi rate control on old Windows systems, but as wireless internet usage moves to mobile, and Google controls android, it becomes less of a problem as Google can just improve Wi-Fi rate control in Linux if it fails.
  - Nrsolis 11y ago
    Yeah. I understand the problem that TCP is trying to solve. My thinking was that there is a whole class of network applications that don't work great under TCP because the retransmission mechanism drives latency super high when congestion is experienced in the network. TCP works to back off transmission that might be the cause of packet loss, but those packets still have to be transmitted again and the bandwidth timeslot consumed by the dropped packet amounts to wasted resources in the network. In a datacenter microburst situation, retransmissions just tickle the problem you're trying to avoid. FEC over a lossy network would allow for a slight increase in the baseline resource utilization with the side benefit of eliminating retransmissions which might be beneficial in a microburst environment. I don't really know, I'm just thinking aloud.
kierank 11y ago
Why not use something more advanced like LDPC instead of basic XOR (unless I'm missing a trick)?
- amock 11y ago
  I think the reason is that the computational power needed to use LDPC is much greater than that required for XOR.

62 points by jsnell 11y ago

muhic 11y ago

It is worth noting that this document reads more like a first draft, in fact the document title is 'QUIC FEC v1'. No details/illustration of the implementation and experimental results are given, instead you find statements like 'Median and mean join latency increased'.

jsnell 11y ago
It's not academic writing, just a short explanation on why something that was expected to be a major advantage of QUIC is being removed from the spec for now, due to having a negative impact on Youtube. (Of course that shows that they're able to revert bad decisions, which is definitely an advantage over TCP...) Though there is an interesting rebuttal in the related mailing list thread [1] suggesting that the feature is sound as-is, but was being applied in the wrong way in these experiments. Specifically, that the largest expected gain is for the client-sent packets very early during the connection setup. [1] https://groups.google.com/a/chromium.org/forum/#!topic/proto-quic/Z5qKkk2XZe0 https://groups.google.com/a/chromium.org/forum/#!topic/proto...

ycmbntrthrwaway 11y ago

Similar idea (coded TCP) is patented: http://www.codeontechnologies.com/technology/use-cases/coded-tcp/ http://www.codeontechnologies.com/technology/use-cases/coded... They are selling licenses to Cisco: http://www.codeontechnologies.com/partners/ http://www.codeontechnologies.com/partners/ The idea is simple: XOR random combinations of packets and use gaussian elimination to restore them. Google uses simplest version of it, where they XOR together groups of N packets and send them as N+1 packets, so they can recover one packet if it is lost.

justicezyx 11y ago
That sounds like network coding
- colanderman 11y ago
  Ya, I don't understand how that's patented. It must be a very specific patent. A few years ago when I first learned of the woes of TCP over lossy links literally the first thought that popped into my head was "why not code N packets into M>N and recover using Gaussian elimination over GF-2"? Such an idea could have passed for non-obvious maybe 50 years ago but it's a pretty basic idea in the 21st century. To be clear, you can trivially apply any technique here: https://en.wikipedia.org/wiki/Erasure_code https://en.wikipedia.org/wiki/Erasure_code across packets in a channel.
- ycmbntrthrwaway 11y ago
  The goal of network coding is increased throughput, and it is only possible in multicast case. Authors of CTCP also call it "network coding", but in their case they just decrease delay in the case of loss. Throughput of normal TCP is lower, but only because it reacts to loss by decreasing throughput, so the same throughput can be obtained by using more aggressive congestion control.

Nrsolis 11y ago

I've often wondered why not implement G.709 on the packet payload (as opposed to the whole frame) and see how that compares to TCP retransmission. https://en.wikipedia.org/wiki/G.709 https://en.wikipedia.org/wiki/G.709

ycmbntrthrwaway 11y ago
I don't know about G.709, but in general coding, including FEC, is used on link layer, as there it is possible to finely adjust it to achieve throughput close to channel capacity and nearly zero packet loss ratio. It is the problem of channel estimation and rate control. In ideal world where users don't contend and always transmit at the same rate, it would be enough. TCP solves another problem: it adjusts source rate. It assumes that link layer works correctly and packets are not lost because incorrect rate (aka MCS) is used. Instead, packet loss is used as the indicator of congestion: users send data faster then it is possible to transmit it through bottleneck. It is hard to predict and packets are not lost with the same probability on the TCP timescale (RTT, around 50ms), so TCP can't react in time and select the code that would correct losses without adding too much overhead. Thus, coding is not used on TCP layer. That is why Google focuses on latency, not throughput. It is the area where you can benefit from FEC on transmission layer. Another problem QUIC can solve is bad rate control, such as Wi-Fi rate control on old Windows systems, but as wireless internet usage moves to mobile, and Google controls android, it becomes less of a problem as Google can just improve Wi-Fi rate control in Linux if it fails.
- Nrsolis 11y ago
  Yeah. I understand the problem that TCP is trying to solve. My thinking was that there is a whole class of network applications that don't work great under TCP because the retransmission mechanism drives latency super high when congestion is experienced in the network. TCP works to back off transmission that might be the cause of packet loss, but those packets still have to be transmitted again and the bandwidth timeslot consumed by the dropped packet amounts to wasted resources in the network. In a datacenter microburst situation, retransmissions just tickle the problem you're trying to avoid. FEC over a lossy network would allow for a slight increase in the baseline resource utilization with the side benefit of eliminating retransmissions which might be beneficial in a microburst environment. I don't really know, I'm just thinking aloud.

kierank 11y ago

Why not use something more advanced like LDPC instead of basic XOR (unless I'm missing a trick)?

amock 11y ago
I think the reason is that the computational power needed to use LDPC is much greater than that required for XOR.