RFC 6816

Simple Low-Density Parity Check (LDPC) Staircase Forward Error Correction (FEC) Scheme for FECFRAME

📅 published December 2012, from ietf

Title Block 🎀

Simple Low-Density Parity Check (LDPC) Staircase Forward Error Correction (FEC) Scheme for FECFRAME is RFC 6816 💖, published by the Internet Engineering Task Force (IETF) in December 2012. The authors are V. Roca (INRIA), M. Cunche (INSA-Lyon/INRIA), and J. Lacan (ISAE, Univ. of Toulouse) ✨. It's on the Standards Track 👑, and its ISSN is 2070-1721. The title block doesn't list anything this document obsoletes or updates, so there's no drama there 🙈.

Abstract 🦋

Okay so this doc is giving a fully specified simple FEC scheme for LDPC Staircase codes, and it's built to protect media streams along the lines FECFRAME defines 🔥. These codes are systematic, they perform close to ideal codes in lots of use-cases, and they have super high encoding and decoding throughputs 💅. So they're a solid pick for protecting a single high bitrate source flow, or for protecting several mid-rate flows together within one FECFRAME instance. They're also the move whenever the processing load of a software encoder or decoder needs to stay at an absolute minimum 🧚.

Status of This Memo 📜

This is an Internet Standards Track document 👑.

It's a product of the Internet Engineering Task Force (IETF), so it represents the consensus of the IETF community ✨. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). If you want more on Internet Standards, check Section 2 of RFC 5741 🫶.

Info about the current status of this document, any errata, and how to give feedback lives at http://www.rfc-editor.org/info/rfc6816 🌸.

Copyright (c) 2012 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 (http://trustee.ietf.org/license-info) as in effect on the date of publication. Please read these carefully, bestie, because they spell out your rights and restrictions for this document 🙈. Code Components pulled out of this document must include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License ⭐.

Table of Contents 🗺️

1. Introduction ....................................................4
2. Terminology .....................................................5
3. Definitions Notations and Abbreviations .........................5
   3.1. Definitions ................................................5
   3.2. Notations ..................................................7
   3.3. Abbreviations ..............................................8
4. Common Procedures Related to the ADU Block and Source
   Block Creation ..................................................8
   4.1. Restrictions ...............................................9
   4.2. ADU Block Creation .........................................9
   4.3. Source Block Creation .....................................11
5. LDPC-Staircase FEC Scheme for Arbitrary ADU Flows ..............13
   5.1. Formats and Codes .........................................13
        5.1.1. FEC Framework Configuration Information ............13
        5.1.2. Explicit Source FEC Payload ID .....................14
        5.1.3. Repair FEC Payload ID ..............................16
   5.2. Procedures ................................................17
   5.3. FEC Code Specification ....................................17
6. Security Considerations ........................................17
   6.1. Attacks against the Data Flow .............................17
        6.1.1. Access to Confidential Content .....................17
        6.1.2. Content Corruption .................................18
   6.2. Attacks against the FEC Parameters ........................18
   6.3. When Several Source Flows Are to Be Protected Together ....19
   6.4. Baseline Secure FEC Framework Operation ...................19
7. Operations and Management Considerations .......................19
   7.1. Operational Recommendations ...............................19
8. IANA Considerations ............................................21
9. Acknowledgments ................................................21
10. References ....................................................21
    10.1. Normative References .....................................21
    10.2. Informative References ...................................22

1. Introduction 🌈

Okay so FEC codes are a classic move for improving reliability of unicast, multicast, and broadcast Content Delivery Protocols (CDPs) and applications [RFC3453] 💖. "Forward Error Correction (FEC) Framework" [RFC6363] is a generic framework for using FEC schemes with media delivery apps, like real-time streaming based on the RTP real-time protocol 🎀. Then "Forward Error Correction (FEC) Building Block" [RFC5052] is the generic framework for using FEC schemes with object delivery apps (think files), based on either Asynchronous Layered Coding (ALC) [RFC5775] or NACK-Oriented Reliable Multicast (NORM) [RFC5740] 🦋.

Now the spicy part 🌶️. The [RFC5053] (Raptor) and [RFC5170] (LDPC-Staircase and LDPC-Triangle) schemes bring in erasure codes based on sparse parity check matrices for object delivery protocols like ALC and NORM ✨. "Reed-Solomon Forward Error Correction (FEC) Schemes" [RFC5510] brings Reed-Solomon codes based on Vandermonde matrices for those same protocols 🔥. All of these are systematic codes, meaning the k source symbols are part of the n encoding symbols 💅.

Here's the tea ☕. Reed-Solomon FEC codes are Maximum Distance Separable (MDS) codes, which makes them optimal for erasure recovery. So a receiver can recover the k source symbols from any set of exactly k encoding symbols out of n 👑. Raptor and LDPC-Staircase don't do that. They need a certain number of encoding symbols on top of k 🙈. But that number is small in practice when the receiver uses an appropriate decoding scheme [Cunche08] 🫶. Another big difference is that Reed-Solomon codecs are way more complex to encode and decode than Raptor or LDPC-Staircase codes. A difference of one or more orders of magnitude in encoding/decoding speed shows up between Reed-Solomon and LDPC-Staircase software codecs [Cunche08][CunchePHD10] 💀. Last but not least, Raptor and LDPC-Staircase are large block FEC codes in the sense of [RFC3453], since they can efficiently handle a large number of source symbols 🧚.

This document is all about LDPC-Staircase codes, which belong to the well-known class of "Low Density Parity Check" codes 💜. Because of their key features, they're a good fit in many situations, as Section 7 details 🍓.

Here's how this doc works 🎀. It inherits the core LDPC-Staircase specs from [RFC5170], Section 6 "Full Specification of the LDPC-Staircase Scheme", and the PRNG specs from Section 5.7 "Pseudo-Random Number Generator" of the same RFC ✨. So this document only specifies what's specific to the FECFRAME context and points to [RFC5170] for the core code specs. To do that, it introduces:

  • the Fully Specified FEC Scheme with FEC Encoding ID 7, which spells out a simple way of using LDPC-Staircase codes to protect arbitrary Application Data Unit (ADU) flows 🦋.

So Sections 4 and 5 of [RFC5170] (except Section 5.7, see above), which define [RFC5052] specific Formats and Procedures, are not considered anymore. They get replaced by FECFRAME specific Formats and Procedures 💅.

Last thing 🫶: publicly available reference implementations of these codes exist at [LDPC-codec] and [LDPC-codec-OpenFEC] ⭐.

2. Terminology 💬

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119] 🎀.

