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/