TSVWG                                                            V. Roca
Internet-Draft                                                  B. Teibi
Intended status: Standards Track                                   INRIA                             E. Baccelli
Expires: March 23, July 21, 2019                                             INRIA
                                                        January 17, 2019                               September 19, 2018

Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC)
                          Schemes for FECFRAME
                   draft-ietf-tsvwg-rlc-fec-scheme-09
                   draft-ietf-tsvwg-rlc-fec-scheme-10

Abstract

   This document describes two fully-specified Forward Erasure
   Correction (FEC) Schemes for Sliding Window Random Linear Codes
   (RLC), one for RLC over the Galois Field (A.K.A.  Finite Field)
   GF(2), a second one for RLC over the Galois Field GF(2^^8), each time
   with the possibility of controlling the code density.  They can
   protect arbitrary media streams along the lines defined by FECFRAME
   extended to sliding window FEC codes, as defined in [fecframe-ext].
   These sliding window FEC codes rely on an encoding window that slides
   over the source symbols, generating new repair symbols whenever
   needed.  Compared to block FEC codes, these sliding window FEC codes
   offer key advantages with real-time flows in terms of reduced FEC-
   related latency while often providing improved packet erasure
   recovery capabilities.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on March 23, July 21, 2019.

Copyright Notice

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

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

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Limits of Block Codes with Real-Time Flows  . . . . . . .   3   4
     1.2.  Lower Latency and Better Protection of Real-Time Flows
           with the Sliding Window RLC Codes . . . . . . . . . . . .   4
     1.3.  Small Transmission Overheads with the Sliding Window RLC
           FEC Scheme  . . . . . . . . . . . . . . . . . . . . . . .   5
     1.4.  Document Organization . . . . . . . . . . . . . . . . . .   6
   2.  Definitions and Abbreviations . . . . . . . . . . . . . . . .   6
   3.  Common Procedures . . . . . . . . . . . . . . . . . . . . . . . . .   7
     3.1.  Possible Parameter Derivations  . . . .  Codec Parameters  . . . . . . . . .   7
       3.1.1.  Case of a CBR Real-Time Flow . . . . . . . . . . .   7
     3.2.  ADU, ADUI and Source Symbols Mappings .   8
       3.1.2.  Other Types of Real-Time Flow . . . . . . . . .   9
     3.3.  Encoding Window Management  . . .  10
       3.1.3.  Case of a Non Real-Time Flow . . . . . . . . . . . .  11
     3.2.  ADU, ADUI and  10
     3.4.  Source Symbols Mappings . . . . . . . . . .  11
     3.3.  Encoding Window Management  . Symbol Identification  . . . . . . . . . . . . . .  13
     3.4.  11
     3.5.  Pseudo-Random Number Generator (PRNG) . . . . . . . . . .  13
     3.5.  11
     3.6.  Coding Coefficients Generation Function . . . . . . . . .  15
     3.6.  17
     3.7.  Finite Fields Operations  . . . . . . . . . . . . . . . .  17
       3.6.1.  19
       3.7.1.  Finite Field Definitions  . . . . . . . . . . . . . .  17
       3.6.2.  19
       3.7.2.  Linear Combination of Source Symbols Computation  . .  17  19
   4.  Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary
       Packet Flows  . . . . . . . . . . . . . . . . . . . . . . . .  18  20
     4.1.  Formats and Codes . . . . . . . . . . . . . . . . . . . .  18  20
       4.1.1.  FEC Framework Configuration Information . . . . . . .  18  20
       4.1.2.  Explicit Source FEC Payload ID  . . . . . . . . . . .  19  22
       4.1.3.  Repair FEC Payload ID . . . . . . . . . . . . . . . .  20
       4.1.4.  Additional  22
     4.2.  Procedures  . . . . . . . . . . . . . . . .  21 . . . . . . .  24
   5.  Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet
       Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . .  21  24
     5.1.  Formats and Codes . . . . . . . . . . . . . . . . . . . .  21  24
       5.1.1.  FEC Framework Configuration Information . . . . . . .  22  24
       5.1.2.  Explicit Source FEC Payload ID  . . . . . . . . . . .  22  24
       5.1.3.  Repair FEC Payload ID . . . . . . . . . . . . . . . .  22
       5.1.4.  Additional  24

     5.2.  Procedures  . . . . . . . . . . . . . . . .  22 . . . . . . .  25
   6.  FEC Code Specification  . . . . . . . . . . . . . . . . . . .  22  25
     6.1.  Encoding Side . . . . . . . . . . . . . . . . . . . . . .  22  25
     6.2.  Decoding Side . . . . . . . . . . . . . . . . . . . . . .  23  25
   7.  Implementation Status . . . . . . . . . . . . . . . . . . . .  24  26
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .  24  27
     8.1.  Attacks Against the Data Flow . . . . . . . . . . . . . .  24  27
       8.1.1.  Access to Confidential Content  . . . . . . . . . . .  24  27
       8.1.2.  Content Corruption  . . . . . . . . . . . . . . . . .  25  27
     8.2.  Attacks Against the FEC Parameters  . . . . . . . . . . .  25  27
     8.3.  When Several Source Flows are to be Protected Together  .  26  29
     8.4.  Baseline Secure FEC Framework Operation . . . . . . . . .  26  29
     8.5.  Additional Security Considerations for Numerical
           Computations  . . . . . . . . . . . . . . . . . . . . . .  27  29
   9.  Operations and Management Considerations  . . . . . . . . . .  27  30
     9.1.  Operational Recommendations: Finite Field GF(2) Versus
           GF(2^^8)  . . . . . . . . . . . . . . . . . . . . . . . .  27  30
     9.2.  Operational Recommendations: Coding Coefficients Density
           Threshold . . . . . . . . . . . . . . . . . . . . . . . .  28  30
   10. IANA Considerations . . . . . . . . . . . . . . . . . . . . .  28  31
   11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .  28  31
   12. References  . . . . . . . . . . . . . . . . . . . . . . . . .  28  31
     12.1.  Normative References . . . . . . . . . . . . . . . . . .  28  31
     12.2.  Informative References . . . . . . . . . . . . . . . . .  29  32
   Appendix A.  TinyMT32 Pseudo-Random Number Generator Validation Criteria (Normative) . . . . . .  31  34
   Appendix B.  Assessing the PRNG Adequacy (Informational)  . . . .  35
   Appendix C.  Possible Parameter Derivation (Informational)  . . .  37
     C.1.  Case of a CBR Real-Time Flow  . . . . . . . . . . . . . .  38
     C.2.  Other Types of Real-Time Flow . . . . . . . . . . . . . .  40
     C.3.  Case of a Non Real-Time Flow  . . . . . . . . . . . . . .  41
   Appendix D.  Decoding Beyond Maximum Latency Optimization
                (Informational)  . . . .  35
   Authors' Addresses . . . . . . . . . . . . . .  41
   Authors' Addresses  . . . . . . . . .  36

1.  Introduction

   Application-Level . . . . . . . . . . . . . .  42

1.  Introduction

   Application-Level Forward Erasure Correction (AL-FEC) codes, or
   simply FEC codes, are a key element of communication systems.  They
   are used to recover from packet losses (or erasures) during content
   delivery sessions to a potentially large number of receivers
   (multicast/broadcast transmissions).  This is the case with the
   FLUTE/ALC protocol [RFC6726] when used for reliable file transfers
   over lossy networks, and the FECFRAME protocol when used for reliable
   continuous media transfers over lossy networks.

   The present document only focuses on the FECFRAME protocol, used in
   multicast/broadcast delivery mode, in particular for contents that
   feature stringent real-time constraints: each source packet has a
   maximum validity period after which it will not be considered by the
   destination application.

1.1.  Limits of Block Codes with Real-Time Flows

   With FECFRAME, there is a single FEC encoding point (either a end-
   host/server (source) or a middlebox) and a single FEC decoding point
   per receiver (either a end-host (receiver) or middlebox).  In this
   context, currently standardized AL-FEC codes for FECFRAME like Reed-Solomon Reed-
   Solomon [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ, are
   all linear block codes: they require the data flow to be segmented
   into blocks of a predefined maximum size.

   To define this block size, it is required to find an appropriate
   balance between robustness and decoding latency: the larger the block
   size, the higher the robustness (e.g., in front case of long packet erasure
   bursts), but also the higher the maximum decoding latency (i.e., the
   maximum time required to recover a lost (erased) packet thanks to FEC
   protection).  Therefore, with a multicast/broadcast session where
   different receivers experience different packet loss rates, the block
   size should be chosen by considering the worst communication
   conditions one wants to support, but without exceeding the desired
   maximum decoding latency.  This choice then impacts the FEC-related
   latency of all receivers, even those experiencing a good
   communication quality, since no FEC encoding can happen until all the
   source data of the block is available at the sender, which directly
   depends on the block size.

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

   This document introduces two fully-specified FEC Schemes that do not
   follow
   a totally different the block code approach: the Sliding Window Random Linear
   Codes (RLC) over either Galois Fields (A.K.A.  Finite Fields) GF(2)
   (the "binary case") or GF(2^^8), each time with the possibility of
   controlling the code density.  These FEC Schemes are used to protect
   arbitrary media streams along the lines defined by FECFRAME extended
   to sliding window FEC codes [fecframe-ext].  These FEC Schemes, and
   more generally Sliding Window FEC codes, are recommended for instance
   instance, with media that feature real-time constraints sent within a
   multicast/broadcast session [Roca17].

   The RLC codes belong to the broad class of sliding window sliding-window AL-FEC
   codes (A.K.A. convolutional codes) [RFC8406].  The encoding process
   is based on an encoding window that slides over the set of source
   packets (in fact source symbols as we will see in Section 3.2), this
   window being either of fixed size or variable size (A.K.A. an elastic
   window).  Repair symbols are generated on-the-fly, by computing a
   random linear combination of the source symbols present in the
   current encoding window, and passed to the transport layer.

   At the receiver, a linear system is managed from the set of received
   source and repair packets.  New variables (representing source
   symbols) and equations (representing the linear combination carried
   by each repair symbol received) are added upon receiving new packets.
   Variables and the equations they are involved in are removed when
   they are too old with respect to their validity period (real-time
   constraints) .  Lost source symbols are then recovered thanks to this
   linear system whenever its rank permits to solve it (at least
   partially).

   The protection of any multicast/broadcast session needs to be
   dimensioned by considering the worst communication conditions one
   wants to support.  This is also true with RLC (more generally any
   sliding window) code.  However  However, the receivers experiencing a good to
   medium communication quality will observe a reduced FEC-related
   latency compared to block codes [Roca17] since an isolated lost
   source packet is quickly recovered with the following repair packet.
   On the opposite, with a block code, recovering an isolated lost
   source packet always requires waiting for the first repair packet to
   arrive after the end of the block.  Additionally, under certain
   situations (e.g., with a limited FEC-related latency budget and with
   constant bitrate transmissions after FECFRAME encoding), sliding
   window codes can more efficiently achieve a target transmission
   quality (e.g., measured by the residual loss after FEC decoding) by
   sending fewer repair packets (i.e., higher code rate) than block
   codes.

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

   The Sliding Window RLC FEC Scheme is designed to limit the packet
   header overhead.  The main requirement is that each repair packet
   header must enable a receiver to reconstruct the set of source
   symbols plus the associated coefficients used during the encoding
   process.  In order to minimize packet overhead, the set of source
   symbols in the encoding window as well as the set of coefficients
   over GF(2^^m) (where m is 1 or 8, depending on the FEC Scheme) used
   in the linear combination are not individually listed in the repair
   packet header.  Instead, each FEC Repair Packet header contains:

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

   Therefore, no matter the number of source symbols present in the
   encoding window, each FEC Repair Packet features a fixed 64-bit long
   header, called Repair FEC Payload ID (Figure 7). 8).  Similarly, each FEC
   Source Packet features a fixed 32-bit long trailer, called Explicit
   Source FEC Payload ID (Figure 5), 6), that contains the ESI of the first
   source symbol (Section 3.2).

1.4.  Document Organization

   This fully-specified FEC Scheme follows the structure required by
   [RFC6363], section 5.6.  "FEC Scheme Requirements", namely:

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