3. Definitions Notations and Abbreviations 📚

3.1. Definitions 📖

okay so this is the glossary bit 🎀 the terms in the first list are FEC scheme specific, and they line up with [RFC5052] ✨

Source symbol: a unit of data used during the encoding process. In this specification, there is always one source symbol per ADU. 💖

Encoding symbol: a unit of data generated by the encoding process. With systematic codes, source symbols are part of the encoding symbols. 🧚

Repair symbol: an encoding symbol that is not a source symbol. 🩹

Code rate: the k/n ratio, aka the ratio between the number of source symbols and the number of encoding symbols. By definition, the code rate is such that: 0 < code rate <= 1. A code rate close to 1 means a small number of repair symbols got produced during encoding. 🌸

Systematic code: a FEC code where the source symbols are part of the encoding symbols. The LDPC-Staircase codes introduced in this document are systematic. 💅

Source block: a block of k source symbols that get considered together for the encoding. 🍓

Packet erasure channel: a communication path where packets are either dropped (e.g., by a congested router, or because the number of transmission errors exceeds the correction capabilities of the physical layer codes) or received. When a packet is received, it is assumed that this packet is not corrupted. 🦋

The next list is FECFRAME specific and lines up with [RFC6363] 👑

Application Data Unit (ADU): the unit of source data provided as payload to the transport layer. Depending on the use-case, an ADU may use an RTP encapsulation. 🎀

(Source) ADU Flow: a sequence of ADUs associated with a transport-layer flow identifier (such as the standard 5-tuple {Source IP address, source port, destination IP address, destination port, transport protocol}). Depending on the use-case, several ADU flows may be protected together by FECFRAME. 🌈

ADU Block: a set of ADUs that get considered together by the FECFRAME instance for the purpose of the FEC scheme. Along with the flow ID (F[]), length (L[]), and padding (Pad[]) fields, they form the set of source symbols over which FEC encoding will be performed. 🧩

ADU Information (ADUI): a unit of data made up of the ADU and the associated Flow ID, Length, and Padding fields (Section 4.3). This is the unit of data that is used as source symbol. ✨

FEC Framework Configuration Information (FFCI): information that controls the operation of the FEC Framework. The FFCI enables the synchronization of the FECFRAME sender and receiver instances. 🔥

FEC Source Packet: at a sender (respectively, at a receiver), a payload submitted to (respectively, received from) the transport protocol containing an ADU along with an optional Explicit Source FEC Payload ID. 🫶

FEC Repair Packet: at a sender (respectively, at a receiver), a payload submitted to (respectively, received from) the transport protocol containing one repair symbol along with a Repair FEC Payload ID and possibly an RTP header. 💜

