< draft-ietf-tsvwg-rlc-fec-scheme-15.txt | draft-ietf-tsvwg-rlc-fec-scheme-16.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: December 20, 2019 June 18, 2019 | Expires: December 20, 2019 June 18, 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-15 | draft-ietf-tsvwg-rlc-fec-scheme-16 | |||

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. These sliding window FEC codes | extended to sliding window FEC codes. These sliding window FEC codes | |||

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

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 numbers which is not representative | a very large sequence of random numbers which is not representative | |||

of 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), increasing the seed value for each sequence, and perform | |||

each of the 16 possible values across all sequences. | statistics on the number of occurrences of each of the 16 possible | |||

values across all sequences. In this first test we consider 32-bit | ||||

seed values in order to assess the PRNG quality after output | ||||

truncation to 4 bits. | ||||

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

3 1250000881 6.2500 | 3 1250000881 6.2500 | |||

4 1250023929 6.2501 | 4 1250023929 6.2501 | |||

5 1249986320 6.2499 | 5 1249986320 6.2499 | |||

6 1249995587 6.2500 | 6 1249995587 6.2500 | |||

7 1250020363 6.2501 | 7 1250020363 6.2501 | |||

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

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 values would appear exactly 1 / 16 * 100 = 6.25% of times. | possible values would appear exactly 1 / 16 * 100 = 6.25% of times. | |||

Since the RLC FEC Schemes use of this PRNG will be limited to 16-bit | ||||

seed values, we carried out the same test for the first 2^^16 seed | ||||

values only. The distribution (not shown) is of course less uniform, | ||||

with value occurences ranging between 6.2121% (i.e., 81,423 | ||||

occurences out of a total of 65536*20=1,310,720) and 6.2948% (i.e., | ||||

82,507 occurences). However, we do not believe it significantly | ||||

impacts the RLC FEC Scheme behavior. | ||||

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, for instance to evaluate 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 | |||

End of changes. 3 change blocks. | ||||

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