2.  Definitions and Abbreviations

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

   This document uses the following definitions and abbreviations:

   a^^b  a to the power of b
   GF(q)  denotes a finite field (also known as the Galois Field) with q
      elements.  We assume that q = 2^^m in this document
   m  defines the length of the elements in the finite field, in bits.
      In this document, m is equal to 1 or 8
   ADU:  Application Data Unit
   ADUI:  Application Data Unit Information (includes the F, L and
      padding fields in addition to the ADU)
   E: size of an encoding symbol (i.e., source or repair symbol),
      assumed fixed (in bytes)
   br_in:  transmission bitrate at the input of the FECFRAME sender,
      assumed fixed (in bits/s)
   br_out:  transmission bitrate at the output of the FECFRAME sender,
      assumed fixed (in bits/s)
   max_lat:  maximum FEC-related latency within FECFRAME (in (a decimal
      number expressed in seconds)
   cr:  RLC coding rate, ratio between the total number of source
      symbols and the total number of source plus repair symbols
   ew_size:  encoding window current size at a sender (in symbols)
   ew_max_size:  encoding window maximum size at a sender (in symbols)
   dw_max_size:  decoding window maximum size at a receiver (in symbols)
   ls_max_size:  linear system maximum size (or width) at a receiver (in
      symbols)
   WSR:  window size ratio parameter used to derive ew_max_size
      (encoder) and ls_max_size (decoder).
   PRNG:  pseudo-random number generator
   tinymt32_rand(maxv):
   TinyMT32:  PRNG defined in Section 3.4 3.5 and used in this
      specification, that returns a new random integer in [0; maxv-1]
      specification.
   DT:  coding coefficients density threshold, an integer between 0 and
      15 (inclusive) the controls the fraction of coefficients that are
      non zero

3.  Common Procedures

   This section introduces the procedures that are used by these FEC
   Schemes.

3.1.  Possible Parameter Derivations

   The  Codec Parameters

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

   Maximum FEC-related latency budget, max_lat (in (a decimal number
   expressed in seconds) with real-
   time real-time flows:
      a source ADU flow can have real-time constraints, and therefore
      any FECFRAME related operation should take place within the
      validity period of each ADU (Appendix B D describes an exception to
      this rule).  When there are multiple flows with different real-
      time constraints, we consider the most stringent constraints (see
      [RFC6363], Section 10.2, item 6, for recommendations when several
      flows are globally protected).  The maximum FEC-related latency
      budget, max_lat, accounts for all sources of latency added by FEC
      encoding (at a sender) and FEC decoding (at a receiver).  Other
      sources of latency (e.g., added by network communications) are out
      of scope and must be considered separately (said differently, they
      have already been deducted from max_lat).  max_lat can be regarded
      as the latency budget permitted for all FEC-related operations.
      This is an input parameter that enables a FECFRAME sender to
      derive other internal parameters as explained below; (see Appendix C);
   Encoding window current (resp. maximum) size, ew_size (resp.
   ew_max_size) (in symbols):
      at a FECFRAME sender, during FEC encoding, a repair symbol is
      computed as a linear combination of the ew_size source symbols
      present in the encoding window.  The ew_max_size is the maximum
      size of this window, while ew_size is the current size.  For
      instance, at session start, upon receiving new source ADUs, the
      ew_size progressively increases until it reaches its maximum
      value, ew_max_size.  We have:

         0 < ew_size <= ew_max_size
   Decoding window maximum size, dw_max_size (in symbols):  at a
      FECFRAME receiver, dw_max_size is the maximum number of received
      or lost source symbols that are still within their latency budget;
   Linear system maximum size, ls_max_size (in symbols):  at a FECFRAME
      receiver, the linear system maximum size, ls_max_size, is the
      maximum number of received or lost source symbols in the linear
      system (i.e., the variables).  It SHOULD NOT be smaller than
      dw_max_size since it would mean that, even after receiving a
      sufficient number of FEC Repair Packets, a lost ADU may not be
      recovered just because the associated source symbols have been
      prematurely removed from the linear system, which is usually
      counter-productive.  On the opposite, the linear system MAY grow
      beyond the dw_max_size (Appendix B); D);
   Symbol size, E (in bytes):  the E parameter determines the source and
      repair symbol sizes (necessarily equal).  This is an input
      parameter that enables a FECFRAME sender to derive other internal
      parameters, as explained below.  An implementation at a sender
      SHOULD
      MUST fix the E parameter and MUST communicate it as part of the
      FEC Scheme-Specific Information (Section 4.1.1.2).
   Code rate, cr:  The code rate parameter determines the amount of
      redundancy added to the flow.  More precisely the cr is the ratio
      between the total number of source symbols and the total number of
      source plus repair symbols and by definition: 0 < cr <= 1.  This
      is an input parameter that enables a FECFRAME sender to derive
      other internal parameters, as explained below.  However  However, there is
      no need to communicate the cr parameter per see (it's not required
      to process a repair symbol at a receiver).  This code rate
      parameter can be static.  However, in specific use-cases (e.g.,
      with unicast transmissions in presence of a feedback mechanism
      that estimates the communication quality, out of scope of
      FECFRAME), the code rate may be adjusted dynamically.

   The FEC Schemes can be used in various manners.  They can be used

   Appendix C proposes non normative technics to
   protect derive those
   parameters, depending on the use-case specificities.

3.2.  ADU, ADUI and Source Symbols Mappings

   At a source sender, an ADU flow having real-time constraints, or a non-
   realtime coming from the application is not directly
   mapped to source ADU flow.  The symbols.  When multiple source ADU flows (e.g., media
   streams) are mapped onto the same FECFRAME instance, each flow may be a Constant
   Bitrate (CBR) or Variable BitRate (VBR) flow.  The flow's minimum/
   maximum bitrate might or might not be known.  The is
   assigned its own Flow ID value (see below).  This Flow ID is then
   prepended to each ADU before FEC Schemes can encoding.  This way, FEC decoding at
   a receiver also recovers this Flow ID and the recovered ADU can be used over
   assigned to the Internet or over a CBR communication path.  It
   follows right source flow (note that the FEC Scheme parameters can be derived in different
   ways, as described in 5-tuple used to
   identify the following sections.

3.1.1.  Case right source flow of a CBR Real-Time Flow

   In the following, we consider a real-time flow received ADU is absent with max_lat latency
   budget.  The encoding symbol size, E, a
   recovered ADU since it is constant.  The code rate,
   cr, not FEC protected).

   Additionally, since ADUs are of variable size, padding is also constant, needed so
   that each ADU (with its value depending on flow identifier) contribute to an integral
   number of source symbols.  This requires adding the expected
   communication loss model (this choice is out original ADU
   length to each ADU before doing FEC encoding.  Because of scope these
   requirements, an intermediate format, the ADUI, or ADU Information,
   is considered [RFC6363].

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

   Flow ID (F) (8-bit field):  this
   document).

   In a first configuration, unsigned byte contains the integer
      identifier associated to the source ADU flow bitrate at the input of
   the FECFRAME sender is fixed and equal to br_in (in bits/s), and which this
   value is known by the FECFRAME sender. ADU
      belongs.  It follows is assumed that the
   transmission bitrate at the output of the FECFRAME sender a single byte is sufficient, which
      implies that no more than 256 flows will be
   higher, depending on the added repair flow overhead.  In order to
   comply with the maximum FEC-related latency budget, we have:

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

   In protected by a second configuration, the single
      FECFRAME sender generates a fixed
   bitrate flow, equal to session instance.
   Length (L) (16-bit field):  this unsigned integer contains the CBR communication path bitrate equal to
   br_out (in bits/s), and length
      of this value ADU, in network byte order (i.e., big endian).  This
      length is known by for the FECFRAME sender,
   as in [Roca17].  The maximum source flow bitrate needs to be such
   that, with the added repair flow overhead, ADU itself and does not include the total transmission
   bitrate remains inferior F, L, or equal to br_out.  We have:

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

   For decoding to be possible within the latency budget, it Pad
      fields.

   Then, zero padding is required
   that added to the encoding window maximum ADU if needed:

   Padding (Pad) (variable size be smaller than or at most
   equal field):  this field contains zero
      padding to align the decoding window maximum size, the exact value having no
   impact on F, L, ADU and padding up to a size that is
      multiple of E bytes (i.e., the source and repair symbol length).

   The data unit resulting from the FEC-related latency budget.  For ADU and the FEC Schemes
   specified in F, L, and Pad fields is
   called ADUI.  Since ADUs can have different sizes, this document, in line with [Roca17], the ew_max_size
   SHOULD be computed with:

      ew_max_size = dw_max_size * 0.75

   The ew_max_size is also the main parameter at a FECFRAME sender.  It is
   RECOMMENDED
   case for ADUIs.  However, an ADUI always contributes to check an integral
   number of source symbols.

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

    Figure 1: ADUI Creation example (here 3 source symbols are created
                              for this ADUI).

   Note that neither the ew_max_size value stays within
   reasonnable bounds in order to avoid hazardous behaviours.

   The dw_max_size is computed by a FECFRAME sender but not explicitly
   communicated to a FECFRAME receiver.  However a FECFRAME receiver can
   easily evaluate initial 3 bytes nor the ew_max_size by observing optional padding are
   sent over the maximum Number of network.  However, they are considered during FEC
   encoding, and a receiver who lost a certain FEC Source Symbols (NSS) value contained in Packet (e.g.,
   the Repair FEC Payload ID of
   received UDP datagram containing this FEC Repair Packets (Section 4.1.3).  A receiver can then
   easily compute dw_max_size:

      dw_max_size = max_NSS_observed / 0.75

   A receiver can then chose an appropriate linear system maximum size:

      ls_max_size >= dw_max_size

   It Source Packet when UDP is good practice to use a larger value for ls_max_size used
   as
   explained in Appendix B, which does not impact maximum latency nor
   interoperability.  However the linear system size should not transport protocol) will be too
   large for practical reasons (e.g., in order to limit computation
   complexity).  It is RECOMMENDED able to check that recover the ls_max_size value
   stays within reasonnable bounds in order ADUI if FEC
   decoding succeeds.  Thanks to avoid hazardous
   behaviours.

   The particular case the initial 3 bytes, this receiver will
   get rid of session start needs to be managed
   appropriately.  Here ew_size increases each time a new source ADU is
   received by the FECFRAME sender, until it reaches padding (if any) and identify the ew_max_size
   value.  A FECFRAME receiver SHOULD continuously observe corresponding ADU
   flow.

3.3.  Encoding Window Management

   Source symbols and the received
   FEC Repair Packets, since corresponding ADUs are removed from the NSS value carried in
   encoding window:

   o  when the Repair FEC
   Payload ID will increase too, and adjust sliding encoding window has reached its ls_max_size accordingly
   if need be.

3.1.2.  Other Types of Real-Time Flow maximum size,
      ew_max_size.  In other configurations, a real-time source ADU flow, with a max_lat
   latency budget, features a variable bitrate (VBR).  A first approach
   consists in considering the smallest instantaneous bitrate of the
   source ADU flow, when this parameter is known, and to reuse the
   derivation of Section 3.1.1.  Considering that case the smallest bitrate means oldest symbol MUST be removed
      before adding a new symbol, so that the current encoding window and decoding window maximum sizes estimation
   are pessimistic: these windows have the smallest
      size required always remains inferior or equal to
   enable a decoding on-time at a FECFRAME receiver.  If the
   instantaneous bitrate is higher than this smallest bitrate, this
   approach leads to maximum size: ew_size
      <= ew_max_size;
   o  when an encoding window that is unnecessarily small,
   which reduces robustness in front of long erasure bursts.

   Another approach consists in using ADU timing information (e.g.,
   using the timestamp field of an RTP packet header, or registering the
   time upon receiving a new ADU).  From the global FEC-related latency
   budget the FECFRAME sender can derive a practical has reached its maximum latency
   budget for encoding operations, max_lat_for_encoding.  For the FEC
   Schemes specified validity duration in case of a
      real-time flow.  When this document, this latency budget SHOULD be
   computed with:

      max_lat_for_encoding = max_lat * 0.75

   It follows that any happens, all source symbols associated
      corresponding to an ADU the ADUI that has
   timed-out with respect to max_lat_for_encoding expired SHOULD be removed from the
      encoding window.  With this approach there is no pre-determined
   ew_size value: this value fluctuates over the time according window;

   Source symbols are added to the
   instantaneous source ADU flow bitrate.  For practical reasons, a
   FECFRAME sender may still require that ew_size does not increase
   beyond sliding encoding window each time a maximum value (Section 3.1.3).

   With both approaches, and no matter
   new ADU arrives, once the choice ADU-to-source symbols mapping has been
   performed (Section 3.2).  The current size of the FECFRAME
   sender, encoding window,
   ew_size, is updated after adding new source symbols.  This process
   may require to remove old source symbols so that: ew_size <=
   ew_max_size.

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

3.4.  Source Symbols (NSS) value
   contained in the Repair FEC Payload Symbol Identification

   Each source symbol is identified by an Encoding Symbol ID of received FEC Repair
   Packets.  A receiver can then compute dw_max_size and derive (ESI), an
   appropriate ls_max_size as explained in Section 3.1.1.

   When
   unsigned integer.  The ESI of source symbols MUST start with value 0
   for the observed NSS fluctuates significantly, a FECFRAME receiver
   may want first source symbol and MUST be managed sequentially.
   Wrapping to adapt its ls_max_size accordingly.  In particular when zero happens after reaching the NSS maximum value made
   possible by the ESI field size (this maximum value is significantly reduced, a FECFRAME receiver may want FEC Scheme
   dependant, for instance, 2^32-1 with FEC Schemes XXX and YYY).

   No such consideration applies to
   reduce the ls_max_size too in repair symbols.

3.5.  Pseudo-Random Number Generator (PRNG)

   In order to limit computation complexity.
   However it is usually preferable to use a ls_max_size "too large"
   (which can increase computation complexity and memory requirements)
   than compute coding coefficients (see Section 3.6), the opposite (which can reduce recovery performance).

   Beyond these general guidelines, RLC
   FEC Schemes defined in this document rely on the details TinyMT32 PRNG (a
   small-sized variant of how to manage these
   situations at a FECFRAME sender the Mersenne Twister PRNG), as defined in the
   reference implementation version 1.1 (2015/04/24) by Mutsuo Saito
   (Hiroshima University) and receiver can depend on additional
   considerations that are out of scope of this document.

3.1.3.  Case Makoto Matsumoto (The University of a Non Real-Time Flow

   Finally there are configurations where a source ADU flow has no real-
   time constraints.  FECFRAME
   Tokyo).

   o  Official web site: <http://www.math.sci.hiroshima-u.ac.jp/~m-
      mat/MT/TINYMT/>
   o  Official github site and reference implementation:
      <https://github.com/MersenneTwister-Lab/TinyMT>

   For the RLC FEC Schemes defined in this
   document can still document, the TinyMT32 32-bit
   version (rather than the 64-bit version) MUST be used.  The choice of appropriate  This PRNG
   requires a parameter
   values can set that needs to be directed by practical considerations. pre-calculated.  For instance it
   can derive from an estimation of the maximum memory amount that could
   be dedicated to
   RLC FEC Schemes defined in this document, the linear system at a FECFRAME receiver, or following parameter set
   MUST be used:

   o  mat1 = 0x8f7011ee = 2406486510
   o  mat2 = 0xfc78ff1f = 4235788063
   o  tmat = 0x3793fdff = 932445695

   This parameter set is the
   maximum computation complexity at a FECFRAME receiver, both first entry of them
   depending on the ls_max_size parameter.  The same considerations also
   apply to the FECFRAME sender, where the maximum memory amount and
   computation complexity depend on the ew_max_size parameter.

   Here also, the NSS value contained precalculated parameter
   sets in FEC Repair Packets file tinymt32dc.0.1048576.txt, by Kenji Rikitake, and
   available at <https://github.com/jj1bdx/tinymtdc-
   longbatch/blob/master/tinymt32dc/tinymt32dc.0.1048576.txt>.  This is
   also the parameter set used by in [KR12].

   This PRNG MUST first be initialized with a
   FECFRAME receiver 32-bit unsigned integer,
   used as a seed.  The following function is used to determine the current coding window size and
   ew_max_size by observing its maximum value over this purpose:

      void tinymt32_init (tinymt32_t * s, uint32_t seed);

   With the time.

   Beyond these general guidelines, FEC Schemes defined in this document, the details of how seed is in
   practice restricted to manage these
   situations at a FECFRAME sender value between 0 and receiver can depend on additional
   considerations 0xFFFF inclusive (note
   that are out of scope of this document.

3.2.  ADU, ADUI and Source Symbols Mappings

   At PRNG accepts a sender, an ADU coming from the application cannot directly be
   mapped to source symbols.  When multiple source flows (e.g., media
   streams) are mapped onto the same FECFRAME instance, each flow is
   assigned its own Flow ID seed value (see below).  At a sender, equal to 0), since this
   identifier is prepended to each ADU before FEC encoding.  This way, the
   Repair_Key 16-bit field value of the Repair FEC decoding at a receiver also recovers this Flow Payload ID and a recovered
   ADU can be assigned
   (Section 4.1.3).  In addition to the right source flow (note that transport
   port numbers and IP addresses cannot be used to that purpose seed, this function takes as they
   are not recovered during FEC decoding).

   Additionally, since ADUs are of variable size, padding is needed so
   that each ADU (with its flow identifier) contribute
   parameter a pointer to an integral
   number instance of source symbols.  This requires adding the original ADU
   length a tinymt32_t structure that is
   used to each ADU before doing FEC encoding.  Because keep the internal state of these
   requirements, an intermediate format, the ADUI, or ADU Information,
   is considered [RFC6363].

   For PRNG.

   Then, each incoming ADU, an ADUI MUST created as follows.  First of
   all, 3 bytes are prepended (Figure 1):

   Flow ID (F) (8-bit field):  this unsigned byte contains the time a new pseudo-random integer
      identifier associated to between 0 and 15
   inclusive (4-bit pseudo-random integer) is needed, the source ADU flow to which this ADU
      belongs.  It following
   function is assumed that used:

      uint32_t tinymt32_rand16 (tinymt32_t * s);

   This function takes as parameter a single byte is sufficient, which
      implies that no more than 256 flows will pointer to the same tinymt32_t
   structure (that needs to be protected by left unchanged between successive calls
   to the function).  Similarly, each time a single
      FECFRAME session instance.
   Length (L) (16-bit field):  this unsigned new pseudo-random integer contains the length
      of this ADU, in network byte order (i.e., big endian).  This
      length
   between 0 and 255 inclusive (8-bit pseudo-random integer) is for needed,
   the ADU itself and does not include following function is used:

      uint32_t tinymt32_rand256 (tinymt32_t * s);

   These two functions keep respectively the F, L, 4 or Pad
      fields.

   Then, zero padding is added to 8 less significant
   bits of the ADU if needed:

   Padding (Pad) (variable size field): 32-bit pseudo-random number generated by the
   tinymt32_generate_uint32() TinyMT32 function.  Test results discussed
   in Appendix B show that this field contains zero
      padding simple technique, applied to align this PRNG,
   is in line with the F, L, ADU and padding up to a size that RLC FEC Schemes needs.

   The TinyMT32 PRNG reference implementation is
      multiple of E bytes (i.e., reproduced in Figure 2,
   with the following differences with respect to the original source and repair symbol length).

   The data unit resulting from
   code:

   o  the ADU and source code initially spread over the F, L, tinymt32.h and Pad fields is
   called ADUI.  Since ADUs can have different sizes, this is also
      tinymt32.c files has been merged;
   o  the
   case for ADUIs.  However an ADUI always contributes to an integral
   number unused parts of source symbols.

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

    Figure 1: ADUI Creation example (here 3 source symbols are created
                              for this ADUI).

   Note that neither the initial 3 bytes nor the optional padding are
   sent over original source code have been removed;
   o  the network.  However, they are considered during FEC
   encoding, unused constants TINYMT32_MEXP and a receiver who lost a certain FEC Source Packet (e.g.,
   the UDP datagram containing this FEC Source Packet when UDP is used
   as the transport protocol) will be able to recover TINYMT32_MUL have been
      removed;
   o  the ADUI if FEC
   decoding succeeds.  Thanks appropriate parameter set has been added to the initial 3 bytes, this receiver will
   get rid of the padding (if any) and identify initialization
      function;
   o  the corresponding ADU
   flow.

3.3.  Encoding Window Management

   Source symbols and function order has been changed;
   o  certain internal variables have been renamed for compactness
      purposes;
   o  the corresponding ADUs are removed from constant definitions use the
   encoding window: const qualifier;
   o  when  the sliding encoding window has reached its maximum size,
      ew_max_size.  In that case tinymt32_rand16() and tinymt32_rand256() functions have been
      added in order to scale the oldest symbol MUST be removed
      before adding initial 32-bit value over a new symbol, so that smaller
      interval;
   o  the current encoding window
      size always remains inferior or equal IETF Trusteed copyright has been added to the maximum size: ew_size
      <= ew_max_size;
   o  when an ADU has reached its maximum validity duration in case of a
      real-time flow.  When this happens, all source symbols
      corresponding to the ADUI that expired SHOULD be removed from the
      encoding window;

   Source symbols are added to the sliding encoding window each time a
   new ADU arrives, once the ADU to source symbols mapping has been
   performed (Section 3.2). derived work.

   <CODE BEGINS>
   /**
    * Tiny Mersenne Twister only 127 bit internal state
    *
    * Authors : Mutsuo Saito (Hiroshima University)
    *           Makoto Matsumoto (University of Tokyo)
    *
    * Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto,
    * Hiroshima University and The current size University of the encoding window,
   ew_size, is updated after adding new source symbols.  This process
   may require to remove old Tokyo.
    * All rights reserved.
    *
    * Redistribution and use in source symbols so that: ew_size <=
   ew_max_size.

   Note and binary forms, with or without
    * modification, are permitted provided that a FEC codec may feature practical limits in the number following conditions
    * are met:
    *
    *   - Redistributions of source symbols in code must retain the encoding window (e.g., for computational
   complexity reasons).  This factor may further limit above copyright
    *     notice, this list of conditions and the ew_max_size
   value, following disclaimer.
    *   - Redistributions in addition to binary form must reproduce the maximum FEC-related latency budget
   (Section 3.1).

3.4.  Pseudo-Random Number Generator (PRNG)

   The RLC FEC Schemes defined in above
    *     copyright notice, this document rely on the TinyMT32
   PRNG, a small-sized variant list of conditions and the Mersenne Twister PRNG, as defined following
    *     disclaimer in the reference implementation version 1.1 (2015/04/24) by Mutsuo
   Saito (Hiroshima University) and Makoto Matsumoto (The University of
   Tokyo).

   o  Official web site: <http://www.math.sci.hiroshima-u.ac.jp/~m-
      mat/MT/TINYMT/>
   o  Official github site and reference implementation:
      <https://github.com/MersenneTwister-Lab/TinyMT>

   For the RLC FEC Schemes defined in this document, the tinymt32 32-bit
   version (rather than the 64-bit version) MUST be used.  This PRNG
   requires a parameter set that needs to be pre-calculated.  For the
   RLC FEC Schemes defined in this document, documentation and/or other materials
    *     provided with the following parameter set
   MUST be used:

   o  mat1 = 0x8f7011ee = 2406486510;
   o  mat2 = 0xfc78ff1f = 4235788063;
   o  tmat = 0x3793fdff = 932445695.

   This parameter set is distribution.
    *   - Neither the first entry name of the precalculated parameter
   sets in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, and
   available at:

   o  <https://github.com/jj1bdx/tinymtdc-
      longbatch/blob/master/tinymt32dc/tinymt32dc.0.1048576.txt>.

   This is also Hiroshima University nor the parameter set used in [KR12].

   The PRNG reference implementation is distributed under a BSD license
   and excerpts of it are reproduced in Appendix A.  In order to
   validate an implementation names of this PRNG, using seed 1, the 10,000th
   value returned by: tinymt32_rand(s, 0xffff) MUST be equal to 0x7c37.

   This PRNG MUST first
    *     its contributors may be initialized with a 32-bit unsigned integer,
   used as a seed.  The following function is used to this purpose:

      void tinymt32_init (tinymt32_t endorse or promote products
    * s, uint32_t seed);

   With the FEC Schemes defined in this document, the seed is in
   practice restricted to a value between 0 and 0xFFFF inclusive (note
   that this PRNG accepts a seed equal to 0), since     derived from this is the
   Repair_Key 16-bit field value of the Repair FEC Payload ID
   (Section 4.1.3).  In addition to the seed, software without specific prior written
    *     permission.
    *
    * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
    * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
    * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
    * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
    * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
    * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
    * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
    * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
    * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
    * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    * SUCH DAMAGE.
    */
   /**
    * The derived work of this function takes document is:
    * Copyright (c) 2018 IETF Trust and the persons identified as
   parameter a pointer to an instance of a tinymt32_t structure that is
   used to keep the
    * document authors. All rights reserved.
    */

   #include <stdint.h>

   /**
    * tinymt32 internal state of the PRNG.

   Then, each time a new pseudo-random integer between 0 vector and maxv-1
   inclusive is needed, the following function is used: parameters
    */
   typedef struct {
       uint32_t status[4];
       uint32_t mat1;
       uint32_t mat2;
       uint32_t tinymt32_rand tmat;
   } tinymt32_t;

   static void tinymt32_next_state (tinymt32_t * s, s);
   static uint32_t maxv);

   This function takes as parameter both a pointer tinymt32_temper (tinymt32_t * s);
   static uint32_t tinymt32_generate_uint32 (tinymt32_t * s);

   /**
    * Parameter set to use for the same
   tinymt32_t structure (that needs to be left unchanged between
   successive calls to the function) and the maxv value.

3.5.  Coding Coefficients Generation Function

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

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

   <CODE BEGINS>
   /* Schemes specification.
    * Fills in Do not change.
    * This parameter set is the table first entry of coding coefficients (of the right size) precalculated
    * provided with the appropriate number of coding coefficients to parameter sets in file tinymt32dc.0.1048576.txt, by Kenji
    * use for the repair symbol key provided. Rikitake, available at:
    *    https://github.com/jj1bdx/tinymtdc-longbatch/blob/master/
    * (in) repair_key    key associated to this repair symbol. This    tinymt32dc/tinymt32dc.0.1048576.txt
    *                    parameter It is ignored (useless) if m=2 and dt=15
    * (in) cc_tab[]      pointer to a table of also the right size to store parameter set used:
    *                    coding coefficients. All coefficients are    Rikitake, K., "TinyMT Pseudo Random Number Generator for
    *                    stored as bytes, regardless of the m parameter,    Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
    *                    upon return of this function.    September, 2012.
    */
   const uint32_t  TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);
   const uint32_t  TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);
   const uint32_t  TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);

   /**
    * (in) cc_nb         number of entries in the table. This value is
    *                    equal to function initializes the current encoding window size. internal state array with a 32-bit
    * (in) dt unsigned integer between 0 and 15 (inclusive) that
    *                    controls the density. With value 15, all seed.
    *                    coefficients are guaranteed @param s     pointer to be non zero tinymt internal state.
    *                    (i.e. equal to 1 with GF(2) and equal to @param seed  a
    *                    value in {1,... 255} with GF(2^^8)), otherwise
    * 32-bit unsigned integer used as a fraction of them will be 0.
    * (in) m             Finite Field GF(2^^m) parameter. In this
    *                    document only values 1 and 8 are considered.
    * (out)              returns an error code seed.
    */
   int generate_coding_coefficients (uint16_t  repair_key,
                                     uint8_t   cc_tab[],
                                     uint16_t  cc_nb,
                                     uint8_t   dt,
                                     uint8_t   m)
   {
   void tinymt32_init (tinymt32_t * s, uint32_t      i;
       tinymt32_t    s;    /* PRNG internal state */

       if (dt > 15) {
           return SOMETHING_WENT_WRONG; /* bad dt parameter */
       }
       switch (m) {
       case 1:
           if (dt == 15) {
               /* all coefficients are 1 */
               memset(cc_tab, 1, cc_nb);
           } else seed)
   {
               /* here coefficients are either 0 or 1 */
               tinymt32_init(&s, repair_key);
       const uint32_t    MIN_LOOP = 8;
       const uint32_t    PRE_LOOP = 8;
       s->status[0] = seed;
       s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
       s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
       s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
       for (i (int i = 0 ; 1; i < cc_nb ; MIN_LOOP; i++) {
                   if (tinymt32_rand(&s, 16) <= dt) {
                       cc_tab[i] = (uint8_t) 1;
                   } else {
                       cc_tab[i] = (uint8_t) 0;
                   }
               }
           }
           break;

       case 8:
           tinymt32_init(&s, repair_key);
           if (dt == 15) {
               /* coefficient 0 is avoided here in order to include
           s->status[i & 3] ^= i + UINT32_C(1812433253)
               * all the source symbols */ (s->status[(i - 1) & 3]
                  ^ (s->status[(i - 1) & 3] >> 30));
       }
       for (i (int i = 0 ; 0; i < cc_nb ; PRE_LOOP; i++) {
                   do {
                       cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
                   } while (cc_tab[i] == 0);
           tinymt32_next_state(s);
       }
   } else {
               /* here

   /**
    * This function outputs a certain fraction of coefficients should be pseudo-random integer in [0 .. 15] range.
    *
    * @param s     pointer to tinymt internal state.
    * @return      unsigned integer between 0 and 15 inclusive.
    */
               for (i = 0 ; i < cc_nb ; i++) {
                   if (tinymt32_rand(&s, 16) <= dt) {
                       do {
                           cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
                       } while (cc_tab[i] == 0);
                   } else
   uint32_t tinymt32_rand16(tinymt32_t *s)
   {
                       cc_tab[i] = 0;
                   }
               }
           }
           break;

       default:

           /* bad parameter m */
       return SOMETHING_WENT_WRONG;
       }
       return EVERYTHING_IS_OKAY; (tinymt32_generate_uint32(s) & 0xF);
   }
   <CODE ENDS>

       Figure 2: Coding Coefficients Generation Function pseudo-code

3.6.  Finite Fields Operations

3.6.1.  Finite Field Definitions

   The two RLC FEC Schemes specified in this document reuse the Finite
   Fields defined

   /**
    * This function outputs a pseudo-random integer in [RFC5510], section 8.1.  More specifically, the
   elements of the field GF(2^^m) are represented by polynomials with
   binary coefficients (i.e., over GF(2)) and degree lower or equal [0 .. 255] range.
    *
    * @param s     pointer to
   m-1.  The addition tinymt internal state.
    * @return      unsigned integer 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 MUST be used for GF(2^^8):

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

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

3.6.2.  Linear Combination of Source Symbols Computation

   The two RLC FEC Schemes require the computation of a linear
   combination of source symbols, using the coding coefficients produced
   by the generate_coding_coefficients() function and stored in the
   cc_tab[] array.

   With the RLC over GF(2^^8) FEC Scheme, a linear combination of the
   ew_size source symbol present in the encoding window, say src_0 to
   src_ew_size_1, in order to generate a repair symbol, is computed as
   follows.  For each byte of position i in each source 0 and the repair
   symbol, where i belongs to {0; E-1}, compute:

      repair[i] = cc_tab[0] 255 inclusive.
    */
   uint32_t tinymt32_rand256(tinymt32_t *s)
   {
       return (tinymt32_generate_uint32(s) & 0xFF);
   }

   /**
    * src_0[i] + cc_tab[1] Internal tinymt32 constants and functions.
    * src_1[i] + ... +
      cc_tab[ew_size - 1] Users should not call these functions directly.
    */
   const uint32_t  TINYMT32_SH0 = 1;
   const uint32_t  TINYMT32_SH1 = 10;
   const uint32_t  TINYMT32_SH8 = 8;
   const uint32_t  TINYMT32_MASK = UINT32_C(0x7fffffff);

   /**
    * src_ew_size_1[i]

   where This function changes internal state of tinymt32.
    * is the multiplication over GF(2^^8) and + is an XOR
   operation.  In practice various optimizations need to be used in
   order @param s     pointer to make this computation efficient (see in particular [PGM13]).

   With the RLC over GF(2) FEC Scheme (binary case), a linear
   combination is computed as follows.  The repair symbol is the XOR sum
   of all the source symbols corresponding tinymt internal state.
    */
   static void tinymt32_next_state (tinymt32_t * s)
   {
       uint32_t x;
       uint32_t y;

       y = s->status[3];
       x = (s->status[0] & TINYMT32_MASK)
           ^ s->status[1]
           ^ s->status[2];
       x ^= (x << TINYMT32_SH0);
       y ^= (y >> TINYMT32_SH0) ^ x;
       s->status[0] = s->status[1];
       s->status[1] = s->status[2];
       s->status[2] = x ^ (y << TINYMT32_SH1);
       s->status[3] = y;
       s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
       s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
   }

   /**
    * This function outputs 32-bit unsigned integer from internal state.
    * @param s     pointer to a coding coefficient
   cc_tab[j] equal tinymt internal state.
    * @return      32-bit unsigned pseudos number
    */
   static uint32_t tinymt32_temper (tinymt32_t * s)
   {
       uint32_t t0, t1;
       t0 = s->status[3];
       t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
       t0 ^= t1;
       t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
       return t0;
   }

   /**
    * This function outputs 32-bit unsigned integer from internal state.
    * @param s     pointer to 1 (i.e., the source symbols corresponding tinymt internal state.
    * @return      32-bit unsigned integer r (0 <= r < 2^32)
    */
   static uint32_t tinymt32_generate_uint32 (tinymt32_t * s) {
       tinymt32_next_state(s);
       return tinymt32_temper(s);
   }
   <CODE ENDS>

                Figure 2: TinyMT32 Reference Implementation

   In addition to zero
   coding coefficients are ignored).  The XOR sum of the byte that, any implementation of
   position i this TinyMT32 PRNG MUST
   fulfill three validation criteria detailed in each source is computed and stored Appendix A.  These
   criteria consist in several random number sequences that MUST be
   matched.  The first criteria focusses on the corresponding
   byte of internal TinyMT32
   unsigned 32-bit integer generator, the repair symbol, where i belongs two others include the mapping
   to {0; E-1}.  In practice, 4-bit and 8-bit intervals.

   Finally, the XOR sums will be computed several bytes at a time (e.g., on 64
   bit words, or on arrays deterministic behavior of 16 or more bytes when using SIMD CPU
   extensions).

   With both FEC Schemes, the details implementation of how Figure 2
   has been checked across several platforms, from high-end 64-bit Mac
   OSX and Linux/Ubuntu laptops, to optimize various low-end embedded cards based
   on 32-bit, 16-bit and 8-bit microcontrollers running RIOT
   [Baccelli18] (details in Appendix A).

