RFC 8681

Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Schemes for FECFRAME

📅 published January 2020, from ietf

Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Schemes for FECFRAME 🦋

Internet Engineering Task Force (IETF) 🌸 Request for Comments: 8681 Category: Standards Track ISSN: 2070-1721 Date: January 2020 Authors: V. Roca and B. Teibi (INRIA) 💜

Quick tea on the title block: it lists no RFC that this one obsoletes and no RFC that it updates. So this is a brand-new spec, not a replacement or a patch. ✨

Abstract

okay bestie, this doc defines two fully specified Forward Erasure Correction (FEC) schemes 🔥. Both are Sliding Window Random Linear Codes (RLC). One runs over the Galois Field (a.k.a. Finite Field) GF(2), and the other runs over GF(2^(8)). In both, you can control the code density 🎛️. They can protect arbitrary media streams along the lines that FECFRAME defines, extended to Sliding Window FEC Codes 💖.

Here's how the magic works: the encoding window slides over the source symbols, and it makes new repair symbols whenever they're needed 🪟✨. Compared to block FEC codes, these sliding window codes are a total win for real-time flows 👑. You get reduced FEC-related latency, and they often recover erased packets better too. It's giving efficiency. 💅

Status of This Memo

This is an Internet Standards Track document. 🎀

This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 7841. 🫶

Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at https://www.rfc-editor.org/info/rfc8681. 🌈

Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved. 🔒

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. 🧾

Table of Contents

1.  Introduction
  1.1.  Limits of Block Codes with Real-Time Flows
  1.2.  Lower Latency and Better Protection of Real-Time Flows with
        the Sliding Window RLC Codes
  1.3.  Small Transmission Overheads with the Sliding Window RLC
        FEC Scheme
  1.4.  Document Organization
2.  Definitions and Abbreviations
3.  Common Procedures
  3.1.  Codec Parameters
  3.2.  ADU, ADUI, and Source Symbols Mappings
  3.3.  Encoding Window Management
  3.4.  Source Symbol Identification
  3.5.  Pseudorandom Number Generator (PRNG)
  3.6.  Coding Coefficients Generation Function
  3.7.  Finite Field Operations
    3.7.1.  Finite Field Definitions
    3.7.2.  Linear Combination of Source Symbol Computation
4.  Sliding Window RLC FEC Scheme over GF(2^(8)) for Arbitrary
        Packet Flows
  4.1.  Formats and Codes
    4.1.1.  FEC Framework Configuration Information
    4.1.2.  Explicit Source FEC Payload ID
    4.1.3.  Repair FEC Payload ID
  4.2.  Procedures
5.  Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet
        Flows
  5.1.  Formats and Codes
    5.1.1.  FEC Framework Configuration Information
    5.1.2.  Explicit Source FEC Payload ID
    5.1.3.  Repair FEC Payload ID
  5.2.  Procedures
6.  FEC Code Specification
  6.1.  Encoding Side
  6.2.  Decoding Side
7.  Security Considerations
  7.1.  Attacks Against the Data Flow
    7.1.1.  Access to Confidential Content
    7.1.2.  Content Corruption
  7.2.  Attacks Against the FEC Parameters
  7.3.  When Several Source Flows are to be Protected Together
  7.4.  Baseline Secure FEC Framework Operation
  7.5.  Additional Security Considerations for Numerical
        Computations
8.  Operations and Management Considerations
  8.1.  Operational Recommendations: Finite Field GF(2) Versus
        GF(2^(8))
  8.2.  Operational Recommendations: Coding Coefficients Density
        Threshold
9.  IANA Considerations
10. References
  10.1.  Normative References
  10.2.  Informative References
Appendix A.  TinyMT32 Validation Criteria (Normative)
Appendix B.  Assessing the PRNG Adequacy (Informational)
Appendix C.  Possible Parameter Derivation (Informational)
  C.1.  Case of a CBR Real-Time Flow
  C.2.  Other Types of Real-Time Flow
  C.3.  Case of a Non-Real-Time Flow
Appendix D.  Decoding Beyond Maximum Latency Optimization
        (Informational)
Acknowledgments
Authors' Addresses

1. Introduction ✨

Application-Level Forward Erasure Correction (AL-FEC) codes, or just FEC codes, are a key element of communication systems 🛰️. They recover packets that get lost (or erased) during content delivery sessions to a potentially huge crowd of receivers (multicast/broadcast transmissions) 📡. Two examples: the File Delivery over Unidirectional Transport (FLUTE)/Asynchronous Layered Coding (ALC) protocol [RFC6726] for reliable file transfers over lossy networks, and the FECFRAME protocol [RFC6363] for reliable continuous media transfers over lossy networks 🎬.

This document only focuses on FECFRAME 🎯. It's used in multicast/broadcast delivery mode, especially for content with stringent real-time constraints. Each source packet has a maximum validity period. After that, the destination application won't consider it anymore ⏰.

1.1. Limits of Block Codes with Real-Time Flows 🧱