Here's the whole vibe in Figure 1, from the sender's point of view 👀

    +----------------------+
    |     Application      |
    +----------------------+
               |
               | (1) Application Data Units (ADUs)
               |
               v
    +----------------------+                           +----------------+
    |    FEC Framework     |                           |                |
    |                      |-------------------------->|   FEC Scheme   |
    |(2) Construct source  |(3) Source Block           |                |
    |    blocks            |                           |(4) FEC Encoding|
    |(6) Construct FEC     |<--------------------------|                |
    |    source and repair |                           |                |
    |    packets           |(5) Explicit Source FEC    |                |
    +----------------------+    Payload IDs            +----------------+
               |                Repair FEC Payload IDs
               |                Repair symbols
               |
               |(7) FEC source and repair packets
               v
    +----------------------+
    |   Transport Layer    |
    |     (e.g., UDP)      |
    +----------------------+

            Figure 1: Terminology Used in This Document (Sender)

3.2. Notations ✨

okay, notations time 🧮 this doc uses the following ones. The ones in the list below are FEC scheme specific:

k      denotes the number of source symbols in a source block.

max_k  denotes the maximum number of source symbols for any source
       block.

n      denotes the number of encoding symbols generated for a source
       block.

E      denotes the encoding symbol length in bytes.

CR     denotes the "code rate", i.e., the k/n ratio.

N1     denotes the target number of "1s" per column in the left side
       of the parity check matrix.

N1m3   denotes the value N1 - 3.

G      G denotes the number of encoding symbols per group, i.e., the
       number of symbols sent in the same packet.

a^^b   denotes a raised to the power b.

The following ones are FECFRAME specific:

B      denotes the number of ADUs per ADU block.

max_B  denotes the maximum number of ADUs for any ADU block.

3.3. Abbreviations 🔤

this doc uses the following abbreviations, bestie 💕

ADU    Application Data Unit

ESI    Encoding Symbol ID

FEC    Forward Error (or Erasure) Correction

FFCI   FEC Framework Configuration Information

FSSI   FEC Scheme-Specific Information

LDPC   Low-Density Parity Check

MDS    Maximum Distance Separable

PRNG   Pseudo-Random Number Generator

SDP    Session Description Protocol

this section is where we get into the procedures for ADU block creation and the related source block creation, for the FEC scheme we're looking at 🛠️

4.1. Restrictions 🚧

this spec has the following restrictions, and they're no joke 😤

  • there MUST be exactly one source symbol per ADUI, and therefore per ADU;
  • there MUST be exactly one repair symbol per FEC repair packet;
  • there MUST be exactly one source block per ADU block;
  • the use of the LDPC-Staircase scheme is such that there MUST be exactly one encoding symbol per group; i.e., G MUST be equal to 1 [RFC5170];

4.2. ADU Block Creation 🧱

two kinds of limitations exist that impact the ADU block creation 👀

  • at the FEC scheme level: the FEC scheme and the FEC codec have limitations that define a maximum source block size;
  • at the FECFRAME instance level: the target use-case can have real-time constraints that can/will define a maximum ADU block size;

note that "maximum source block size" and "maximum ADU block size" depend on which point of view you take (FEC scheme versus FECFRAME instance). In this document, though, both refer to the same value, since Section 4.1 requires there be exactly one source symbol per ADU. so let's break down each one 🫧

the maximum source block size in symbols, max_k, depends on a few parameters: the code rate (CR) and the Encoding Symbol ID (ESI) field length in the Explicit Source/Repair FEC Payload ID (16 bits), plus any possible internal codec limitations. More specifically, max_k cannot be larger than the following values, derived from the ESI field size limitation, for a given code rate:

max1_k = 2^^(16 - ceil(Log2(1/CR)))

some common max1_k values are:

  • CR == 1 (no repair symbol): max1_k = 2^^16 = 65536 symbols
  • 1/2 <= CR < 1: max1_k = 2^^15 = 32,768 symbols
  • 1/4 <= CR < 1/2: max1_k = 2^^14 = 16,384 symbols

a codec can also impose other limitations on the maximum source block size, for instance because of a limited working memory size. This decision MUST be clarified at implementation time, when the target use-case is known. This results in a max2_k limitation.

then max_k is given by:

max_k = min(max1_k, max2_k)

note that this calculation is only required at the encoder (sender), since the actual k parameter (k <= max_k) is communicated to the decoder (receiver) through the Explicit Source/Repair FEC Payload ID. 🎯

