draft-ietf-tsvwg-rlc-fec-scheme-12.txt   draft-ietf-tsvwg-rlc-fec-scheme-13.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 15, 2019 February 11, 2019 Expires: September 6, 2019 March 5, 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-12 draft-ietf-tsvwg-rlc-fec-scheme-13
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 15, 2019. This Internet-Draft will expire on September 6, 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 8, line 11 skipping to change at page 8, line 11
as the latency budget permitted for all FEC-related operations. as the latency budget permitted for all FEC-related operations.
This is an input parameter that enables a FECFRAME sender to This is an input parameter that enables a FECFRAME sender to
derive other internal parameters (see Appendix C); derive other internal parameters (see Appendix C);
Encoding window current (resp. maximum) size, ew_size (resp. Encoding window current (resp. maximum) size, ew_size (resp.
ew_max_size) (in symbols): ew_max_size) (in symbols):
at a FECFRAME sender, during FEC encoding, a repair symbol is at a FECFRAME sender, during FEC encoding, a repair symbol is
computed as a linear combination of the ew_size source symbols computed as a linear combination of the ew_size source symbols
present in the encoding window. The ew_max_size is the maximum present in the encoding window. The ew_max_size is the maximum
size of this window, while ew_size is the current size. For size of this window, while ew_size is the current size. For
instance, at session start, upon receiving new source ADUs, the example, in the common case at session start, upon receiving new
ew_size progressively increases until it reaches its maximum source ADUs, the ew_size progressively increases until it reaches
value, ew_max_size. We have: its maximum value, ew_max_size. We have:
0 < ew_size <= ew_max_size 0 < ew_size <= ew_max_size
Decoding window maximum size, dw_max_size (in symbols): at a Decoding window maximum size, dw_max_size (in symbols): at a
FECFRAME receiver, dw_max_size is the maximum number of received FECFRAME receiver, dw_max_size is the maximum number of received
or lost source symbols that are still within their latency budget; or lost source symbols that are still within their latency budget;
Linear system maximum size, ls_max_size (in symbols): at a FECFRAME Linear system maximum size, ls_max_size (in symbols): at a FECFRAME
receiver, the linear system maximum size, ls_max_size, is the receiver, the linear system maximum size, ls_max_size, is the
maximum number of received or lost source symbols in the linear maximum number of received or lost source symbols in the linear
system (i.e., the variables). It SHOULD NOT be smaller than system (i.e., the variables). It SHOULD NOT be smaller than
dw_max_size since it would mean that, even after receiving a dw_max_size since it would mean that, even after receiving a
skipping to change at page 32, line 30 skipping to change at page 32, line 30
14 1250000569 6.2500 14 1250000569 6.2500
15 1249978831 6.2499 15 1249978831 6.2499
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 values 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, 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
skipping to change at page 33, line 29 skipping to change at page 33, line 29
13 5 22 6.3100 13 5 22 6.3100
14 4 26 6.3950 14 4 26 6.3950
15 4 21 6.1700 15 4 21 6.1700
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 tests, 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
possible value would appear exactly 1 / 256 * 100 = 0.390625% of 256 possible values would appear exactly 1 / 256 * 100 = 0.390625% of
times. times.
Appendix C. Possible Parameter Derivation (Informational) Appendix C. Possible Parameter Derivation (Informational)
Section 3.1 defines several parameters to control the encoder or Section 3.1 defines several parameters to control the encoder or
decoder. This annex proposes techniques to derive these parameters decoder. This annex proposes techniques to derive these parameters
according to the target use-case. This annex is informational, in according to the target use-case. This annex is informational, in
the sense that using a different derivation technique will not the sense that using a different derivation technique will not
prevent the encoder and decoder to interoperate: a decoder can still prevent the encoder and decoder to interoperate: a decoder can still
recover an erased source symbol without any error. However, in case recover an erased source symbol without any error. However, in case
 End of changes. 7 change blocks. 
9 lines changed or deleted 9 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/