With FECFRAME, there is a single FEC encoding point 🖥️. That's either an end host/server (source) or a middlebox. There's also a single FEC decoding point per receiver, which is either an end host (receiver) or a middlebox. In this setup, the standardized AL-FEC codes for FECFRAME, like Reed-Solomon [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ [RFC6681], are all linear block codes. That means they need the data flow chopped into blocks of a predefined maximum size 🍰.

Picking that block size is a balancing act between robustness and decoding latency ⚖️. A bigger block size gives you more robustness (for example, when there are long packet erasure bursts). But it also raises the maximum decoding latency, which is the maximum time needed to recover a lost (erased) packet thanks to FEC protection. So in a multicast/broadcast session where receivers see different packet loss rates, the block size should be chosen by thinking about the worst communication conditions you want to support, without going over the maximum decoding latency you want 🎯. Here's the catch: this choice hits the FEC-related latency of every receiver, even the ones with great connections 😭. No FEC encoding can happen until all the source data of the block is available at the sender, and that depends directly on the block size.

1.2. Lower Latency and Better Protection of Real-Time Flows with the Sliding Window RLC Codes 🦋

This document introduces two fully specified FEC schemes that skip the block code approach entirely 🙅‍♀️. They are Sliding Window Random Linear Codes (RLC) over either Galois Fields (a.k.a. Finite Fields) GF(2) (the "binary case") or GF(2^(8)). In both, you can control the code density 🎛️. These FEC schemes protect arbitrary media streams along the lines that FECFRAME defines, extended to Sliding Window FEC Codes [RFC8680]. For instance, they're recommended for media with real-time constraints that's sent within a multicast/broadcast session [Roca17]. Iykyk, these are the vibes ✨.

The RLC codes belong to the broad class of Sliding Window AL-FEC Codes (a.k.a. convolutional codes) [RFC8406] 🌀. The encoding process uses an encoding window that slides over the set of source packets (well, source symbols, as we'll see in Section 3.2 👀). This window can be either fixed size or variable size (a.k.a. an elastic window). Repair symbols get generated on-the-fly. Each one is a random linear combination of the source symbols currently in the encoding window, and then it's passed down to the transport layer 🚀.

On the receiver side, a linear system gets managed from the set of received source and repair packets 🧮. New variables (representing source symbols) and new equations (representing the linear combination carried by each received repair symbol) get added as new packets arrive. Variables and the equations they're involved in get removed once they're too old for their validity period (the real-time constraints) 🗑️. Lost source symbols are then recovered using this linear system, as long as its rank allows it to be solved, at least partially 💜.

Protection for any multicast/broadcast session has to be dimensioned around the worst communication conditions you want to support 🛡️. That's true for RLC codes, and for any sliding window code too. But receivers with good to medium communication quality see a reduced FEC-related latency compared to block codes [Roca17]. The reason is that an isolated lost source packet gets recovered quickly, with the following repair packet 🏃‍♀️. With a block code, recovering an isolated lost source packet always means waiting for the first repair packet to arrive after the end of the block 😩. Plus, in some situations (for example, a limited FEC-related latency budget, and constant bitrate transmissions after FECFRAME encoding), Sliding Window Codes can hit a target transmission quality more efficiently. Quality can be measured by the residual loss after FEC decoding, for example. They do it by sending fewer repair packets (that is, a higher code rate) than block codes 🌟.

1.3. Small Transmission Overheads with the Sliding Window RLC FEC Scheme

Okay so the Sliding Window RLC FEC scheme is obsessed with keeping packet headers tiny 🎀 because nobody wants their packets to be mostly paperwork ✨. The main requirement is that each repair packet header must let a receiver rebuild the set of source symbols plus the coefficients used during encoding 💅. To keep the overhead low, the source symbols in the encoding window and the coefficients over GF(2^(m)) (where m is 1 or 8, depending on the FEC scheme) used in the linear combination are not listed one by one in the repair packet header. Instead, each FEC Repair Packet header contains:

  • the Encoding Symbol Identifier (ESI) of the first source symbol in the encoding window, plus the number of symbols (since that number can vary with a variable size, elastic window). These two pieces of info let each receiver rebuild the source symbols considered during encoding 🦋, with 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 info let each receiver generate the same coding coefficients over GF(2^(m)) as the sender 🫶.

So no matter how many source symbols are in the encoding window, each FEC Repair Packet gets a fixed 64-bit long header, called Repair FEC Payload ID (Figure 8) 🍓. Similarly, each FEC Source Packet gets a fixed 32-bit long trailer, called Explicit Source FEC Payload ID (Figure 6), which holds the ESI of the first source symbol (Section 3.2) 🧚.

1.4. Document Organization

This fully-specified FEC scheme follows the structure required by [RFC6363], Section 5.6 ("FEC Scheme Requirements"), which means:

  1. Procedures: this section covers the procedures specific to this FEC scheme: RLC parameters derivation, ADUI and source symbols mapping, pseudorandom number generator, and coding coefficients generation function 💖;
  2. Formats and Codes: this section defines the Source FEC Payload ID and Repair FEC Payload ID formats, which carry the signaling info for each source or repair symbol. It also defines the FEC Framework Configuration Information (FFCI), which carries signaling info for the session 🌸;
  3. FEC Code Specification: finally, this section gives the code specification 👑.

2. Definitions and Abbreviations

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🎀.

This document uses the following definitions and abbreviations:

  • 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) that controls the fraction of coefficients that are nonzero 🦋

3. Common Procedures

This section introduces the procedures that these FEC schemes all use 💅.

3.1. Codec Parameters

A codec implementing the Sliding Window RLC FEC scheme relies on several parameters 🌈:

  • 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, so 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 go with the most stringent constraints (see item 6 in Section 10.2 of [RFC6363] for recommendations when several flows are globally protected). The maximum FEC-related latency budget, max_lat, covers all the 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 seen as the latency budget allowed for all FEC-related operations. It's an input parameter that lets a FECFRAME sender 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. 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, as new source ADUs come in, ew_size grows 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, 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. If it were, then even after receiving enough FEC Repair Packets, a lost ADU might not be recovered just because its source symbols were removed from the linear system too early, which is usually counter-productive 🙈. On the flip side, the linear system MAY grow beyond the dw_max_size (Appendix D).
  • Symbol size, E (in bytes): the E parameter sets the source and repair symbol sizes (which are necessarily equal). It's an input parameter that lets a FECFRAME sender 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 sets how much redundancy gets added to the flow. More precisely, 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. It's an input parameter that lets a FECFRAME sender derive other internal parameters, as explained below. However, there's 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., unicast transmissions with a feedback mechanism that estimates the communication quality, which is out of scope for FECFRAME), the code rate may be adjusted dynamically 🌸.

Appendix C proposes non-normative techniques to derive those parameters, depending on the use case specifics 🧚.

3.2. ADU, ADUI, and Source Symbols Mappings

Okay so at a sender, an ADU from the application isn't mapped straight onto source symbols 🙅‍♀️. When multiple source flows (e.g., media streams) get mapped onto the same FECFRAME instance, each flow gets its own Flow ID value (see below). That Flow ID then gets prepended to each ADU before FEC encoding. This way, FEC decoding at a receiver also recovers the Flow ID, and the recovered ADU can be assigned to the right source flow. (Note that the 5-tuple used to identify the right source flow of a received ADU is missing from a recovered ADU, since it isn't FEC protected 🫣.)

Also, since ADUs come in variable sizes, padding is needed so that each ADU (with its flow identifier) contributes to an integral number of source symbols. This means the original ADU length has to be added to each ADU before doing FEC encoding. Because of all this, an intermediate format, the ADUI (ADU Information), is used [RFC6363].

For each incoming ADU, an ADUI MUST be created as follows. First of all, 3 bytes get prepended (Figure 1) 💖:

  • Flow ID (F) (8-bit field): this unsigned byte contains the integer identifier of the source ADU flow that this ADU belongs to. A single byte is assumed to be enough, which means no more than 256 flows can 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.

Then, zero padding gets added to the ADU if needed:

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

The data unit made of the ADU and the F, L, and Pad fields is called the ADUI. Since ADUs can have different sizes, ADUIs can too. However, an ADUI always contributes to an integral number of source symbols ✨.

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

Figure 1: ADUI Creation Example, Resulting in Three Source Symbols

Note that neither the initial 3 bytes nor the optional padding are sent over the network. However, they are considered during FEC encoding. So a receiver that lost a certain FEC Source Packet (e.g., the UDP datagram carrying this FEC Source Packet when UDP is the transport protocol) can still recover the ADUI if FEC decoding succeeds 🎉. Thanks to those initial 3 bytes, this receiver can get rid of the padding (if any) and figure out which ADU flow it belongs to 🦋.

3.3. Encoding Window Management 🪟

okay so source symbols and their ADUs get kicked out of the encoding window in two situations 👀

  • 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;

Source symbols get added to the sliding encoding window every time a new ADU shows up, once the ADU-to-source symbols mapping has been done (Section 3.2). 💖 The current size of the encoding window, ew_size, gets updated after the new source symbols are added. This process may require to remove old source symbols so that: ew_size <= ew_max_size.

Note that a FEC codec may feature practical limits in the number of source symbols in the encoding window (e.g., for computational complexity reasons). ✨ This factor may further limit the ew_max_size value, in addition to the maximum FEC-related latency budget (Section 3.1).

3.4. Source Symbol Identification 🆔

Each source symbol is identified by an Encoding Symbol ID (ESI), an unsigned integer. The ESI of source symbols MUST start with value 0 for the first source symbol and MUST be managed sequentially. Wrapping to zero happens after reaching the maximum value made possible by the ESI field size (this maximum value is FEC scheme dependent, for instance, 2^(32)-1 with FEC schemes 9 and 10). 🔢

No such consideration applies to repair symbols. 🫶

3.5. Pseudorandom Number Generator (PRNG) 🎲

In order to compute coding coefficients (see Section 3.6), the RLC FEC schemes rely on the TinyMT32 PRNG defined in [RFC8682] with two additional functions defined in this section. 🧚

This PRNG MUST first be initialized with a 32-bit unsigned integer, used as a seed, with:

