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