the source ADU flows can have real-time constraints 🎬 When there are multiple flows, with different real-time constraints, let's consider the most stringent constraints (see [RFC6363], Section 10.2, item 6, for recommendations when several flows are globally protected). In that case, the maximum number of ADUs of an ADU block must not exceed a certain threshold, since it directly impacts the decoding delay. The larger the ADU block size, the longer a decoder may have to wait until it has received a sufficient number of encoding symbols for decoding to succeed, and therefore the larger the decoding delay. When the target use-case is known, these real-time constraints result in an upper bound to the ADU block size, max_rt.

for instance, if the use-case specifies a maximum decoding latency, l, and if each source ADU covers a duration d of a continuous media (we assume here the simple case of a constant bit rate ADU flow), then the ADU block size must not exceed:

max_rt = floor(l / d)

after encoding, this block will produce a set of at most n = max_rt / CR encoding symbols. These n encoding symbols will have to be sent at a rate of n / l packets per second. For instance, with d = 10 ms, l = 1 s, max_rt = 100 ADUs. 🎀

if we take all these constraints into account, we get:

max_B = min(max_k, max_rt)

this max_B parameter is an upper bound to the number of ADUs that can constitute an ADU block. 💖

4.3. Source Block Creation 🎀

okay so bestie, in its most general form, FECFRAME and the LDPC-Staircase FEC Scheme are meant to protect a whole bunch of independent flows 🌈 and since those flows have zero relationship to each other, the ADU size of each flow can vary a LOT. Even if you only have ONE flow, the ADU sizes can still be super all over the place (think the different frames inside a Group of Pictures (GOP) of an H.264 flow) 🎬 This diversity has to be handled, because the LDPC-Staircase FEC Scheme needs a constant encoding symbol size (the E parameter) per source block. And since this specification says there's only one source symbol per ADU, E has to be big enough to fit ALL the ADUs of an ADU block plus their prepended 3 bytes (more on that below) ✨

In situations where E gets decided per source block (the default, set by the FFCI/FSSI with S = 0, Section 5.1.1.2), E is equal to the size of the largest ADU in that source block plus three (for the prepended 3 bytes, see below) 💅 In this case, when a receiver gets the first FEC repair packet for this source block, that packet MUST contain a single repair symbol (Section 5.1.3), so the receiver figures out the E parameter used for this source block from it 🔥

In situations where E is fixed (set by the FFCI/FSSI with S = 1, Section 5.1.1.2), then E must be greater than or equal to the size of the largest ADU in this source block plus three (for the prepended 3 bytes, see below). If that's not the case, an error gets returned 😭 How to handle that error depends on the use case (for example, a larger E parameter could be communicated to the receivers in an updated FFCI message, using an appropriate mechanism). This specification does not consider it, so it's not covered here 🙈

The ADU block is always encoded as a single source block 🧚 There are a total of B <= max_B ADUs in this ADU block. For the ADU i, with 0 <= i <= B-1, 3 bytes get prepended (Figure 2):

  • The first byte, F[i] (Flow ID), contains the integer identifier associated with the source ADU flow that this ADU belongs to. It's assumed that a single byte is enough, or said differently, that no more than 256 flows will be protected by a single instance of FECFRAME 🦋
  • The following two bytes, L[i] (Length), contain 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[i], L[i], or Pad[i] fields 💜

Then, zero padding is added to ADU i (if needed) in field Pad[i], for alignment purposes, up to a size of exactly E bytes 🌸 The data unit made from the ADU i plus the F[i], L[i], and Pad[i] fields is called ADU Information (or ADUI). Each ADUI contributes to exactly one source symbol of the source block ✨

                     Encoding Symbol Length (E)
< -------------------------------------------------------------- >
+----+----+-----------------------+------------------------------+
|F[0]|L[0]|        ADU[0]         |            Pad[0]            |
+----+----+----------+------------+------------------------------+
|F[1]|L[1]| ADU[1]   |                         Pad[1]            |
+----+----+----------+-------------------------------------------+
|F[2]|L[2]|                    ADU[2]                            |
+----+----+------+-----------------------------------------------+
|F[3]|L[3]|ADU[3]|                             Pad[3]            |
+----+----+------+-----------------------------------------------+
\_______________________________  _______________________________/
                                \/
                       simple FEC encoding

+----------------------------------------------------------------+
|                            Repair 4                            |
+----------------------------------------------------------------+
.                                                                .
.                                                                .
+----------------------------------------------------------------+
|                            Repair 7                            |
+----------------------------------------------------------------+

Figure 2: Source Block Creation, for Code Rate 1/2 (Equal Number of Source and Repair Symbols, 4 in This Example), and S = 0

Note that neither the initial 3 bytes nor the optional padding are sent over the network 👀 BUT they totally count during FEC encoding! That means a receiver who lost a certain FEC source packet (for example, the UDP datagram carrying this FEC source packet) can still recover the ADUI if FEC decoding succeeds 🫶 Thanks to those initial 3 bytes, this receiver can get rid of the padding (if there is any) and figure out which ADU flow it belongs to 🌈