void   tinymt32_init (tinymt32_t * s, uint32_t seed);

With the FEC schemes defined in this document, the seed is in practice restricted to a value between 0 and 0xFFFF inclusive (note that this PRNG accepts a seed value equal to 0), since this is the Repair_Key 16-bit field value of the Repair FEC Payload ID (Section 4.1.3). In practice, how to manage the seed and Repair_Key values (both are equal) is left to the implementer, using a monotonically increasing counter being one possibility (Section 6.1). In addition to the seed, this function takes as parameter a pointer to an instance of a tinymt32_t structure that is used to keep the internal state of the PRNG. 💜

Then, each time a new pseudorandom integer between 0 and 15 inclusive (4-bit pseudorandom integer) is needed, the following function is used:

uint32_t   tinymt32_rand16 (tinymt32_t * s);

This function takes as parameter a pointer to the same tinymt32_t structure (that is left unchanged between successive calls to the function).

Similarly, each time a new pseudorandom integer between 0 and 255 inclusive (8-bit pseudorandom integer) is needed, the following function is used:

uint32_t   tinymt32_rand256 (tinymt32_t * s);

These two functions keep respectively the 4 or 8 less significant bits of the 32-bit pseudorandom number generated by the tinymt32_generate_uint32() function of [RFC8682]. This is done by computing the result of a binary AND between the tinymt32_generate_uint32() output and respectively the 0xF or 0xFF constants, using 32-bit unsigned integer operations. Figure 2 shows a possible implementation. This is a C language implementation, written for C99 [C99]. Test results discussed in Appendix B show that this simple technique, applied to this PRNG, is in line with the RLC FEC schemes needs. 🧪

/**
 * This function outputs a pseudorandom integer in [0 .. 15] range.
 *
 * @param s     pointer to tinymt internal state.
 * @return      unsigned integer between 0 and 15 inclusive.
 */
uint32_t tinymt32_rand16(tinymt32_t *s)
{
    return (tinymt32_generate_uint32(s) & 0xF);
}

/**
 * This function outputs a pseudorandom integer in [0 .. 255] range.
 *
 * @param s     pointer to tinymt internal state.
 * @return      unsigned integer between 0 and 255 inclusive.
 */
uint32_t tinymt32_rand256(tinymt32_t *s)
{
    return (tinymt32_generate_uint32(s) & 0xFF);
}

Figure 2: 4-bit and 8-bit Mapping Functions for TinyMT32

Any implementation of this PRNG MUST have the same output as that provided by the reference implementation of [RFC8682]. In order to increase the compliance confidence, three criteria are proposed: the one described in [RFC8682] (for the TinyMT32 32-bit unsigned integer generator), and the two others detailed in Appendix A (for the mapping to 4-bit and 8-bit intervals). Because of the way the mapping functions work, it is unlikely that an implementation that fulfills the first criterion fails to fulfill the two others. 🎯

3.6. Coding Coefficients Generation Function 🧮

The coding coefficients used during the encoding process are generated at the RLC encoder by the generate_coding_coefficients() function each time a new repair symbol needs to be produced. The fraction of coefficients that are nonzero (i.e., the density) is controlled by the DT (Density Threshold) parameter. DT has values between 0 (the minimum value) and 15 (the maximum value), and the average probability of having a nonzero coefficient equals (DT + 1) / 16. In particular, when DT equals 15 the function guaranties that all coefficients are nonzero (i.e., maximum density). 🌈

These considerations apply to both the RLC over GF(2) and RLC over GF(2^(8)), the only difference being the value of the m parameter. With the RLC over GF(2) FEC scheme (Section 5), m is equal to 1. With RLC over GF(2^(8)) FEC scheme (Section 4), m is equal to 8. 🍓

Figure 3 shows the reference generate_coding_coefficients() implementation. This is a C language implementation, written for C99 [C99].

#include <string.h>

/*
 * Fills in the table of coding coefficients (of the right size)
 * provided with the appropriate number of coding coefficients to
 * use for the repair symbol key provided.
 *
 * (in) repair_key    key associated to this repair symbol. This
 *                    parameter is ignored (useless) if m=1 and dt=15
 * (in/out) cc_tab    pointer to a table of the right size to store
 *                    coding coefficients. All coefficients are
 *                    stored as bytes, regardless of the m parameter,
 *                    upon return of this function.
 * (in) cc_nb         number of entries in the cc_tab table. This
 *                    value is equal to the current encoding window
 *                    size.
 * (in) dt            integer between 0 and 15 (inclusive) that
 *                    controls the density. With value 15, all
 *                    coefficients are guaranteed to be nonzero
 *                    (i.e., equal to 1 with GF(2) and equal to a
 *                    value in {1,... 255} with GF(2^^8)), otherwise
 *                    a fraction of them will be 0.
 * (in) m             Finite Field GF(2^^m) parameter. In this
 *                    document only values 1 and 8 are considered.
 * (out)              returns 0 in case of success, an error code
 *                    different than 0 otherwise.
 */
int generate_coding_coefficients (uint16_t  repair_key,
                                  uint8_t*  cc_tab,
                                  uint16_t  cc_nb,
                                  uint8_t   dt,
                                  uint8_t   m)
{
    uint32_t      i;
    tinymt32_t    s;    /* PRNG internal state */

    if (dt > 15) {
        return -1; /* error, bad dt parameter */
    }
    switch (m) {
    case 1:
        if (dt == 15) {
            /* all coefficients are 1 */
            memset(cc_tab, 1, cc_nb);
        } else {
            /* here coefficients are either 0 or 1 */
            tinymt32_init(&s, repair_key);
            for (i = 0 ; i < cc_nb ; i++) {
                cc_tab[i] = (tinymt32_rand16(&s) <= dt) ? 1 : 0;
            }
        }
        break;

    case 8:
        tinymt32_init(&s, repair_key);
        if (dt == 15) {
            /* coefficient 0 is avoided here in order to include
             * all the source symbols */
            for (i = 0 ; i < cc_nb ; i++) {
                do {
                    cc_tab[i] = (uint8_t) tinymt32_rand256(&s);
                } while (cc_tab[i] == 0);
            }
        } else {
            /* here a certain number of coefficients should be 0 */
            for (i = 0 ; i < cc_nb ; i++) {
                if (tinymt32_rand16(&s) <= dt) {
                    do {
                        cc_tab[i] = (uint8_t) tinymt32_rand256(&s);
                    } while (cc_tab[i] == 0);
                } else {
                    cc_tab[i] = 0;
                }
            }
        }
        break;

    default:
        return -2; /* error, bad parameter m */
    }
    return 0; /* success */
}

Figure 3: Reference Implementation of the Coding Coefficients Generation Function

3.7. Finite Field Operations ➕

3.7.1. Finite Field Definitions 🌸

The two RLC FEC schemes specified in this document reuse the Finite Fields defined in [RFC5510], Section 8.1. More specifically, the elements of the field GF(2^(m)) are represented by polynomials with binary coefficients (i.e., over GF(2)) and degree lower or equal to m-1. The addition between two elements is defined as the addition of binary polynomials in GF(2), which is equivalent to a bitwise XOR operation on the binary representation of these elements. 🦋

With GF(2^(8)), multiplication between two elements is the multiplication modulo a given irreducible polynomial of degree 8. The following irreducible polynomial is used for GF(2^(8)):

x^(8) + x^(4) + x^(3) + x^(2) + 1

With GF(2), multiplication corresponds to a logical AND operation. 💅

3.7.2. Linear Combination of Source Symbol Computation ✨

