draft-ietf-tsvwg-rlc-fec-scheme-13.txt | draft-ietf-tsvwg-rlc-fec-scheme-14.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: September 6, 2019 March 5, 2019 | Expires: November 28, 2019 May 27, 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-13 | draft-ietf-tsvwg-rlc-fec-scheme-14 | |||

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 September 6, 2019. | This Internet-Draft will expire on November 28, 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 4 ¶ | skipping to change at page 12, line 4 ¶ | |||

function). | function). | |||

Similarly, each time a new pseudo-random integer between 0 and 255 | Similarly, each time a new pseudo-random integer between 0 and 255 | |||

inclusive (8-bit pseudo-random integer) is needed, the following | inclusive (8-bit pseudo-random integer) is needed, the following | |||

function is used: | 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() function of [tinymt32]. Test results | tinymt32_generate_uint32() function of [tinymt32]. This is done by | |||

discussed in Appendix B show that this simple technique, applied to | computing the result of a binary AND between the | |||

this PRNG, is in line with the RLC FEC Schemes needs. | tinymt32_generate_uint32() output and respectively the 0xF or 0xFF | |||

constants, using 32-bit unsigned integer operations. Figure 2 shows | ||||

a possible implementation. Test results discussed in Appendix B show | ||||

that this simple technique, applied to this PRNG, is in line with the | ||||

RLC FEC Schemes needs. | ||||

<CODE BEGINS> | <CODE BEGINS> | |||

/** | /** | |||

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

{ | { | |||

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

Figure 12: 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 12 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 test, as well as the average number of | times it appeared in a test, 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. | |||

Evaluation of tinymt32_rand256(): The same approach is used here. | Evaluation of tinymt32_rand256(): The same approach is used here. | |||

Results (not shown) are similar: occurrences vary between 7,810,3368 | Results (not shown) are similar: occurrences vary between 7,810,3368 | |||

(i.e., 0.3905%) and 7,814,7952 (i.e., 0.3907%). Here also we see a | (i.e., 0.3905%) and 7,814,7952 (i.e., 0.3907%). Here also we see a | |||

convergence to the theoretical uniform distribution where each of the | convergence to the theoretical uniform distribution where each of the | |||

256 possible values would appear exactly 1 / 256 * 100 = 0.390625% of | 256 possible values would appear exactly 1 / 256 * 100 = 0.390625% of | |||

End of changes. 5 change blocks. | ||||

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