 1/draftietftsvwgrlcfecscheme04.txt 20180524 05:13:25.380277537 0700
+++ 2/draftietftsvwgrlcfecscheme05.txt 20180524 05:13:25.452279253 0700
@@ 1,19 +1,19 @@
TSVWG V. Roca
InternetDraft B. Teibi
Intended status: Standards Track INRIA
Expires: November 18, 2018 May 17, 2018
+Expires: November 24, 2018 May 23, 2018
Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC)
Schemes for FECFRAME
 draftietftsvwgrlcfecscheme04
+ draftietftsvwgrlcfecscheme05
Abstract
This document describes two fullyspecified Forward Erasure
Correction (FEC) Schemes for Sliding Window Random Linear Codes
(RLC), one for RLC over GF(2) (binary case), a second one for RLC
over GF(2^^8), both of them 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.
These sliding window FEC codes rely on an encoding window that slides
@@ 31,21 +31,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at https://datatracker.ietf.org/drafts/current/.
InternetDrafts 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 InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on November 18, 2018.
+ This InternetDraft will expire on November 24, 2018.
Copyright Notice
Copyright (c) 2018 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/licenseinfo) in effect on the date of
publication of this document. Please review these documents
@@ 64,63 +64,64 @@
1.3. Small Transmission Overheads with the Sliding Window RLC
FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Document Organization . . . . . . . . . . . . . . . . . . 6
2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6
3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Possible Parameter Derivations . . . . . . . . . . . . . 7
3.1.1. Case of a CBR RealTime Flow . . . . . . . . . . . . 8
3.1.2. Other Types of RealTime Flow . . . . . . . . . . . . 10
3.1.3. Case of a Non RealTime Flow . . . . . . . . . . . . 11
3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11
 3.3. Encoding Window Management . . . . . . . . . . . . . . . 12
 3.4. PseudoRandom Number Generator . . . . . . . . . . . . . 13
+ 3.3. Encoding Window Management . . . . . . . . . . . . . . . 13
+ 3.4. PseudoRandom Number Generator (PRNG) . . . . . . . . . . 13
3.5. Coding Coefficients Generation Function . . . . . . . . . 14
3.6. Finite Fields Operations . . . . . . . . . . . . . . . . 17
 3.6.1. Linear Combination of Source Symbols Computation . . 17
+ 3.6.1. Finite Field Definitions . . . . . . . . . . . . . . 17
+ 3.6.2. Linear Combination of Source Symbols Computation . . 17
4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18
4.1.1. FEC Framework Configuration Information . . . . . . . 18
4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 19
4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20
4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21
5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 22
 5.1.1. FEC Framework Configuration Information . . . . . . . 22
+ 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 21
+ 5.1.1. FEC Framework Configuration Information . . . . . . . 21
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 22
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22
5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 22
6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 22
6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 22
6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 23

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 24
8. Security Considerations . . . . . . . . . . . . . . . . . . . 24
8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24
8.1.1. Access to Confidential Content . . . . . . . . . . . 24
 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 25
+ 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 24
8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 25
8.3. When Several Source Flows are to be Protected Together . 25
8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25
 9. Operations and Management Considerations . . . . . . . . . . 26
+ 9. Operations and Management Considerations . . . . . . . . . . 25
9.1. Operational Recommendations: Finite Field GF(2) Versus
GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2. Operational Recommendations: Coding Coefficients Density
Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26
 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27
+ 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27
12.1. Normative References . . . . . . . . . . . . . . . . . . 27
 12.2. Informative References . . . . . . . . . . . . . . . . . 28
 Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 30
 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 31