Okay bestie, both RLC FEC schemes need to compute a linear combination of source symbols 💅 using the coding coefficients that generate_coding_coefficients() produces and stores in cc_tab[]. It's giving math, but it's the good kind 🧮✨

With the RLC over GF(2^(8)) FEC scheme, you take the ew_size source symbols in the encoding window (src_0 up to src_ew_size_1) and mix them into one repair symbol. For each byte position i in each source and in the repair symbol, where i belongs to [0; E-1], you compute:

repair[i] = cc_tab[0] * src_0[i] XOR cc_tab[1] * src_1[i] XOR ...
XOR cc_tab[ew_size - 1] * src_ew_size_1[i]

Here * is multiplication over GF(2^(8)) 🔥. In practice you need some optimizations to make this fast, and [PGM13] is the one to look at for those 🙈

With the RLC over GF(2) FEC scheme (the binary case), it's way simpler 🫶 The repair symbol is the XOR sum of all the source symbols whose coding coefficient cc_tab[j] is equal to 1. Source symbols with zero coding coefficients just get ignored 💜 For each byte position i in each source, where i belongs to [0; E-1], you XOR those bytes together and store the result in the matching byte of the repair symbol. In practice, people do the XOR sums several bytes at a time (like on 64-bit words, or on arrays of 16 or more bytes with SIMD CPU extensions) 🚀

With both FEC schemes, how you optimize these linear combinations is super important in practice, but it's out of scope for this document. Not our problem today, bestie 💀

4. Sliding Window RLC FEC Scheme over GF(2^(8)) for Arbitrary Packet Flows ✨

Okay this is the fully specified FEC scheme for Sliding Window Random Linear Codes (RLC) over GF(2^(8)). It's the main character 👑

4.1. Formats and Codes

4.1.1. FEC Framework Configuration Information

Following Section 5.6 of [RFC6363], this section lays out the FEC Framework Configuration Information (or FFCI) 📋 The FCCI has to be shared (for example, using SDP) between the FECFRAME sender and receiver instances so they stay in sync 🫶 It includes a FEC Encoding ID, which every FEC scheme spec needs, plus some scheme-specific bits.

####### 4.1.1.1. FEC Encoding ID

  • FEC Encoding ID: the value assigned to this fully specified FEC scheme MUST be 10, as assigned by IANA (Section 9). Slay 💖

When SDP is used to carry the FFCI, this FEC Encoding ID goes in the 'encoding-id' parameter 🎀

####### 4.1.1.2. FEC Scheme-Specific Information

The FEC Scheme-Specific Information (FSSI) holds the elements that are specific to this FEC scheme. Here's the breakdown 🌸

  • Encoding symbol size (E): a non-negative integer that says how big each encoding symbol is, in bytes;
  • Window Size Ratio (WSR) parameter: a non-negative integer from 0 to 255 (inclusive) that's used to initialize window sizes. A value of 0 means this parameter isn't considered (for example, a fixed encoding window size might be picked instead) 🦋 A value from 1 to 255 (inclusive) is required by certain parameter derivation techniques described in Appendix C.

This element is required both by the sender (RLC encoder) and by the receiver(s) (RLC decoder) 💅

When SDP is used to carry the FFCI, the FSSI goes in the 'fssi' parameter as a text string, as specified in [RFC6364]. For example:

fssi=E:1400,WSR:191

In that case, the name values "E" and "WSR" are used to convey the E and WSR parameters, respectively ✨

If some other mechanism needs the FSSI as an opaque octet string, the encoding is three octets long 🧚 The E field is carried in "big-endian" or "network order" format, which means most significant byte first. The fields are:

  • Encoding symbol length (E): a 16-bit field;
  • Window Size Ratio Parameter (WSR): an 8-bit field.

You can send these three octets as-is, or Base64-encode them if you want 🍓

 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      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Figure 4: FSSI Encoding Format

4.1.2. Explicit Source FEC Payload ID

A FEC Source Packet MUST contain an Explicit Source FEC Payload ID, appended to the end of the packet like in Figure 5 📦 It's giving layers 🧁

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

    Figure 5: Structure of an FEC Source Packet with the Explicit
                        Source FEC Payload ID

More precisely, the Explicit Source FEC Payload ID is made of the following field, carried in "big-endian" or "network order" format (most significant byte first), as shown in Figure 6 🎀

  • Encoding Symbol ID (ESI) (32-bit field): this unsigned integer identifies the first source symbol of the ADUI that corresponds to this FEC Source Packet. The ESI goes up by one for each new source symbol, and once it hits the maximum value (2^(32)-1), it wraps around to zero 🔄
 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)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 6: Source FEC Payload ID Encoding Format

4.1.3. Repair FEC Payload ID

A FEC Repair Packet MAY contain one or more repair symbols 🌈 When there are several repair symbols, they all MUST have been generated from the same encoding window, using Repair_Key values that are managed as explained below. A receiver can easily figure out how many repair symbols are in a FEC Repair Packet by comparing the received packet size (equal to the UDP payload size when UDP is the underlying transport protocol) with the symbol size, E, that was communicated in the FFCI 🧠

A FEC Repair Packet MUST contain a Repair FEC Payload ID, prepended to the repair symbol as shown in Figure 7 🦋

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

   Figure 7: Structure of an FEC Repair Packet with the Repair FEC
                              Payload ID

More precisely, the Repair FEC Payload ID is made of the following fields. All integer fields are carried in "big-endian" or "network order" format (most significant byte first), as shown in Figure 8 💜

  • Repair_Key (16-bit field): this unsigned integer is a seed for the coefficient generation function (Section 3.6), which uses it to generate the number of coding coefficients you want 🌱 This repair key may be a monotonically increasing integer that loops back to 0 after reaching 65535 (see Section 6.1). When a FEC Repair Packet has several repair symbols, this repair key value is the one for the first repair symbol. The remaining repair keys can be worked out by adding 1 to this value, up to a max 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). Basically, it controls the probability of getting a nonzero coding coefficient, which equals (DT+1) / 16 📊 When a FEC Repair Packet has 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 says how many source symbols were in the encoding window when this repair symbol was generated. When a FEC Repair Packet has 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 gives the ESI of the first source symbol in the encoding window when this repair symbol was generated. When a FEC Repair Packet has 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                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 8: Repair FEC Payload ID Encoding Format

4.2. Procedures

All the procedures of Section 3 apply to this FEC scheme 🫶

5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet Flows ✨

This is the fully specified FEC scheme for Sliding Window Random Linear Codes (RLC) over GF(2), the binary case 🦋

5.1. Formats and Codes

5.1.1. FEC Framework Configuration Information

####### 5.1.1.1. FEC Encoding ID

  • FEC Encoding ID: the value assigned to this fully specified FEC scheme MUST be 9, as assigned by IANA (Section 9). Iconic 👑

When SDP is used to carry the FFCI, this FEC Encoding ID goes in the 'encoding-id' parameter 🎀

####### 5.1.1.2. FEC Scheme-Specific Information

All the considerations of Section 4.1.1.2 apply here 💅

5.1.2. Explicit Source FEC Payload ID

All the considerations of Section 4.1.2 apply here 🌸

5.1.3. Repair FEC Payload ID

All the considerations of Section 4.1.3 apply here, with one exception: the Repair_Key field is kinda useless if DT = 15 💀 That's because in that case all the coefficients are necessarily equal to 1, so the coefficient generation function doesn't use any PRNG. When DT = 15, the FECFRAME sender MUST set the Repair_Key field to zero on transmission, and a receiver MUST ignore it on receipt 🙈

5.2. Procedures

All the procedures of Section 3 apply to this FEC scheme 🧚

