• the Encoding Symbol Identifier (ESI) of the first source symbol in the encoding window as well as the number of symbols (since this number may vary with a variable size, elastic window). These two pieces of information enable each receiver to reconstruct the set of source symbols considered during encoding, the only constraint being that there cannot be any gap;
• the seed and density threshold parameters used by a coding coefficients generation function (Section 3.6). These two pieces of information enable each receiver to generate the same set of coding coefficients over GF(2^m) as the sender;

3. Procedures: This section describes procedures specific to this FEC scheme, namely: RLC parameters derivation, ADUI and source symbols mapping, pseudorandom number generator, and coding coefficients generation function;
4. Formats and Codes: This section defines the Source FEC Payload ID and Repair FEC Payload ID formats, carrying the signaling information associated to each source or repair symbol. It also defines the FEC Framework Configuration Information (FFCI) carrying signaling information for the session;
5. FEC Code Specification: Finally this section provides the code specification.

a^b

a to the power of b

GF(q)

denotes a finite field (also known as the Galois Field) with q elements. We assume that q = 2^m in this document

m

defines the length of the elements in the finite field, in bits. In this document, m is equal to 1 or 8

ADU:

Application Data Unit

ADUI:

Application Data Unit Information (includes the F, L and padding fields in addition to the ADU)

E:

size of an encoding symbol (i.e., source or repair symbol), assumed fixed (in bytes)

br_in:

transmission bitrate at the input of the FECFRAME sender, assumed fixed (in bits/s)

br_out:

transmission bitrate at the output of the FECFRAME sender, assumed fixed (in bits/s)

max_lat:

maximum FEC-related latency within FECFRAME (a decimal number expressed in seconds)

cr:

RLC coding rate, ratio between the total number of source symbols and the total number of source plus repair symbols

ew_size:

encoding window current size at a sender (in symbols)

ew_max_size:

encoding window maximum size at a sender (in symbols)

dw_max_size:

decoding window maximum size at a receiver (in symbols)

ls_max_size:

linear system maximum size (or width) at a receiver (in symbols)

WSR:

window size ratio parameter used to derive ew_max_size (encoder) and ls_max_size (decoder).

PRNG:

pseudorandom number generator

TinyMT32:

PRNG used in this specification.

DT:

coding coefficients density threshold, an integer between 0 and 15 (inclusive) the controls the fraction of coefficients that are nonzero

Maximum FEC-related latency budget, max_lat (a decimal number expressed in seconds) with real-time flows:

a source ADU flow can have real-time constraints, and therefore any FECFRAME related operation should take place within the validity period of each ADU (Appendix D describes an exception to this rule). When there are multiple flows with different real-time constraints, we consider the most stringent constraints (see item 6 in Section 10.2 of RFC 6363, for recommendations when several flows are globally protected). The maximum FEC-related latency budget, max_lat, accounts for all sources of latency added by FEC encoding (at a sender) and FEC decoding (at a receiver). Other sources of latency (e.g., added by network communications) are out of scope and must be considered separately (said differently, they have already been deducted from max_lat). max_lat can be regarded as the latency budget permitted for all FEC-related operations. This is an input parameter that enables a FECFRAME sender to derive other internal parameters (see Appendix C);

Encoding window current (resp. maximum) size, ew_size (resp. ew_max_size) (in symbols):

at a FECFRAME sender, during FEC encoding, a repair symbol is computed as a linear combination of the ew_size source symbols present in the encoding window. The ew_max_size is the maximum size of this window, while ew_size is the current size. For example, in the common case at session start, upon receiving new source ADUs, the ew_size progressively increases until it reaches its maximum value, ew_max_size. We have:

• 0 < ew_size <= ew_max_size

Decoding window maximum size, dw_max_size (in symbols):

at a FECFRAME receiver, dw_max_size is the maximum number of received or lost source symbols that are still within their latency budget;

Linear system maximum size, ls_max_size (in symbols):

at a FECFRAME receiver, the linear system maximum size, ls_max_size, is the maximum number of received or lost source symbols in the linear system (i.e., the variables). It SHOULD NOT be smaller than dw_max_size since it would mean that, even after receiving a sufficient number of FEC Repair Packets, a lost ADU may not be recovered just because the associated source symbols have been prematurely removed from the linear system, which is usually counter-productive. On the opposite, the linear system MAY grow beyond the dw_max_size (Appendix D);

Symbol size, E (in bytes):

