--- 1/draft-ietf-tsvwg-rlc-fec-scheme-11.txt 2019-02-11 04:13:26.830241882 -0800 +++ 2/draft-ietf-tsvwg-rlc-fec-scheme-12.txt 2019-02-11 04:13:26.910243807 -0800 @@ -1,19 +1,19 @@ TSVWG V. Roca Internet-Draft B. Teibi 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) Schemes for FECFRAME - draft-ietf-tsvwg-rlc-fec-scheme-11 + draft-ietf-tsvwg-rlc-fec-scheme-12 Abstract This document describes two fully-specified Forward Erasure Correction (FEC) Schemes for Sliding Window Random Linear Codes (RLC), one for RLC over the Galois Field (A.K.A. Finite Field) GF(2), a second one for RLC over the Galois Field GF(2^^8), each time with the possibility of controlling the code density. They can protect arbitrary media streams along the lines defined by FECFRAME extended to sliding window FEC codes, as defined in [fecframe-ext]. @@ -32,21 +32,21 @@ Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." - This Internet-Draft will expire on August 5, 2019. + This Internet-Draft will expire on August 15, 2019. Copyright Notice Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents @@ -539,27 +539,27 @@ * @return unsigned integer between 0 and 255 inclusive. */ uint32_t tinymt32_rand256(tinymt32_t *s) { return (tinymt32_generate_uint32(s) & 0xFF); } Figure 2: 4-bit and 8-bit mapping functions for TinyMT32 - Any implementation of this PRNG MUST fulfil three validation - criteria, the one described in [tinymt32] (for the TinyMT32 32-bit - unsigned integer generator) and the two ones detailed in Appendix A - (for the mapping to 4-bit and 8-bit intervals). Because of the way - the mapping functions work, it is unlikely that an implementation - that fulfils the first criteria fails to fulfil the two additional - ones. + Any implementation of this PRNG MUST fulfill three validation + criteria: the one described in [tinymt32] (for the TinyMT32 32-bit + unsigned integer generator), and the two others detailed in + Appendix A (for the mapping to 4-bit and 8-bit intervals). Because + of the way the mapping functions work, it is unlikely that an + implementation that fulfills the first criterion fails to fulfill the + two others. 3.6. Coding Coefficients Generation Function The coding coefficients, used during the encoding process, are generated at the RLC encoder by the generate_coding_coefficients() function each time a new repair symbol needs to be produced. The fraction of coefficients that are non zero (i.e., the density) is controlled by the DT (Density Threshold) parameter. DT has values between 0 (the minimum value) and 15 (the maximum value), and the average probability of having a non zero coefficient equals (DT + 1) @@ -1219,25 +1219,25 @@ o XXXX refers to the Sliding Window Random Linear Codes (RLC) over GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in Section 4 of this document. 11. Acknowledgments The authors would like to thank the three TSVWG chairs, Wesley Eddy, our shepherd, David Black and Gorry Fairhurst, as well as Spencer Dawkins, our responsible AD, and all those who provided comments, namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ - Housley, Emmanuel Lochin, and Marie-Jose Montpetit. Last but not - least, the authors are really grateful to the IESG members, in - particular Benjamin Kaduk, Mirja Kuhlewind, Eric Rescorla, and Adam - Roach for their highly valuable feedbacks that greatly contributed to - improve this specification. + Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner. + Last but not least, the authors are really grateful to the IESG + members, in particular Benjamin Kaduk, Mirja Kuhlewind, Eric + Rescorla, and Adam Roach for their highly valuable feedbacks that + greatly contributed to improve this specification. 12. References 12.1. Normative References [fecframe-ext] Roca, V. and A. Begen, "Forward Error Correction (FEC) Framework Extension to Sliding Window Codes", Transport Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext (Work in Progress), January 2019, @@ -1258,21 +1258,21 @@ Forward Error Correction (FEC) Framework", RFC 6364, DOI 10.17487/RFC6364, October 2011, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [tinymt32] 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- tinymt32 (Work in Progress), February 2019, . 12.2. Informative References [PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete Treatment of Software Implementations of Finite Field Arithmetic for Erasure Coding Applications", University of Tennessee Technical Report UT-CS-13-717, @@ -1328,43 +1328,43 @@ Case Study", 13th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob17), October 2017 https://hal.inria.fr/hal-01571609v1/en/, October 2017, . Appendix A. TinyMT32 Validation Criteria (Normative) PRNG determinism, for a given seed, is a requirement. Consequently, 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 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 provided in Figure 9. 37 225 177 176 21 246 54 139 168 237 211 187 62 190 104 135 210 99 176 11 207 35 40 113 179 214 254 101 212 211 226 41 234 232 203 29 194 211 112 107 217 104 197 135 23 89 210 252 109 166 Figure 9: First 50 decimal values returned by tinymt32_rand256() as 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 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 provided in Figure 10. 5 1 1 0 5 6 6 11 8 13 3 11 14 14 8 7 2 3 0 11 15 3 8 1 3 @@ -1378,22 +1378,22 @@ 4-bit unsigned integers, with a seed value of 1. Appendix B. Assessing the PRNG Adequacy (Informational) This annex discusses the adequacy of the TinyMT32 PRNG and the tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC Schemes. The goal is to assess the adequacy of these two functions in producing coding coefficients that are sufficiently different from one another, across various repair symbols with repair key values in sequence (we can expect this approach to be commonly used by - implementers Section 6.1). This section is purely informational and - does not claim to be a solid evaluation. + implementers, see Section 6.1). This section is purely informational + and does not claim to be a solid evaluation. 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. A different repair key is used for each repair symbol, usually by incrementing the repair key value (Section 6.1). For each repair symbol, a limited number of pseudo-random numbers is needed, depending on the DT and encoding window size (Section 3.6), using either tinymt32_rand16() or tinymt32_rand256(). Therefore we are more interested in the randomness of small sequences of random numbers mapped to 4-bit or 8-bit integers, than in the randomness of @@ -1426,22 +1426,22 @@ Figure 11: tinymt32_rand16(): occurrence statistics across a huge number (1,000,000,000) of small sequences (20 pseudo-random numbers per sequence), with 0 as the first PRNG seed. The results (Figure 11) show that all possible values are almost equally represented, or said differently, that the tinymt32_rand16() output converges to a uniform distribution where each of the 16 possible value would appear exactly 1 / 16 * 100 = 6.25% of times. Other types of biases may exist that may be visible with smaller - tests (e.g., to evaluation the convergence speed to a uniform - distribution). We therefore perform 200 tests, each of them + tests, for instance to evaluate the convergence speed to a uniform + distribution. We therefore perform 200 tests, each of them consisting in producing 200 sequences, keeping only the first value of each sequence. We use non overlapping repair keys for each sequence, starting with value 0 and increasing it after each use. value min occurrences max occurrences average occurrences 0 4 21 6.3675 1 4 22 6.0200 2 4 20 6.3125 3 5 23 6.1775 4 5 24 6.1000