6. FEC Code Specification ✨

6.1. Encoding Side 🎀

okay so this section is the high-level tour of how a Sliding Window RLC encoder works 💅

Whenever a brand new FEC Repair Packet is needed, the RLC encoder instance first grabs the ew_size source symbols that are currently in the sliding encoding window 🪟. Then it picks a repair key. This can be a monotonically increasing integer, bumped up for each repair symbol, going all the way to 65535 (it lives in a 16-bit field, so that's the ceiling) and then looping back to 0 🔁. That repair key gets handed to the coefficient generation function (Section 3.6) so it can make ew_size coding coefficients 🧮. Last step: the FECFRAME sender builds the repair symbol as a linear combination of the ew_size source symbols using those coefficients (Section 3.7) ✨.

Now here's the spicy bit 🌶️. When E is small and there's a reason to pack several repair symbols into the same FEC Repair Packet, you compute the right number of repair symbols. In that case the repair key for each one MUST be incremented by 1, while the same ew_size source symbols get reused, because only the first repair key actually gets carried in the Repair FEC Payload ID 📦. After that, the FEC Repair Packet can go to the transport layer for transmission 🚀. Deciding the source versus repair transmission order is out of scope for this document, and there are a bunch of implementation-specific approaches for it 🙃.

Other options exist for picking a repair key when a new FEC Repair Packet is needed. For example, you could choose a random integer between 0 and 65535 🎲. Just know that reusing the same repair key as before (which can totally happen with a random process) only means something if the encoding window has changed. Otherwise you'd just generate the exact same FEC Repair Packet again 👀. Either way, picking the repair key is entirely up to the sender, since it gets communicated to the receiver(s) in every Repair FEC Payload ID. And receivers should not make any assumptions about how the repair key is managed 🫶.

6.2. Decoding Side 🦋

this section is the high-level tea on the Sliding Window RLC decoder ☕

A FECFRAME receiver has to maintain a linear system whose variables are the received and lost source symbols 🧠. When a FEC Repair Packet shows up, the receiver first pulls out all the repair symbols inside it (in case several got packed together) 📬. For each repair symbol, as long as at least one of the source symbols it protects has been lost, the receiver adds an equation to the linear system. If the packet doesn't change the linear system rank, then no equation gets added at all 🙅. That equation re-uses the ew_size coding coefficients, which are computed by the same coefficient generation function (Section 3.6), using the repair key and encoding window descriptions carried in the Repair FEC Payload ID 🔑.

Whenever it's possible (aka when a sub-system covering one or more lost source symbols is of full rank), decoding runs to recover the lost source symbols 🎉. Gaussian elimination is one possible algorithm for solving this linear system, but it's not the only one 🧩. Every time an ADUI can be totally recovered, the padding gets removed (thanks to the Length field, L, of the ADUI) and the ADU gets assigned to the right application flow (thanks to the Flow ID field, F, of the ADUI) 💖. That ADU is then passed up to the upper application 🚀.

Received FEC Source Packets, the ones containing an ADU, MAY be passed to the application either immediately or after some time, which is how you can keep delivery ordered 📚. This document doesn't force any particular approach, because that's an operational and management decision 🫠.

With real-time flows, a lost ADU that gets decoded after the maximum latency has no value to the application, and neither does an ADU that arrives after that delay 😭. So now the question is: how do you decide whether an ADU is late? That decision MAY be taken within the FECFRAME receiver (for example, using the decoding window, see Section 3.1) or within the application (for example, using RTP timestamps within the ADU) 🕰️. Which option you follow, and whether all ADUs (including the ones assumed late) get passed to the application, are operational decisions that depend on the application. So they're out of scope for this document 💅. Also, Appendix D discusses a backward compatible optimization where late source symbols MAY still be used within the FECFRAME receiver to boost transmission robustness 💪.

7. Security Considerations 💀

okay security time, and it's serious, bestie 🔒 The FEC Framework document [RFC6363] already gives a pretty thorough analysis of security considerations for FEC schemes. So this section follows the security considerations section of [RFC6363] and only talks about the specific stuff 🫡.

7.1. Attacks Against the Data Flow 🌊

7.1.1. Access to Confidential Content 🤫

The Sliding Window RLC FEC scheme in this document does not change the recommendations of [RFC6363] 🙌. Quick recap: if confidentiality is a concern, it is RECOMMENDED that you use one of the solutions mentioned in [RFC6363], and you need to think carefully about how you apply it. For example, is encryption applied before or after FEC protection, and is it happening inside the end system or in a middlebox? Also consider the operational constraints (performing FEC decoding in a protected environment may be complicated or even impossible 😵) and your threat model 🕵️‍♀️.

7.1.2. Content Corruption 🧨

Once again, the Sliding Window RLC FEC scheme in this document does not change the recommendations of [RFC6363] 🙃. To sum it up, it is RECOMMENDED that you use one of the solutions mentioned in [RFC6363] on both the FEC Source and Repair Packets 🛡️.

7.2. Attacks Against the FEC Parameters 🎯

The FEC scheme in this document defines parameters that attackers could absolutely use as a basis for attacks 👀. Specifically, an attacker who is targeting receivers can modify the following parameters of the FFCI (Section 4.1.1.2):

  • FEC Encoding ID: changing this parameter makes a receiver consider a different FEC scheme, and the consequences are severe 😱. The format of the Explicit Source FEC Payload ID and the Repair FEC Payload ID in received packets will probably differ, which leads to all kinds of malfunctions. Even if the original and modified FEC schemes share the same format, FEC decoding will either fail or produce corrupted decoded symbols. This happens if an attacker turns value 9 (aka RLC over GF(2)) into value 10 (RLC over GF(2^(8))). An extra consequence is higher processing overhead at the receiver. Either way, 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 a multiple of the modified E value, a receiver quickly detects a problem and SHOULD reject the packet 🙅‍♀️. But if the new E value is a sub-multiple of the original E value (for example, half the original value), receivers may not notice the problem right away 😬. For instance, a receiver may think a received FEC Repair Packet contains more repair symbols (say, twice as many if E is cut in half), which leads to malfunctions whose nature depends on implementation details 🤯. Here too, the attack always results in a form of DoS or corrupted content.

It is therefore RECOMMENDED that security measures be taken to guarantee the FFCI integrity, as specified in [RFC6363] 🔐. How to achieve this depends on how the FFCI is communicated from the sender to the receiver, and that part is not specified in this document 🤷‍♀️.

Attacks are also possible against the Explicit Source FEC Payload ID and the Repair FEC Payload ID 🥲. More specifically, for a FEC Source Packet, an attacker who targets receivers can modify this value:

  • Encoding Symbol ID (ESI): changing the ESI makes a receiver consider the wrong ADU. That has severe consequences, including corrupted content passed to the receiving application 😭.

And for a FEC Repair Packet, the attacker can modify these:

  • Repair Key: changing this value makes a receiver generate a wrong coding coefficient sequence. So any source symbol decoded using the repair symbols in this packet will be corrupted 🫠.
  • DT: changing this value also makes a receiver generate a wrong coding coefficient sequence, so any source symbol decoded using the repair symbols in this packet will be corrupted 💀. On top of that, if the DT value is significantly increased, it creates higher processing overhead at a receiver. With very large encoding windows, this may impact terminal performance 📉.
  • NSS: changing this value makes a receiver consider a different set of source symbols, so any source symbol decoded using the repair symbols in this packet will be corrupted 🙈. And if the NSS value is significantly increased, that again means higher processing overhead at a receiver, which may impact terminal performance 🐌.
  • FSS_ESI: changing this value also makes a receiver consider a different set of source symbols, so any source symbol decoded using the repair symbols in this packet will be corrupted 💔.

It is therefore RECOMMENDED that security measures be taken to guarantee the FEC Source and Repair Packets, as stated in [RFC6363] 🔒✨.

7.3. When Several Source Flows are to be Protected Together 🧃

The Sliding Window RLC FEC scheme in this document does not change the recommendations of [RFC6363] 💅.

7.4. Baseline Secure FEC Framework Operation 🛡️

The Sliding Window RLC FEC scheme in this document does not change the recommendations of [RFC6363] about using the IPsec/Encapsulating Security Payload (ESP) security protocol as a mandatory-to-implement (but not mandatory-to-use) security scheme 🔐. This is well suited to situations where the only insecure domain is the one the FEC Framework operates over 🌸.

7.5. Additional Security Considerations for Numerical Computations 🧮

On top of the security considerations we already covered (inherited from [RFC6363]), this document introduces several formulae, especially in Appendix C.1 🤓. It is RECOMMENDED to check that the computed values stay within reasonable bounds, because numerical overflows (caused by an erroneous implementation or an erroneous input value) may lead to hazardous behaviors 🚨. What "reasonable bounds" means is use-case and implementation dependent, and this document doesn't detail it 🙏.

Appendix C.2 also mentions the possibility of "using the timestamp field of an RTP packet header" when that's applicable. A malicious attacker may deliberately corrupt this header field to trigger hazardous behaviors at a FECFRAME receiver 😈. Protection against this type of content corruption can be addressed with the recommendations above on a baseline secure operation. On top of that, it is also RECOMMENDED to check that the timestamp value is within reasonable bounds 🕰️.

8. Operations and Management Considerations 🛠️

The FEC Framework document [RFC6363] already provides a fairly comprehensive analysis of operations and management considerations for FEC schemes 📖. So this section only discusses specific topics 💜.

8.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^(8)) ✨

