RFC 9407

Tetrys: An On-the-Fly Network Coding Protocol

📅 published June 2023, from ietf

📜 RFC 9407: Tetrys, an On-the-Fly Network Coding Protocol 🦋

okay bestie, let's get into it! 💖 this one is an Experimental doc from the IRTF (the research side of the Internet, not the IETF standards side 🌸), and it's written by J. Detchart, E. Lochin, J. Lacan, and V. Roca from ISAE-SUPAERO, ENAC, and INRIA. it came out in June 2023 🎀 and it's published under ISSN 2070-1721. it doesn't obsolete or update any other RFCs, so it's a clean slate 🧚

the vibe is the Coding for Efficient NetWork Communications Research Group (NWCRG) 💅 and it's all about Tetrys, which is an on-the-fly network coding protocol for sending data that is both delay-sensitive AND loss-sensitive over a lossy network 😭🔥

Abstract ✨

okay so Tetrys can recover from erasures in an RTT-independent delay because it sends coded packets 🙈 it's giving "I'm cute AND I'm resilient" energy. this doc is basically a diary of what the authors learned while building and testing Tetrys in real conditions 📓💜

it's a product of NWCRG and it follows the NWCRG taxonomy from RFC 8406 🫶

Status of This Memo ✨

not me reading "this is NOT an Internet Standards Track spec" 💀 it's published for examination, experimental implementation, and evaluation 🧪

it defines an Experimental Protocol for the Internet community 🌈 it's an IRTF product, and IRTF shares research results that might not be ready for deployment (so don't ship it to prod, bestie 😭). it reflects the consensus of NWCRG, and anything approved by the IRSG is not a candidate for any level of Internet Standard, see Section 2 of RFC 7841 💅

current status, errata, and feedback info live at https://www.rfc-editor.org/info/rfc9407 🔗

Copyright (c) 2023 IETF Trust and the document authors, all rights reserved 💖

this doc is subject to BCP 78 and the IETF Trust's Legal Provisions (https://trustee.ietf.org/license-info) as of the publication date, so read those carefully because they spell out your rights and restrictions 📝

Table of Contents 🗺️

1.  Introduction
  1.1.  Requirements Notation
2.  Definitions, Notations, and Abbreviations
3.  Architecture
  3.1.  Use Cases
  3.2.  Overview
4.  Tetrys Basic Functions
  4.1.  Encoding
  4.2.  The Elastic Encoding Window
  4.3.  Decoding
5.  Packet Format
  5.1.  Common Header Format
    5.1.1.  Header Extensions
  5.2.  Source Packet Format
  5.3.  Coded Packet Format
    5.3.1.  The Encoding Vector
  5.4.  Window Update Packet Format
6.  Research Issues
  6.1.  Interaction with Congestion Control
  6.2.  Adaptive Coding Rate
  6.3.  Using Tetrys below the IP Layer for Tunneling
7.  Security Considerations
  7.1.  Problem Statement
  7.2.  Attacks against the Data Flow
  7.3.  Attacks against Signaling
  7.4.  Attacks against the Network
  7.5.  Baseline Security Operation
8.  IANA Considerations
9.  References
  9.1.  Normative References
  9.2.  Informative References
Acknowledgments
Authors' Addresses

1. Introduction 🦋

okay so this doc is a product of the NWCRG's collaborative work and consensus 🫶 but it is NOT an IETF product or an IETF standard, just so we're clear 💅

Tetrys is an on-the-fly network coding protocol for delay-sensitive and loss-sensitive data over a lossy network 🔥. network codes showed up in the early 2000s [AHL-00] to fix the usual Internet problems (delay, capacity, and packet loss) 😩. network codes have gotten some real deployment recently, and the IETF already standardized application-layer erasure codes through the RMT [RFC5052] [RFC5445] and FECFRAME [RFC8680] Working Groups 🌸. Tetrys can be seen as a network-coding extension to standard unicast transport protocols (multicast or anycast work too, with a few tweaks) 🧚. the current proposal is basically a combo of network erasure coding and feedback mechanisms [Tetrys] [Tetrys-RT] ✨

the main innovation is generating coded packets from an elastic encoding window 💖. this window gets filled with source packets from an input flow and is periodically updated with receiver feedback 📬. that feedback tells the sender the highest sequence number received or rebuilt, which lets the sender flush the matching source packets out of the window 🧹. the window size can be fixed or dynamic 📏. if the window is full, new source packets replace older ones that get dropped, so its limit should be sized correctly 🙈. Tetrys also handles losses on both the forward and return paths and is especially resilient to acknowledgment losses 🫶. all the details are in Section 4 🎀

with Tetrys, a coded packet is a linear combination over a finite field of the source packets in the coding window 🧮. picking the coefficients (as finite field elements) is a trade-off: 256-element fields give the best erasure recovery, but 16-element fields are preferred for system constraints, and the application decides which one makes sense 💅

the coded packets get built on-the-fly using a predefined method for choosing coefficients 🦋. the redundancy ratio can be adjusted dynamically, and the coefficients can be generated in different ways during transmission 🌈. compared to FEC block codes, this cuts bandwidth use and decoding delay 🏃‍♀️💨