3.6.  Coding Coefficients Generation Function

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

   These considerations apply to both the RLC over GF(2) and RLC over
   GF(2^^8), the only difference being the value of this document.

4.  Sliding Window the m parameter.
   With the RLC over GF(2) FEC Scheme (Section 5), m is equal to 1.
   With RLC over GF(2^^8) for Arbitrary Packet
    Flows

   This fully-specified FEC Scheme defines (Section 4), m is equal to 8.

   <CODE BEGINS>
   /*
    * Fills in the Sliding Window Random
   Linear Codes (RLC) over GF(2^^8).

4.1.  Formats and Codes

4.1.1.  FEC Framework Configuration Information

   Following table of coding coefficients (of the guidelines right size)
    * provided with the appropriate number of [RFC6363], section 5.6, this section
   provides coding coefficients to
    * use for the FEC Framework Configuration Information (or FFCI).  This
   FCCI needs repair symbol key provided.
    *
    * (in) repair_key    key associated to be shared (e.g., using SDP) between the FECFRAME sender this repair symbol. This
    *                    parameter is ignored (useless) if m=1 and receiver instances in order dt=15
    * (in/out) cc_tab[]  pointer to synchronize them.  It includes a
   FEC Encoding ID, mandatory for any FEC Scheme specification, plus
   scheme-specific elements.

4.1.1.1.  FEC Encoding ID

   o  FEC Encoding ID: table of the value assigned right size to this fully specified FEC
      Scheme MUST be XXXX, store
    *                    coding coefficients. All coefficients are
    *                    stored as assigned by IANA (Section 10).

   When SDP is used to communicate bytes, regardless of the FFCI, m parameter,
    *                    upon return of this FEC Encoding ID is
   carried in the 'encoding-id' parameter.

4.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:

   Encoding symbol size (E):  a non-negative integer that indicates the
      size function.
    * (in) cc_nb         number of each encoding symbol entries in bytes;

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

   When SDP table. This value is used
    *                    equal 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=E:1400

   If another mechanism requires current encoding window size.
    * (in) dt            integer between 0 and 15 (inclusive) that
    *                    controls the FSSI density. With value 15, all
    *                    coefficients are guaranteed to be carried as an opaque
   octet string (for instance, after non zero
    *                    (i.e. equal to 1 with GF(2) and equal to a Base64 encoding), the encoding
   format consists
    *                    value in {1,... 255} with GF(2^^8)), otherwise
    *                    a fraction of the following 2 octets:

      Encoding symbol length (E): 16-bit field. them will be 0.
    * (in) m             Finite Field GF(2^^m) parameter. In this
    *                    document only values 1 and 8 are considered.
    * (out)              returns 0 in case of success, an error code
    *                    different than 0 otherwise.
    */
   int generate_coding_coefficients (uint16_t  repair_key,
                                     uint8_t   cc_tab[],
                                     uint16_t  cc_nb,
                                     uint8_t   dt,
                                     uint8_t   m)
   {
       uint32_t      i;
       tinymt32_t    s;    /* PRNG internal state */

       if (dt > 15) {
           return -1; /* error, bad dt parameter */
       }
       switch (m) {
       case 1:
           if (dt == 15) {
               /* all coefficients are 1 */
               memset(cc_tab, 1, cc_nb);
           } else {
               /* here coefficients are either 0 or 1 2 3 4 5 6 7 8 9 */
               tinymt32_init(&s, repair_key);
               for (i = 0 ; i < cc_nb ; i++) {
                   cc_tab[i] = (tinymt32_rand16(&s) <= dt) ? 1 2 3 4 5
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Encoding Symbol Length (E)  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                      Figure 3: FSSI Encoding Format

4.1.2.  Explicit Source FEC Payload ID

   A FEC Source Packet MUST contain an Explicit Source FEC Payload ID
   that : 0;
               }
           }
           break;

       case 8:
           tinymt32_init(&s, repair_key);
           if (dt == 15) {
               /* coefficient 0 is appended avoided here in order to include
                * all the end source symbols */
               for (i = 0 ; i < cc_nb ; i++) {
                   do {
                       cc_tab[i] = (uint8_t) tinymt32_rand256(&s);
                   } while (cc_tab[i] == 0);
               }
           } else {
               /* here a certain number of the packet as illustrated in Figure 4.

   +--------------------------------+
   |           IP Header            |
   +--------------------------------+
   |        Transport Header        |
   +--------------------------------+
   |              ADU               |
   +--------------------------------+
   | Explicit Source FEC Payload ID |
   +--------------------------------+ coefficients should be 0 */
               for (i = 0 ; i < cc_nb ; i++) {
                   if (tinymt32_rand16(&s) <= dt) {
                       do {
                           cc_tab[i] = (uint8_t) tinymt32_rand256(&s);
                       } while (cc_tab[i] == 0);
                   } else {
                       cc_tab[i] = 0;
                   }
               }
           }
           break;

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

        Figure 4: Structure of an 3: Coding Coefficients Generation Function Reference
                              Implementation

3.7.  Finite Fields Operations

3.7.1.  Finite Field Definitions

   The two RLC FEC Source Packet with Schemes specified in this document reuse the Explicit Source
                              FEC Payload ID Finite
   Fields defined in [RFC5510], section 8.1.  More precisely, specifically, the Explicit Source FEC Payload ID is composed
   elements of the
   following field (Figure 5):

   Encoding Symbol ID (ESI) (32-bit field):  this unsigned integer
      identifies GF(2^^m) are represented by polynomials with
   binary coefficients (i.e., over GF(2)) and degree lower or equal to
   m-1.  The addition between two elements is defined as the first source symbol 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 ADUI corresponding
   multiplication modulo a given irreducible polynomial of degree 8.
   The following irreducible polynomial MUST be used for GF(2^^8):

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

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

3.7.2.  Linear Combination of Source Packet. Symbols Computation

   The ESI is incremented for each new two RLC FEC Schemes require the computation of a linear
   combination of source symbol, and after reaching symbols, using the maximum value (2^32-1),
      wrapping to zero occurs.

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

              Figure 5: Source FEC Payload ID Encoding Format

4.1.3.  Repair FEC Payload ID

   A coding coefficients produced
   by the generate_coding_coefficients() function and stored in the
   cc_tab[] array.

   With the RLC over GF(2^^8) FEC Repair Packet MAY contain one or more repair symbols.  When
   there are several repair symbols, all Scheme, a linear combination of them MUST have been
   generated from the same
   ew_size source symbol present in the encoding window, using Repair_Key values that
   are managed say src_0 to
   src_ew_size_1, in order to generate a repair symbol, is computed as explained below.  A receiver can easily deduce the
   number
   follows.  For each byte of repair symbols within a FEC Repair Packet by comparing position i in each source and the
   received FEC Repair Packet size (equal repair
   symbol, where i belongs to the UDP payload size when
   UDP {0; E-1}, compute:

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

   where * is the underlying transport protocol) and the symbol size, E,
   communicated multiplication over GF(2^^8).  In practice various
   optimizations need to be used in order to make this computation
   efficient (see in particular [PGM13]).

   With the FFCI.

   A RLC over GF(2) FEC Repair Packet MUST contain Scheme (binary case), a Repair FEC Payload ID that linear
   combination is
   prepended to the computed as follows.  The repair symbol as illustrated in Figure 6.

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

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

   More precisely, the Repair FEC Payload ID is composed of the
   following fields (Figure 7):

   Repair_Key (16-bit field):  this unsigned integer is used as a seed
      by the coefficient generation function (Section 3.5) in order to
      generate the desired number of coding coefficients.  When a FEC
      Repair Packet contains several repair symbols, this repair key
      value is that XOR sum
   of all the first repair symbol.  The remaining repair
      keys can be deduced by incrementing by 1 this value, up source symbols corresponding to a
      maximum value of 65535 after which it loops back to 0.

   Density Threshold for the coding coefficients, DT (4-bit field):
      this unsigned integer carries the Density Threshold (DT) used by
      the coding coefficient generation function Section 3.5.  More
      precisely, it controls
   cc_tab[j] equal to 1 (i.e., the probability of having a non source symbols corresponding to zero
   coding
      coefficient, which equals (DT+1) / 16.  When a FEC Repair Packet
      contains several repair symbols, the DT value applies to all of
      them;
   Number coefficients are ignored).  The XOR sum of Source Symbols in the encoding window, NSS (12-bit field):

      this unsigned integer indicates the number byte of
   position i in each source symbols is computed and stored in the encoding window when this repair symbol was generated.  When a
      FEC Repair Packet contains several corresponding
   byte of the repair symbols, this NSS value
      applies symbol, where i belongs to all of them;
   ESI of First Source Symbol in the encoding window, FSS_ESI (32-bit
   field):
      this unsigned integer indicates the ESI of the first source symbol
      in {0; E-1}.  In practice,
   the encoding window when this repair symbol was generated.
      When a FEC Repair Packet contains XOR sums will be computed several repair symbols, this
      FSS_ESI value applies to all bytes at a time (e.g., on 64
   bit words, or on arrays of them;

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

              Figure 7: Repair 16 or more bytes when using SIMD CPU
   extensions).

   With both FEC Payload ID Encoding Format

4.1.4.  Additional Procedures

   The following procedure applies:

   o  The ESI of source symbols MUST start with value 0 for Schemes, the first
      source symbol and MUST be managed sequentially.  Wrapping details of how to zero
      happens after reaching optimize the maximum 32-bit value.

5. computation
   of these linear combinations are of high practical importance but out
   of scope of this document.

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

   This fully-specified FEC Scheme defines the Sliding Window Random
   Linear Codes (RLC) over GF(2) (binary case).

5.1. GF(2^^8).

4.1.  Formats and Codes
5.1.1.

4.1.1.  FEC Framework Configuration Information

5.1.1.1.  FEC Encoding ID

   o  FEC Encoding ID: the value assigned to this fully specified FEC
      Scheme MUST be YYYY, as assigned by IANA (Section 10).

   When SDP is used to communicate

   Following the FFCI, guidelines of [RFC6363], section 5.6, this FEC Encoding ID is
   carried in section
   provides the 'encoding-id' parameter.

5.1.1.2. FEC Scheme-Specific Framework Configuration Information

   All (or FFCI).  This
   FCCI needs to be shared (e.g., using SDP) between the considerations of Section 4.1.1.2 apply here.

5.1.2.  Explicit Source FECFRAME sender
   and receiver instances in order to synchronize them.  It includes a
   FEC Payload Encoding ID, mandatory for any FEC Scheme specification, plus
   scheme-specific elements.

4.1.1.1.  FEC Encoding ID

   All

   o  FEC Encoding ID: the considerations of Section 4.1.1.2 apply here.

5.1.3.  Repair value assigned to this fully specified FEC Payload ID

   All
      Scheme MUST be XXXX, as assigned by IANA (Section 10).

   When SDP is used to communicate the considerations of Section 4.1.1.2 apply here, with FFCI, this FEC Encoding ID is
   carried in the only
   exception 'encoding-id' parameter.

4.1.1.2.  FEC Scheme-Specific Information

   The FEC Scheme-Specific Information (FSSI) includes elements that are
   specific to the Repair_Key field is useless if DT = 15 (indeed, in present FEC Scheme.  More precisely:

   Encoding symbol size (E):  a non-negative integer that case all indicates the coefficients are necessarily equal
      size of each encoding symbol in bytes;
   Window Size Ratio (WSR) parameter:   a non-negative integer between 0
      and 255 (both inclusive) used to initialize window sizes.  A value
      of 0 indicates this parameter is not considered (e.g., a fixed
      encoding window size may be chosen).  A value between 1 and 255
      inclusive is required by certain of the
   coefficient generation function does not use any PRNG).  When DT = 15
   it parameter derivation
      techniques described in Appendix C;

   This element is RECOMMENDED that required both by the sender use value 0 for (RLC encoder) and the Repair_Key
   field, but a receiver SHALL ignore
   receiver(s) (RLC decoder).

   When SDP is used to communicate the FFCI, this field.

5.1.4.  Additional Procedures

   All FEC Scheme-specific
   information is carried in the considerations of Section 4.1.1.2 apply here.

6.  FEC Code Specification

6.1.  Encoding Side

   This section provides a high level description of a Sliding Window
   RLC encoder.

   Whenever a new FEC Repair Packet is needed, the RLC encoder instance
   first gathers the ew_size source symbols currently in the sliding
   encoding window.  Then it chooses a repair key, which can be a
   monotonically increasing integer value, incremented for each repair
   symbol up to a maximum value of 65535 (as it is carried within a
   16-bit field) after which it loops back to 0.  This repair key is
   communicated to the coefficient generation function (Section 3.5) 'fssi' parameter in
   order to generate ew_size coding coefficients.  Finally, the FECFRAME
   sender computes the repair symbol textual
   representation as a linear combination of the
   ew_size source symbols using specified in [RFC6364].  For instance:

   fssi=E:1400,WSR:191

   In that case the ew_size coding coefficients
   (Section 3.6).  When E is small name values "E" and when there is an incentive "WSR" are used to
   pack several repair symbols within convey the same FEC Repair Packet, E
   and WSR parameters respectively.

   If another mechanism requires the
   appropriate number of repair symbols are computed.  In that case FSSI to be carried as an opaque
   octet string, the
   repair key for each encoding format consists of them MUST be incremented by 1, keeping the
   same ew_size source symbols, since only following three
   octets, where the first repair key will be E field is carried in the Repair FEC Payload ID.  The FEC Repair Packet "big-endian" or "network
   order" format, that is, most significant byte first:

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

   These three octets can then be passed to the transport layer communicated as such, or for transmission.  The source versus
   repair FEC packet transmission order is out of scope of this document
   and several approaches exist that are implementation specific.

   Other solutions are possible instance, be
   subject to select a repair key value when a new an additional Base64 encoding.

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

                      Figure 4: FSSI Encoding Format

4.1.2.  Explicit Source FEC Repair Payload ID

   A FEC Source Packet MUST contain an Explicit Source FEC Payload ID
   that is needed, for instance by choosing a random
   integer between 0 and 65535.  However, selecting appended to the same repair key end of the packet as before (which may happen illustrated in case Figure 5.

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

   Figure 5: Structure of a random process) is only
   meaningful if the encoding window has changed, otherwise the same an FEC
   Repair Source Packet will be generated.

6.2.  Decoding Side

   This section provides a high level description of a Sliding Window
   RLC decoder.

   A FECFRAME receiver needs to maintain a linear system whose variables
   are with the received and lost source symbols.  Upon receiving a Explicit Source
                              FEC
   Repair Packet, a receiver first extracts all Payload ID

   More precisely, the repair symbols it
   contains (in case several repair symbols are packed together).  For
   each repair symbol, when at least one Explicit Source FEC Payload ID is composed of the corresponding source
   symbols it protects has been lost, the receiver adds an equation to
   the linear system (or no equation if
   following field, carried in "big-endian" or "network order" format,
   that is, most significant byte first (Figure 6):

   Encoding Symbol ID (ESI) (32-bit field):  this repair packet does not
   change unsigned integer
      identifies the linear system rank).  This equation first source symbol of course re-uses the
   ew_size coding coefficients that are computed by the same coefficient
   generation function (Section Section 3.5), using the repair key ADUI corresponding to
      this FEC Source Packet.  The ESI is incremented for each new
      source symbol, and
   encoding window descriptions carried in after reaching the maximum value (2^32-1),
      wrapping to zero occurs.

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

              Figure 6: Source FEC Payload ID Encoding Format

4.1.3.  Repair FEC Payload ID.
   Whenever possible (i.e., when a sub-system covering ID

   A FEC Repair Packet MAY contain one or more lost
   source symbols is of full rank), decoding is performed in order to
   recover lost source repair symbols.  Each time an ADUI  When
   there are several repair symbols, all of them MUST have been
   generated from the same encoding window, using Repair_Key values that
   are managed as explained below.  A receiver can be totally
   recovered, padding is removed (thanks to easily deduce the Length field, L,
   number of repair symbols within a FEC Repair Packet by comparing the
   ADUI) and the ADU is assigned
   received FEC Repair Packet size (equal to the corresponding application flow
   (thanks to UDP payload size when
   UDP is the Flow ID field, F, of underlying transport protocol) and the ADUI).  This ADU symbol size, E,
   communicated in the FFCI.

   A FEC Repair Packet MUST contain a Repair FEC Payload ID that is finally
   passed
   prepended to the corresponding upper application.  Received repair symbol as illustrated in Figure 7.

   +--------------------------------+
   |           IP Header            |
   +--------------------------------+
   |        Transport Header        |
   +--------------------------------+
   |     Repair FEC Source
   Packets, containing Payload ID      |
   +--------------------------------+
   |         Repair Symbol          |
   +--------------------------------+

      Figure 7: Structure of an ADU, MAY be passed to FEC Repair Packet with the application either
   immediately or after some time to guaranty an ordered delivery to Repair FEC
                                Payload ID

   More precisely, the
   application.  This document does not mandate any approach as this is
   an operational and management decision.

   With real-time flows, a lost ADU that Repair FEC Payload ID is decoded after composed of the maximum
   latency
   following fields where all integer fields are carried in "big-endian"
   or an ADU received after "network order" format, that is, most significant byte first
   (Figure 8):

   Repair_Key (16-bit field):  this delay has no value to unsigned integer is used as a seed
      by the
   application.  This raises coefficient generation function (Section 3.6) in order to
      generate the question desired number of deciding whether or not an
   ADU is late. coding coefficients.  This decision MAY repair
      key may be taken within the FECFRAME receiver
   (e.g., using the decoding window, see a monotonically increasing integer value that loops
      back to 0 after reaching 65535 (see Section 3.1) or within 6.1).  When a FEC
      Repair Packet contains several repair symbols, this repair key
      value is that of the
   application (e.g., using RTP timestamps within the ADU).  Deciding
   which option to follow and whether or not first repair symbol.  The remaining repair
      keys can be deduced by incrementing by 1 this value, up to pass all ADUs, including
   those assumed late, a
      maximum value of 65535 after which it loops back to 0.
   Density Threshold for the application are operational decisions that
   depend on coding coefficients, DT (4-bit field):
      this unsigned integer carries the application and are therefore out Density Threshold (DT) used by
      the coding coefficient generation function Section 3.6.  More
      precisely, it controls the probability of scope having a non zero coding
      coefficient, which equals (DT+1) / 16.  When a FEC Repair Packet
      contains several repair symbols, the DT value applies to all of
      them;
   Number of Source Symbols in the encoding window, NSS (12-bit field):

      this
   document.  Additionally, Appendix B discusses a backward compatible
   optimization whereby late unsigned integer indicates the number of source symbols MAY still be used within the
   FECFRAME receiver in order
      the encoding window when this repair symbol was generated.  When a
      FEC Repair Packet contains several repair symbols, this NSS value
      applies to improve transmission robustness.

7.  Implementation Status

   Editor's notes: RFC Editor, please remove all of them;
   ESI of First Source Symbol in the encoding window, FSS_ESI (32-bit
   field):
      this section motivated by
   RFC 6982 before publishing unsigned integer indicates the RFC.  Thanks.

   An implementation ESI of the Sliding Window RLC FEC Scheme for FECFRAME
   exists:

   o  Organisation: Inria
   o  Description: This is an implementation of first source symbol
      in the Sliding Window RLC encoding window when this repair symbol was generated.

      When a FEC Scheme limited to GF(2^^8).  It relies on a modified version Repair Packet contains several repair symbols, this
      FSS_ESI value applies to all of our OpenFEC (http://openfec.org) FEC code library.  It is
      integrated them;

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       Repair_Key              |  DT   |NSS (# src symb in our FECFRAME software (see [fecframe-ext]).
   o  Maturity: prototype.
   o  Coverage: this software complies with ew) |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            FSS_ESI                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 8: Repair FEC Payload ID Encoding Format

4.2.  Procedures

   All the procedures of Section 3 apply to this FEC Scheme.

5.  Sliding Window RLC FEC
      Scheme.
   o  Licensing: proprietary.
   o  Contact: vincent.roca@inria.fr

8.  Security Considerations

   The Scheme over GF(2) for Arbitrary Packet Flows

   This fully-specified FEC Scheme defines the Sliding Window Random
   Linear Codes (RLC) over GF(2) (binary case).

5.1.  Formats and Codes

5.1.1.  FEC Framework document [RFC6363] provides a comprehensive
   analysis of security considerations applicable Configuration Information

5.1.1.1.  FEC Encoding ID

   o  FEC Encoding ID: the value assigned to this fully specified FEC Schemes.
   Therefore,
      Scheme MUST be YYYY, as assigned by IANA (Section 10).

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

5.1.1.2.  FEC Scheme-Specific Information

   All the security considerations
   section of [RFC6363] Section 4.1.1.2 apply here.

5.1.2.  Explicit Source FEC Payload ID

   All the considerations of Section 4.1.2 apply here.

5.1.3.  Repair FEC Payload ID

   All the considerations of Section 4.1.3 apply here, with the only
   exception that the Repair_Key field is useless if DT = 15 (indeed, in
   that case all the coefficients are necessarily equal to 1 and the
   coefficient generation function does not use any PRNG).  When DT = 15
   the FECFRAME sender MUST set the Repair_Key field to zero on
   transmission and a receiver MUST ignore it on receipt.

5.2.  Procedures

   All the procedures of Section 3 apply to this FEC Scheme.

6.  FEC Code Specification

6.1.  Encoding Side

   This section provides a high level description of a Sliding Window
   RLC encoder.

   Whenever a new FEC Repair Packet is needed, the RLC encoder instance
   first gathers the ew_size source symbols currently in the sliding
   encoding window.  Then it chooses a repair key, which can be a
   monotonically increasing integer value, incremented for each repair
   symbol up to a maximum value of 65535 (as it is carried within a
   16-bit field) after which it loops back to 0.  This repair key is
   communicated to the coefficient generation function (Section 3.6) in
   order to generate ew_size coding coefficients.  Finally, the FECFRAME
   sender computes the repair symbol as a linear combination of the
   ew_size source symbols using the ew_size coding coefficients
   (Section 3.7).  When E is small and when there is an incentive to
   pack several repair symbols within the same FEC Repair Packet, the
   appropriate number of repair symbols are computed.  In that case the
   repair key for each of them MUST be incremented by 1, keeping the
   same ew_size source symbols, since only the first repair key will be
   carried in the Repair FEC Payload ID.  The FEC Repair Packet can then
   be passed to the transport layer for transmission.  The source versus
   repair FEC packet transmission order is out of scope of this document
   and several approaches exist that are implementation-specific.

   Other solutions are possible to select a repair key value when a new
   FEC Repair Packet is needed, for instance, by choosing a random
   integer between 0 and 65535.  However, selecting the same repair key
   as before (which may happen in case of a random process) is only
   meaningful if the encoding window has changed, otherwise the same FEC
   Repair Packet will be generated.

6.2.  Decoding Side

   This section provides a high level description of a Sliding Window
   RLC decoder.

   A FECFRAME receiver needs to maintain a linear system whose variables
   are the received and lost source symbols.  Upon receiving a FEC
   Repair Packet, a receiver first extracts all the repair symbols it
   contains (in case several repair symbols are packed together).  For
   each repair symbol, when at least one of the corresponding source
   symbols it protects has been lost, the receiver adds an equation to
   the linear system (or no equation if this repair packet does not
   change the linear system rank).  This equation of course re-uses the
   ew_size coding coefficients that are computed by the same coefficient
   generation function (Section Section 3.6), using the repair key and
   encoding window descriptions carried in the Repair FEC Payload ID.
   Whenever possible (i.e., when a sub-system covering one or more lost
   source symbols is of full rank), decoding is performed in order to
   recover lost source symbols.  Gaussian elimination is one possible
   algorithm to solve this linear system.  Each time an ADUI can be
   totally recovered, padding is removed (thanks to the Length field, L,
   of the ADUI) and the ADU is assigned to the corresponding application
   flow (thanks to the Flow ID field, F, of the ADUI).  This ADU is
   finally passed to the corresponding upper application.  Received FEC
   Source Packets, containing an ADU, MAY be passed to the application
   either immediately or after some time to guaranty an ordered delivery
   to the application.  This document does not mandate any approach as
   this is an operational and management decision.

   With real-time flows, a lost ADU that is decoded after the maximum
   latency or an ADU received after this delay has no value to the
   application.  This raises the question of deciding whether or not an
   ADU is late.  This decision MAY be taken within the FECFRAME receiver
   (e.g., using the decoding window, see Section 3.1) or within the
   application (e.g., using RTP timestamps within the ADU).  Deciding
   which option to follow and whether or not to pass all ADUs, including
   those assumed late, to the application are operational decisions that
   depend on the application and are therefore out of scope of this
   document.  Additionally, Appendix D discusses a backward compatible
   optimization whereby late source symbols MAY still be used within the
   FECFRAME receiver in order to improve transmission robustness.

7.  Implementation Status

   Editor's notes: RFC Editor, please remove this section motivated by
   RFC 6982 before publishing the RFC.  Thanks.

   An implementation of the Sliding Window RLC FEC Scheme for FECFRAME
   exists:

   o  Organisation: Inria
   o  Description: This is an implementation of the Sliding Window RLC
      FEC Scheme limited to GF(2^^8).  It relies on a modified version
      of our OpenFEC (http://openfec.org) FEC code library.  It is
      integrated in our FECFRAME software (see [fecframe-ext]).

   o  Maturity: prototype.
   o  Coverage: this software complies with the Sliding Window RLC FEC
      Scheme.
   o  Licensing: proprietary.
   o  Contact: vincent.roca@inria.fr

8.  Security Considerations

   The FEC Framework document [RFC6363] provides a fairly comprehensive
   analysis of security considerations applicable to FEC Schemes.
   Therefore, the present section follows the security considerations
   section of [RFC6363] and only discusses specific topics.

8.1.  Attacks Against the Data Flow

8.1.1.  Access to Confidential Content

   The Sliding Window RLC FEC Scheme specified in this document does not
   change the recommendations of [RFC6363].  To summarize, if
   confidentiality is a concern, it is RECOMMENDED that one of the
   solutions mentioned in [RFC6363] is used with special considerations
   to the way this solution is applied (e.g., is encryption applied
   before or after FEC protection, within the end-system or in a
   middlebox), to the operational constraints (e.g., performing FEC
   decoding in a protected environment may be complicated or even
   impossible) and to the threat model.

8.1.2.  Content Corruption

   The Sliding Window RLC FEC Scheme specified in this document does not
   change the recommendations of [RFC6363].  To summarize, it is
   RECOMMENDED that one of the solutions mentioned in [RFC6363] is used
   on both the FEC Source and Repair Packets.

8.2.  Attacks Against the FEC Parameters

   The FEC Scheme specified in this document defines parameters that can
   be the basis of attacks.  More specifically, the following parameters
   of the FFCI may be modified by an attacker who targets receivers
   (Section 4.1.1.2):

   o  FEC Encoding ID: changing this parameter leads a receiver to
      consider a different FEC Scheme.  The consequences are severe, the
      format of the Explicit Source FEC Payload ID and Repair FEC
      Payload ID of received packets will probably differ, leading to
      various malfunctions.  Even if the original and modified FEC
      Schemes share the same format, FEC decoding will either fail or
      lead to corrupted decoded symbols.  This will happen if an
      attacker turns value YYYY (i.e., RLC over GF(2)) to value XXXX
      (RLC over GF(2^^8)), an additional consequence being a higher
      processing overhead at the receiver.  In any case, the attack
      results in a form of Denial of Service (DoS) or corrupted content.
   o  Encoding symbol length (E): setting this E parameter to a
      different value will confuse a receiver.  If the size of a
      received FEC Repair Packet is no longer multiple of the modified E
      value, a receiver quickly detects a problem and SHOULD reject the
      packet.  If the new E value is a sub-multiple of the original E
      value (e.g., half the original value), then receivers may not
      detect the problem immediately.  For instance, a receiver may
      think that a received FEC Repair Packet contains more repair
      symbols (e.g., twice as many if E is reduced by half), leading to
      malfunctions whose nature depends on implementation details.  Here
      also, the attack always results in a form of DoS or corrupted
      content.

   It is therefore RECOMMENDED that security measures be taken to
   guarantee the FFCI integrity, as specified in [RFC6363].  How to
   achieve this depends on the way the FFCI is communicated from the
   sender to the receiver, which is not specified in this document.

   Similarly, attacks are possible against the Explicit Source FEC
   Payload ID and Repair FEC Payload ID.  More specifically, in case of
   a FEC Source Packet, the following value can be modified by an
   attacker who targets receivers:

   o  Encoding Symbol ID (ESI): changing the ESI leads a receiver to
      consider a wrong ADU, resulting in severe consequences, including
      corrupted content passed to the receiving application;

   And in case of a FEC Repair Packet:

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

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

8.3.  When Several Source Flows are to be Protected Together

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

8.4.  Baseline Secure FEC Framework Operation

   The Sliding Window RLC FEC Scheme specified in this document does not
   change the recommendations of [RFC6363] concerning the use of the
   IPsec/ESP security protocol as a mandatory to implement (but not
   mandatory to use) security scheme.  This is well suited to situations
   where the only insecure domain is the one over which the FEC
   Framework operates.

8.5.  Additional Security Considerations for Numerical Computations

   In addition to the above security considerations, inherited from
   [RFC6363], the present document introduces several formulae, in
   particular in Appendix C.1.  It is RECOMMENDED to check that the
   computed values stay within reasonable bounds since numerical
   overflows, caused by an erroneous implementation or an erroneous
   input value, may lead to hazardous behaviours.  However, what
   "reasonable bounds" means is use-case and implementation dependent
   and is not detailed in this document.

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

9.  Operations and Management Considerations

   The FEC Framework document [RFC6363] provides a fairly comprehensive
   analysis of operations and management considerations applicable to
   FEC Schemes.  Therefore, the present section only discusses specific
   topics.

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

   The present document specifies two FEC Schemes that differ on the
   Finite Field used for the coding coefficients.  It is expected that
   the RLC over GF(2^^8) FEC Scheme will be mostly used since it
   warrants a higher packet loss protection.  In case of small encoding
   windows, the associated processing overhead is not an issue (e.g., we
   measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM
   Cortex-A15 embedded board in [Roca17] for an encoding window of size
   18 or 23 symbols).  Of course the CPU overhead will increase with the
   encoding window size, because more operations in the GF(2^^8) finite
   field will be needed.

   The RLC over GF(2) FEC Scheme offers an alternative.  In that case
   operations symbols can be directly XOR-ed together which warrants
   high bitrate encoding and decoding operations, and can be an
   advantage with large encoding windows.  However, packet loss
   protection is significantly reduced by using this FEC Scheme.

9.2.  Operational Recommendations: Coding Coefficients Density Threshold

   In addition to the choice of the Finite Field, the two FEC Schemes
   define a coding coefficient density threshold (DT) parameter.  This
   parameter enables a sender to control the code density, i.e., the
   proportion of coefficients that are non zero on average.  With RLC
   over GF(2^^8), it is usually appropriate that small encoding windows
   be associated to a density threshold equal to 15, the maximum value,
   in order to warrant a high loss protection.

   On the opposite, with larger encoding windows, it is usually
   appropriate that the density threshold be reduced.  With large
   encoding windows, an alternative can be to use RLC over GF(2) and a
   density threshold equal to 7 (i.e., an average density equal to 1/2)
   or smaller.

   Note that using a density threshold equal to 15 with RLC over GF(2)
   is equivalent to using an XOR code that computes the XOR sum of all
   the source symbols in the encoding window.  In that case: (1) only a
   single repair symbol can be produced for any encoding window, and (2)
   the repair_key parameter becomes useless (the coding coefficients
   generation function does not rely on the PRNG).

10.  IANA Considerations

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

   o  YYYY refers to the Sliding Window Random Linear Codes (RLC) over
      GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in
      Section 5 of this document.
   o  XXXX refers to the Sliding Window Random Linear Codes (RLC) over
      GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in
      Section 4 of this document.

11.  Acknowledgments

   The authors would like to thank the three TSVWG chairs, Wesley Eddy,
   our shepherd, David Black and Gorry Fairhurst, as well as Spencer
   Dawkins, our responsible AD, and all those who provided comments,
   namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ
   Housley, Emmanuel Lochin, and Marie-Jose Montpetit.  Last but not
   least, the authors are really grateful to the IESG members, in
   particular Benjamin Kaduk, Mirja Kuhlewind, Eric Rescorla, and Adam
   Roach for their highly valuable feedbacks that greatly contributed to
   improve this specification.

12.  References

12.1.  Normative References

   [fecframe-ext]
              Roca, V. and A. Begen, "Forward Error Correction (FEC)
              Framework Extension to Sliding Window Codes", Transport
              Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext
              (Work in Progress), January 2019,
              <https://tools.ietf.org/html/
              draft-ietf-tsvwg-fecframe-ext>.

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

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

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

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

12.2.  Informative References

   [Baccelli18]
              Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P.,
              Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and
              M. Wahlisch, "RIOT: An Open Source Operating System for
              Low-End Embedded Devices in the IoT",  IEEE Internet of
              Things Journal (Volume 5, Issue 6), DOI:
              10.1109/JIOT.2018.2815038, December 2018.

   [KR12]     Rikitake, K., "TinyMT Pseudo Random Number Generator for
              Erlang",  ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
              September 14, 2012, Copenhagen, Denmark, DOI:
              http://dx.doi.org/10.1145/2364489.2364504, September 2012.

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

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

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

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

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

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

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

   [Roca16]   Roca, V., Teibi, B., Burdinat, C., Tran, T., and C.
              Thienot, "Block or Convolutional AL-FEC Codes? A
              Performance Comparison for Robust Low-Latency
              Communications", HAL open-archive document,hal-01395937
              https://hal.inria.fr/hal-01395937/en/, November 2016,
              <https://hal.inria.fr/hal-01395937/en/>.

   [Roca17]   Roca, V., Teibi, B., Burdinat, C., Tran, T., and C.
              Thienot, "Less Latency and only discusses specific topics.

8.1.  Attacks Against the Data Flow

8.1.1.  Access to Confidential Content

   The Better Protection with AL-FEC
              Sliding Window RLC FEC Scheme specified in this document does not
   change the recommendations of [RFC6363].  To summarize, if
   confidentiality is Codes: a concern, it Robust Multimedia CBR Broadcast
              Case Study", 13th IEEE International Conference on
              Wireless and Mobile Computing, Networking and
              Communications (WiMob17), October
              2017 https://hal.inria.fr/hal-01571609v1/en/, October
              2017, <https://hal.inria.fr/hal-01571609v1/en/>.

Appendix A.  TinyMT32 Validation Criteria (Normative)

   PRNG determinism, for a given seed, is RECOMMENDED that one of the
   solutions mentioned a requirement.  Consequently,
   in [RFC6363] is used with special considerations order to validate an implementation of the way this solution is applied (e.g., is encryption applied
   before or after FEC protection, within the end-system or in a
   middlebox), to TinyMT32 PRNG, the operational constraints (e.g., performing FEC
   decoding in a protected environment may
   following criterias MUST be complicated or even
   impossible) and to the threat model.

8.1.2.  Content Corruption met.

   The Sliding Window RLC FEC Scheme specified in this document does not
   change first criteria focusses on the recommendations of [RFC6363].  To summarize, it is
   RECOMMENDED core TinyMT32 PRNG, that one produces
   32-bit pseudo-random numbers.  Using a seed value of 1, the solutions mentioned in [RFC6363] is used
   on both the FEC Source and Repair Packets.

8.2.  Attacks Against the FEC Parameters

   The FEC Scheme specified first 50
   values returned by: tinymt32_generate_uint32(s) as 32-bit unsigned
   integers MUST be equal to values provided in this document defines parameters Figure 9.  Note that can
   be the basis of attacks.  More specifically, the following parameters
   of
   these values come from the FFCI may be modified by an attacker who targets receivers
   (Section 4.1.1.2):

   o  FEC Encoding ID: changing this parameter leads a receiver tinymt/check32.out.txt file provided by
   the authors to
      consider validate implementations of TinyMT32, as part of the
   MersenneTwister-Lab/TinyMT Github repository.

   2545341989  981918433 3715302833 2387538352 3591001365
   3820442102 2114400566 2196103051 2783359912  764534509
    643179475 1822416315  881558334 4207026366 3690273640
   3240535687 2921447122 3984931427 4092394160   44209675
   2188315343 2908663843 1834519336 3774670961 3019990707
   4065554902 1239765502 4035716197 3412127188  552822483
    161364450  353727785  140085994  149132008 2547770827
   4064042525 4078297538 2057335507  622384752 2041665899
   2193913817 1080849512   33160901  662956935  642999063
   3384709977 1723175122 3866752252  521822317 2292524454

               Figure 9: First 50 decimal values returned by
   tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a different FEC Scheme. seed
                                value of 1.

   The consequences are severe, second criteria focusses on the
      format of tinymt32_rand256(), where the Explicit Source FEC Payload ID and Repair FEC
      Payload ID
   32-bit integer of received packets will probably differ, leading to
      various malfunctions.  Even if the original and modified FEC
      Schemes share the same format, FEC decoding will either fail or
      lead to corrupted decoded symbols.  This will happen if an
      attacker turns value YYYY (i.e., RLC over GF(2)) core TinyMT32 PRNG is scaled down to value XXXX
      (RLC over GF(2^^8)), an additional consequence being 8-bit
   integer.  Using a higher
      processing overhead at the receiver.  In any case, seed value of 1, the attack
      results first 50 values returned by:
   tinymt32_rand256() as 8-bit unsigned integers MUST be equal to values
   provided in Figure 10.

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

   Figure 10: First 50 decimal values returned by tinymt32_rand256() as
             8-bit unsigned integers, with a form seed value of Denial 1.

   The third criteria focusses on the tinymt32_rand16(), where the
   32-bit integer of Service (DoS);
   o  Encoding symbol length (E): setting this E parameter the core TinyMT32 PRNG is scaled down to a
      different value will confuse 4-bit
   integer.  Using a receiver.  If the size seed value of 1, the first 50 values returned by:
   tinymt32_rand16() as 4-bit unsigned integers MUST be equal to values
   provided in Figure 11.

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

    Figure 11: First 50 decimal values returned by tinymt32_rand16() as
             4-bit unsigned integers, with a
      received FEC Repair Packet is no longer multiple seed value of 1.

   The deterministic behavior of the modified E
      value, implementation of Figure 2 has been
   checked across several platforms: high-end laptops running 64-bits
   Mac OSX and Linux/Ubuntu; a receiver quickly detects board featuring a problem 32-bits ARM Cortex-A15
   and SHOULD reject running 32-bit Linux/Ubuntu; several embedded cards featuring
   either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit
   microcontroller, all of them running RIOT [Baccelli18]; two low-end
   embedded cards featuring either a 16-bit microcontroller (TI MSP430)
   or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running
   RIOT.

Appendix B.  Assessing the
      packet.  If PRNG Adequacy (Informational)

   This annex discusses the new E value is a sub-multiple adequacy of the original E
      value (e.g., half TinyMT32 PRNG and the original value), then receivers may not
      detect
   tinymt32_rand16() and tinymt32_rand256() functions, to the problem immediately.  For instance a receiver may think
      that a received RLC FEC Repair Packet contains more repair symbols
      (e.g., twice as many if E
   Schemes.  The goal is reduced by half), leading to
      malfunctions whose nature depends on implementation details.  Here
      also, assess the attack always results in a form adequacy of DoS;

   It is therefore RECOMMENDED these two functions
   in producing coding coefficients that security measures are sufficiently different from
   one another, across various repair symbols with repair key values in
   sequence (we can expect this approach to be taken commonly used by
   implementers Section 6.1).  This section is purely informational and
   does not claim to
   guarantee be a solid evaluation.

   The two RLC FEC Schemes use the FFCI integrity, as specified in [RFC6363].  How PRNG to
   achieve this depends on the way produce pseudo-random coding
   coefficients (Section 3.6), each time a new repair symbol is needed.
   A different repair key is used for each repair symbol, usually by
   incrementing the FFCI repair key value (Section 6.1).  For each repair
   symbol, a limited number of pseudo-random numbers is communicated from needed,
   depending on the
   sender DT and encoding window size (Section 3.6), using
   either tinymt32_rand16() or tinymt32_rand256().  Therefore we are
   more interested in the randomness of small sequences of random
   numbers mapped to 4-bit or 8-bit integers, than in the receiver, randomness of
   a very large sequence of random nmbers which is not specified in this document.

   Similarly, attacks are possible against the Explicit Source FEC
   Payload ID and Repair FEC Payload ID.  More specifically, in case representative of
   a FEC Source Packet, the following value can be modified by an
   attacker who targets receivers:

   o  Encoding Symbol ID (ESI): changing
   the ESI leads a receiver to
      consider a wrong ADU, resulting in severe consequences, including
      corrupted content passed to usage of the receiving application;

   And in case PRNG.

   Evaluation of a FEC Repair Packet:

   o  Repair Key: changing this value leads a receiver to tinymt32_rand16(): We first generate a
      wrong coding coefficient sequence, huge number
   (1,000,000,000) of small sequences (20 pseudo-random numbers per
   sequence), and therefore any source symbol
      decoded using perform statistics on the repair symbols contained in this packet will be
      corrupted;
   o  DT: changing this number of occurrences of
   each of the 16 possible values across all sequences.

   value also leads    occurrences       percentage (%) (total of 20000000000)
   0        1250036799        6.2502
   1        1249995831        6.2500
   2        1250038674        6.2502
   3        1250000881        6.2500
   4        1250023929        6.2501
   5        1249986320        6.2499
   6        1249995587        6.2500
   7        1250020363        6.2501
   8        1249995276        6.2500
   9        1249982856        6.2499
   10       1249984111        6.2499
   11       1250009551        6.2500
   12       1249955768        6.2498
   13       1249994654        6.2500
   14       1250000569        6.2500
   15       1249978831        6.2499

     Figure 12: tinymt32_rand16(): occurrence statistics across a receiver huge
    number (1,000,000,000) of small sequences (20 pseudo-random numbers
               per sequence), with 0 as the first PRNG seed.

   The results (Figure 12) show that all possible values are almost
   equally represented, or said differently, that the tinymt32_rand16()
   output converges to generate a wrong
      coding coefficient sequence, and therefore any source symbol
      decoded using the repair symbols contained in this packet will be
      corrupted.  In addition, if uniform distribution where each of the DT 16
   possible value is significantly
      increased, it will generate a higher processing overhead at a
      receiver.  In case would appear exactly 1 / 16 * 100 = 6.25% of very large encoding windows, this times.

   Other types of biases may impact exist that may be visible with smaller
   tests (e.g., to evaluation the terminal performance;
   o  NSS: changing this value leads a receiver convergence speed to consider a different
      set of source symbols, and uniform
   distribution).  We therefore any source symbol decoded
      using the repair symbols contained perform 200 tests, each of them
   consisting in this packet will be
      corrupted.  In addition, if producing 200 sequences, keeping ony the NSS first value is significantly
      increased, of
   each sequence.  We use non overlapping repair keys for each sequence,
   starting with value 0 and increasing it will generate a higher processing overhead at a
      receiver, which may impact the terminal performance;
   o  FSS_ESI: changing this after each use.

   value also leads a receiver to consider a
      different set    min occurrences  max occurrences   average occurrences
   0        4                21                6.3675
   1        4                22                6.0200
   2        4                20                6.3125
   3        5                23                6.1775
   4        5                24                6.1000
   5        4                21                6.5925
   6        5                30                6.3075
   7        6                22                6.2225
   8        5                26                6.1750
   9        3                21                5.9425
   10       5                24                6.3175
   11       4                22                6.4300
   12       5                21                6.1600
   13       5                22                6.3100
   14       4                26                6.3950
   15       4                21                6.1700

   Figure 13: tinymt32_rand16(): occurrence statistics across 200 tests,
    each of source symbols and therefore any source symbol
      decoded using the repair symbols contained them consisting in this packet will be
      corrupted.

   It is therefore RECOMMENDED that security measures are taken to
   guarantee the FEC Source and Repair Packets as stated 200 sequences of 1 pseudo-random number
    each, with non overlapping PRNG seeds in [RFC6363].

8.3.  When Several Source Flows are to be Protected Together

   The Sliding Window RLC FEC Scheme specified sequence starting from 0.

   Figure 13 shows across all 200 tests, for each of the 16 possible
   pseudo-random number values, the minimum (resp. maximum) number of
   times it appeared in this document does not
   change a tests, as well as the recommendations average number of [RFC6363].

8.4.  Baseline Secure FEC Framework Operation

   The Sliding Window RLC FEC Scheme specified
   occurrences across the 200 tests.  Although the distribution is not
   perfect, there is no major bias.  On the opposite, in this document does not
   change the recommendations of [RFC6363] concerning same
   conditions, the use Park Miller linear congruential PRNG of the
   IPsec/ESP security protocol as [RFC5170]
   with a mandatory to implement (but not
   mandatory to use) security scheme.  This is well suited result scaled down to situations
   where 4-bit values, using seeds in sequence
   starting from 1, returns systematically 0 as the only insecure domain first value during
   some time, then after a certain repair key value threshold, it
   systematically returns 1, etc.

   Evaluation of tinymt32_rand256(): The same approach is the one over which the FEC
   Framework operates.

8.5.  Additional Security Considerations for Numerical Computations

   In addition used here.
   Results (not shown) are similar: occurrences vary between 7,810,3368
   (i.e., 0.3905%) and 7,814,7952 (i.e., 0.3907%).  Here also we see a
   convergence to the above security considerations, inherited from
   [RFC6363], theoretical uniform distribution where each of the present document introduces several formulae, in
   particular in
   possible value would appear exactly 1 / 256 * 100 = 0.390625% of
   times.

Appendix C.  Possible Parameter Derivation (Informational)

   Section 3.1.1.  It is RECOMMENDED 3.1 defines several parameters to check that control the
   computed values stay within reasonnable bounds since numerical
   overflows, caused by an erroneous implementation encoder or an erroneous
   input value, may lead
   decoder.  This annex proposes techniques to hazardous behaviours.  However what
   "reasonnable bounds" means is use-case and implementation dependent
   and derive these parameters
   according to the target use-case.  This annex is not detailed informational, in this document.

   Section 3.1.2 also mentions
   the possibility of "using sense that using a different derivation technique will not
   prevent the timestamp
   field of an RTP packet header" when applicable.  A malicious attacker
   may deliberately corrupt this header field in order encoder and decoder to trigger
   hazardous behaviours at interoperate: a FECFRAME receiver.  Protection against this
   type of content corruption decoder can be addressed with the above
   recommendations on a baseline secure operation.  In addition, it is
   also RECOMMENDED still
   recover an erased source symbol without any error.  However, in case
   of a real-time flow, an inappropriate parameter derivation may lead
   to check that the timestamp value be within
   reasonnable bounds.

9.  Operations and Management Considerations

   The FEC Framework document [RFC6363] provides a comprehensive
   analysis decoding of operations and management considerations applicable erased source packets after their validity period,
   making them useless to
   FEC Schemes.  Therefore, the present section only discusses specific
   topics.

9.1.  Operational Recommendations: Finite Field GF(2) Versus GF(2^^8) target application.  This annex proposes
   an approach to reduce this risk, among other things.

   The present document specifies two FEC Schemes that differ defined in this document can be used in various
   manners, depending on the
   Finite Field used for target use-case:

   o  the coding coefficients.  It is expected that source ADU flow they protect may or may not have real-time
      constraints;
   o  the RLC over GF(2^^8) FEC Scheme will source ADU flow may be mostly used since it
   warrants a higher packet loss protection.  In case of small encoding
   windows, Constant Bitrate (CBR) or Variable
      BitRate (VBR) flow;
   o  with a VBR source ADU flow, the associated processing overhead is flow's minimum and maximum
      bitrates may or may not an issue (e.g., we
   measured decoding speeds between 745 Mbps be known;
   o  and 2.8 Gbps on an ARM
   Cortex-A15 embedded board in [Roca17]).  Of course the CPU overhead
   will increase with the encoding window size, because more operations
   in the GF(2^^8) finite field will communication path between encoder and decoder may be needed. a
      CBR communication path (e.g., as with certain LTE-based broadcast
      channels) or not (general case, e.g., with Internet).

   The RLC over GF(2) FEC Scheme offers an alternative.  In that case
   operations symbols can be directly XOR-ed together which warrants
   high bitrate encoding and decoding operations, and can parameter derivation technique should be an
   advantage suited to the use-case,
   as described in the following sections.

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

   In the following, we consider a real-time flow with large max_lat latency
   budget.  The encoding windows.  However packet symbol size, E, is constant.  The code rate,
   cr, is also constant, its value depending on the expected
   communication loss
   protection model (this choice is significantly reduced by using out of scope of this FEC Scheme.

9.2.  Operational Recommendations: Coding Coefficients Density Threshold
   document).

   In addition to a first configuration, the choice of source ADU flow bitrate at the Finite Field, input of
   the two FEC Schemes
   define a coding coefficient density threshold (DT) parameter.  This
   parameter enables a FECFRAME sender is fixed and equal to control br_in (in bits/s), and this
   value is known by the code density, i.e., FECFRAME sender.  It follows that the
   proportion
   transmission bitrate at the output of coefficients that are non zero the FECFRAME sender will be
   higher, depending on average.  With RLC
   over GF(2^^8), it is usually appropriate the added repair flow overhead.  In order to
   comply with the maximum FEC-related latency budget, we have:

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

   assuming that small the encoding windows
   be associated and decoding times are negligible with
   respect to the target max_lat.  This is a density threshold equal to 15, reasonable assumption in
   many situations (e.g., see Section 9.1 in case of small window
   sizes).  Otherwise the maximum value, max_lat parameter should be adjusted in order
   to warrant a high loss protection.

   On the opposite, with larger encoding windows, it is usually
   appropriate that avoid the density threshold be reduced.  With large
   encoding windows, an alternative can problem.  In any case, interoperability will never be to use RLC over GF(2) and
   compromized by choosing a too large value.

   In a
   density threshold equal to 7 (i.e., an average density second configuration, the FECFRAME sender generates a fixed
   bitrate flow, equal to 1/2)
   or smaller.

   Note that using a density threshold the CBR communication path bitrate equal to 15 with RLC over GF(2)
   br_out (in bits/s), and this value is equivalent to using an XOR code that compute the XOR sum of all known by the source symbols FECFRAME sender,
   as in [Roca17].  The maximum source flow bitrate needs to be such
   that, with the encoding window.  In that case: (1) a
   single added repair symbol can be produced for any flow overhead, the total transmission
   bitrate remains inferior or equal to br_out.  We have:

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

   assuming here also that the encoding window, and (2) decoding times are
   negligible with respect to the repair_key parameter becomes useless (the coding coefficients
   generation function does not rely on target max_lat.

   For decoding to be possible within the PRNG).

10.  IANA Considerations

   This document registers two values in latency budget, it is required
   that the "FEC Framework (FECFRAME)
   FEC Encoding IDs" registry [RFC6363] as follows:

   o  YYYY refers encoding window maximum size be smaller than or at most
   equal to the Sliding Window Random Linear Codes (RLC) over
      GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in
      Section 5 of this document.
   o  XXXX refers to decoding window maximum size.  The ew_max_size is the Sliding Window Random Linear Codes (RLC) over
      GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in
      Section 4 of this document.

11.  Acknowledgments
   main parameter at a FECFRAME sender, but its exact value has no
   impact on the the FEC-related latency budget.  The authors would like ew_max_size
   parameter is computed as follows:

      ew_max_size = dw_max_size * WSR / 255

   In line with [Roca17], WSR = 191 is considered as a reasonable value
   (the resulting encoding to thank Russ Housley, Alan DeKok, Spencer
   Dawkins, Gorry Fairhurst, Jonathan Detchart, Emmanuel Lochin, decoding window size ratio is then close
   to 0.75), but other values between 1 and
   Marie-Jose Montpetit for their valuable feedbacks 255 inclusive are possible,
   depending on this document.

12.  References

12.1.  Normative References

   [fecframe-ext]
              Roca, V. and A. Begen, "Forward Error Correction (FEC)
              Framework Extension to Sliding Window Codes", Transport
              Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext
              (Work in Progress), September 2018,
              <https://tools.ietf.org/html/
              draft-ietf-tsvwg-fecframe-ext>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs the use-case.

   The dw_max_size is computed by a FECFRAME sender but not explicitly
   communicated to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

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

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

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

12.2.  Informative References

   [KR12]     Rikitake, K., "TinyMT Pseudo Random ew_max_size by observing the maximum Number Generator for
              Erlang",  ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
              September 14, 2012, Copenhagen, Denmark, DOI:
              http://dx.doi.org/10.1145/2364489.2364504, September 2012.

   [PGM13]    Plank, J., Greenan, K., and E. Miller, "A Complete
              Treatment
   of Software Implementations Source Symbols (NSS) value contained in the Repair FEC Payload ID
   of Finite Field
              Arithmetic received FEC Repair Packets (Section 4.1.3).  A receiver can then
   easily compute dw_max_size:

      dw_max_size = max_NSS_observed * 255 / WSR

   A receiver can then chose an appropriate linear system maximum size:

      ls_max_size >= dw_max_size

   It is good practice to use a larger value for Erasure Coding Applications", University of
              Tennessee Technical Report UT-CS-13-717,
              http://web.eecs.utk.edu/~plank/plank/papers/
              UT-CS-13-717.html, October 2013,
              <http://web.eecs.utk.edu/~plank/plank/papers/
              UT-CS-13-717.html>.

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

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

   [RFC6816]  Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density
              Parity Check (LDPC) Staircase Forward Error Correction
              (FEC) Scheme ls_max_size as
   explained in Appendix D, which does not impact maximum latency nor
   interoperability.

   In any case, for FECFRAME", RFC 6816,
              DOI 10.17487/RFC6816, December 2012,
              <https://www.rfc-editor.org/info/rfc6816>.

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

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

   [Roca16]   Roca, V., Teibi, B., Burdinat, C., Tran, T.,
   communication impairments) and C.
              Thienot, "Block or Convolutional AL-FEC Codes? A
              Performance Comparison for Robust Low-Latency
              Communications", HAL open-archive document,hal-01395937
              https://hal.inria.fr/hal-01395937/en/, November 2016,
              <https://hal.inria.fr/hal-01395937/en/>.

   [Roca17]   Roca, V., Teibi, B., Burdinat, C., Tran, T., the computed ew_max_size,
   dw_max_size and C.
              Thienot, "Less Latency ls_max_size values, it is RECOMMENDED to check that
   the maximum encoding time and Better Protection with AL-FEC
              Sliding Window Codes: maximum memory requirements at a Robust Multimedia CBR Broadcast
              Case Study", 13th IEEE International Conference on
              Wireless
   FECFRAME sender, and Mobile Computing, Networking maximum decoding time and
              Communications (WiMob17), October
              2017 https://hal.inria.fr/hal-01571609v1/en/, October
              2017, <https://hal.inria.fr/hal-01571609v1/en/>.

Appendix A.  TinyMT32 Pseudo-Random Number Generator maximum memory
   requirements at a FECFRAME receiver, stay within reasonable bounds.
   When assuming that the encoding and decoding times are negligible
   with respect to the target max_lat, this should be verified as well,
   otherwise the max_lat SHOULD be adjusted accordingly.

   The TinyMT32 PRNG reference implementation particular case of session start needs to be managed
   appropriately since the ew_size, starting at zero, increases each
   time a new source ADU is distributed under received by the FECFRAME sender, until it
   reaches the ew_max_size value.  Therefore a FECFRAME receiver SHOULD
   continuously observe the received FEC Repair Packets, since the NSS
   value carried in the Repair FEC Payload ID will increase too, and
   adjust its ls_max_size accordingly if need be.  With a CBR flow,
   session start is expected to be the only moment when the encoding
   window size will increase.  Similarly, with a CBR real-time flow, the
   session end is expected to be the only moment when the encoding
   window size will progressively decrease.  No adjustment of the
   ls_max_size is required at the FECFRAME receiver in that case.

C.2.  Other Types of Real-Time Flow

   In the following, we consider a real-time source ADU flow with a BSD
   license by the authors
   max_lat latency budget and excerpts a variable bitrate (VBR) measured at the
   entry of it are reproduced in Figure 8.
   The differences with respect to the original source code are:

   o FECFRAME sender.  A first approach consists in
   considering the unused parts smallest instantaneous bitrate of the original source code have been removed;
   o  the appropriate ADU
   flow, when this parameter set has been added is known, and to reuse the initialization
      function;
   o derivation of
   Appendix C.1.  Considering the tinymt32_rand() function has been added;
   o smallest bitrate means that the function order has been changed;
   o  certain internal variables have been renamed for compactness
      purposes.

 <CODE BEGINS>
 /**
  * Tiny Mersenne Twister only 127 bit internal state
  *
  * Authors : Mutsuo Saito (Hiroshima University)
  *           Makoto Matsumoto (University of Tokyo)
  *
  * Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto,
  * Hiroshima University and The University of Tokyo.
  * All rights reserved.
  *
  * Redistribution and use in source
   encoding and binary forms, with or without
  * modification, decoding window maximum size estimations are permitted provided that
   pessimistic: these windows have the following conditions
  * are met:
  *
  *   - Redistributions of source code must retain smallest size required to enable
   on-time decoding at a FECFRAME receiver.  If the above copyright
  *     notice, instantaneous
   bitrate is higher than this list of conditions and the following disclaimer.
  *   - Redistributions in binary form must reproduce the above
  *     copyright notice, smallest bitrate, this list approach leads to
   an encoding window that is unnecessarily small, which reduces
   robustness in front of conditions and the following
  *     disclaimer long erasure bursts.

   Another approach consists in using ADU timing information (e.g.,
   using the documentation and/or other materials
  *     provided with the distribution.
  *   - Neither the name timestamp field of an RTP packet header, or registering the Hiroshima University nor
   time upon receiving a new ADU).  From the names of
  *     its contributors may be used to endorse or promote products
  *     derived from this software without specific prior written
  *     permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */

 #include <stdint.h>

 /**
  * tinymt32 internal state vector and parameters
  */
 typedef struct {
     uint32_t status[4];
     uint32_t mat1;
     uint32_t mat2;
     uint32_t tmat;
 } tinymt32_t;

 static void tinymt32_next_state (tinymt32_t * s);
 static uint32_t tinymt32_temper (tinymt32_t * s);
 static double tinymt32_generate_32double (tinymt32_t * s);

 /**
  * Parameter set to use global FEC-related latency
   budget, the FECFRAME sender can derive a practical maximum latency
   budget for encoding operations, max_lat_for_encoding.  For the IETF RLC FEC
   Schemes specification.
  * Do not change.
  * This parameter set is the first entry of the precalculated parameter
  * sets specified in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, available
  * at: https://github.com/jj1bdx/tinymtdc-longbatch/blob/master/
  *     tinymt32dc/tinymt32dc.0.1048576.txt this document, this latency budget SHOULD be
   computed with:

      max_lat_for_encoding = max_lat * WSR / 255

   It is also follows that any source symbols associated to an ADU that has
   timed-out with respect to max_lat_for_encoding SHOULD be removed from
   the parameter set used:
  *    Rikitake, K., "TinyMT Pseudo Random Number Generator for
  *    Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
  *    September, 2012.
  */
 #define TINYMT32_MAT1_PARAM     0x8f7011ee
 #define TINYMT32_MAT2_PARAM     0xfc78ff1f
 #define TINYMT32_TMAT_PARAM     0x3793fdff

 /**
  * This function initializes encoding window.  With this approach there is no pre-determined
   ew_size value: this value fluctuates over the internal state array with a 32-bit
  * unsigned integer seed.
  * @param s     pointer time according to tinymt internal state.
  * @param seed the
   instantaneous source ADU flow bitrate.  For practical reasons, a 32-bit unsigned integer used as
   FECFRAME sender may still require that ew_size does not increase
   beyond a seed.
  */
 void tinymt32_init (tinymt32_t * s, uint32_t seed)
 {
 #define MIN_LOOP 8
 #define PRE_LOOP 8
     s->status[0] = seed;
     s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
     s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
     s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
     for (int i = 1; i < MIN_LOOP; i++) {
         s->status[i & 3] ^= i + UINT32_C(1812433253)
             * (s->status[(i - 1) & 3]
                ^ (s->status[(i - 1) & 3] >> 30));
     }
     for (int i = 0; i < PRE_LOOP; i++) {
         tinymt32_next_state(s);
     }
 }

 /**
  * This function outputs maximum value (Appendix C.3).

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

   When the [0 .. maxv-1] range.
  * @param s     pointer observed NSS fluctuates significantly, a FECFRAME receiver
   may want to tinymt internal state.
  * @return      32-bit unsigned integer adapt its ls_max_size accordingly.  In particular when
   the NSS is significantly reduced, a FECFRAME receiver may want to
   reduce the ls_max_size too in order to limit computation complexity.
   A balance must be found between 0 using an ls_max_size "too large"
   (which increases computation complexity and maxv-1 inclusive.
  */
 uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv)
 {
     return (uint32_t)(tinymt32_generate_32double(s) * (double)maxv);
 }

 /**
  * Internal tinymt32 constants memory requirements) and functions.
  * Users should not call these functions directly.
  */
 #define TINYMT32_MEXP 127
 #define TINYMT32_SH0 1
 #define TINYMT32_SH1 10
 #define TINYMT32_SH8 8
 #define TINYMT32_MASK UINT32_C(0x7fffffff)
 #define TINYMT32_MUL (1.0f / 16777216.0f)

 /**
  * This function changes internal state of tinymt32.
  * @param s     pointer to tinymt internal state.
  */
 static void tinymt32_next_state (tinymt32_t * s)
 {
     uint32_t x;
     uint32_t y;

     y = s->status[3];
     x = (s->status[0] & TINYMT32_MASK)
         ^ s->status[1]
         ^ s->status[2];
     x ^= (x << TINYMT32_SH0);
     y ^= (y >> TINYMT32_SH0) ^ x;
     s->status[0] = s->status[1];
     s->status[1] = s->status[2];
     s->status[2] = x ^ (y << TINYMT32_SH1);
     s->status[3] = y;
     s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
     s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
 }

 /**
  * This function outputs 32-bit unsigned integer
   the opposite (which reduces recovery performance).

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

   Finally there are configurations where a source ADU flow has no real-
   time constraints.  FECFRAME and the FEC Schemes defined in this
   document can still be used.  The choice of appropriate parameter
   values can be directed by practical considerations.  For instance, it
   can derive from internal state.
  * @param s     pointer an estimation of the maximum memory amount that could
   be dedicated to tinymt internal state.
  * @return      32-bit unsigned pseudos number
  */
 static uint32_t tinymt32_temper (tinymt32_t * s)
 {
     uint32_t t0, t1;
     t0 = s->status[3];
     t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
     t0 ^= t1;
     t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
     return t0;
 }

 /**
  * This function outputs double precision floating point number from
  * internal state. the linear system at a FECFRAME receiver, or the
   maximum computation complexity at a FECFRAME receiver, both of them
   depending on the ls_max_size parameter.  The returned same considerations also
   apply to the FECFRAME sender, where the maximum memory amount and
   computation complexity depend on the ew_max_size parameter.

   Here also, the NSS value has 32-bit precision.
  * In other words, this function makes one double precision floating
  * point number from one 32-bit unsigned integer.
  * @param s     pointer contained in FEC Repair Packets is used by a
   FECFRAME receiver to tinymt internal state.
  * @return      floating point number r (0.0 <= r < 1.0)
  */
 static double tinymt32_generate_32double (tinymt32_t * s)
 {
     tinymt32_next_state(s);
     return (double)tinymt32_temper(s) * (1.0 / 4294967296.0);
 }
 <CODE ENDS>

                      Figure 8: TinyMT32 pseudo-code determine the current coding window size and
   ew_max_size by observing its maximum value over the time.

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

   This annex introduces non normative considerations.  It is provided
   as suggestions, without any impact on interoperability.  For more
   information see [Roca16].

   With a real-time source ADU flow, it is possible to improve the
   decoding performance of sliding window codes without impacting
   maximum latency, at the cost of extra memory and CPU overhead.  The
   optimization consists, for a FECFRAME receiver, to extend the linear
   system beyond the decoding window maximum size, by keeping a certain
   number of old source symbols whereas their associated ADUs timed-out:

      ls_max_size > dw_max_size

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

      ls_max_size = 2 * dw_max_size

   When the dw_max_size is very small, it may be preferable to keep a
   minimum ls_max_size value (e.g., LS_MIN_SIZE_DEFAULT = 40 symbols).
   Going below this threshold will not save a significant amount of
   memory nor CPU cycles.  Therefore:

      ls_max_size = max(2 * dw_max_size, LS_MIN_SIZE_DEFAULT)

   Finally, it is worth noting that a good receiver, i.e., a receiver that benefits from an FEC
   protection significantly higher than what is required to recover from
   packet losses, can choose to reduce the ls_max_size.  In that case
   lost ADUs will be recovered without relying on this optimization.

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

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

    Figure 9: 14: Relationship between parameters to decode beyond maximum
                                 latency.

   It means that source symbols, and therefore ADUs, may be decoded even
   if the added latency exceeds the maximum value permitted by the
   application (the "late source symbols" of Figure 9). 14).  It follows
   that the corresponding ADUs will not be useful to the application.
   However, decoding these "late symbols" significantly improves the
   global robustness in bad reception conditions and is therefore
   recommended for receivers experiencing bad communication conditions
   [Roca16].  In any case whether or not to use this optimization and
   what exact value to use for the ls_max_size parameter are local
   decisions made by each receiver independently, without any impact on
   the other receivers nor on the source.

Authors' Addresses

   Vincent Roca
   INRIA
   Univ. Grenoble Alpes
   France

   EMail: vincent.roca@inria.fr
   Belkacem Teibi
   INRIA
   Univ. Grenoble Alpes
   France

   EMail: belkacem.teibi@inria.fr belkacem.teibi@gmail.com

   Emmanuel Baccelli
   INRIA
   France

   EMail: emmanuel.baccelli@inria.fr