+ 12.2. Informative References . . . . . . . . . . . . . . . . . 27
+ Appendix A. TinyMT32 PseudoRandom Number Generator . . . . . . 29
+ Appendix B. Decoding Beyond Maximum Latency Optimization . . . . 32
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 33
1. Introduction
ApplicationLevel Forward Erasure Correction (ALFEC) 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 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
@@ 177,21 +178,21 @@
(symbols) are generated onthefly, 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 of each
repair symbol received) are added upon receiving new packets.
Variables are removed when they are too old with respect to their
validity period (realtime constraints), as well as the associated
 equations they are involved in (Appendix A introduces an optimization
+ equations they are involved in (Appendix B introduces an optimization
that extends the time a variable is considered in the system). Lost
source symbols are then recovered thanks to this linear system
whenever its rank permits it.
With RLC codes (more generally with sliding window codes), the
protection of a multicast/broadcast session also needs to be
dimensioned by considering the worst communication conditions one
wants to support. However the receivers experiencing a good to
medium communication quality will observe a reduced FECrelated
latency compared to block codes [Roca17] since an isolated lost
@@ 276,21 +277,21 @@
assumed fixed (in bits/s)
max_lat: maximum FECrelated latency within FECFRAME (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)
PRNG: pseudorandom number generator
 pmms_rand(maxv): PRNG defined in Section 3.4 and used in this
+ tinymt32_rand(maxv): PRNG defined in Section 3.4 and used in this
specification, that returns a new random integer in [0; maxv1]
DT: coding coefficients density threshold, an integer between 0 and
15 (inclusive) the controls the fraction of coefficients that are
non zero
3. Procedures
This section introduces the procedures that are used by these FEC
Schemes.
@@ 331,21 +333,21 @@
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
counterproductive. On the opposite, the linear system MAY grow
 beyond the dw_max_size (Appendix A);
+ beyond the dw_max_size (Appendix B);
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 fix the E parameter and communicate it as part of the FEC
SchemeSpecific 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
@@ 411,21 +413,21 @@
received 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 is good practice to use a larger value for ls_max_size as
 explained in Appendix A, which does not impact maximum latency nor
+ explained in Appendix B, which does not impact maximum latency nor
interoperability. However the linear system size should not be too
large for practical reasons (e.g., in order to limit computation
complexity).
The particular case 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 the ew_max_size
value. 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
@@ 465,21 +467,21 @@
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
appropriate ls_max_size as explained in Section 3.1.1.
When the observed NSS fluctuates significantly, a FECFRAME receiver
may want to adapt its ls_max_size accordingly. In particular when
 the NSS is significanlty reduced, a FECFRAME receiver may want to
+ the NSS is significantly reduced, a FECFRAME receiver may want to
reduce the ls_max_size too 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 the opposite (which can reduce recovery performance).
Beyond these general guidelines, the details of how to manage these
situations at a FECFRAME sender and receiver can depend on additional
considerations that are out of scope of this document.
3.1.3. Case of a Non RealTime Flow
@@ 585,77 +587,78 @@
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 FEC codec may feature practical limits in the number of
source symbols in the encoding window (e.g., for computational
complexity reasons). This factor may further limit the ew_max_size
value, in addition to the maximum FECrelated latency budget
(Section 3.1).
3.4. PseudoRandom Number Generator

 The RLC codes rely on the following PseudoRandom Number Generator
 (PRNG), identical to the PRNG used with LDPCStaircase codes
 ([RFC5170], section 5.7).
+3.4. PseudoRandom Number Generator (PRNG)
 The ParkMiler "minimal standard" PRNG [PM88] MUST be used. It
 defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij
 (modulo M), with the following choices: A = 7^^5 = 16807 and M =
 2^^31  1 = 2147483647. A validation criteria of such a PRNG is the
 following: if seed = 1, then the 10,000th value returned MUST be
 equal to 1043618065.
+ The RLC FEC Schemes defined in this document rely on the TinyMT32
+ PRNG, a smallsized variant of the Mersenne Twister PRNG, as defined
+ in the reference implementation version 1.1 (2015/04/24) by Mutsuo
+ Saito (Hiroshima University) and Makoto Matsumoto (The University of
+ Tokyo).
 Several implementations of this PRNG are known and discussed in the
 literature. An optimized implementation of this algorithm, using
 only 32bit mathematics, and which does not require any division, can
 be found in [rand31pmc]. It uses the Park and Miller algorithm
 [PM88] with the optimization suggested by D. Carta in [CA90]. The
 history behind this algorithm is detailed in [WI08].
+ o Official web site:
+ o Official github site and reference implementation:
+
 This PRNG produces, natively, a 31bit value between 1 and 0x7FFFFFFE
 (2^^312) inclusive. Since it is desired to scale the pseudorandom
 number between 0 and maxv1 inclusive, one must keep the most
 significant bits of the value returned by the PRNG (the least
 significant bits are known to be less random, and modulobased
 solutions should be avoided [PTVF92]). The following algorithm MUST
 be used:
+ For the RLC FEC Schemes defined in this document, the tinymt32 32bit
+ version (rather than the 64bit version) MUST be used. This PRNG
+ requires a parameter set that needs to be precalculated. For the
+ RLC FEC Schemes defined in this document, the following parameter set
+ MUST be used:
 Input:
+ o mat1 = 0x8f7011ee = 2406486510;
+ o mat2 = 0xfc78ff1f = 4235788063;
+ o tmat = 0x3793fdff = 932445695.
 raw_value: random integer generated by the inner PRNG algorithm,
 between 1 and 0x7FFFFFFE (2^^312) inclusive.
 maxv: upper bound used during the scaling operation.
+ This parameter set is the first entry of the precalculated parameter
+ sets in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, and
+ available at:
 Output:
+ o .
 scaled_value: random integer between 0 and maxv1 inclusive.
+ This is also the parameter set used in [KR12].
 Algorithm:
+ 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 of this PRNG, using seed 1, the 10,000th
+ value returned by: tinymt32_rand(s, 0xffff) MUST be equal to 0x7c37.
 scaled_value = (unsigned long) ((double)maxv * (double)raw_value /
 (double)0x7FFFFFFF);
 (NB: the above C type casting to unsigned long is equivalent to
 using floor() with positive floating point values.)
+ This PRNG MUST first be initialized with a 32bit unsigned integer,
+ used as a seed. The following function is used to this purpose:
 In this document, pmms_rand(maxv) denotes the PRNG function that
 implements the ParkMiller "minimal standard" algorithm, defined
 above, and that scales the raw value between 0 and maxv1 inclusive,
 using the above scaling algorithm.
+ void tinymt32_init (tinymt32_t * s, uint32_t seed);
 Additionally, the pmms_srand(seed) function must be provided to
 enable the initialization of the PRNG with a seed before calling
 pmms_rand(maxv) the first time. The seed is a 31bit integer between
 1 and 0x7FFFFFFE inclusive. In this specification, the seed is
 restricted to a value between 1 and 0xFFFF inclusive, as this is the
+ 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 this is the
Repair_Key 16bit field value of the Repair FEC Payload ID
 (Section 4.1.3).
+ (Section 4.1.3). In addition to the seed, this function takes as
+ parameter a pointer to an instance of a tinymt32_t structure that is
+ used to keep the internal state of the PRNG.
+
+ Then, each time a new pseudorandom integer between 0 and maxv1
+ inclusive is needed, the following function is used:
+
+ uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv);
+
+ This function takes as parameter both a pointer to 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
@@ 685,122 +687,105 @@
* (in) dt integer between 0 and 15 (inclusive) that
* controls the density. With value 15, all
* coefficients are guaranteed to be non zero
* (i.e. equal to 1 with GF(2) and equal to a
* value in {1,... 255} with GF(2^^8)), otherwise
* a fraction of them will be 0.
* (in) m Finite Field GF(2^^m) parameter. In this
* document only values 1 and 8 are considered.
* (out) returns an error code
*/
 int generate_coding_coefficients (UINT16 repair_key,
 UINT8 cc_tab[],
 UINT16 cc_nb,
 UINT8 dt,
 UINT8 m)
