Forward Erasure Correction for QUIC loss recovery

2.1. FEC-related definitions

Source symbol: piece of information exchanged by two endpoints. This document considers QUIC packets payloads as source symbols.¶

Repair symbol: redundant information constructed from the combination of several source symbols.¶

Erasure: loss of one or more symbols¶

Erasure correction code: algorithm generating repair symbols and reconstructing missing source symbols from a set of source and repair symbols.¶

Forward Erasure Correction: process of recovering erased symbols before the detection of their erasure.¶

FEC scheme: the conjunction of an erasure correction code and the specific protocol elements required to use it with the design described in this document.¶

Encoder: entity producing repair symbols using an erasure correction code. The encoder can be a library used by the protocol implementation or a program running in a separate process or machine.¶

Decoder: entity reconstructing missing source symbols using an erasure correction code. The decoder can be a library used by the protocol implementation or a program running in a separate process or machine.¶

Coding window: window of source symbols that are required to decode a repair symbol.¶

5.1. Defining the FEC-protected parts of a QUIC payload

There is no need to protect every piece information sent on the wire by QUIC. Some pieces of information are already sent redundantly (e.g. ACKs) and some data are not delay sensitive and can be retransmitted later with no harm (e.g. background download on a separate stream). Endpoints need to agree on which parts of the packets are part of the protected source symbols and how to compose a source symbol from what is sent on the wire.¶

Versions 01 and 02 of [I-D.swett-nwcrg-coding-for-quic] only protect streams payload. The idea is simple when using a single stream but becomes complicated and requires more signaling in a multi-stream scenario. It also cannot protect DATAGRAM frames. In this document, we propose to consider whole frames as part of the source symbols. Source symbols are thus the counterpart to QUIC packets for the coding channel. Packets carry frames through the network channel and source symbols allow receiving frames from the coding channel. In order to reduce signalling between the peers, a single source symbol MUST NOT contain the frames of several QUIC packets at the same time.¶

5.2. Identifying the source symbols from QUIC packets

Upon reception of a QUIC packet, a receiver needs to identify the source symbols contained in the packet to forward to the FEC decoder. The decoder also needs to know which source symbols were lost. Since QUIC does not enforce sending contiguously increasing packet numbers, it is not possible for a receiver to distinguish a lost packet from a packet that has never been sent. Furthermore, a QUIC sender may not want to protect the payload of some packets if they do not carry latency-sensitive information. Source symbols are thus attributed a Symbol ID (SID). The SID of the first source symbol MUST be zero and the SIDs are contiguously increasing. When a FEC decoder notes gaps in the received SIDs, the missing SIDs correspond to lost source symbols that can be recovered using FEC.¶

As the QUIC packet number cannot be used to carry the SID, it must be transmitted using either a dedicated QUIC frame or a dedicated header field. The second solution being incompatible with [QUICv1], it is not discussed in this document. The source symbol payload can either be put inside a dedicated frame (Section 5.2.1) or infered when handling a specific frame (Section 5.2.2). Both alternatives lead to the exact same packet wire format and outcome.¶

SOURCE_SYMBOL {
  SID (i),
  FEC Protected Payload (..)
}