5. LDPC-Staircase FEC Scheme for Arbitrary ADU Flows 👑

5.1. Formats and Codes 💖

5.1.1. FEC Framework Configuration Information 🧚

The FEC Framework Configuration Information (or FFCI) includes information that MUST be communicated between the sender and receiver(s) 💅 More specifically, it's what keeps the FECFRAME sender and receiver instances in sync. It includes both mandatory elements and scheme-specific elements, as detailed below.

5.1.1.1. Mandatory Information 🎀

  • FEC Encoding ID: the value assigned to this fully specified FEC scheme MUST be 7, as assigned by IANA (Section 8) ✨

When SDP is used to communicate the FFCI, this FEC Encoding ID is carried in the 'encoding-id' parameter 🦋

5.1.1.2. FEC Scheme-Specific Information 🌸

The FEC Scheme-Specific Information (FSSI) includes elements that are specific to the present FEC scheme. More precisely:

  • PRNG seed (seed): a non-negative 32-bit integer used as the seed of the Pseudo-Random Number Generator, as defined in [RFC5170] 🔥
  • Encoding symbol length (E): a non-negative integer that indicates either the length of each encoding symbol in bytes (strict mode, i.e., if S = 1) or the maximum length of any encoding symbol (i.e., if S = 0) 💜
  • Strict (S) flag: when set to 1, this flag indicates that the E parameter is the actual encoding symbol length value for each block of the session (unless otherwise notified by an updated FFCI, if this possibility is considered by the use case or CDP). When set to 0, this flag indicates that the E parameter is the maximum encoding symbol length value for each block of the session (unless otherwise notified by an updated FFCI, if this possibility is considered by the use case or CDP) 🙈
  • N1 minus 3 (n1m3): an integer between 0 (default) and 7, inclusive. The number of "1s" per column in the left side of the parity check matrix, N1, is then equal to N1m3 + 3, as specified in [RFC5170] 🍓

These elements are required both by the sender (LDPC-Staircase encoder) and the receiver(s) (LDPC-Staircase decoder) 🫶

When SDP is used to communicate the FFCI, this FEC scheme-specific information is carried in the 'fssi' parameter in textual representation, as specified in [RFC6364]. For instance:

fssi=seed:1234,E:1400,S:0,n1m3:0

If another mechanism requires the FSSI to be carried as an opaque octet string (for instance, after a Base64 encoding), the encoding format consists of the following 7 octets:

  • PRNG seed (seed): 32-bit field.
  • Encoding symbol length (E): 16-bit field.
  • Strict (S) flag: 1-bit field.
  • Reserved: a 4-bit field that MUST be set to zero 🌈
  • N1m3 parameter (n1m3): 3-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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      PRNG seed (seed)                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Encoding Symbol Length (E)  |S| resvd | n1m3|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 3: FSSI Encoding Format

5.1.2. Explicit Source FEC Payload ID 🦋

A FEC source packet MUST contain an Explicit Source FEC Payload ID that is appended to the end of the packet, as illustrated in Figure 4 💖

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

Figure 4: Structure of a FEC Source Packet with the Explicit Source FEC Payload ID

More precisely, the Explicit Source FEC Payload ID is made up of the following fields (Figure 5):

  • Source Block Number (SBN) (16-bit field): this field identifies the source block that this FEC source packet belongs to 🧚
  • Encoding Symbol ID (ESI) (16-bit field): this field identifies the source symbol contained in this FEC source packet. This value is such that 0 <= ESI <= k - 1 for source symbols ✨
  • Source Block Length (k) (16-bit field): this field provides the number of source symbols for this source block, i.e., the k parameter 💅
 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Source Block Number (SBN)   |   Encoding Symbol ID (ESI)    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Source Block Length (k)    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 5: Source FEC Payload ID Encoding Format

5.1.3. Repair FEC Payload ID ✨

okay so this is the repair packet's ID card 🪪💖 A FEC repair packet MUST contain a Repair FEC Payload ID, and it gets stuck in front of the repair symbol(s), like a little name tag. There MUST be a single repair symbol per FEC repair packet, so one repair symbol per packet, no sharing 🫶

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

          Figure 6: Structure of a FEC Repair Packet with
                       the Repair Payload ID