this design is backed up by the authors' own experience developing and testing Tetrys in realistic conditions 📓. several research issues get discussed in Section 6 🔍

1.1. Requirements Notation 📐

the BCP 14 key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this doc are to be read as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they show up in ALL CAPS 💜 (like this 💅)

2. Definitions, Notations, and Abbreviations 📖

the notation in this doc is based on the NWCRG taxonomy [RFC8406] 🫶

Source Symbol: a symbol sent between the ingress and egress of the network 📤

Coded Symbol: a linear combination over a finite field of a set of source symbols 🧮

Source Symbol ID: a sequence number that identifies the source symbols 🔢

Coded Symbol ID: a sequence number that identifies the coded symbols 🔢

Encoding Coefficients: elements of the finite field that characterize the linear combination used to make coded symbols ✨

Encoding Vector: a set of the coding coefficients and input source symbol IDs 🦋

Source Packet: a source packet holds a source symbol plus its associated IDs 📦

Coded Packet: a coded packet holds a coded symbol, the coded symbol's ID, and the encoding vector 🎁

Input Symbol: a symbol at the input of the Tetrys encoder 🌸

Output Symbol: a symbol generated by the Tetrys encoder. in non-systematic mode, all output symbols are coded symbols 🙈. in systematic mode, output symbols MAY be the input symbols plus a number of coded symbols that are linear combinations of the input symbols plus the encoding vectors 💖

Feedback Packet: a packet with info about the decoded or received source symbols 📬. it MAY also include extra info about the Packet Error Rate or the number of various packets in the receiver decoding window 📊

Elastic Encoding Window: an encoder-side buffer that stores all the unacknowledged source packets of the input flow involved in the coding process 🪟

Coding Coefficient Generator Identifier (CCGI): a unique identifier for a function or algorithm that generates the encoding vector 🆔

Code Rate: the rate between the number of input symbols and the number of output symbols 📉

3. Architecture 🏗️

3.1. Use Cases 🎬

Tetrys is well suited to (but not limited to!) the use case with a single flow from a single source, with intra-stream coding at a single encoding node 💅. the input stream MAY be a multiplex of several upper-layer streams 🌈. transmission MAY go over a single path or multiple paths 🛤️. this is the simplest use case and it lines up really well with currently proposed scenarios for end-to-end streaming 📺🔥

okay bestie that's part 1 of 6! 🎀 more parts are coming, so stay tuned 💜🫶

3.2. Overview ✨

      +----------+                +----------+
      |          |                |          |
      |    App   |                |    App   |
      |          |                |          |
      +----------+                +----------+
           |                           ^
           |  Source           Source  |
           |  Symbols          Symbols |
           |                           |
           v                           |
      +----------+                +----------+
      |          | Output Packets |          |
      |  Tetrys  |--------------->|  Tetrys  |
      |  Encoder |Feedback Packets|  Decoder |
      |          |<---------------|          |
      +----------+                +----------+

                       Figure 1: Tetrys Architecture

Okay so Tetrys has a whole set of key functionalities, and bestie, the mandatory ones are the non-negotiables 💅:

  • on-the-fly encoding;
  • decoding;
  • signaling, to carry in particular the symbol IDs in the encoding window and the associated coding coefficients when meaningful;
  • feedback management;
  • elastic window management; and
  • Tetrys packet header creation and processing.

The optional features are the extras that make it even more iconic 🦋:

  • channel estimation;
  • dynamic adjustment of the code rate and flow control; and
  • congestion control management (if appropriate). See Section 6.1 for further details.

Then there are a few building blocks that each handle a piece of the job 🧚:

The Tetrys Building Block: this one embeds both the Tetrys decoder and Tetrys encoder, so it gets used during both encoding and decoding. It must be noted that Tetrys does not mandate a specific building block. Instead, any building block compatible with the elastic encoding window feature of Tetrys may be used. Main character energy, no single block is forced on you 👑.

The Window Management Building Block: this one is in charge of managing the encoding window at a Tetrys sender. 🫶

To make it easy to add future components and services, Tetrys includes a header extension mechanism that is compatible with the one used by Layered Coding Transport (LCT) [RFC5651], NACK-Oriented Reliable Multicast (NORM) [RFC5740], and FEC Framework (FECFRAME) [RFC8680]. Literally so compatible it's giving family reunion 🌈.

4. Tetrys Basic Functions 🎀

4.1. Encoding 💖

At the beginning of a transmission, a Tetrys encoder MUST choose an initial code rate that adds redundancy, because it doesn't know the packet loss rate of the channel yet. In the steady state, the Tetrys encoder MAY generate coded symbols when it receives a source symbol from the application, or some feedback from the decoding blocks, depending on the code rate. Smart start, no cap ✨.

When a Tetrys encoder needs to generate a coded symbol, it looks at the set of source symbols stored in the elastic encoding window and builds an encoding vector with the coded symbol. These source symbols are the ones that the receiver has not yet acknowledged. For each source symbol, a finite field coefficient gets determined by a Coding Coefficient Generator. This generator MAY take the source symbol IDs and the coded symbol ID as an input, and MAY determine a coefficient in a deterministic way as presented in Section 5.3. Finally, the coded symbol is the sum of the source symbols multiplied by their corresponding coefficients. The math is literally so satisfying 🧮🌸.

