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/ |