the E parameter determines the source and repair symbol sizes (necessarily equal). This is an input parameter that enables a FECFRAME sender to derive other internal parameters, as explained below. An implementation at a sender MUST fix the E parameter and MUST communicate it as part of the FEC Scheme-Specific Information (Section 4.1.1.2).

Code rate, cr:

The code rate parameter determines the amount of redundancy added to the flow. More precisely the cr is the ratio between the total number of source symbols and the total number of source plus repair symbols and by definition: 0 < cr <= 1. This is an input parameter that enables a FECFRAME sender to derive other internal parameters, as explained below. However, there is no need to communicate the cr parameter per see (it's not required to process a repair symbol at a receiver). This code rate parameter can be static. However, in specific use-cases (e.g., with unicast transmissions in presence of a feedback mechanism that estimates the communication quality, out of scope of FECFRAME), the code rate may be adjusted dynamically.

Flow ID (F) (8-bit field):

this unsigned byte contains the integer identifier associated to the source ADU flow to which this ADU belongs. It is assumed that a single byte is sufficient, which implies that no more than 256 flows will be protected by a single FECFRAME session instance.

Length (L) (16-bit field):

this unsigned integer contains the length of this ADU, in network byte order (i.e., big endian). This length is for the ADU itself and does not include the F, L, or Pad fields.

Padding (Pad) (variable size field):

this field contains zero padding to align the F, L, ADU and padding up to a size that is multiple of E bytes (i.e., the source and repair symbol length).

   symbol length, E              E                     E
< ------------------ >< ------------------ >< ------------------ >
+-+--+---------------------------------------------+-------------+
|F| L|                     ADU                     |     Pad     |
+-+--+---------------------------------------------+-------------+

• when the sliding encoding window has reached its maximum size, ew_max_size. In that case the oldest symbol MUST be removed before adding a new symbol, so that the current encoding window size always remains inferior or equal to the maximum size: ew_size <= ew_max_size;
• when an ADU has reached its maximum validity duration in case of a real-time flow. When this happens, all source symbols corresponding to the ADUI that expired SHOULD be removed from the encoding window;

• x⁸ + x⁴ + x³ + x² + 1

FEC Encoding ID:

the value assigned to this fully specified FEC scheme MUST be 10, as assigned by IANA (Section 9).

Encoding symbol size (E):

a non-negative integer that indicates the size of each encoding symbol in bytes;

Window Size Ratio (WSR) parameter:

a non-negative integer between 0 and 255 (both inclusive) used to initialize window sizes. A value of 0 indicates this parameter is not considered (e.g., a fixed encoding window size may be chosen). A value between 1 and 255 inclusive is required by certain of the parameter derivation techniques described in Appendix C;

   fssi=E:1400,WSR:191

Encoding symbol length (E): 16-bit field;

Window Size Ratio Parameter (WSR): 8-bit field.

 0                   1                   2
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Encoding Symbol Length (E)  |      WSR      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+--------------------------------+
|           IP Header            |
+--------------------------------+
|        Transport Header        |
+--------------------------------+
|              ADU               |
+--------------------------------+
| Explicit Source FEC Payload ID |
+--------------------------------+

Encoding Symbol ID (ESI) (32-bit field):

this unsigned integer identifies the first source symbol of the ADUI corresponding to this FEC Source Packet. The ESI is incremented for each new source symbol, and after reaching the maximum value (2³²-1), wrapping to zero occurs.

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Encoding Symbol ID (ESI)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+--------------------------------+
|           IP Header            |
+--------------------------------+
|        Transport Header        |
+--------------------------------+
|     Repair FEC Payload ID      |
+--------------------------------+
|         Repair Symbol          |
+--------------------------------+

Repair_Key (16-bit field):

this unsigned integer is used as a seed by the coefficient generation function (Section 3.6) in order to generate the desired number of coding coefficients. This repair key may be a monotonically increasing integer value that loops back to 0 after reaching 65535 (see Section 6.1). When a FEC Repair Packet contains several repair symbols, this repair key value is that of the first repair symbol. The remaining repair keys can be deduced by incrementing by 1 this value, up to a maximum value of 65535 after which it loops back to 0.

Density Threshold for the coding coefficients, DT (4-bit field):

this unsigned integer carries the Density Threshold (DT) used by the coding coefficient generation function Section 3.6. More precisely, it controls the probability of having a nonzero coding coefficient, which equals (DT+1) / 16. When a FEC Repair Packet contains several repair symbols, the DT value applies to all of them;

Number of Source Symbols in the encoding window, NSS (12-bit field):

this unsigned integer indicates the number of source symbols in the encoding window when this repair symbol was generated. When a FEC Repair Packet contains several repair symbols, this NSS value applies to all of them;

ESI of First Source Symbol in the encoding window, FSS_ESI (32-bit field):

this unsigned integer indicates the ESI of the first source symbol in the encoding window when this repair symbol was generated. When a FEC Repair Packet contains several repair symbols, this FSS_ESI value applies to all of them;

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Repair_Key              |  DT   |NSS (# src symb in ew) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            FSS_ESI                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

FEC Encoding ID:

the value assigned to this fully specified FEC scheme MUST be 9, as assigned by IANA (Section 9).

FEC Encoding ID:

changing this parameter leads a receiver to consider a different FEC scheme. The consequences are severe, the format of the Explicit Source FEC Payload ID and Repair FEC Payload ID of received packets will probably differ, leading to various malfunctions. Even if the original and modified FEC schemes share the same format, FEC decoding will either fail or lead to corrupted decoded symbols. This will happen if an attacker turns value 9 (i.e., RLC over GF(2)) to value 10 (RLC over GF(2⁸)), an additional consequence being a higher processing overhead at the receiver. In any case, the attack results in a form of Denial of Service (DoS) or corrupted content.

Encoding symbol length (E):

setting this E parameter to a different value will confuse a receiver. If the size of a received FEC Repair Packet is no longer multiple of the modified E value, a receiver quickly detects a problem and SHOULD reject the packet. If the new E value is a sub-multiple of the original E value (e.g., half the original value), then receivers may not detect the problem immediately. For instance, a receiver may think that a received FEC Repair Packet contains more repair symbols (e.g., twice as many if E is reduced by half), leading to malfunctions whose nature depends on implementation details. Here also, the attack always results in a form of DoS or corrupted content.

Encoding Symbol ID (ESI):

changing the ESI leads a receiver to consider a wrong ADU, resulting in severe consequences, including corrupted content passed to the receiving application;

Repair Key:

changing this value leads a receiver to generate a wrong coding coefficient sequence, and therefore any source symbol decoded using the repair symbols contained in this packet will be corrupted;

DT:

changing this value also leads a receiver to generate a wrong coding coefficient sequence, and therefore any source symbol decoded using the repair symbols contained in this packet will be corrupted. In addition, if the DT value is significantly increased, it will generate a higher processing overhead at a receiver. In case of very large encoding windows, this may impact the terminal performance;

NSS:

changing this value leads a receiver to consider a different set of source symbols, and therefore any source symbol decoded using the repair symbols contained in this packet will be corrupted. In addition, if the NSS value is significantly increased, it will generate a higher processing overhead at a receiver, which may impact the terminal performance;

FSS_ESI:

changing this value also leads a receiver to consider a different set of source symbols and therefore any source symbol decoded using the repair symbols contained in this packet will be corrupted.

• 9 refers to the Sliding Window Random Linear Codes (RLC) over GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in Section 5 of this document.
• 10 refers to the Sliding Window Random Linear Codes (RLC) over GF(2⁸) FEC Scheme for Arbitrary Packet Flows, as defined in Section 4 of this document.

[C99]

International Organization for Standardization, "Programming languages - C: C99, correction 3:2007", ISO/IEC 9899:1999/Cor 3:2007, November 2007.

[RFC2119]

S. Bradner, "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.

[RFC6363]

M. Watson, A. Begen, and V. Roca, "Forward Error Correction (FEC) Framework", RFC 6363, DOI 10.17487/RFC6363, October 2011,
<https://www.rfc-editor.org/info/rfc6363>.

[RFC6364]

A. Begen, "Session Description Protocol Elements for the Forward Error Correction (FEC) Framework", RFC 6364, DOI 10.17487/RFC6364, October 2011,
<https://www.rfc-editor.org/info/rfc6364>.

[RFC8174]

B. Leiba, "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017,
<https://www.rfc-editor.org/info/rfc8174>.

[RFC8680]

V Roca, and A Begen, "Forward Error Correction (FEC) Framework Extension to Sliding Window Codes", RFC 8680, DOI 10.17487/RFC8680, January 2020,
<https://www.rfc-editor.org/info/rfc8680>.

[RFC8682]

M Saito, M Matsumoto, V Roca, and E Baccelli, "TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682, DOI 10.17487/RFC8682, January 2020,
<https://www.rfc-editor.org/info/rfc8682>.

[PGM13]

J. Plank, K. Greenan, and E. Miller, "A Complete Treatment of Software Implementations of Finite Field Arithmetic for Erasure Coding Applications", University of Tennessee Technical Report UT-CS-13-717, October 2013,
<http://web.eecs.utk.edu/~plank/plank/papers/UT-CS-13-717.html>.

[RFC5170]

V. Roca, C. Neumann, and D. Furodet, "Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, June 2008,
<https://www.rfc-editor.org/info/rfc5170>.

[RFC5510]

J. Lacan, V. Roca, J. Peltotalo, and S. Peltotalo, "Reed-Solomon Forward Error Correction (FEC) Schemes", RFC 5510, DOI 10.17487/RFC5510, April 2009,
<https://www.rfc-editor.org/info/rfc5510>.

[RFC6681]

M. Watson, T. Stockhammer, and M. Luby, "Raptor Forward Error Correction (FEC) Schemes for FECFRAME", RFC 6681, DOI 10.17487/RFC6681, August 2012,
<https://www.rfc-editor.org/info/rfc6681>.

[RFC6726]

T. Paila, R. Walsh, M. Luby, V. Roca, and R. Lehtonen, "FLUTE - File Delivery over Unidirectional Transport", RFC 6726, DOI 10.17487/RFC6726, November 2012,
<https://www.rfc-editor.org/info/rfc6726>.

[RFC6816]

V. Roca, M. Cunche, and J. Lacan, "Simple Low-Density Parity Check (LDPC) Staircase Forward Error Correction (FEC) Scheme for FECFRAME", RFC 6816, DOI 10.17487/RFC6816, December 2012,
<https://www.rfc-editor.org/info/rfc6816>.

[RFC6865]

V. Roca, M. Cunche, J. Lacan, A. Bouabdallah, and K. Matsuzono, "Simple Reed-Solomon Forward Error Correction (FEC) Scheme for FECFRAME", RFC 6865, DOI 10.17487/RFC6865, February 2013,
<https://www.rfc-editor.org/info/rfc6865>.

[RFC8406]

B. Adamson, C. Adjih, J. Bilbao, V. Firoiu, F. Fitzek, S. Ghanem, E. Lochin, A. Masucci, M-J. Montpetit, M. Pedersen, G. Peralta, V. Roca, Saxena, and S. Sivakumar, "Taxonomy of Coding Techniques for Efficient Network Communications", RFC 8406, DOI 10.17487/RFC8406, June 2018,
<https://www.rfc-editor.org/info/rfc8406>.

[Roca16]

V. Roca, B. Teibi, C. Burdinat, T. Tran-Thai, and C. Thienot, "Block or Convolutional AL-FEC Codes? A Performance Comparison for Robust Low-Latency Communications", HAL ID hal-01395937v2, February 2017,
<https://hal.inria.fr/hal-01395937/en/>.

[Roca17]

V. Roca, B. Teibi, C. Burdinat, T. Tran, and C. Thienot, "Less Latency and Better Protection with AL-FEC Sliding Window Codes: a Robust Multimedia CBR Broadcast Case Study", HAL ID hal-01571609, October 2017,
<https://hal.inria.fr/hal-01571609v1/en/>.

• the source ADU flow they protect may or may not have real-time constraints;
• the source ADU flow may be a Constant Bitrate (CBR) or Variable Bitrate (VBR) flow;
• with a VBR source ADU flow, the flow's minimum and maximum bitrates may or may not be known;
• and the communication path between encoder and decoder may be a CBR communication path (e.g., as with certain LTE-based broadcast channels) or not (general case, e.g., with Internet).

• dw_max_size = (max_lat * br_in) / (8 * E)

• dw_max_size = (max_lat * br_out * cr) / (8 * E)

• ew_max_size = dw_max_size * WSR / 255

• dw_max_size = max_NSS_observed * 255 / WSR

• ls_max_size >= dw_max_size

• max_lat_for_encoding = max_lat * WSR / 255

• ls_max_size > dw_max_size

• ls_max_size = 2 * dw_max_size

• ls_max_size = max(2 * dw_max_size, LS_MIN_SIZE_DEFAULT)

                             ls_max_size
/---------------------------------^-------------------------------\

        late source symbols
 (pot. decoded but not delivered)            dw_max_size
/--------------^-----------------\ /--------------^---------------\
src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12

Vincent Roca

Belkacem Teibi