A Tetrys encoder MUST set a limit to the elastic encoding window maximum size. This controls the algorithmic complexity at the encoder and decoder by limiting the size of linear combinations. It is also needed in situations where all window update packets are lost or absent. Boundaries are everything, bestie 🙈.

4.2. The Elastic Encoding Window 🦋

When an input source symbol is passed to a Tetrys encoder, it gets added to the elastic encoding window. This window MUST have a limit set by the encoding building block. If the elastic encoding window has reached its limit, the window slides over the symbols: the first (oldest) symbol is removed, and the newest symbol is added. As an element of the coding window, this symbol is included in the next linear combinations created to generate the coded symbols. It's giving conveyor belt, but make it iconic 💅.

As explained below, the Tetrys decoder sends periodic feedback indicating the received or decoded source symbols. When the sender receives the information that a source symbol was received or decoded by the receiver, it removes this symbol from the coding window. Closure arc, we love to see it 🌈.

4.3. Decoding 🧚

A standard Gaussian elimination is sufficient to recover the erased source symbols when the matrix rank enables it. Simple, classic, and it works 🫶✨.

5. Packet Format 🎀

5.1. Common Header Format 💜

All types of Tetrys packets share the same common header format (see Figure 2). Consistency is the whole vibe 🍓.

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   V   | C |S|     Reserved    |   HDR_LEN     |    PKT_TYPE   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Congestion Control Information (CCI, length = 32*C bits)    |
   |                          ...                                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Transport Session Identifier (TSI, length = 32*S bits)     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                Header Extensions (if applicable)              |
   |                          ...                                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Figure 2: Common Header Format

As noted above, this format is inspired by, and inherits from, the LCT header format [RFC5651], with a few slight modifications. Glow-up from a classic, bestie 🦋.

Tetrys version number (V): 4 bits. Indicates the Tetrys version number. The Tetrys version number for this specification is 1. Version one, the OG 👑.

Congestion control flag (C): 2 bits. C set to 0b00 indicates the Congestion Control Information (CCI) field is 0 bits in length. C set to 0b01 indicates the CCI field is 32 bits in length. C set to 0b10 indicates the CCI field is 64 bits in length. C set to 0b11 indicates the CCI field is 96 bits in length. Four sizes, pick your fighter 💅.

Transport Session Identifier flag (S): 1 bit. This is the number of full 32-bit words in the TSI field. The TSI field is 32*S bits in length; i.e., the length is either 0 bits or 32 bits. Just one bit, but it's doing a lot 🙈.

Reserved (Resv): 9 bits. These bits are reserved. In this version of the specification, they MUST be set to zero by senders and MUST be ignored by receivers. Hands off, these are reserved for later 🔒💀.

Header length (HDR_LEN): 8 bits. The total length of the Tetrys header in units of 32-bit words. The length of the Tetrys header MUST be a multiple of 32 bits. This field may be used to directly access the portion of the packet beyond the Tetrys header, i.e., to the first next header if it exists, to the packet payload if it exists and there is no other header, or to the end of the packet if there are no other headers or packet payload. It's basically your GPS to the good stuff 🧭✨.

Tetrys packet type (PKT_TYPE): 8 bits. There are three types of packets: the PKT_TYPE_SOURCE (0b00) defined in Section 5.2, the PKT_TYPE_CODED (0b01) defined in Section 5.3, and the PKT_TYPE_WND_UPT (0b11) for window update packets defined in Section 5.4. Three types, three vibes 🌸.

Congestion Control Information (CCI): 0, 32, 64, or 96 bits. Used to carry congestion control information. For example, the congestion control information could include layer numbers, logical channel numbers, and sequence numbers. This field is opaque for this specification. This field MUST be 0 bits (absent) if C is set to 0b00. This field MUST be 32 bits if C is set to 0b01. This field MUST be 64 bits if C is set to 0b10. This field MUST be 96 bits if C is set to 0b11. The size has to match the C flag exactly, no wiggle room 🙅‍♀️.

Transport Session Identifier (TSI): 0 or 32 bits. The TSI uniquely identifies a session among all sessions from a particular Tetrys encoder. The TSI is scoped by the IP address of the sender, so the IP address of the sender and the TSI together uniquely identify the session. Although a TSI always uniquely identifies a session together with the IP address of the sender, whether the TSI is included in the Tetrys header depends on what is used as the TSI value. If the underlying transport is UDP, then the 16-bit UDP source port number MAY serve as the TSI for the session. If there is no underlying TSI provided by the network, transport, or any other layer, then the TSI MUST be included in the Tetrys header. The identity crisis is resolved, the session is uniquely yours 🦋💜.

5.1.1. Header Extensions ✨

okay so header extensions are how Tetrys fits in optional header fields 🎀 the ones that aren't always used or that come in variable sizes. it's such a clean trick, no cap. The presence of header extensions MAY be inferred from the Tetrys header length (HDR_LEN). If HDR_LEN is bigger than the standard header, whatever space is left over gets taken up by header extensions 🦋