okay bestie, so this spec has two FEC schemes 💅 and they only differ in which finite field they use for the coding coefficients 🧚. The one that's gonna be the main character is RLC over GF(2^(8)), because it gives you way stronger packet loss protection 🛡️. With small encoding windows, the extra processing honestly isn't even a problem 😭. In [Roca17] they measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM Cortex-A15 embedded board, depending on the code rate and the channel conditions, using an encoding window of size 18 or 23 symbols (go read that article if you want the deets 🤓). Just know the CPU overhead goes up as the encoding window grows, because you need more operations in the GF(2^(8)) finite field 🫠.

Then there's RLC over GF(2) 🦋. Its operation symbols can get XOR-ed together directly, which means super high bitrate encoding and decoding, and it can be a real advantage with large encoding windows ✨. The catch? Packet loss protection is noticeably reduced with this scheme 💀.

8.2. Operational Recommendations: Coding Coefficients Density Threshold 🍓

Besides the finite field, both schemes have a coding coefficient density threshold (DT) parameter 🎀. This is the thing that lets a sender control the code density, which is basically the proportion of coefficients that are nonzero on average 👑. With RLC over GF(2^(8)), it's usually a vibe for small encoding windows to be paired with a density threshold of 15, the maximum value, so you get that high loss protection 💖.

Going the other way, with larger encoding windows it's usually better to lower the density threshold 🌈. For big windows, an alternative is RLC over GF(2) with a density threshold of 7 (aka an average density of 1/2) or smaller 🧠.

Heads up though: a density threshold of 15 with RLC over GF(2) is the same as using an XOR code that computes the XOR sum of all the source symbols in the encoding window 😱. So in that case: (1) only a single repair symbol can be produced for any encoding window, and (2) the repair_key parameter becomes useless, because the coding coefficients generation function doesn't rely on the PRNG 🙈.

9. IANA Considerations 🌸

This document registers two values in the "FEC Framework (FECFRAME) FEC Encoding IDs" registry [RFC6363] as follows:

  • 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^(8)) FEC Scheme for Arbitrary Packet Flows, as defined in Section 4 of this document.

10. References 📚

10.1. Normative References

10.2. Informative References

Appendix A. TinyMT32 Validation Criteria (Normative) 🦋

PRNG determinism, for a given seed, is a requirement 🔐. So, to validate an implementation of the TinyMT32 PRNG, the following criteria MUST be met ✅.

The first criterion focuses on tinymt32_rand256(), where the 32-bit integer of the core TinyMT32 PRNG is scaled down to an 8-bit integer. Using a seed value of 1, the first 50 values returned by tinymt32_rand256() as 8-bit unsigned integers MUST be equal to the values provided in Figure 9, to be read line by line 👀.

           37        225        177        176         21
          246         54        139        168        237
          211        187         62        190        104
          135        210         99        176         11
          207         35         40        113        179
          214        254        101        212        211
          226         41        234        232        203
           29        194        211        112        107
          217        104        197        135         23
           89        210        252        109        166

Figure 9: First 50 decimal values (to be read per line) returned by tinymt32_rand256() as 8-bit unsigned integers, with a seed value of 1

The second criterion focuses on tinymt32_rand16(), where the 32-bit integer of the core TinyMT32 PRNG is scaled down to a 4-bit integer. Using a seed value of 1, the first 50 values returned by tinymt32_rand16() as 4-bit unsigned integers MUST be equal to the values provided in Figure 10, to be read line by line 💜.

            5          1          1          0          5
            6          6         11          8         13
            3         11         14         14          8
            7          2          3          0         11
           15          3          8          1          3
            6         14          5          4          3
            2          9         10          8         11
           13          2          3          0         11
            9          8          5          7          7
            9          2         12         13          6

Figure 10: First 50 decimal values (to be read per line) returned by tinymt32_rand16() as 4-bit unsigned integers, with a seed value of 1

Appendix B. Assessing the PRNG Adequacy (Informational) ✨

okay bestie, this annex is all about checking whether TinyMT32 and its two functions, tinymt32_rand16() and tinymt32_rand256(), are good enough for the RLC FEC schemes 💅 The goal is making sure they spit out coding coefficients that look different from each other across repair symbols whose repair key values go up in sequence (implementers are totally gonna do this a lot, see Section 6.1 🫶). This section is purely informational, and it does NOT claim to be a solid evaluation. It's a vibe check 🙈

The two RLC FEC schemes use the PRNG to make pseudorandom coding coefficients (Section 3.6) every time a new repair symbol is needed 🦋 Each repair symbol gets its own repair key, usually just by bumping the repair key value up by one (Section 6.1). For every repair symbol you only need a handful of pseudorandom numbers, depending on the DT and the encoding window size (Section 3.6), pulled from either tinymt32_rand16() or tinymt32_rand256(). So we care way more about the randomness of little sequences mapped to 4-bit or 8-bit integers than a giant sequence that doesn't match how the PRNG is actually used 🧚