so the actual fields in the Repair FEC Payload ID are (see Figure 7) 👀

  • Source Block Number (SBN) (16-bit field): tells you which source block this FEC repair packet belongs to 🧩
  • Encoding Symbol ID (ESI) (16-bit field): tells you which repair symbol is inside this packet 🎀 For repair symbols, the value has to satisfy k <= ESI <= n - 1.
  • Source Block Length (k) (16-bit field): the number of source symbols in this source block, aka the k parameter 🌸
  • Number of Encoding Symbols (n) (16-bit field): the number of encoding symbols for this source block, aka the n parameter ✨
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Source Block Number (SBN)   |   Encoding Symbol ID (ESI)    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Source Block Length (k)    |  Number Encoding Symbols (n)  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

          Figure 7: Repair FEC Payload ID Encoding Format

5.2. Procedures 💅

these are the rules you follow, no cap 📜

  • The source block creation MUST follow the procedures specified in Section 4.3.
  • The SBN value MUST start with value 0 for the first block of the ADU flow and MUST be incremented by 1 for each new source block. It wraps back to zero on long sessions, after the value 2^^16 - 1. 🔁
  • The ESI of encoding symbols MUST start with value 0 for the first symbol and MUST be managed sequentially. The first k values (0 <= ESI <= k - 1) identify source symbols, and the last n-k values (k <= ESI <= n - 1) identify repair symbols. 🔢
  • The FEC repair packet creation MUST follow the procedures specified in Section 5.1.3.

5.3. FEC Code Specification 🧠

this doc inherits the core LDPC-Staircase codes from [RFC5170] for a packet erasure transmission channel (see Section 1). it's giving "borrowing from the best" 🫶

because of the requirement to have exactly one encoding symbol per group, i.e., because G MUST be equal to 1 (Section 4.1), a bunch of [RFC5170] just isn't relevant. the big one is Section 5.6, "Identifying the G Symbols of an Encoding Symbol Group", which is a no-show here 🙈

6. Security Considerations 🔐

ngl this part is so serious but also so important 😭 The FEC Framework document [RFC6363] already does a full, comprehensive analysis of security considerations for FEC schemes. So this section just follows the security considerations section of [RFC6363] and only covers the stuff that's specific to LDPC-Staircase codes. no copy-paste drama here 💅

6.1. Attacks against the Data Flow 🌊

6.1.1. Access to Confidential Content 🤫

the LDPC-Staircase FEC Scheme in this doc does not change the recommendations of [RFC6363]. tl;dr: if confidentiality is a concern, it is RECOMMENDED that one of the solutions mentioned in [RFC6363] be used. but you gotta think about how you apply it 👀 Is encryption applied before or after FEC protection? Is it inside the end-system or in a middlebox? You also have to consider the operational constraints (performing FEC decoding in a protected environment may be complicated or even impossible) and the threat model 🧐

6.1.2. Content Corruption 🩹

again, no change to [RFC6363]. tl;dr: it is RECOMMENDED that one of the solutions mentioned in [RFC6363] be used on both the FEC source and repair packets. both sides get protected, bestie 🛡️

6.2. Attacks against the FEC Parameters 🎯

the FEC scheme in this doc defines parameters that can be the basis of several attacks, so let's spill the tea 🍵 More specifically, the following parameters of the FFCI may be modified by an attacker (Section 5.1.1.2):

  • FEC Encoding ID: changing this one makes the receiver consider a different FEC scheme. that lets an attacker create a Denial of Service (DoS) 💀
  • Encoding symbol length (E): setting E to a value smaller than the valid one lets an attacker create a DoS, because the repair symbols and certain source symbols will be larger than E, which is an incoherency for the receiver. setting E to a value larger than the valid one has similar impacts when S=1, since the received repair symbol size will be smaller than expected. on the flip side, it won't cause any incoherency when S=0, since the actual symbol length for the block is determined by the size of any received repair symbol, as long as that size is smaller than E. still, a bigger E may affect receivers that pre-allocate memory in advance to store incoming symbols 🧺
  • Strict (S) flag: flipping S from 0 to 1 (so E is now considered a strict value) lets an attacker mislead the receiver if the actual symbol size varies across source blocks. flipping S from 1 to 0 doesn't have major consequences, unless the receiver needs a fixed E value (e.g., because it pre-allocates memory space) 🚩
  • N1 minus 3 (n1m3): changing this one makes the receiver consider a different code, which lets an attacker create a DoS 💥

so yeah, it is RECOMMENDED that security measures be taken to guarantee the FFCI integrity, as specified in [RFC6363]. how you do that depends on how the FFCI gets communicated from sender to receiver, and this doc doesn't specify that part 🤷‍♀️