if there are header extensions, they MUST be processed so they get recognized before any congestion control procedure runs or before a packet gets accepted. 💅 the default move for an unrecognized header extension is to ignore it. that's what lets Tetrys get backward-compatible upgrades in the future without bumping the Tetrys version number ✨ but any header extension that is NOT backward-compatible MUST NOT be introduced unless the Tetrys version number changes. no shortcuts, bestie 🙈

there are two formats for header extensions, shown in Figure 3 🌸

  • The first format is for variable-length extensions with header extension type (HET) values between 0 and 127.
  • The second format is for fixed-length extensions (one 32-bit word) using HET values from 128 to 255.
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  HET (<=127)  |       HEL     |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
   .                                                               .
   .              Header Extension Content (HEC)                   .
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  HET (>=128)  |       Header Extension Content (HEC)          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 3: Header Extension Format

Here's the breakdown of each piece 💜

  • Header Extension Type (HET): 8 bits. The type of the header extension. This document defines several possible types. Additional types may be defined in future versions of this specification. HET values from 0 to 127 are used for variable-length header extensions. HET values from 128 to 255 are used for fixed-length, 32-bit header extensions.
  • Header Extension Length (HEL): 8 bits. The length of the whole header extension field, expressed in multiples of 32-bit words. This field MUST be present for variable-length extensions (HETs between 0 and 127) and MUST NOT be present for fixed-length extensions (HETs between 128 and 255).
  • Header Extension Content (HEC): Length of the variable. The content of the header extension. The format of this subfield depends on the header extension type. For fixed-length header extensions, the HEC is 24 bits. For variable-length header extensions, the HEC field has a variable size as specified by the HEL field. Note that the length of each header extension MUST be a multiple of 32 bits. Additionally, the total size of the Tetrys header, including all header extensions and optional header fields, cannot exceed 255 32-bit words. 🫶

5.2. Source Packet Format

okay so a source packet is a common packet header encapsulation, plus a source symbol ID, plus a source symbol (the payload) 🧚 the source symbols MAY have variable sizes, so they're not all boxed the same way ✨

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   /                      Common Packet Header                     /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Source Symbol ID                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   /                            Payload                            /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 4: Source Packet Format

  • Common Packet Header: A common packet header (as common header format) where packet type is set to 0b00.
  • Source Symbol ID: The sequence number to identify a source symbol.
  • Payload: The payload (source symbol).

5.3. Coded Packet Format

a coded packet is the encapsulation of a common packet header, a coded symbol ID, the associated encoding vector, and a coded symbol (payload) 💖 this one's giving math, so hold on to your hat 🤓

since the source symbols MAY have variable sizes, all the source symbol sizes need to be encoded too. to make this encoded payload size a 16-bit unsigned value, the linear combination uses the same coefficients as the coded payload. the result MUST be stored in the coded packet as the encoded payload size (16 bits) 🔥 and because it's an optional field, the encoding vector MUST signal the use of variable source symbol sizes with the field V (see Section 5.3.1) 🌈

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   /                      Common Packet Header                     /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Coded Symbol ID                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   /                         Encoding Vector                       /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Encoded Payload Size      |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
   |                                                               |
   /                            Payload                            /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 5: Coded Packet Format

  • Common Packet Header: A common packet header (as common header format) where packet type is set to 0b01.
  • Coded Symbol ID: The sequence number to identify a coded symbol.
  • Encoding Vector: An encoding vector to define the linear combination used (coefficients and source symbols).
  • Encoded Payload Size: The coded payload size used if the source symbols have a variable size (optional, Section 5.3.1).
  • Payload: The coded symbol.

5.3.1. The Encoding Vector ✨

okay so bestie, an encoding vector is literally the full recipe 🧁 for one coded symbol. It holds all the info about the linear combination used to generate it, like the source identifiers and the coefficient for each source symbol. It MAY be stored in different ways depending on the situation, which is giving flexibility 💅

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     EV_LEN    |  CCGI | I |C|V|    NB_IDS     |   NB_COEFS    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        FIRST_SOURCE_ID                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     b_id      |                                               |
   +-+-+-+-+-+-+-+-+            id_bit_vector        +-+-+-+-+-+-+-+
   |                                                 |   Padding   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                          coef_bit_vector        +-+-+-+-+-+-+-+
   |                                                 |   Padding   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 6: Encoding Vector Format 🖼️

  • Encoding Vector Length (EV_LEN): 8 bits. The size in units of 32-bit words. 📏
  • Coding Coefficient Generator Identifier (CCGI): this is a 4-bit ID that identifies the algorithm or function used to generate the coefficients. Since a CCGI is included in each encoded vector, it MAY dynamically change between the generation of two coded symbols. The CCGI builds the coding coefficients used to generate the coded symbols. They MUST be known by all the Tetrys encoders or decoders. 🔐

Okay, the two RLC FEC schemes 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 with 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^(4)), multiplication between two elements is the multiplication modulo a given irreducible polynomial of degree 4. The following irreducible polynomial is used for GF(2^(4)):

x^(4) + x + 1