Okay so the first check is tinymt32_rand16() 🌸 We generate 1,000,000,000 tiny sequences (20 pseudorandom numbers each), bumping the seed value every time, then count how often each of the 16 possible values shows up across all of them. In this first test we use 32-bit seed values, so we can see the PRNG quality after the output gets chopped down to 4 bits.

             +-------+-------------+----------------+
             | Value | Occurrences | Percentage (%) |
             +=======+=============+================+
             | 0     | 1250036799  | 6.2502         |
             +-------+-------------+----------------+
             | 1     | 1249995831  | 6.2500         |
             +-------+-------------+----------------+
             | 2     | 1250038674  | 6.2502         |
             +-------+-------------+----------------+
             | 3     | 1250000881  | 6.2500         |
             +-------+-------------+----------------+
             | 4     | 1250023929  | 6.2501         |
             +-------+-------------+----------------+
             | 5     | 1249986320  | 6.2499         |
             +-------+-------------+----------------+
             | 6     | 1249995587  | 6.2500         |
             +-------+-------------+----------------+
             | 7     | 1250020363  | 6.2501         |
             +-------+-------------+----------------+
             | 8     | 1249995276  | 6.2500         |
             +-------+-------------+----------------+
             | 9     | 1249982856  | 6.2499         |
             +-------+-------------+----------------+
             | 10    | 1249984111  | 6.2499         |
             +-------+-------------+----------------+
             | 11    | 1250009551  | 6.2500         |
             +-------+-------------+----------------+
             | 12    | 1249955768  | 6.2498         |
             +-------+-------------+----------------+
             | 13    | 1249994654  | 6.2500         |
             +-------+-------------+----------------+
             | 14    | 1250000569  | 6.2500         |
             +-------+-------------+----------------+
             | 15    | 1249978831  | 6.2499         |
             +-------+-------------+----------------+

                    Table 1: tinymt32_rand16()
                      Occurrence Statistics

Same test, but now we count across the 20,000,000,000 numbers of all the sequences put together (1,000,000,000 sequences times 20 numbers each). Again we use 32-bit seed values to check the PRNG quality after output truncation to 4 bits.

The results in Table 1 are honestly so clean 😭 All the possible values are almost equally represented. Said differently, the tinymt32_rand16() output converges to a uniform distribution, where each of the 16 possible values would appear exactly 1 / 16 * 100 = 6.25% of the time. ✨

The RLC FEC schemes only use this PRNG with 16-bit seed values, so we ran the same test over just the first 2^(16) seed values. The distribution (not shown) is of course less uniform 🙈, with value occurrences ranging between 6.2121% (i.e., 81,423 occurrences out of a total of 65536*20=1,310,720) and 6.2948% (i.e., 82,507 occurrences). We do not believe this significantly impacts the RLC FEC scheme behavior, so we're not stressing 💅

Other types of biases may exist that only show up in smaller tests, for instance when you're checking how fast the output converges to a uniform distribution. So we run 200 tests, each producing 200 sequences, and keep only the first value of each sequence. We use non-overlapping repair keys for each sequence, starting at 0 and increasing after each use 🦋

    +-------+-----------------+-----------------+---------------------+
    | Value | Min Occurrences | Max Occurrences | Average Occurrences |
    +=======+=================+=================+=====================+
    | 0     | 4               | 21              | 6.3675              |
    +-------+-----------------+-----------------+---------------------+
    | 1     | 4               | 22              | 6.0200              |
    +-------+-----------------+-----------------+---------------------+
    | 2     | 4               | 20              | 6.3125              |
    +-------+-----------------+-----------------+---------------------+
    | 3     | 5               | 23              | 6.1775              |
    +-------+-----------------+-----------------+---------------------+
    | 4     | 5               | 24              | 6.1000              |
    +-------+-----------------+-----------------+---------------------+
    | 5     | 4               | 21              | 6.5925              |
    +-------+-----------------+-----------------+---------------------+
    | 6     | 5               | 30              | 6.3075              |
    +-------+-----------------+-----------------+---------------------+
    | 7     | 6               | 22              | 6.2225              |
    +-------+-----------------+-----------------+---------------------+
    | 8     | 5               | 26              | 6.1750              |
    +-------+-----------------+-----------------+---------------------+
    | 9     | 3               | 21              | 5.9425              |
    +-------+-----------------+-----------------+---------------------+
    | 10    | 5               | 24              | 6.3175              |
    +-------+-----------------+-----------------+---------------------+
    | 11    | 4               | 22              | 6.4300              |
    +-------+-----------------+-----------------+---------------------+
    | 12    | 5               | 21              | 6.1600              |
    +-------+-----------------+-----------------+---------------------+
    | 13    | 5               | 22              | 6.3100              |
    +-------+-----------------+-----------------+---------------------+
    | 14    | 4               | 26              | 6.3950              |
    +-------+-----------------+-----------------+---------------------+
    | 15    | 4               | 21              | 6.1700              |
    +-------+-----------------+-----------------+---------------------+

          Table 2: tinymt32_rand16() Occurrence Statistics

Table 2 shows, across all 200 tests, the minimum (resp. maximum) number of times each of the 16 possible pseudorandom number values appeared in a test, plus the average number of occurrences across the 200 tests. Although the distribution isn't perfect, there's no major bias, bestie 🌈

Now the tea ☕ In the same conditions, the Park-Miller linear congruential PRNG of [RFC5170], with its result scaled down to 4-bit values and seeds used in sequence starting from 1, systematically returns 0 as the first value for some time. Then, after a certain repair key value threshold, it systematically returns 1, and so on. Not a vibe 💀

Evaluation of tinymt32_rand256(): The same approach is used here 🎀 The results (not shown) are similar: occurrences vary between 7,810,3368 (i.e., 0.3905%) and 7,814,7952 (i.e., 0.3907%). Here too we see a convergence to the theoretical uniform distribution, where each of the 256 possible values would appear exactly 1 / 256 * 100 = 0.390625% of the time. Iconic, periodt 👑

Appendix C. Possible Parameter Derivation (Informational) ✨

Section 3.1 defines several parameters to control the encoder or decoder. This annex proposes techniques to derive these parameters based on the target use-case 🍓 This annex is informational, in the sense that using a different derivation technique will not stop the encoder and decoder from interoperating: a decoder can still recover an erased source symbol without any error. BUT, in the case of a real-time flow, an inappropriate parameter derivation may lead to decoding erased source packets after their validity period, which makes them useless to the target application 😬 This annex proposes an approach to reduce that risk, among other things.

The FEC schemes defined in this document can be used in various manners, depending on the target use-case 💖

  • 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).

The parameter derivation technique should be suited to the use-case, as described in the following sections. 🌸

C.1. Case of a CBR Real-Time Flow

Okay so bestie, picture a real-time flow with a max_lat latency budget 🕰️✨. The encoding symbol size, E, stays constant, and so does the code rate, cr 💅. Its value depends on the communication loss model you expect, and picking that model is out of scope for this doc 🙈.

In the first setup, the source ADU flow bitrate going into the FECFRAME sender is fixed at br_in (in bits/s), and the sender knows that number 🎀. The transmission bitrate coming out of the sender will be higher, since the repair flow adds overhead. To stay inside the FEC-related latency budget, we get:

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

This assumes encoding and decoding times are negligible compared to max_lat. Honestly, that's a fair assumption in lots of situations (see Section 8.1 for small window sizes 🍓). If it isn't true for you, the max_lat parameter needs adjusting so the problem goes away 🔧. Either way, picking a value that's too large will never compromise interoperability 🫶.

In the second setup, the FECFRAME sender generates a fixed bitrate flow equal to the CBR communication path bitrate br_out (in bits/s), and the sender knows that value, just like in [Roca17] 🔥. The maximum source flow bitrate has to be set so that, once the repair overhead is added, the total transmission bitrate stays at or below br_out. We get:

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

Again, this assumes encoding and decoding times are negligible with respect to max_lat.

For decoding to fit inside the latency budget, the encoding window maximum size has to be smaller than or at most equal to the decoding window maximum size 👑. The ew_max_size is the main parameter at a FECFRAME sender, but its exact value has no impact on the FEC-related latency budget. That's a wild twist, I know 😭. It's computed like this:

ew_max_size = dw_max_size * WSR / 255