Sender                                                       Receiver
  |                                                             |
  | Pkt(5)[ACK[..], SOURCE_SYMBOL(0, { STREAM(4, "abc") }]      |
  |------------------------------------------------------------>|
  |                                                             |
  | Pkt(6)[STREAM(2, "xyz"),                                    |
  |        SOURCE_SYMBOL(1, { STREAM(8, "def"),                 |
  |                           DATAGRAM("msg") }]                |
  |------------------------------------------------------------>|
  |                                                             |
  |                                            Pkt(1)[ACK[..]]  |
  |<------------------------------------------------------------|
  |                                                             |

SID {
  SID (i),
}

Sender                                       Receiver
  |                                            |
  | Pkt(5)[ACK[..], SID(0), STREAM(4, "abc")]  |
  |------------------------------------------->|
  |                                            |
  | Pkt(6)[STREAM(2, "xyz"),                   |
  |        SID(1), STREAM(8, "def"),           |
  |        DATAGRAM("msg")]                    |
  |------------------------------------------->|
  |                                            |
  |                            Pkt(1)[ACK[..]] |
  |<-------------------------------------------|
  |                                            |

5.3. Sending the repair symbols

The repair symbols and the metadata attached to them are transferred using the REPAIR frame shown in Figure 6.¶

REPAIR {
  FEC Scheme Specific Repair Payload (1..),
}

The payload of the REPAIR frame is specific to the underlying FEC scheme. In addition to the repair symbol itself, it may contain any metadata needed by the erasure-correcting code (e.g. identifying the source symbols protected by the repair symbol carried by the frame). Depending on the FEC scheme, the REPAIR frame MAY contain only a part of a repair symbol.¶

5.4. Announcing the coding window size

The receiver needs to store the received symbols in order to recover the lost source symbols. The FEC_WINDOW frame is sent by the receiver to announce the number of symbols that can be stored simultaneously by the receiver at a given point of time. The format of the FEC_WINDOW frame is described in Figure 7.¶

FEC_WINDOW {
  FEC Window Epoch (i),
  FEC Window Size (i),
}

The FEC Window Epoch field is a unique identifier for the announced window. The first epoch is set to 0. Each time a new FEC_WINDOW frame is sent, the FEC Window Epoch field is increased by exactly one.¶

The Window Size field indicates the number of symbols that can be stored simultaneously by the receiver. The Window Size value overrides the window sizes received for smaller window epochs.¶

5.5. Announcing the recovered symbols

The FEC receiver MAY advertise the source symbols that have been received either through the network or coding channels to avoid the sender retransmitting the data of the recovered source symbols. This can be done using the SYMBOL_ACK frame as shown in Figure 8.¶

SYMBOL_ACK {
  Largest Acknowledged (i),
  ACK Range Count (i),
  First ACK Range (i),
  ACK Range (..) ...,
}

The frame has a similar format as the ACK frame, announcing the reception of SIDs instead of packet numbers. In addition to symbols recovered by FEC, this frame MAY also announce symbols received regularly through the network to avoid gaps in the ACK ranges and reduce the frame size. There is no obligation for a FEC receiver to send SYMBOL_ACK frames. The FEC receiver MAY decide to only advertize a subset of the received source symbols. The SYMBOL_ACK frame MUST NOT be used to infer any congestion state on the network (see Section 6).¶

7.1. enable_fec

The use of the FEC extension is negociated using the enable_fec transport parameter defined in Table 1 :¶

When the enable_fec value is 0 or is not advertized by the peer, the QUIC endpoint MUST NOT use any frame or mechanism described in this document.¶

7.2. decoder_fec_scheme

Each QUIC endpoint uses the decoder_fec_scheme transport parameter to define the FEC scheme used to decode the received repair symbols. The QUIC sender MUST use the specified FEC scheme to generate repair symbols. The decoder_fec_scheme parameter is an integer value representing the identifier of the desired FEC scheme. For instance, a FEC scheme using Reed Solomon could be identified by the ID 0x0 and a FEC scheme using LDPC could be identified by 0x1.¶

This document does not specify nor identify any FEC scheme yet. Several FEC schemes have been proposed [I-D.roca-nwcrg-rlc-fec-scheme-for-quic] [RFC6865] [I-D.irtf-nwcrg-tetrys]. The next version of this document will detail how some of these schemes can be directly integrated in QUIC.¶

Future versions of this document will provide ways to format FEC scheme-specific payload for REPAIR frames. When the decoder_fec_scheme parameter is not advertized by the peer, the QUIC sender MUST NOT send any repair symbol.¶

7.3. initial_coding_window

Each QUIC endpoint uses the initial_coding_window transport parameter to define the initial coding window size it uses to store source and repair symbols (see Section 5.4). When the initial_coding_window parameter is not advertized by the peer, the QUIC sender MUST consider a default value of 0 and MUST NOT send any repair symbol.¶

8.1. DoS due to difficult symbols recoveries

An attacker could try to cause a DoS of a receiver by selectively sending source and repair symbols to trigger intensive erasure correction operations on the receiver. A QUIC receiver is never forced to perform any erasure correction and may ignore any received repair symbol if it has doubts in its capabilities to decode it in a reasonable amount of time.¶

9.1. New transport parameters

The XX in 0x238ffeceXX are to be replaced by the version of this document that is implemented by the QUIC endpoint (e.g. the parameter ID for the version 00 of this document is 0x238ffece00).¶

9.2. New frames