Now the actual CCGI options 👀

  • 0b00: Vandermonde-based coefficients over the finite field GF(2^(4)) as defined below. Each coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 16), with alpha the root of the primitive polynomial.
  • 0b01: Vandermonde-based coefficients over the finite field GF(2^(8)) as defined below. Each coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 256), with alpha the root of the primitive polynomial.
  • Let's say we want to generate the coded symbol 2 as a linear combination of the source symbols 1, 2, and 4 using CCGI set to 0b01. The coefficients will be alpha^( (1 * 1) % 256), alpha^( (1 * 2) % 256), and alpha^( (1 * 4) % 256). 🧮

Next up, the Store the Source Symbol ID Format (I) field, which is 2 bits 🎀

  • 0b00 means there is no source symbol ID information.
  • 0b01 means the encoding vector contains the edge blocks of the source symbol IDs without compression.
  • 0b10 means the encoding vector contains the compressed list of the source symbol IDs.
  • 0b11 means the encoding vector contains the compressed edge blocks of the source symbol IDs.

More fields, bestie 💖

  • Store the Encoding Coefficients (C): 1 bit to indicate if an encoding vector contains information about the coefficients used.
  • Having Source Symbols with Variable Size Encoding (V): Set V to 0b01 if the combination that refers to the encoding vector is a combination of source symbols with variable sizes. In this case, the coded packets MUST have the 'Encoded Payload Size' field. 📦
  • Number of Source IDs (NB_IDS): The number of source IDs stored in the encoding vector (depending on I).
  • Number of Coefficients (NB_COEFS): The number of the coefficients used to generate the associated coded symbol.
  • The First Source Identifier (FIRST_SOURCE_ID): The first source symbol ID used in the combination.
  • Number of Bits for Each Edge Block (b_id): The number of bits needed to store the edge.
  • Information about the Source Symbol IDs (id_bit_vector): If I is set to 0b01, store the edge blocks as b_id * (NB_IDS * 2 - 1). If I is set to 0b10, store the edge blocks in a compressed way.
  • The Coefficients (coef_bit_vector): The coefficients stored depending on the CCGI (4 or 8 bits for each coefficient).
  • Padding: Padding to have an encoding vector size that is a multiple of 32 bits (for the ID and coefficient part). 🫧

The source symbol IDs are organized as a sorted list of 32-bit unsigned integers. Depending on the feedback, the source symbol IDs in the list MAY be successive or not. If they are successive, the boundaries are stored in the encoding vector, and it just needs 2*32 bits of information. ✨ If not, the full list or the edge blocks MAY be stored, and a differential transform to reduce the number of bits needed to represent an identifier MAY be used. 🧠

For the following subsections, let's use an example: generating an encoding vector for a coded symbol that is a linear combination of the source symbols with IDs 1, 2, 3, 5, 6, 8, 9, and 10 (or as edge blocks: [1..3], [5..6], [8..10]). 🌸

There are several ways to store the source symbol IDs into the encoding vector:

  • If no information about the source symbol IDs is needed, the field I MUST be set to 0b00: no b_id and no id_bit_vector field.
  • If the edge blocks are stored without compression, the field I MUST be set to 0b01. In this case, set b_id to 32 (as a Symbol ID is 32 bits), and store the list of 32-bit unsigned integers (1, 3, 4, 5, 6, 10) into id_bit_vectors.
  • If the source symbol IDs are stored as a list with compression, the field I MUST be set to 0b10. In this case, see Section 5.3.1.1, but rather than compressing the edge blocks, we compress the full list of the source symbol IDs.
  • If the edge blocks are stored with compression, the field I MUST be set to 0b11. In this case, see Section 5.3.1.1.

5.3.1.1. Compressed List of Source Symbol IDs 🗜️

Let's keep going with the coded symbol from the previous section. The source symbol IDs used in the linear combination are: [1..3], [5..6], [8..10].

If we want to compress and store this list into the encoding vector, we MUST follow this procedure:

  1. Keep the first element in the packet as the first_source_id: 1.
  2. Apply a differential transform to the other elements ([3, 5, 6, 8, 10]) that removes the element i-1 from the element i, starting with the first_source_id as i0, and get the list L = [2, 2, 1, 2, 2].
  3. Compute b, the number of bits needed to store all the elements, which is ceil(log2(max(L))), where max(L) represents the maximum of the elements of the list L; here, it is 2 bits.
  4. Write b in the corresponding field, and write all the b * [(2 * NB blocks) - 1] elements in a bit vector here: 10, 10, 01, 10, 10.

5.3.1.2. Decompressing the Source Symbol IDs 🔓

When a Tetrys decoding block wants to reverse the operations, this algorithm is used:

  1. Rebuild the list of the transmitted elements by reading the bit vector and b: [10, 10, 01, 10, 10] => [2, 2, 1, 2, 2].
  2. Apply the reverse transform by adding successively the elements, starting with first_source_id: [1, 1 + 2, (1 + 2) + 2, (1 + 2 + 2) + 1, ...] => [1, 3, 5, 6, 8, 10].
  3. Rebuild the blocks using the list and first_source_id: [1..3], [5..6], [8..10]. 🎉

5.4. Window Update Packet Format ✨