+ int generate_coding_coefficients (uint16_t repair_key,
+ uint8_t cc_tab[],
+ uint16_t cc_nb,
+ uint8_t dt,
+ uint8_t m)
{
 UINT32 i;
+ 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 {
/* here coefficients are either 0 or 1 */
 if (repair_key == 0) {
 return SOMETHING_WENT_WRONG; /* bad repair_key */
 }
 pmms_srand(repair_key);
 pmms_rand(16); /* skip the first PRNG value */
+ tinymt32_init(&s, repair_key);
for (i = 0 ; i < cc_nb ; i++) {
 if (pmms_rand(16) <= dt) {
 cc_tab[i] = (UINT8) 1;
+ if (tinymt32_rand(&s, 16) <= dt) {
+ cc_tab[i] = (uint8_t) 1;
} else {
 cc_tab[i] = (UINT8) 0;
+ cc_tab[i] = (uint8_t) 0;
}
}
}
break;
case 8:
 if (repair_key == 0) {
 return SOMETHING_WENT_WRONG; /* bad repair_key */
 }
 pmms_srand(repair_key);
 pmms_rand(256); /* skip the first PRNG value */
+ tinymt32_init(&s, repair_key);
if (dt == 15) {
/* coefficient 0 is avoided here in order to include
* all the source symbols */
for (i = 0 ; i < cc_nb ; i++) {
do {
 cc_tab[i] = (UINT8) pmms_rand(256);
+ cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
} while (cc_tab[i] == 0);
}
} else {
/* here a certain fraction of coefficients should be 0 */
for (i = 0 ; i < cc_nb ; i++) {
 if (pmms_rand(16) <= dt) {
+ if (tinymt32_rand(&s, 16) <= dt) {
do {
 cc_tab[i] = (UINT8) pmms_rand(256);
+ cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
} while (cc_tab[i] == 0);
} else {
cc_tab[i] = 0;
}
}
}
break;
default:
/* bad parameter m */
return SOMETHING_WENT_WRONG;
}
return EVERYTHING_IS_OKAY;
}
 Figure 2: Coding Coefficients Generation Function pseudocode
 One can note in the above function that each call to pmms_srand()
 (PRNG initialisation) is immediately followed by a call to
 pmms_rand() whose return value is ignored. This extra call is
 motivated by a possible bias in the first value generated depending
 on the way the repair key is managed by a FECFRAME implementation.
 Indeed, the PRNG sequences produced by two seeds in sequence have a
 high probability of starting with the same value since I1 = A * seed
 (modulo M) which is further scaled to a small range (either {0, ...
 15} or {0, ... 255}). Producing several times the same first coding
 coefficient could reduce the protection of the first source symbol if
 multiple repair symbols are produced with the same coding window's
 left edge. The extra call avoids such side effects.
+ Figure 2: Coding Coefficients Generation Function pseudocode
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 in [RFC5510], section 8.1. More specifically, the
elements of the field GF(2^^m) are represented by polynomials with
binary coefficients (i.e., over GF(2)) and degree lower or equal to
m1. The addition between two elements is defined as the addition of
binary polynomials in GF(2), which is equivalent to a bitwise XOR
operation on the binary representation of these elements.
With GF(2^^8), multiplication between two elements is the
multiplication modulo a given irreducible polynomial of degree 8.
The following irreducible polynomial 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.1. Linear Combination of Source Symbols Computation
+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 and the repair
@@ 943,26 +927,25 @@
++
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 (16bit 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. Value 0 MUST
 NOT be used. When a FEC Repair Packet contains several repair
 symbols, this repair key value is that of the first repair symbol.
 The remaining repair keys can be deduced by incrementing by 1 this
 value, up to a maximum value of 65535 after which it loops back to
 1 (note that 0 is not a valid value).
+ generate the desired number of coding coefficients. When a FEC
+ Repair Packet contains several repair symbols, this repair key
+ value is that of the first repair symbol. The remaining repair
+ keys can be deduced by incrementing by 1 this value, up to a
+ maximum value of 65535 after which it loops back to 0.
Density Threshold for the coding coefficients, DT (4bit field):
this unsigned integer carries the Density Threshold (DT) used by
the coding coefficient generation function Section 3.5. More
precisely, it controls the probability of 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 (12bit field):
this unsigned integer indicates the number of source symbols in
@@ 1034,42 +1017,41 @@
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 non
 zero monotonically increasing integer value, incremented for each
 repair symbol up to a maximum value of 65535 (as it is carried within
 a 16bit field) after which it loops back to 1 (indeed, being used as
 a PRNG seed, value 0 is prohibited). This repair key is communicated
 to the coefficient generation function (Section Section 3.5) in order
 to generate ew_size coding coefficients. Finally, the FECFRAME
+ 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
+ 16bit field) after which it loops back to 0. This repair key is
+ communicated to the coefficient generation function (Section 3.5) 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. 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.
+ ew_size source symbols using the ew_size coding coefficients
+ (Section 3.6). 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 1 and 65535. However, selecting the same repair key
+ 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
@@ 1097,23 +1079,23 @@
With realtime 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 A discusses a backward compatible
+ document. Additionally, Appendix B discusses a backward compatible
optimization whereby late source symbols MAY still be used within the
 FECFRAME receiver in order to improve the global robustness.
+ 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
@@ 1283,51 +1265,34 @@
DOI 10.17487/RFC6363, October 2011,
.
[RFC6364] Begen, A., "Session Description Protocol Elements for the
Forward Error Correction (FEC) Framework", RFC 6364,
DOI 10.17487/RFC6364, October 2011,
.
12.2. Informative References
 [CA90] Carta, D., "Two Fast Implementations of the Minimal
 Standard Random Number Generator", Communications of the
 ACM, Vol. 33, No. 1, pp.8788, January 1990.
+ [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 UTCS13717,
http://web.eecs.utk.edu/~plank/plank/papers/
UTCS13717.html, October 2013,
.
 [PM88] Park, S. and K. Miller, "Random Number Generators: Good
 Ones are Hard to Find", Communications of the ACM, Vol.
 31, No. 10, pp.11921201, 1988.

 [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
 "Numerical Recipies in C; Second Edition", Cambridge
 University Press, ISBN: 0521431085, 1992.

 [rand31pmc]
 Whittle, R., "31 bit pseudorandom number generator",
 September 2005, .

 [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, .

[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"ReedSolomon Forward Error Correction (FEC) Schemes",
RFC 5510, DOI 10.17487/RFC5510, April 2009,
.
[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,
.
@@ 1352,25 +1317,199 @@
[Roca17] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C.
Thienot, "Less Latency and Better Protection with ALFEC
Sliding Window Codes: a 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/hal01571609v1/en/, October
2017, .
 [WI08] Whittle, R., "ParkMillerCarta PseudoRandom Number
 Generator", http://www.firstpr.com.au/dsp/rand31/,
 January 2008, .
+Appendix A. TinyMT32 PseudoRandom Number Generator
Appendix A. Decoding Beyond Maximum Latency Optimization
+ The TinyMT32 PRNG reference implementation is distributed under a BSD
+ license by the authors and excerpts of it are reproduced in Figure 8.
+ Differences with respect to the original source code are the
+ following:
+
+ o unused parts of the original source code have been removed;
+ o the appropriate parameter set has been added to the initialisation
+ function;
+ o function tinymt32_rand() has been added;
+ o function order has been changed;
+ o certain internal variables have been renamed for compactness
+ purposes.
+
+
+ /**
+ * 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 and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ *  Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *  Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *  Neither the name of the Hiroshima University nor 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.
+ */
+
+ /**
+ * 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 for RLC FEC Schemes. Do not change.
+ */
+ #define TINYMT32_MAT1_PARAM 0x8f7011ee
+ #define TINYMT32_MAT2_PARAM 0xfc78ff1f
+ #define TINYMT32_TMAT_PARAM 0x3793fdff
+
+ /**
+ * This function initializes the internal state array with a 32bit
+ * unsigned integer seed.
+ * @param s tinymt state vector.
+ * @param seed a 32bit unsigned integer used as 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 an integer in the [0 .. maxv1] range.
+ * @param s tinymt internal status
+ * @return floating point number r (0.0 <= r < 1.0)
+ */
+ uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv)
+ {
+ return (uint32_t)(tinymt32_generate_32double(s) * (double)maxv);
+ }
+
+ /**
+ * Internal tinymt32 constants 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 tinymt internal status
+ */
+ 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 32bit unsigned integer from internal state.
+ * @param s tinymt internal status
+ * @return 32bit 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 returned value has 32bit precision.
+ * In other words, this function makes one double precision floating
+ * point number from one 32bit unsigned integer.
+ * @param s tinymt internal status
+ * @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);
+ }
+
+
+ Figure 8: TinyMT32 pseudocode
+
+Appendix B. Decoding Beyond Maximum Latency Optimization
This annex introduces non normative considerations. They are
provided as suggestions, without any impact on interoperability. For
more information see [Roca16].
With a realtime source ADU flow, it is possible to improve the
decoding performance of sliding window codes without impacting
maximum latency, at the cost of extra 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
@@ 1397,21 +1536,21 @@
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 8: Relationship between parameters to decode beyond maximum
+ Figure 9: 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. 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