similarly, attacks are possible against the Explicit Source FEC Payload ID and the Repair FEC Payload ID. if an attacker modifies the Source Block Number (SBN), the Encoding Symbol ID (ESI), the Source Block Length (k), or the Number Encoding Symbols (n), they can easily corrupt the block identified by the SBN. other consequences, which are use-case and/or CDP dependent, may also happen. so it is RECOMMENDED that security measures be taken to guarantee the FEC source and repair packets as stated in [RFC6363] 🔒✨

6.3. When Several Source Flows Are to Be Protected Together 🫂

the LDPC-Staircase FEC Scheme in this doc does not change the recommendations of [RFC6363]. same energy as before, no new drama 💖

6.4. Baseline Secure FEC Framework Operation 🛡️

the LDPC-Staircase FEC Scheme in this doc does not change the recommendations of [RFC6363] about using the IPsec/ESP security protocol as a mandatory to implement (but not mandatory to use) security scheme. this is a great fit when the only insecure domain is the one the FEC Framework operates over 🌈

7. Operations and Management Considerations 🛠️

the FEC Framework document [RFC6363] already gives a comprehensive analysis of operations and management considerations for FEC schemes. so this section only covers the stuff that's specific to using LDPC-Staircase codes as specified in this doc 🎀

7.1. Operational Recommendations 💅

Okay bestie, LDPC-Staircase codes are seriously good at erasure recovery when the source blocks are big, like close-to-ideal MDS codes 😭✨ This part is independent of FECFRAME, it's just the code doing its thing. Picture a source block of k=1024 symbols, CR=2/3 (so 512 repair symbols get added), N1=7, G=1, every symbol sent in a random order, and a hybrid ITerative/Maximum Likelihood (IT/ML) decoder (more on that in a sec). An ideal MDS code at rate 2/3 can recover from erasures up to a 33.33% channel loss rate. With LDPC-Staircase, the average overhead is 0.237%. That means receiving 2.43 symbols on top of k (a 33.18% channel loss rate) gives a successful decode with probability 0.5. An overhead of 1.46% (15 symbols on top of k, a 32.36% channel loss rate) is enough to drop the decoding failure probability down to 8.2*10^^-5 🔥

This is why these codes are such a good move for protecting a single high bitrate source flow, like in [Matsuzono10], or for protecting a bunch of mid-rate source flows together within a single FECFRAME instance. Either way, the source block size can be assumed to be a few hundred (or more) source symbols.

LDPC-Staircase codes are also a great choice when the processing load at a software encoder or decoder needs to stay as low as possible 🧚 This holds when the decoder uses an IT decoding algorithm, an ML algorithm (we use Gaussian Elimination as the ML algorithm) when it's carefully implemented, or a mix of both, which is the recommended solution [Cunche08][CunchePHD10][LDPC-codec-OpenFEC]. Same conditions again (k=1024, CR=2/3, N1=7, G=1) with 1024-byte encoding symbols. On an Intel Xeon 5120/1.86 GHz workstation running Linux/64 bits, the average decoding speed lands between 1.78 Gbps (2 symbols of overhead on top of k, a very bad channel at a 33.20% loss rate, close to the theoretical decoding limit where ML decoding is required) and 3.91 Gbps (a good channel with only a 5% loss rate, where IT decoding is enough) 🍓 Under the same conditions on a Samsung Galaxy SII smartphone (GT-I9100P model, ARM Cortex-A9/1.2 GHz processor, running Android 2.3.4), the speed is between 397 Mbps (bad channel, 33.20% loss rate, close to the theoretical decoding limit) and 813 Mbps (good channel, 5% loss rate only).

As the source block size goes down, the erasure recovery of LDPC codes in general also goes down, ngl 🥺 To limit this, for LDPC-Staircase codes it's recommended to use an N1 value of at least 7 (for example, the experiments in [Matsuzono10] use N1=7 if k=170 symbols, and N1=5 otherwise). Here's an example, still independent of FECFRAME: with a source block of k=256 symbols, CR=2/3 (so 128 repair symbols are added), N1=7, and G=1, the average overhead is 0.706% (receiving 1.8 symbols on top of k gives a successful decode with probability 0.5), and an overhead of 5.86% (15 symbols on top of k) is enough to bring the decoding failure probability down to 5.9*10^^-5 ✨

The processing load also drops as the source block size drops 💖 Under these conditions (k=256, CR=2/3, N1=7, G=1), with 1024-byte encoding symbols on a Samsung Galaxy SII, the decoding speed is between 518 Mbps (bad channel) and 863 Mbps (good channel with a 5% loss rate only).

With very small source blocks (like a few tens of symbols), using something like Reed-Solomon codes [SIMPLE_RS] or 2D parity check codes may be more appropriate.