okay so a Tetrys decoder MAY send window update packets back to another building block 🎀 these little messages tell the other side what got received, what got decoded, what got dropped, and extra stuff like the packet loss rate or how big the decoding buffers are 📦. the whole point is to help tune what's sitting in the encoding window 💅. and the window update packets are OPTIONAL, so they could be skipped or even lost in transit and the protocol behavior would still be totally fine 🦋 no drama.

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   /                      Common Packet Header                     /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        nb_missing_src                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   nb_not_used_coded_symb                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         first_src_id                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      plr      |   sack_size   |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
   |                                                               |
   /                          SACK Vector                          /
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 7: Window Update Packet Format

  • Common Packet Header: a common packet header (as common header format) where packet type is set to 0b10.
  • nb_missing_src: the number of missing source symbols in the receiver since the beginning of the session.
  • nb_not_used_coded_symb: the number of coded symbols at the receiver that have not already been used for decoding (e.g., the linear combinations contain at least two unknown source symbols).
  • first_src_id: ID of the first source symbol to consider in the selective acknowledgment (SACK) vector.
  • plr: packet loss ratio expressed as a percentage normalized to an 8-bit unsigned integer. For example, 2.5% will be stored as floor(2.5 * 256/100) = 6. Conversely, if 6 is the stored value, the corresponding packet loss ratio expressed as a percentage is 6*100/256 = 2.34%. This value is used in the case of dynamic code rate or for a statistical purpose. The choice of calculation is left to the Tetrys decoder, depending on a window observation, but should be the PLR seen before decoding.
  • sack_size: the size of the SACK vector in 32-bit words. For instance, with a value of 2, the SACK vector is 64 bits long.
  • SACK vector: bit vector indicating symbols that must be removed in the encoding window from the first source symbol ID. In most cases, these symbols were received by the receiver. The other cases concern some events with non-recoverable packets (i.e., in the case of a burst of losses) where it is better to drop and abandon some packets and remove them from the encoding window to allow the recovery of the following packets. The "First Source Symbol" is included in this bit vector. A bit equal to 1 at the i-th position means that this window update packet removes the source symbol of the ID equal to "First Source Symbol ID" + i from the encoding window.

6. Research Issues 🔬

okay bestie, so this part is all about the stuff we still need to figure out 🧠. the current document describes the baseline protocol, which lets a Tetrys encoder and Tetrys decoder talk to each other 💬. but in practice Tetrys can be used as a standalone protocol or embedded inside an existing one, and it can sit above, within, or below the transport layer 🌈. each of those setups has its own research questions that should be looked into for future improvements, and we break them down in the subsections below ✨.

6.1. Interaction with Congestion Control 🚦

the Tetrys component and the congestion control component make two separate channels (see [RFC9265], Section 2.1) 🛣️:

  • The Tetrys channel carries source and coded packets (from the sender to the receiver) and information from the receiver to the sender (e.g., signaling which symbols have been recovered, loss rate before and/or after decoding, etc.).
  • The congestion control channel carries packets from a sender to a receiver and packets signaling information about the network (e.g., number of packets received versus lost, Explicit Congestion Notification (ECN) marks, etc.) from the receiver to the sender.

the following topics, which [RFC9265] identifies and discusses, get adapted to the specific ways Tetrys can be deployed (i.e., above, within, or below the transport layer) 🎯:

  • Congestion-related losses may be hidden if Tetrys is deployed below the transport layer without any precaution (i.e., Tetrys recovering packets lost because of a congested router), which can severely impact the congestion control efficiency. An approach is suggested to avoid hiding such signals in [RFC9265], Section 5. 😬
  • Tetrys and non-Tetrys flows sharing the same network links can raise fairness issues between these flows. In particular, the situation depends on whether some of these flows and not others are congestion controlled and which type of congestion control is used. The details are out of scope of this document, but may have major impacts in practice. 🫣
  • Coding rate adaptation within Tetrys can have major impacts on congestion control if done inappropriately. This topic is discussed more in detail in Section 6.2. 📈
  • Tetrys can leverage multipath transmissions, with the Tetrys packets being sent to the same receiver through multiple paths. Since paths can largely differ, a per-path flow control and congestion control adaptation could be needed. 🛤️
  • Protecting several application flows within a single Tetrys flow raises additional questions. This topic is discussed more in detail in Section 6.3. 🧩

6.2. Adaptive Coding Rate 🎚️

when the network conditions (e.g., delay and loss rate) change a lot over time, an adaptive coding rate can be used to dynamically increase or reduce the amount of coded packets in a transmission (i.e., the added redundancy) 📊. this works with the help of a dedicated algorithm similar to [A-FEC]. once again, the strategy depends on which layer Tetrys is deployed in (i.e., above, within, or below the transport layer) 🍰. basically, we can split these strategies into two distinct classes: Tetrys deployment inside the transport layer versus outside the transport layer (i.e., above or below). a deployment within the transport layer means that interactions between transport protocol mechanisms such as error recovery, congestion control, and/or flow control are envisioned. otherwise, deploying Tetrys within a transport protocol that is not congestion controlled, like UDP, would not bring out any other advantage than deploying it below or above the transport layer 🤷‍♀️.

