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