< draft-ietf-tsvwg-rlc-fec-scheme-10.txt   draft-ietf-tsvwg-rlc-fec-scheme-11.txt >
TSVWG V. Roca TSVWG V. Roca
Internet-Draft B. Teibi Internet-Draft B. Teibi
Intended status: Standards Track E. Baccelli Intended status: Standards Track INRIA
Expires: July 21, 2019 INRIA Expires: August 5, 2019 February 1, 2019
January 17, 2019
Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC)
Schemes for FECFRAME Schemes for FECFRAME
draft-ietf-tsvwg-rlc-fec-scheme-10 draft-ietf-tsvwg-rlc-fec-scheme-11
Abstract Abstract
This document describes two fully-specified Forward Erasure This document describes two fully-specified Forward Erasure
Correction (FEC) Schemes for Sliding Window Random Linear Codes Correction (FEC) Schemes for Sliding Window Random Linear Codes
(RLC), one for RLC over the Galois Field (A.K.A. Finite Field) (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 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 with the possibility of controlling the code density. They can
protect arbitrary media streams along the lines defined by FECFRAME protect arbitrary media streams along the lines defined by FECFRAME
extended to sliding window FEC codes, as defined in [fecframe-ext]. extended to sliding window FEC codes, as defined in [fecframe-ext].
skipping to change at page 1, line 44 skipping to change at page 1, line 43
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on July 21, 2019. This Internet-Draft will expire on August 5, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 36 skipping to change at page 2, line 31
1.3. Small Transmission Overheads with the Sliding Window RLC 1.3. Small Transmission Overheads with the Sliding Window RLC
FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5 FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Document Organization . . . . . . . . . . . . . . . . . . 6 1.4. Document Organization . . . . . . . . . . . . . . . . . . 6
2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6 2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6
3. Common Procedures . . . . . . . . . . . . . . . . . . . . . . 7 3. Common Procedures . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Codec Parameters . . . . . . . . . . . . . . . . . . . . 7 3.1. Codec Parameters . . . . . . . . . . . . . . . . . . . . 7
3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9
3.3. Encoding Window Management . . . . . . . . . . . . . . . 10 3.3. Encoding Window Management . . . . . . . . . . . . . . . 10
3.4. Source Symbol Identification . . . . . . . . . . . . . . 11 3.4. Source Symbol Identification . . . . . . . . . . . . . . 11
3.5. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 11 3.5. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 11
3.6. Coding Coefficients Generation Function . . . . . . . . . 17 3.6. Coding Coefficients Generation Function . . . . . . . . . 12
3.7. Finite Fields Operations . . . . . . . . . . . . . . . . 19 3.7. Finite Fields Operations . . . . . . . . . . . . . . . . 15
3.7.1. Finite Field Definitions . . . . . . . . . . . . . . 19 3.7.1. Finite Field Definitions . . . . . . . . . . . . . . 15
3.7.2. Linear Combination of Source Symbols Computation . . 19 3.7.2. Linear Combination of Source Symbols Computation . . 15
4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary
Packet Flows . . . . . . . . . . . . . . . . . . . . . . . . 20 Packet Flows . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 20 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 16
4.1.1. FEC Framework Configuration Information . . . . . . . 20 4.1.1. FEC Framework Configuration Information . . . . . . . 16
4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 22 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 17
4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 18
4.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 24 4.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 19
5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 24 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 20
5.1.1. FEC Framework Configuration Information . . . . . . . 24 5.1.1. FEC Framework Configuration Information . . . . . . . 20
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 24 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 20
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 24 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20
5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 20
5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 25 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 20
6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 25 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 20
6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 25 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 21
6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 25 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 22
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 26 8. Security Considerations . . . . . . . . . . . . . . . . . . . 22
8. Security Considerations . . . . . . . . . . . . . . . . . . . 27 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 23
8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 27 8.1.1. Access to Confidential Content . . . . . . . . . . . 23
8.1.1. Access to Confidential Content . . . . . . . . . . . 27 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 23
8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 27 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 23
8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 27 8.3. When Several Source Flows are to be Protected Together . 25
8.3. When Several Source Flows are to be Protected Together . 29 8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25
8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 29
8.5. Additional Security Considerations for Numerical 8.5. Additional Security Considerations for Numerical
Computations . . . . . . . . . . . . . . . . . . . . . . 29 Computations . . . . . . . . . . . . . . . . . . . . . . 25
9. Operations and Management Considerations . . . . . . . . . . 30 9. Operations and Management Considerations . . . . . . . . . . 25
9.1. Operational Recommendations: Finite Field GF(2) Versus 9.1. Operational Recommendations: Finite Field GF(2) Versus
GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 30 GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 25
9.2. Operational Recommendations: Coding Coefficients Density 9.2. Operational Recommendations: Coding Coefficients Density
Threshold . . . . . . . . . . . . . . . . . . . . . . . . 30 Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 31 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 31 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27
12.1. Normative References . . . . . . . . . . . . . . . . . . 31 12.1. Normative References . . . . . . . . . . . . . . . . . . 27
12.2. Informative References . . . . . . . . . . . . . . . . . 32 12.2. Informative References . . . . . . . . . . . . . . . . . 28
Appendix A. TinyMT32 Validation Criteria (Normative) . . . . . . 34 Appendix A. TinyMT32 Validation Criteria (Normative) . . . . . . 30
Appendix B. Assessing the PRNG Adequacy (Informational) . . . . 35 Appendix B. Assessing the PRNG Adequacy (Informational) . . . . 31
Appendix C. Possible Parameter Derivation (Informational) . . . 37 Appendix C. Possible Parameter Derivation (Informational) . . . 33
C.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . . . 38 C.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . . . 34
C.2. Other Types of Real-Time Flow . . . . . . . . . . . . . . 40 C.2. Other Types of Real-Time Flow . . . . . . . . . . . . . . 36
C.3. Case of a Non Real-Time Flow . . . . . . . . . . . . . . 41 C.3. Case of a Non Real-Time Flow . . . . . . . . . . . . . . 37
Appendix D. Decoding Beyond Maximum Latency Optimization Appendix D. Decoding Beyond Maximum Latency Optimization
(Informational) . . . . . . . . . . . . . . . . . . 41 (Informational) . . . . . . . . . . . . . . . . . . 37
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 42 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 38
1. Introduction 1. Introduction
Application-Level Forward Erasure Correction (AL-FEC) codes, or Application-Level Forward Erasure Correction (AL-FEC) codes, or
simply FEC codes, are a key element of communication systems. They simply FEC codes, are a key element of communication systems. They
are used to recover from packet losses (or erasures) during content are used to recover from packet losses (or erasures) during content
delivery sessions to a potentially large number of receivers delivery sessions to a potentially large number of receivers
(multicast/broadcast transmissions). This is the case with the (multicast/broadcast transmissions). This is the case with the
FLUTE/ALC protocol [RFC6726] when used for reliable file transfers FLUTE/ALC protocol [RFC6726] when used for reliable file transfers
over lossy networks, and the FECFRAME protocol when used for reliable over lossy networks, and the FECFRAME protocol when used for reliable
skipping to change at page 7, line 24 skipping to change at page 7, line 21
cr: RLC coding rate, ratio between the total number of source cr: RLC coding rate, ratio between the total number of source
symbols and the total number of source plus repair symbols symbols and the total number of source plus repair symbols
ew_size: encoding window current size at a sender (in symbols) ew_size: encoding window current size at a sender (in symbols)
ew_max_size: encoding window maximum 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) 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 ls_max_size: linear system maximum size (or width) at a receiver (in
symbols) symbols)
WSR: window size ratio parameter used to derive ew_max_size WSR: window size ratio parameter used to derive ew_max_size
(encoder) and ls_max_size (decoder). (encoder) and ls_max_size (decoder).
PRNG: pseudo-random number generator PRNG: pseudo-random number generator
TinyMT32: PRNG defined in Section 3.5 and used in this TinyMT32: PRNG used in this specification.
specification.
DT: coding coefficients density threshold, an integer between 0 and DT: coding coefficients density threshold, an integer between 0 and
15 (inclusive) the controls the fraction of coefficients that are 15 (inclusive) the controls the fraction of coefficients that are
non zero non zero
3. Common Procedures 3. Common Procedures
This section introduces the procedures that are used by these FEC This section introduces the procedures that are used by these FEC
Schemes. Schemes.
3.1. Codec Parameters 3.1. Codec Parameters
skipping to change at page 11, line 19 skipping to change at page 11, line 19
for the first source symbol and MUST be managed sequentially. for the first source symbol and MUST be managed sequentially.
Wrapping to zero happens after reaching the maximum value made Wrapping to zero happens after reaching the maximum value made
possible by the ESI field size (this maximum value is FEC Scheme possible by the ESI field size (this maximum value is FEC Scheme
dependant, for instance, 2^32-1 with FEC Schemes XXX and YYY). dependant, for instance, 2^32-1 with FEC Schemes XXX and YYY).
No such consideration applies to repair symbols. No such consideration applies to repair symbols.
3.5. Pseudo-Random Number Generator (PRNG) 3.5. Pseudo-Random Number Generator (PRNG)
In order to compute coding coefficients (see Section 3.6), the RLC In order to compute coding coefficients (see Section 3.6), the RLC
FEC Schemes defined in this document rely on the TinyMT32 PRNG (a FEC Schemes rely on the TinyMT32 PRNG defined in [tinymt32] with two
small-sized variant of the Mersenne Twister PRNG), as defined in the additional functions defined in this section.
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, the following parameter set
MUST be used:
o mat1 = 0x8f7011ee = 2406486510
o mat2 = 0xfc78ff1f = 4235788063
o tmat = 0x3793fdff = 932445695
This parameter set is the first entry of the precalculated parameter
sets in 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 in [KR12].
This PRNG MUST first be initialized with a 32-bit unsigned integer, This PRNG MUST first be initialized with a 32-bit unsigned integer,
used as a seed. The following function is used to this purpose: used as a seed, with:
void tinymt32_init (tinymt32_t * s, uint32_t seed); void tinymt32_init (tinymt32_t * s, uint32_t seed);
With the FEC Schemes defined in this document, the seed is in With the FEC Schemes defined in this document, the seed is in
practice restricted to a value between 0 and 0xFFFF inclusive (note practice restricted to a value between 0 and 0xFFFF inclusive (note
that this PRNG accepts a seed value equal to 0), since this is the that this PRNG accepts a seed value equal to 0), since this is the
Repair_Key 16-bit field value of the Repair FEC Payload ID Repair_Key 16-bit field value of the Repair FEC Payload ID
(Section 4.1.3). In addition to the seed, this function takes as (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 parameter a pointer to an instance of a tinymt32_t structure that is
used to keep the internal state of the PRNG. used to keep the internal state of the PRNG.
Then, each time a new pseudo-random integer between 0 and 15 Then, each time a new pseudo-random integer between 0 and 15
inclusive (4-bit pseudo-random integer) is needed, the following inclusive (4-bit pseudo-random integer) is needed, the following
function is used: function is used:
uint32_t tinymt32_rand16 (tinymt32_t * s); uint32_t tinymt32_rand16 (tinymt32_t * s);
This function takes as parameter a pointer to the same tinymt32_t This function takes as parameter a pointer to the same tinymt32_t
structure (that needs to be left unchanged between successive calls structure (that is left unchanged between successive calls to the
to the function). Similarly, each time a new pseudo-random integer function).
between 0 and 255 inclusive (8-bit pseudo-random integer) is needed,
the following function is used: Similarly, each time a new pseudo-random integer between 0 and 255
inclusive (8-bit pseudo-random integer) is needed, the following
function is used:
uint32_t tinymt32_rand256 (tinymt32_t * s); uint32_t tinymt32_rand256 (tinymt32_t * s);
These two functions keep respectively the 4 or 8 less significant These two functions keep respectively the 4 or 8 less significant
bits of the 32-bit pseudo-random number generated by the bits of the 32-bit pseudo-random number generated by the
tinymt32_generate_uint32() TinyMT32 function. Test results discussed tinymt32_generate_uint32() function of [tinymt32]. Test results
in Appendix B show that this simple technique, applied to this PRNG, discussed in Appendix B show that this simple technique, applied to
is in line with the RLC FEC Schemes needs. this PRNG, is in line with the RLC FEC Schemes needs.
The TinyMT32 PRNG reference implementation is reproduced in Figure 2,
with the following differences with respect to the original source
code:
o the source code initially spread over the tinymt32.h and
tinymt32.c files has been merged;
o the unused parts of the original source code have been removed;
o the unused constants TINYMT32_MEXP and TINYMT32_MUL have been
removed;
o the appropriate parameter set has been added to the initialization
function;
o the function order has been changed;
o certain internal variables have been renamed for compactness
purposes;
o the constant definitions use the const qualifier;
o the tinymt32_rand16() and tinymt32_rand256() functions have been
added in order to scale the initial 32-bit value over a smaller
interval;
o the IETF Trusteed copyright has been added to this derived work.
<CODE BEGINS> <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 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.
*/
/**
* The derived work of this document is:
* Copyright (c) 2018 IETF Trust and the persons identified as the
* document authors. All rights reserved.
*/
#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 uint32_t tinymt32_generate_uint32 (tinymt32_t * s);
/**
* Parameter set to use for the IETF RLC FEC Schemes specification.
* Do not change.
* This parameter set is the first entry of the precalculated
* parameter sets in file tinymt32dc.0.1048576.txt, by Kenji
* Rikitake, available at:
* https://github.com/jj1bdx/tinymtdc-longbatch/blob/master/
* tinymt32dc/tinymt32dc.0.1048576.txt
* It is also the parameter set used:
* Rikitake, K., "TinyMT Pseudo Random Number Generator for
* Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
* 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);
/**
* This function initializes the internal state array with a 32-bit
* unsigned integer seed.
* @param s pointer to tinymt internal state.
* @param seed a 32-bit unsigned integer used as a seed.
*/
void tinymt32_init (tinymt32_t * s, uint32_t seed)
{
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 (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 a pseudo-random integer in [0 .. 15] range. * This function outputs a pseudo-random integer in [0 .. 15] range.
* *
* @param s pointer to tinymt internal state. * @param s pointer to tinymt internal state.
* @return unsigned integer between 0 and 15 inclusive. * @return unsigned integer between 0 and 15 inclusive.
*/ */
uint32_t tinymt32_rand16(tinymt32_t *s) uint32_t tinymt32_rand16(tinymt32_t *s)
{ {
return (tinymt32_generate_uint32(s) & 0xF); return (tinymt32_generate_uint32(s) & 0xF);
} }
/** /**
* This function outputs a pseudo-random integer in [0 .. 255] range. * This function outputs a pseudo-random integer in [0 .. 255] range.
* *
* @param s pointer to tinymt internal state. * @param s pointer to tinymt internal state.
* @return unsigned integer between 0 and 255 inclusive. * @return unsigned integer between 0 and 255 inclusive.
*/ */
uint32_t tinymt32_rand256(tinymt32_t *s) uint32_t tinymt32_rand256(tinymt32_t *s)
{ {
return (tinymt32_generate_uint32(s) & 0xFF); return (tinymt32_generate_uint32(s) & 0xFF);
} }
/**
* Internal tinymt32 constants and functions.
* 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);
/**
* 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 from internal state.
* @param s pointer 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 32-bit unsigned integer from internal state.
* @param s pointer to 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> <CODE ENDS>
Figure 2: TinyMT32 Reference Implementation Figure 2: 4-bit and 8-bit mapping functions for TinyMT32
In addition to that, any implementation of this TinyMT32 PRNG MUST
fulfill three validation criteria detailed in Appendix A. These
criteria consist in several random number sequences that MUST be
matched. The first criteria focusses on the internal TinyMT32
unsigned 32-bit integer generator, the two others include the mapping
to 4-bit and 8-bit intervals.
Finally, the deterministic behavior of the implementation of Figure 2 Any implementation of this PRNG MUST fulfil three validation
has been checked across several platforms, from high-end 64-bit Mac criteria, the one described in [tinymt32] (for the TinyMT32 32-bit
OSX and Linux/Ubuntu laptops, to various low-end embedded cards based unsigned integer generator) and the two ones detailed in Appendix A
on 32-bit, 16-bit and 8-bit microcontrollers running RIOT (for the mapping to 4-bit and 8-bit intervals). Because of the way
[Baccelli18] (details in Appendix A). the mapping functions work, it is unlikely that an implementation
that fulfils the first criteria fails to fulfil the two additional
ones.
3.6. Coding Coefficients Generation Function 3.6. Coding Coefficients Generation Function
The coding coefficients, used during the encoding process, are The coding coefficients, used during the encoding process, are
generated at the RLC encoder by the generate_coding_coefficients() generated at the RLC encoder by the generate_coding_coefficients()
function each time a new repair symbol needs to be produced. The function each time a new repair symbol needs to be produced. The
fraction of coefficients that are non zero (i.e., the density) is fraction of coefficients that are non zero (i.e., the density) is
controlled by the DT (Density Threshold) parameter. DT has values controlled by the DT (Density Threshold) parameter. DT has values
between 0 (the minimum value) and 15 (the maximum value), and the between 0 (the minimum value) and 15 (the maximum value), and the
average probability of having a non zero coefficient equals (DT + 1) average probability of having a non zero coefficient equals (DT + 1)
skipping to change at page 32, line 14 skipping to change at page 28, line 5
[RFC6364] Begen, A., "Session Description Protocol Elements for the [RFC6364] Begen, A., "Session Description Protocol Elements for the
Forward Error Correction (FEC) Framework", RFC 6364, Forward Error Correction (FEC) Framework", RFC 6364,
DOI 10.17487/RFC6364, October 2011, DOI 10.17487/RFC6364, October 2011,
<https://www.rfc-editor.org/info/rfc6364>. <https://www.rfc-editor.org/info/rfc6364>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
12.2. Informative References [tinymt32]
Saito, M., Matsumoto, M., Roca, V., and E. Baccelli,
[Baccelli18] "TinyMT32 PRNG">TinyMT32 Pseudo Random Number Generator",
Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P., Transport Area Working Group (TSVWG) draft-roca-tsvwg-
Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and tinymt32 (Work in Progress), February 2019,
M. Wahlisch, "RIOT: An Open Source Operating System for <https://tools.ietf.org/html/draft-roca-tsvwg-tinymt32>.
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 12.2. Informative References
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 [PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete
Treatment of Software Implementations of Finite Field Treatment of Software Implementations of Finite Field
Arithmetic for Erasure Coding Applications", University of Arithmetic for Erasure Coding Applications", University of
Tennessee Technical Report UT-CS-13-717, Tennessee Technical Report UT-CS-13-717,
http://web.eecs.utk.edu/~plank/plank/papers/ http://web.eecs.utk.edu/~plank/plank/papers/
UT-CS-13-717.html, October 2013, UT-CS-13-717.html, October 2013,
<http://web.eecs.utk.edu/~plank/plank/papers/ <http://web.eecs.utk.edu/~plank/plank/papers/
UT-CS-13-717.html>. UT-CS-13-717.html>.
skipping to change at page 34, line 11 skipping to change at page 30, line 11
Communications (WiMob17), October Communications (WiMob17), October
2017 https://hal.inria.fr/hal-01571609v1/en/, October 2017 https://hal.inria.fr/hal-01571609v1/en/, October
2017, <https://hal.inria.fr/hal-01571609v1/en/>. 2017, <https://hal.inria.fr/hal-01571609v1/en/>.
Appendix A. TinyMT32 Validation Criteria (Normative) Appendix A. TinyMT32 Validation Criteria (Normative)
PRNG determinism, for a given seed, is a requirement. Consequently, PRNG determinism, for a given seed, is a requirement. Consequently,
in order to validate an implementation of the TinyMT32 PRNG, the in order to validate an implementation of the TinyMT32 PRNG, the
following criterias MUST be met. following criterias MUST be met.
The first criteria focusses on the core TinyMT32 PRNG, that produces The first criteria focusses on the tinymt32_rand256(), where the
32-bit pseudo-random numbers. Using a seed value of 1, the first 50
values returned by: tinymt32_generate_uint32(s) as 32-bit unsigned
integers MUST be equal to values provided in Figure 9. Note that
these values come from the tinymt/check32.out.txt file provided by
the authors to 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 seed
value of 1.
The second criteria focusses on the tinymt32_rand256(), where the
32-bit integer of the core TinyMT32 PRNG is scaled down to an 8-bit 32-bit integer of the core TinyMT32 PRNG is scaled down to an 8-bit
integer. Using a seed value of 1, the first 50 values returned by: integer. Using a seed value of 1, the first 50 values returned by:
tinymt32_rand256() as 8-bit unsigned integers MUST be equal to values tinymt32_rand256() as 8-bit unsigned integers MUST be equal to values
provided in Figure 10. provided in Figure 9.
37 225 177 176 21 37 225 177 176 21
246 54 139 168 237 246 54 139 168 237
211 187 62 190 104 211 187 62 190 104
135 210 99 176 11 135 210 99 176 11
207 35 40 113 179 207 35 40 113 179
214 254 101 212 211 214 254 101 212 211
226 41 234 232 203 226 41 234 232 203
29 194 211 112 107 29 194 211 112 107
217 104 197 135 23 217 104 197 135 23
89 210 252 109 166 89 210 252 109 166
Figure 10: First 50 decimal values returned by tinymt32_rand256() as Figure 9: First 50 decimal values returned by tinymt32_rand256() as
8-bit unsigned integers, with a seed value of 1. 8-bit unsigned integers, with a seed value of 1.
The third criteria focusses on the tinymt32_rand16(), where the The second criteria focusses on the tinymt32_rand16(), where the
32-bit integer of the core TinyMT32 PRNG is scaled down to a 4-bit 32-bit integer of the core TinyMT32 PRNG is scaled down to a 4-bit
integer. Using a seed value of 1, the first 50 values returned by: integer. Using a seed value of 1, the first 50 values returned by:
tinymt32_rand16() as 4-bit unsigned integers MUST be equal to values tinymt32_rand16() as 4-bit unsigned integers MUST be equal to values
provided in Figure 11. provided in Figure 10.
5 1 1 0 5 5 1 1 0 5
6 6 11 8 13 6 6 11 8 13
3 11 14 14 8 3 11 14 14 8
7 2 3 0 11 7 2 3 0 11
15 3 8 1 3 15 3 8 1 3
6 14 5 4 3 6 14 5 4 3
2 9 10 8 11 2 9 10 8 11
13 2 3 0 11 13 2 3 0 11
9 8 5 7 7 9 8 5 7 7
9 2 12 13 6 9 2 12 13 6
Figure 11: First 50 decimal values returned by tinymt32_rand16() as Figure 10: First 50 decimal values returned by tinymt32_rand16() as
4-bit unsigned integers, with a seed value of 1. 4-bit unsigned integers, with a seed value of 1.
The deterministic behavior of the implementation of Figure 2 has been
checked across several platforms: high-end laptops running 64-bits
Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM Cortex-A15
and 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 PRNG Adequacy (Informational) Appendix B. Assessing the PRNG Adequacy (Informational)
This annex discusses the adequacy of the TinyMT32 PRNG and the This annex discusses the adequacy of the TinyMT32 PRNG and the
tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC
Schemes. The goal is to assess the adequacy of these two functions Schemes. The goal is to assess the adequacy of these two functions
in producing coding coefficients that are sufficiently different from in producing coding coefficients that are sufficiently different from
one another, across various repair symbols with repair key values in one another, across various repair symbols with repair key values in
sequence (we can expect this approach to be commonly used by sequence (we can expect this approach to be commonly used by
implementers Section 6.1). This section is purely informational and implementers Section 6.1). This section is purely informational and
does not claim to be a solid evaluation. does not claim to be a solid evaluation.
The two RLC FEC Schemes use the PRNG to produce pseudo-random coding The two RLC FEC Schemes use the PRNG to produce pseudo-random coding
coefficients (Section 3.6), each time a new repair symbol is needed. coefficients (Section 3.6), each time a new repair symbol is needed.
A different repair key is used for each repair symbol, usually by A different repair key is used for each repair symbol, usually by
incrementing the repair key value (Section 6.1). For each repair incrementing the repair key value (Section 6.1). For each repair
symbol, a limited number of pseudo-random numbers is needed, symbol, a limited number of pseudo-random numbers is needed,
depending on the DT and encoding window size (Section 3.6), using depending on the DT and encoding window size (Section 3.6), using
either tinymt32_rand16() or tinymt32_rand256(). Therefore we are either tinymt32_rand16() or tinymt32_rand256(). Therefore we are
more interested in the randomness of small sequences of random more interested in the randomness of small sequences of random
numbers mapped to 4-bit or 8-bit integers, than in the randomness of numbers mapped to 4-bit or 8-bit integers, than in the randomness of
a very large sequence of random nmbers which is not representative of a very large sequence of random numbers which is not representative
the usage of the PRNG. of the usage of the PRNG.
Evaluation of tinymt32_rand16(): We first generate a huge number Evaluation of tinymt32_rand16(): We first generate a huge number
(1,000,000,000) of small sequences (20 pseudo-random numbers per (1,000,000,000) of small sequences (20 pseudo-random numbers per
sequence), and perform statistics on the number of occurrences of sequence), and perform statistics on the number of occurrences of
each of the 16 possible values across all sequences. each of the 16 possible values across all sequences.
value occurrences percentage (%) (total of 20000000000) value occurrences percentage (%) (total of 20000000000)
0 1250036799 6.2502 0 1250036799 6.2502
1 1249995831 6.2500 1 1249995831 6.2500
2 1250038674 6.2502 2 1250038674 6.2502
skipping to change at page 36, line 32 skipping to change at page 32, line 23
7 1250020363 6.2501 7 1250020363 6.2501
8 1249995276 6.2500 8 1249995276 6.2500
9 1249982856 6.2499 9 1249982856 6.2499
10 1249984111 6.2499 10 1249984111 6.2499
11 1250009551 6.2500 11 1250009551 6.2500
12 1249955768 6.2498 12 1249955768 6.2498
13 1249994654 6.2500 13 1249994654 6.2500
14 1250000569 6.2500 14 1250000569 6.2500
15 1249978831 6.2499 15 1249978831 6.2499
Figure 12: tinymt32_rand16(): occurrence statistics across a huge Figure 11: tinymt32_rand16(): occurrence statistics across a huge
number (1,000,000,000) of small sequences (20 pseudo-random numbers number (1,000,000,000) of small sequences (20 pseudo-random numbers
per sequence), with 0 as the first PRNG seed. per sequence), with 0 as the first PRNG seed.
The results (Figure 12) show that all possible values are almost The results (Figure 11) show that all possible values are almost
equally represented, or said differently, that the tinymt32_rand16() equally represented, or said differently, that the tinymt32_rand16()
output converges to a uniform distribution where each of the 16 output converges to a uniform distribution where each of the 16
possible value would appear exactly 1 / 16 * 100 = 6.25% of times. possible value would appear exactly 1 / 16 * 100 = 6.25% of times.
Other types of biases may exist that may be visible with smaller Other types of biases may exist that may be visible with smaller
tests (e.g., to evaluation the convergence speed to a uniform tests (e.g., to evaluation the convergence speed to a uniform
distribution). We therefore perform 200 tests, each of them distribution). We therefore perform 200 tests, each of them
consisting in producing 200 sequences, keeping ony the first value of consisting in producing 200 sequences, keeping only the first value
each sequence. We use non overlapping repair keys for each sequence, of each sequence. We use non overlapping repair keys for each
starting with value 0 and increasing it after each use. sequence, starting with value 0 and increasing it after each use.
value min occurrences max occurrences average occurrences value min occurrences max occurrences average occurrences
0 4 21 6.3675 0 4 21 6.3675
1 4 22 6.0200 1 4 22 6.0200
2 4 20 6.3125 2 4 20 6.3125
3 5 23 6.1775 3 5 23 6.1775
4 5 24 6.1000 4 5 24 6.1000
5 4 21 6.5925 5 4 21 6.5925
6 5 30 6.3075 6 5 30 6.3075
7 6 22 6.2225 7 6 22 6.2225
8 5 26 6.1750 8 5 26 6.1750
9 3 21 5.9425 9 3 21 5.9425
10 5 24 6.3175 10 5 24 6.3175
11 4 22 6.4300 11 4 22 6.4300
12 5 21 6.1600 12 5 21 6.1600
13 5 22 6.3100 13 5 22 6.3100
14 4 26 6.3950 14 4 26 6.3950
15 4 21 6.1700 15 4 21 6.1700
Figure 13: tinymt32_rand16(): occurrence statistics across 200 tests, Figure 12: tinymt32_rand16(): occurrence statistics across 200 tests,
each of them consisting in 200 sequences of 1 pseudo-random number each of them consisting in 200 sequences of 1 pseudo-random number
each, with non overlapping PRNG seeds in sequence starting from 0. each, with non overlapping PRNG seeds in sequence starting from 0.
Figure 13 shows across all 200 tests, for each of the 16 possible Figure 12 shows across all 200 tests, for each of the 16 possible
pseudo-random number values, the minimum (resp. maximum) number of pseudo-random number values, the minimum (resp. maximum) number of
times it appeared in a tests, as well as the average number of times it appeared in a tests, as well as the average number of
occurrences across the 200 tests. Although the distribution is not occurrences across the 200 tests. Although the distribution is not
perfect, there is no major bias. On the opposite, in the same perfect, there is no major bias. On the opposite, in the same
conditions, the Park Miller linear congruential PRNG of [RFC5170] conditions, the Park Miller linear congruential PRNG of [RFC5170]
with a result scaled down to 4-bit values, using seeds in sequence with a result scaled down to 4-bit values, using seeds in sequence
starting from 1, returns systematically 0 as the first value during starting from 1, returns systematically 0 as the first value during
some time, then after a certain repair key value threshold, it some time, then after a certain repair key value threshold, it
systematically returns 1, etc. systematically returns 1, etc.
skipping to change at page 42, line 30 skipping to change at page 38, line 30
lost ADUs will be recovered without relying on this optimization. lost ADUs will be recovered without relying on this optimization.
ls_max_size ls_max_size
/---------------------------------^-------------------------------\ /---------------------------------^-------------------------------\
late source symbols late source symbols
(pot. decoded but not delivered) dw_max_size (pot. decoded but not delivered) dw_max_size
/--------------^-----------------\ /--------------^---------------\ /--------------^-----------------\ /--------------^---------------\
src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12
Figure 14: Relationship between parameters to decode beyond maximum Figure 13: Relationship between parameters to decode beyond maximum
latency. latency.
It means that source symbols, and therefore ADUs, may be decoded even It means that source symbols, and therefore ADUs, may be decoded even
if the added latency exceeds the maximum value permitted by the if the added latency exceeds the maximum value permitted by the
application (the "late source symbols" of Figure 14). It follows application (the "late source symbols" of Figure 13). It follows
that the corresponding ADUs will not be useful to the application. that the corresponding ADUs will not be useful to the application.
However, decoding these "late symbols" significantly improves the However, decoding these "late symbols" significantly improves the
global robustness in bad reception conditions and is therefore global robustness in bad reception conditions and is therefore
recommended for receivers experiencing bad communication conditions recommended for receivers experiencing bad communication conditions
[Roca16]. In any case whether or not to use this optimization and [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 what exact value to use for the ls_max_size parameter are local
decisions made by each receiver independently, without any impact on decisions made by each receiver independently, without any impact on
the other receivers nor on the source. the other receivers nor on the source.
Authors' Addresses Authors' Addresses
skipping to change at page 43, line 10 skipping to change at line 1737
Univ. Grenoble Alpes Univ. Grenoble Alpes
France France
EMail: vincent.roca@inria.fr EMail: vincent.roca@inria.fr
Belkacem Teibi Belkacem Teibi
INRIA INRIA
Univ. Grenoble Alpes Univ. Grenoble Alpes
France France
EMail: belkacem.teibi@gmail.com EMail: belkacem.teibi@gmail.com
Emmanuel Baccelli
INRIA
France
EMail: emmanuel.baccelli@inria.fr
 End of changes. 37 change blocks. 
341 lines changed or deleted 93 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/