the impact of deploying a FEC mechanism within the transport layer is further discussed in Section 4 of [RFC9265], where considerations about the interactions between congestion control and coding rates, or the impact of fairness, get investigated 🔍. this adaptation may be done jointly with the congestion control mechanism of a transport layer protocol as proposed by [CTCP] 🤝. this lets you use monitored congestion control metrics (e.g., RTT, congestion events, or current congestion window size) to adapt the coding rate together with the computed transport sending rate ⏱️. the reasoning is to compute an amount of repair traffic that does not lead to congestion 🧘‍♀️. this joint optimization is mandatory to prevent flows from consuming the whole available capacity, as discussed in [RMCAT-ADAPTIVE-FEC], where the authors point out that an increase in the repair ratio should be done conjointly with a decrease in the source sending rate 💜.

finally, adapting a coding rate can also be done outside the transport layer without considering transport-layer metrics 🌐. in particular, this adaptation may be done jointly with the network, as proposed in [RED-FEC]. in that paper, the authors propose a Random Early Detection FEC mechanism in the context of video transmission over wireless networks 📺. basically, the idea is to add more redundancy packets if the queue at the access point is less occupied, and vice versa 🔁. a first theoretical attempt at video delivery with Tetrys has been proposed [THAI] 🎬. this approach is interesting because it shows a joint collaboration between the application requirements and the network conditions, and it combines both signals coming from the application needs and the network state (i.e., signals below or above the transport layer) 🫶.

to wrap this up, there are multiple ways to enable an adaptive coding rate 🎀. however, all of them depend on:

  • the signal metrics that can be monitored and used to adapt the coding rate;
  • the transport layer used, whether it is congestion controlled or not; and
  • the objective sought (e.g., to minimize congestion or to fit application requirements).

6.3. Using Tetrys below the IP Layer for Tunneling 🚇

using Tetrys to protect an aggregate of flows raises research questions when Tetrys is used to recover from IP datagram losses while tunneling 🧳. applying redundancy without flow differentiation may contradict the service requirements of individual flows: some flows may be penalized more by high latency and jitter than by partial reliability, while other flows may be penalized more by partial reliability 😵‍💫. in practice, head-of-line blocking impacts all flows in a similar manner despite their different needs, which suggests that more elaborate strategies inside Tetrys are needed 🙈.

7. Security Considerations 💀🔐

okay, this part is SERIOUS bestie, so listen up 🚨. first of all, it must be clear that using FEC protection on a data stream does not provide any kind of security per se 🙅‍♀️. on the contrary, using FEC protection on a data stream raises security risks 😱. the situation with Tetrys is mostly similar to that of other content delivery protocols that use FEC protection, and this is well described in FECFRAME [RFC6363] 📚. this section builds on that reference and adds new considerations to account for Tetrys specifics where it's meaningful 🧠✨.

7.1. Problem Statement 🕵️‍♀️

an attacker can target the content, the protocol, or the network 🎯. the consequences will differ a lot depending on the goal, like gaining access to confidential content, corrupting the content, compromising the Tetrys encoder and/or Tetrys decoder, or compromising the network behavior 🥀. in particular, several of these attacks aim to create a Denial-of-Service (DoS) with consequences that may be limited to a single node (e.g., the Tetrys decoder), or that may impact all the nodes attached to the targeted network (e.g., by making flows unresponsive to congestion signals) 📉.

in the following sections, we discuss these attacks according to the component the attacker targets 🧵.

7.2. Attacks against the Data Flow 👀✨

Okay so an attacker might wanna eavesdrop on the traffic between the Tetrys encoder/decoder and read the tea 🍵. The usual fix is traffic encryption 🔐, and you can slap it on the source flow upstream of the Tetrys encoder or on the output packets downstream of it. Where you put it depends on stuff like the attacker model. For example, if encryption happens below Tetrys, the security risk is assumed to be on the interconnection network 🧚.

An attacker could also try to corrupt the content 💀, like by injecting forged or modified source and coded packets so the Tetrys decoder can't recover the original source flow. To stop that, you need content integrity and source authentication at the packet level 🛡️. These services need to live below Tetrys so the receiver can drop the sus packets and only pass legit ones to the Tetrys decoder 💅. Also, forging or modifying feedback packets won't corrupt the content, but it will absolutely compromise Tetrys operation (see Section 7.3) 😭.

7.3. Attacks against Signaling 📡💜

Messing with signaling is a whole mood. If someone forges or modifies feedback packets to fake good reception or recovery of source content, the Tetrys decoder can easily stop recovering the source flow, and boom, that's a DoS 🙈. To prevent this, you need content integrity and source authentication at the packet level for the feedback flow from the Tetrys decoder to the Tetrys encoder too 🔒. Again, these services need to be provided below Tetrys so undesired packets get dropped and only legit feedback packets reach the Tetrys encoder 🧼.

Now the plot twist 🌀: an attacker who can only selectively drop feedback packets (instead of modifying them) won't really hurt Tetrys, since it's naturally robust when hit with that kind of loss 💪. Still, there are side effects. The Tetrys encoder can't remove well-received or decoded source packets from its linear system, so the systems get bigger, and that mechanically increases computational costs on both sides (encoder and decoder) 🧮💀.