The way the FEC repair packets get sent really matters 👑 A solid strategy that works well for any kind of channel loss model is to send the FEC repair packets in random order (not in sequence), while the FEC source packets go out first and in sequence. Sending all packets in random order is another option, but it means all the repair symbols for a source block have to be produced first, which adds some extra delay at the sender.

8. IANA Considerations 🎀

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

  • 7 refers to the Simple LDPC-Staircase FEC Scheme for Arbitrary Packet Flows, as defined in Section 5 of this document.

9. Acknowledgments 🫶

The authors want to thank K. Matsuzono, J. Detchart, and H. Asaeda for their contributions in evaluating the use of LDPC-Staircase codes in the context of FECFRAME [Matsuzono10].

10. References 📚

10.1. Normative References

[RFC2119]    Bradner, S., "Key words for use in RFCs to Indicate
             Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC5170]    Roca, V., Neumann, C., and D. Furodet, "Low Density
             Parity Check (LDPC) Staircase and Triangle Forward Error
             Correction (FEC) Schemes", RFC 5170, June 2008.

[RFC6363]    Watson, M., Begen, A., and V. Roca, "Forward Error
             Correction (FEC) Framework", RFC 6363, October 2011.

[RFC6364]    Begen, A., "Session Description Protocol Elements for
             the Forward Error Correction (FEC) Framework", RFC 6364,
             October 2011.

10.2. Informative References

[Cunche08]   Cunche, M. and V. Roca, "Optimizing the Error Recovery
             Capabilities of LDPC-Staircase Codes Featuring a
             Gaussian Elimination Decoding Scheme",  10th IEEE
             International Workshop on Signal Processing for Space
             Communications (SPSC'08), October 2008.

[CunchePHD10]
             Cunche, M., "High performances AL-FEC codes for the
             erasure channel : variation around LDPC codes", PhD
             dissertation (in French) (http://
             tel.archives-ouvertes.fr/tel-00451336/en/), June 2010.

[LDPC-codec]
             Cunche, M., Roca, V., Neumann, C., and J.  Laboure,
             "LDPC-Staircase/LDPC-Triangle Codec Reference
             Implementation", INRIA Rhone-Alpes and
             STMicroelectronics,
             <http://planete-bcast.inrialpes.fr/>.

[LDPC-codec-OpenFEC]
             "The OpenFEC project", <http://openfec.org/>.

[Matsuzono10]
             Matsuzono, K., Detchart, J., Cunche, M., Roca, V., and
             H. Asaeda, "Performance Analysis of a High-Performance
             Real-Time Application with Several AL-FEC Schemes", 35th
             Annual IEEE Conference on Local Computer Networks (LCN
             2010), October 2010.

[RFC3453]    Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley,
             M., and J. Crowcroft, "The Use of Forward Error
             Correction (FEC) in Reliable Multicast", RFC 3453,
             December 2002.

[RFC5052]    Watson, M., Luby, M., and L. Vicisano, "Forward Error
             Correction (FEC) Building Block", RFC 5052, August 2007.

[RFC5053]    Luby, M., Shokrollahi, A., Watson, M., and T.
             Stockhammer, "Raptor Forward Error Correction Scheme for
             Object Delivery", RFC 5053, October 2007.

[RFC5510]    Lacan, J., Roca, V., Peltotalo, J., and S.  Peltotalo,
             "Reed-Solomon Forward Error Correction (FEC) Schemes",
             RFC 5510, April 2009.

[RFC5740]    Adamson, B., Bormann, C., Handley, M., and J.  Macker,
             "NACK-Oriented Reliable Multicast (NORM) Transport
             Protocol", RFC 5740, November 2009.

[RFC5775]    Luby, M., Watson, M., and L. Vicisano, "Asynchronous
             Layered Coding (ALC) Protocol Instantiation", RFC 5775,
             April 2010.

[SIMPLE_RS]  Roca, V., Cunche, M., Lacan, J., Bouabdallah, A., and K.
             Matsuzono, "Simple Reed-Solomon Forward Error Correction
             (FEC) Scheme for FECFRAME", Work in Progress, October
             2012.

Authors' Addresses 🌸

Vincent Roca
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex  38334
France

EMail: vincent.roca@inria.fr
URI:   http://planete.inrialpes.fr/people/roca/


Mathieu Cunche
INSA-Lyon/INRIA
Laboratoire CITI
6 av. des Arts
Villeurbanne cedex  69621
France

EMail: mathieu.cunche@inria.fr
URI:   http://mathieu.cunche.free.fr/


Jerome Lacan
ISAE, Univ. of Toulouse
10 av. Edouard Belin; BP 54032
Toulouse cedex 4  31055
France

EMail: jerome.lacan@isae.fr
URI:   http://personnel.isae.fr/jerome-lacan/
📦 where this page comes from