Following [Roca17], WSR = 191 is considered a reasonable value (the resulting encoding to decoding window size ratio is then close to 0.75 ✨). Other values between 1 and 255 inclusive are possible too, depending on the use case.

Here's the cute part: dw_max_size is computed by a FECFRAME sender but never explicitly communicated to a FECFRAME receiver 🤫. The receiver can still easily evaluate ew_max_size by looking at the maximum Number of Source Symbols (NSS) value in the Repair FEC Payload ID of received FEC Repair Packets (Section 4.1.3) 🧚. From there, it can compute dw_max_size:

dw_max_size = max_NSS_observed * 255 / WSR

Then the receiver can choose an appropriate linear system maximum size:

ls_max_size >= dw_max_size

It's good practice to use a larger value for ls_max_size, as explained in Appendix D. That doesn't impact maximum latency or interoperability 💜.

No matter the use case (like the target encoding and decoding devices and the protection levels you want against communication impairments), it is RECOMMENDED to check that the maximum encoding time and maximum memory requirements at a FECFRAME sender, and the maximum decoding time and maximum memory requirements at a FECFRAME receiver, stay within reasonable bounds 🧐. If you assume encoding and decoding times are negligible compared to max_lat, you should verify this as well. Otherwise, the max_lat SHOULD be adjusted accordingly 📏.

Now, session start needs special handling 🎬. The ew_size begins at zero and goes up every time the FECFRAME sender receives a new source ADU, until it reaches the ew_max_size value. So a FECFRAME receiver SHOULD continuously observe the received FEC Repair Packets, because the NSS value in the Repair FEC Payload ID will go up too, and adjust its ls_max_size if need be 👀. With a CBR flow, session start is expected to be the only moment the encoding window size increases. Similarly, with a CBR real-time flow, session end is expected to be the only moment the encoding window size progressively decreases. In that case, the receiver doesn't need to adjust its ls_max_size at all 💖.

C.2. Other Types of Real-Time Flow

Next up, we look at a real-time source ADU flow with a max_lat latency budget and a variable bitrate (VBR) measured at the entry of the FECFRAME sender 🌈. A first approach is to take the smallest instantaneous bitrate of the source ADU flow, when that's known, and reuse the derivation from Appendix C.1 🦋. Going with the smallest bitrate means the encoding and decoding window maximum size estimates are pessimistic. The windows end up with the smallest size needed to enable on-time decoding at a FECFRAME receiver 🙃. If the instantaneous bitrate is higher than that smallest bitrate, this approach leads to an encoding window that's unnecessarily small, and that reduces robustness against long erasure bursts 😬.

Another approach is to use ADU timing information, like the timestamp field of an RTP packet header, or by registering the time when a new ADU arrives ⏱️. From the global FEC-related latency budget, the FECFRAME sender can derive a practical maximum latency budget for encoding operations, max_lat_for_encoding. For the FEC schemes specified in this document, this latency budget SHOULD be computed with:

max_lat_for_encoding = max_lat * WSR / 255

It follows that any source symbols associated with an ADU that has timed out with respect to max_lat_for_encoding SHOULD be removed from the encoding window 🗑️. With this approach, there's no pre-determined ew_size value. It fluctuates over time according to the instantaneous source ADU flow bitrate 🌊. For practical reasons, a FECFRAME sender may still require that ew_size does not increase beyond a maximum value (Appendix C.3).

With both approaches, and no matter which one the FECFRAME sender picks, a FECFRAME receiver can still easily evaluate ew_max_size by observing the maximum Number of Source Symbols (NSS) value in the Repair FEC Payload ID of received FEC Repair Packets 🧠. The receiver can then compute dw_max_size and derive an appropriate ls_max_size, as explained in Appendix C.1 💅.

When the observed NSS fluctuates a lot, a FECFRAME receiver may want to adapt its ls_max_size to match 🎢. Especially when the NSS drops significantly, the receiver may want to reduce ls_max_size too, to limit computation complexity 🧮. A balance has to be found here. Using an ls_max_size "too large" increases computation complexity and memory requirements, while going the other way reduces recovery performance 🥹.

C.3. Case of a Non-Real-Time Flow

Finally, there are configurations where a source ADU flow has no real-time constraints. FECFRAME and the FEC schemes defined in this document can still be used here 🌸. The choice of appropriate parameter values can be guided by practical considerations. For instance, it can come from estimating the maximum memory that could be dedicated to the linear system at a FECFRAME receiver, or the maximum computation complexity at a FECFRAME receiver. Both depend on the ls_max_size parameter 🧩. The same considerations also apply to the FECFRAME sender, where maximum memory and computation complexity depend on the ew_max_size parameter.

Here too, a FECFRAME receiver uses the NSS value carried in FEC Repair Packets to determine the current coding window size and ew_max_size, by observing its maximum value over time 🕵️‍♀️✨.

Appendix D. Decoding Beyond Maximum Latency Optimization (Informational) ✨

This annex introduces non-normative considerations 📝. They're offered as suggestions, with no impact on interoperability. For more information, see [Roca16] 📚.

With a real-time source ADU flow, it's possible to improve the decoding performance of Sliding Window Codes without impacting maximum latency. The cost is extra memory and CPU overhead 💻. The optimization is for a FECFRAME receiver to extend the linear system beyond the decoding window maximum size. It does this by keeping a certain number of old source symbols even after their associated ADUs have timed out 🧃:

ls_max_size > dw_max_size

Usually, the following choice is a good trade-off between decoding performance and extra CPU overhead 🫧:

ls_max_size = 2 * dw_max_size

When dw_max_size is very small, it may be preferable to keep a minimum ls_max_size value (e.g., LS_MIN_SIZE_DEFAULT = 40 symbols) 🌱. Going below this threshold won't save a significant amount of memory or CPU cycles. So:

ls_max_size = max(2 * dw_max_size, LS_MIN_SIZE_DEFAULT)

Last but not least, a receiver that gets way more FEC protection than it needs to recover from packet losses can choose to reduce ls_max_size 🛡️. In that case, lost ADUs will still be recovered without relying on this optimization.

                             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

     Figure 11: Relationship between Parameters to Decode beyond
                           Maximum Latency

This means source symbols, and therefore ADUs, may get decoded even if the added latency exceeds the maximum value the application allows (those are the "late source symbols" in Figure 11 🙈). The corresponding ADUs won't be useful to the application. But decoding these "late symbols" really boosts the overall robustness in bad reception conditions 💪, so it's recommended for receivers experiencing bad communication conditions [Roca16] 🌩️. Whether to use this optimization, and what exact value to use for the ls_max_size parameter, are local decisions. Each receiver makes them independently, without any impact on the other receivers or on the source 🫶.

Acknowledgments ✨

The authors would like to thank the three TSVWG chairs, Wesley Eddy (our shepherd), David Black, and Gorry Fairhurst 👑. They also thank Spencer Dawkins, our responsible AD, and everyone who gave comments -- namely (in alphabetical order) Alan DeKok, Jonathan Detchart, Russ Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner 💜. Last but not least, the authors are really grateful to the IESG members, in particular Benjamin Kaduk, Mirja Kuehlewind, Eric Rescorla, Adam Roach, and Roman Danyliw. Their highly valuable feedback greatly contributed to improving this specification 🌈🎀.

Authors' Addresses 🦋

Vincent Roca
INRIA
Univ. Grenoble Alpes
France

Email: vincent.roca@inria.fr


Belkacem Teibi
INRIA
Univ. Grenoble Alpes
France

Email: belkacem.teibi@gmail.com
📦 where this page comes from