7.4. Attacks against the Network 🌐🔥

Tetrys can react to congestion signals (Section 6.1) so it plays fair with other flows on a shared network 🤝. Sneaky attacker alert 🚨: someone could exploit that by creating or reinforcing congestion events (e.g., by forging or modifying feedback packets), which can potentially hit a significant number of nodes attached to the network 😱. To mitigate this, content integrity and source authentication at the packet level are needed so the receiver can drop undesired packets and only pass legit ones to the Tetrys encoder and decoder 🫶.

7.5. Baseline Security Operation 🔒🌈

Tetrys can totally benefit from an IPsec / Encapsulating Security Payload (IPsec/ESP) [RFC4303] 🎀. It gives you confidentiality, origin authentication, integrity, and anti-replay services, among others ✨. IPsec/ESP can protect the Tetrys data flows (both directions) against attackers hanging out in the interconnection network, or attackers who try to eavesdrop, inject forged traffic, or replay legit traffic 🦋.

8. IANA Considerations 🌸

This document has no IANA actions. Nothing to see here for the registry gremlins 🧚.

9. References 📚

9.1. Normative References 💖

9.2. Informative References 🦋

  • [A-FEC] Bolot, J., Fosse-Parisis, S., and D. Towsley, "Adaptive FEC-based error control for Internet telephony", IEEE INFOCOM '99, Conference on Computer Communications, New York, NY, USA, Vol. 3, pp. 1453-1460, DOI 10.1109/INFCOM.1999.752166, March 1999, https://doi.org/10.1109/INFCOM.1999.752166.
  • [AHL-00] Ahlswede, R., Cai, N., Li, S., and R. Yeung, "Network information flow", IEEE Transactions on Information Theory, Vol. 46, Issue 4, pp. 1204-1216, DOI 10.1109/18.850663, July 2000, https://doi.org/10.1109/18.850663.
  • [CTCP] Kim, M., Cloud, J., ParandehGheibi, A., Urbina, L., Fouli, K., Leith, D., and M. Medard, "Network Coded TCP (CTCP)", arXiv 1212.2291v3, April 2013, https://arxiv.org/abs/1212.2291.
  • [RED-FEC] Lin, C., Shieh, C., Chilamkurti, N., Ke, C., and W. Hwang, "A RED-FEC Mechanism for Video Transmission Over WLANs", IEEE Transactions on Broadcasting, Vol. 54, Issue 3, pp. 517-524, DOI 10.1109/TBC.2008.2001713, September 2008, https://doi.org/10.1109/TBC.2008.2001713.
  • [RMCAT-ADAPTIVE-FEC] Singh, V., Nagy, M., Ott, J., and L. Eggert, "Congestion Control Using FEC for Conversational Media", Work in Progress, Internet-Draft, draft-singh-rmcat-adaptive-fec-03, 20 March 2016, https://datatracker.ietf.org/doc/html/draft-singh-rmcat-adaptive-fec-03.
  • [Tetrys] Lacan, J. and E. Lochin, "Rethinking reliability for long-delay networks", International Workshop on Satellite and Space Communications, Toulouse, France, pp. 90-94, DOI 10.1109/IWSSC.2008.4656755, October 2008, https://doi.org/10.1109/IWSSC.2008.4656755.
  • [Tetrys-RT] Tournoux, P., Lochin, E., Lacan, J., Bouabdallah, A., and V. Roca, "On-the-Fly Erasure Coding for Real-Time Video Applications", IEEE Transactions on Multimedia, Vol. 13, Issue 4, pp. 797-812, DOI 10.1109/TMM.2011.2126564, August 2011, http://dx.doi.org/10.1109/TMM.2011.2126564.
  • [THAI] Tran Thai, T., Lacan, J., and E. Lochin, "Joint on-the-fly network coding/video quality adaptation for real-time delivery", Signal Processing: Image Communication, Vol. 29 Issue 4, pp. 449-461, DOI 10.1016/j.image.2014.02.003, April 2014, https://doi.org/10.1016/j.image.2014.02.003.

Acknowledgments 🫶💕

First, the authors want to sincerely thank Marie-Jose Montpetit for continuous help and support on Tetrys. Marie-Jo, many thanks! 🥰

The authors also wish to thank NWCRG group members for numerous discussions on on-the-fly coding that helped finalize this document 🧠✨.

Finally, the authors would like to thank Colin Perkins for providing comments and feedback on the document 🎀.

Authors' Addresses 💌

Jonathan Detchart
ISAE-SUPAERO
BP 54032
10, avenue Edouard Belin
31055 Toulouse CEDEX 4
France
Email: jonathan.detchart@isae-supaero.fr
Emmanuel Lochin
ENAC
7, avenue Edouard Belin
31400 Toulouse
France
Email: emmanuel.lochin@enac.fr
Jerome Lacan
ISAE-SUPAERO
BP 54032
10, avenue Edouard Belin
31055 Toulouse CEDEX 4
France
Email: jerome.lacan@isae-supaero.fr
Vincent Roca
INRIA
Inovallee; Montbonnot
655, avenue de l'Europe
38334 St Ismier CEDEX
France
Email: vincent.roca@inria.fr
📦 where this page comes from