draft-ietf-tsvwg-rlc-fec-scheme-11.txt | draft-ietf-tsvwg-rlc-fec-scheme-12.txt | |||
---|---|---|---|---|

TSVWG V. Roca | TSVWG V. Roca | |||

Internet-Draft B. Teibi | Internet-Draft B. Teibi | |||

Intended status: Standards Track INRIA | Intended status: Standards Track INRIA | |||

Expires: August 5, 2019 February 1, 2019 | Expires: August 15, 2019 February 11, 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-11 | draft-ietf-tsvwg-rlc-fec-scheme-12 | |||

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 43 ¶ | 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 August 5, 2019. | This Internet-Draft will expire on August 15, 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 12, line 34 ¶ | skipping to change at page 12, line 34 ¶ | |||

* @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); | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

Figure 2: 4-bit and 8-bit mapping functions for TinyMT32 | Figure 2: 4-bit and 8-bit mapping functions for TinyMT32 | |||

Any implementation of this PRNG MUST fulfil three validation | Any implementation of this PRNG MUST fulfill three validation | |||

criteria, the one described in [tinymt32] (for the TinyMT32 32-bit | criteria: the one described in [tinymt32] (for the TinyMT32 32-bit | |||

unsigned integer generator) and the two ones detailed in Appendix A | unsigned integer generator), and the two others detailed in | |||

(for the mapping to 4-bit and 8-bit intervals). Because of the way | Appendix A (for the mapping to 4-bit and 8-bit intervals). Because | |||

the mapping functions work, it is unlikely that an implementation | of the way the mapping functions work, it is unlikely that an | |||

that fulfils the first criteria fails to fulfil the two additional | implementation that fulfills the first criterion fails to fulfill the | |||

ones. | two others. | |||

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 27, line 11 ¶ | skipping to change at page 27, line 11 ¶ | |||

o XXXX refers to the Sliding Window Random Linear Codes (RLC) over | o XXXX refers to the Sliding Window Random Linear Codes (RLC) over | |||

GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in | GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in | |||

Section 4 of this document. | Section 4 of this document. | |||

11. Acknowledgments | 11. Acknowledgments | |||

The authors would like to thank the three TSVWG chairs, Wesley Eddy, | The authors would like to thank the three TSVWG chairs, Wesley Eddy, | |||

our shepherd, David Black and Gorry Fairhurst, as well as Spencer | our shepherd, David Black and Gorry Fairhurst, as well as Spencer | |||

Dawkins, our responsible AD, and all those who provided comments, | Dawkins, our responsible AD, and all those who provided comments, | |||

namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ | namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ | |||

Housley, Emmanuel Lochin, and Marie-Jose Montpetit. Last but not | Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner. | |||

least, the authors are really grateful to the IESG members, in | Last but not least, the authors are really grateful to the IESG | |||

particular Benjamin Kaduk, Mirja Kuhlewind, Eric Rescorla, and Adam | members, in particular Benjamin Kaduk, Mirja Kuhlewind, Eric | |||

Roach for their highly valuable feedbacks that greatly contributed to | Rescorla, and Adam Roach for their highly valuable feedbacks that | |||

improve this specification. | greatly contributed to improve this specification. | |||

12. References | 12. References | |||

12.1. Normative References | 12.1. Normative References | |||

[fecframe-ext] | [fecframe-ext] | |||

Roca, V. and A. Begen, "Forward Error Correction (FEC) | Roca, V. and A. Begen, "Forward Error Correction (FEC) | |||

Framework Extension to Sliding Window Codes", Transport | Framework Extension to Sliding Window Codes", Transport | |||

Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext | Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext | |||

(Work in Progress), January 2019, | (Work in Progress), January 2019, | |||

skipping to change at page 28, line 7 ¶ | skipping to change at page 28, line 7 ¶ | |||

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

[tinymt32] | [tinymt32] | |||

Saito, M., Matsumoto, M., Roca, V., and E. Baccelli, | Saito, M., Matsumoto, M., Roca, V., and E. Baccelli, | |||

"TinyMT32 PRNG">TinyMT32 Pseudo Random Number Generator", | "TinyMT32 Pseudo Random Number Generator (PRNG)", | |||

Transport Area Working Group (TSVWG) draft-roca-tsvwg- | Transport Area Working Group (TSVWG) draft-roca-tsvwg- | |||

tinymt32 (Work in Progress), February 2019, | tinymt32 (Work in Progress), February 2019, | |||

<https://tools.ietf.org/html/draft-roca-tsvwg-tinymt32>. | <https://tools.ietf.org/html/draft-roca-tsvwg-tinymt32>. | |||

12.2. Informative References | 12.2. Informative References | |||

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

skipping to change at page 30, line 9 ¶ | skipping to change at page 30, line 9 ¶ | |||

Case Study", 13th IEEE International Conference on | Case Study", 13th IEEE International Conference on | |||

Wireless and Mobile Computing, Networking and | Wireless and Mobile Computing, Networking and | |||

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 criteria MUST be met. | |||

The first criteria focusses on the tinymt32_rand256(), where the | The first criterion 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 9. | 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 9: 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 second criteria focusses on the tinymt32_rand16(), where the | The second criterion 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 10. | 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 | |||

skipping to change at page 31, line 13 ¶ | skipping to change at page 31, line 13 ¶ | |||

4-bit unsigned integers, with a seed value of 1. | 4-bit unsigned integers, with a seed value of 1. | |||

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, see Section 6.1). This section is purely informational | |||

does not claim to be a solid evaluation. | and 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 | |||

skipping to change at page 32, line 33 ¶ | skipping to change at page 32, line 33 ¶ | |||

Figure 11: 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 11) 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, for instance to evaluate 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 only the first value | consisting in producing 200 sequences, keeping only the first value | |||

of each sequence. We use non overlapping repair keys for each | of each sequence. We use non overlapping repair keys for each | |||

sequence, 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 | |||

End of changes. 11 change blocks. | ||||

23 lines changed or deleted | | 23 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/ |