```
/**
* This function outputs a pseudo-random integer in [0 .. 15] range.
*
* @param s pointer to tinymt internal state.
* @return unsigned integer between 0 and 15 inclusive.
*/
@@ -543,59 +546,67 @@
* @return unsigned integer between 0 and 255 inclusive.
*/
uint32_t tinymt32_rand256(tinymt32_t *s)
{
return (tinymt32_generate_uint32(s) & 0xFF);
}
``````
Figure 2: 4-bit and 8-bit mapping functions for TinyMT32
- Any implementation of this PRNG MUST fulfill three validation
- criteria: the one described in [tinymt32] (for the TinyMT32 32-bit
- unsigned integer generator), and the two others detailed in
- Appendix A (for the mapping to 4-bit and 8-bit intervals). Because
- of the way the mapping functions work, it is unlikely that an
- implementation that fulfills the first criterion fails to fulfill the
- two others.
+ Any implementation of this PRNG MUST have the same output as that
+ provided by the reference implementation of [tinymt32]. In order to
+ increase the compliancy confidence, three criteria are proposed: the
+ one described in [tinymt32] (for the TinyMT32 32-bit unsigned integer
+ generator), and the two others detailed in Appendix A (for the
+ mapping to 4-bit and 8-bit intervals). Because of the way the
+ mapping functions work, it is unlikely that an implementation that
+ fulfills the first criterion fails to fulfill the two others.
3.6. Coding Coefficients Generation Function
The coding coefficients, used during the encoding process, are
generated at the RLC encoder by the generate_coding_coefficients()
function each time a new repair symbol needs to be produced. The
fraction of coefficients that are non zero (i.e., the density) is
controlled by the DT (Density Threshold) parameter. DT has values
between 0 (the minimum value) and 15 (the maximum value), and the
average probability of having a non zero coefficient equals (DT + 1)
/ 16. In particular, when DT equals 15 the function guaranties that
all coefficients are non zero (i.e., maximum density).
These considerations apply to both the RLC over GF(2) and RLC over
GF(2^^8), the only difference being the value of the m parameter.
With the RLC over GF(2) FEC Scheme (Section 5), m is equal to 1.
With RLC over GF(2^^8) FEC Scheme (Section 4), m is equal to 8.
+ Figure 3 shows the reference generate_coding_coefficients()
+ implementation. This is a C language implementation, written for C99
+ [C99].
+
``````
+ #include
```
+
/*
* Fills in the table of coding coefficients (of the right size)
* provided with the appropriate number of coding coefficients to
* use for the repair symbol key provided.
*
* (in) repair_key key associated to this repair symbol. This
* parameter is ignored (useless) if m=1 and dt=15
- * (in/out) cc_tab[] pointer to a table of the right size to store
+ * (in/out) cc_tab pointer to a table of the right size to store
* coding coefficients. All coefficients are
* stored as bytes, regardless of the m parameter,
* upon return of this function.
- * (in) cc_nb number of entries in the table. This value is
- * equal to the current encoding window size.
+ * (in) cc_nb number of entries in the cc_tab table. This
+ * value is equal to the current encoding window
+ * size.
* (in) dt integer between 0 and 15 (inclusive) that
* controls the density. With value 15, all
* coefficients are guaranteed to be non zero
* (i.e. equal to 1 with GF(2) and equal to a
* value in {1,... 255} with GF(2^^8)), otherwise
* a fraction of them will be 0.
* (in) m Finite Field GF(2^^m) parameter. In this
* document only values 1 and 8 are considered.
* (out) returns 0 in case of success, an error code
* different than 0 otherwise.
@@ -592,23 +603,24 @@
* (in) dt integer between 0 and 15 (inclusive) that
* controls the density. With value 15, all
* coefficients are guaranteed to be non zero
* (i.e. equal to 1 with GF(2) and equal to a
* value in {1,... 255} with GF(2^^8)), otherwise
* a fraction of them will be 0.
* (in) m Finite Field GF(2^^m) parameter. In this
* document only values 1 and 8 are considered.
* (out) returns 0 in case of success, an error code
* different than 0 otherwise.
+
*/
int generate_coding_coefficients (uint16_t repair_key,
- uint8_t cc_tab[],
+ uint8_t* cc_tab,
uint16_t cc_nb,
uint8_t dt,
uint8_t m)
{
uint32_t i;
tinymt32_t s; /* PRNG internal state */
if (dt > 15) {
return -1; /* error, bad dt parameter */
}
@@ -640,80 +652,81 @@
/* here a certain number of coefficients should be 0 */
for (i = 0 ; i < cc_nb ; i++) {
if (tinymt32_rand16(&s) <= dt) {
do {
cc_tab[i] = (uint8_t) tinymt32_rand256(&s);
} while (cc_tab[i] == 0);
} else {
cc_tab[i] = 0;
}
}
+
}
break;
default:
return -2; /* error, bad parameter m */
}
- return 0 /* success */
+ return 0; /* success */
}
```
Figure 3: Coding Coefficients Generation Function Reference
Implementation
3.7. Finite Fields Operations
3.7.1. Finite Field Definitions
The two RLC FEC Schemes specified in this document reuse the Finite
Fields defined in [RFC5510], section 8.1. More specifically, the
elements of the field GF(2^^m) are represented by polynomials with
binary coefficients (i.e., over GF(2)) and degree lower or equal to
m-1. The addition between two elements is defined as the addition of
binary polynomials in GF(2), which is equivalent to a bitwise XOR
operation on the binary representation of these elements.
With GF(2^^8), multiplication between two elements is the
multiplication modulo a given irreducible polynomial of degree 8.
- The following irreducible polynomial MUST be used for GF(2^^8):
+ The following irreducible polynomial is used for GF(2^^8):
x^^8 + x^^4 + x^^3 + x^^2 + 1
With GF(2), multiplication corresponds to a logical AND operation.
3.7.2. Linear Combination of Source Symbols Computation
The two RLC FEC Schemes require the computation of a linear
combination of source symbols, using the coding coefficients produced
by the generate_coding_coefficients() function and stored in the
cc_tab[] array.
With the RLC over GF(2^^8) FEC Scheme, a linear combination of the
ew_size source symbol present in the encoding window, say src_0 to
src_ew_size_1, in order to generate a repair symbol, is computed as
follows. For each byte of position i in each source and the repair
- symbol, where i belongs to {0; E-1}, compute:
+ symbol, where i belongs to [0; E-1], compute:
repair[i] = cc_tab[0] * src_0[i] XOR cc_tab[1] * src_1[i] XOR ...
XOR cc_tab[ew_size - 1] * src_ew_size_1[i]
where * is the multiplication over GF(2^^8). In practice various
optimizations need to be used in order to make this computation
efficient (see in particular [PGM13]).
With the RLC over GF(2) FEC Scheme (binary case), a linear
combination is computed as follows. The repair symbol is the XOR sum
of all the source symbols corresponding to a coding coefficient
cc_tab[j] equal to 1 (i.e., the source symbols corresponding to zero
coding coefficients are ignored). The XOR sum of the byte of
position i in each source is computed and stored in the corresponding
- byte of the repair symbol, where i belongs to {0; E-1}. In practice,
+ byte of the repair symbol, where i belongs to [0; E-1]. In practice,
the XOR sums will be computed several bytes at a time (e.g., on 64
bit words, or on arrays of 16 or more bytes when using SIMD CPU
extensions).
With both FEC Schemes, the details of how to optimize the computation
of these linear combinations are of high practical importance but out
of scope of this document.
4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary Packet
Flows
@@ -959,50 +973,54 @@
carried in the Repair FEC Payload ID. The FEC Repair Packet can then
be passed to the transport layer for transmission. The source versus
repair FEC packet transmission order is out of scope of this document
and several approaches exist that are implementation-specific.
Other solutions are possible to select a repair key value when a new
FEC Repair Packet is needed, for instance, by choosing a random
integer between 0 and 65535. However, selecting the same repair key
as before (which may happen in case of a random process) is only
meaningful if the encoding window has changed, otherwise the same FEC
- Repair Packet will be generated.
+ Repair Packet will be generated. In any case, choosing the repair
+ key is entirely at the discretion of the sender, since it is
+ communicated to the receiver(s) in each Repair FEC Payload ID. A
+ receiver should not make any assumption on the way the repair key is
+ managed.
6.2. Decoding Side
This section provides a high level description of a Sliding Window
RLC decoder.
A FECFRAME receiver needs to maintain a linear system whose variables
are the received and lost source symbols. Upon receiving a FEC
Repair Packet, a receiver first extracts all the repair symbols it
contains (in case several repair symbols are packed together). For
each repair symbol, when at least one of the corresponding source
symbols it protects has been lost, the receiver adds an equation to
the linear system (or no equation if this repair packet does not
change the linear system rank). This equation of course re-uses the
ew_size coding coefficients that are computed by the same coefficient
- generation function (Section Section 3.6), using the repair key and
- encoding window descriptions carried in the Repair FEC Payload ID.
- Whenever possible (i.e., when a sub-system covering one or more lost
- source symbols is of full rank), decoding is performed in order to
- recover lost source symbols. Gaussian elimination is one possible
- algorithm to solve this linear system. Each time an ADUI can be
- totally recovered, padding is removed (thanks to the Length field, L,
- of the ADUI) and the ADU is assigned to the corresponding application
- flow (thanks to the Flow ID field, F, of the ADUI). This ADU is
- finally passed to the corresponding upper application. Received FEC
- Source Packets, containing an ADU, MAY be passed to the application
- either immediately or after some time to guaranty an ordered delivery
- to the application. This document does not mandate any approach as
- this is an operational and management decision.
+ generation function (Section 3.6), using the repair key and encoding
+ window descriptions carried in the Repair FEC Payload ID. Whenever
+ possible (i.e., when a sub-system covering one or more lost source
+ symbols is of full rank), decoding is performed in order to recover
+ lost source symbols. Gaussian elimination is one possible algorithm
+ to solve this linear system. Each time an ADUI can be totally
+ recovered, padding is removed (thanks to the Length field, L, of the
+ ADUI) and the ADU is assigned to the corresponding application flow
+ (thanks to the Flow ID field, F, of the ADUI). This ADU is finally
+ passed to the corresponding upper application. Received FEC Source
+ Packets, containing an ADU, MAY be passed to the application either
+ immediately or after some time to guaranty an ordered delivery to the
+ application. This document does not mandate any approach as this is
+ an operational and management decision.
With real-time flows, a lost ADU that is decoded after the maximum
latency or an ADU received after this delay has no value to the
application. This raises the question of deciding whether or not an
ADU is late. This decision MAY be taken within the FECFRAME receiver
(e.g., using the decoding window, see Section 3.1) or within the
application (e.g., using RTP timestamps within the ADU). Deciding
which option to follow and whether or not to pass all ADUs, including
those assumed late, to the application are operational decisions that
depend on the application and are therefore out of scope of this
@@ -1171,24 +1189,25 @@
topics.
9.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^^8)
The present document specifies two FEC Schemes that differ on the
Finite Field used for the coding coefficients. It is expected that
the RLC over GF(2^^8) FEC Scheme will be mostly used since it
warrants a higher packet loss protection. In case of small encoding
windows, the associated processing overhead is not an issue (e.g., we
measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM
- Cortex-A15 embedded board in [Roca17] for an encoding window of size
- 18 or 23 symbols). Of course the CPU overhead will increase with the
- encoding window size, because more operations in the GF(2^^8) finite
- field will be needed.
+ Cortex-A15 embedded board in [Roca17] depending on the code rate and
+ the channel conditions, using an encoding window of size 18 or 23
+ symbols; see the above article for the details). Of course the CPU
+ overhead will increase with the encoding window size, because more
+ operations in the GF(2^^8) finite field will be needed.
The RLC over GF(2) FEC Scheme offers an alternative. In that case
operations symbols can be directly XOR-ed together which warrants
high bitrate encoding and decoding operations, and can be an
advantage with large encoding windows. However, packet loss
protection is significantly reduced by using this FEC Scheme.
9.2. Operational Recommendations: Coding Coefficients Density Threshold
In addition to the choice of the Finite Field, the two FEC Schemes
@@ -1226,27 +1245,31 @@
11. Acknowledgments
The authors would like to thank the three TSVWG chairs, Wesley Eddy,
our shepherd, David Black and Gorry Fairhurst, as well as Spencer
Dawkins, our responsible AD, and all those who provided comments,
namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ
Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner.
Last but not least, the authors are really grateful to the IESG
members, in particular Benjamin Kaduk, Mirja Kuhlewind, Eric
- Rescorla, and Adam Roach for their highly valuable feedbacks that
- greatly contributed to improve this specification.
+ Rescorla, Adam Roach, and Roman Danyliw for their highly valuable
+ feedbacks that greatly contributed to improve this specification.
12. References
12.1. Normative References
+ [C99] "Programming languages - C: C99, correction 3:2007",
+ International Organization for Standardization, ISO/IEC
+ 9899:1999/Cor 3:2007, November 2007.
+
[fecframe-ext]
Roca, V. and A. Begen, "Forward Error Correction (FEC)
Framework Extension to Sliding Window Codes", Transport
Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext
(Work in Progress), January 2019,
```.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
@@ -1288,20 +1311,25 @@
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
June 2008, .
[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"Reed-Solomon Forward Error Correction (FEC) Schemes",
RFC 5510, DOI 10.17487/RFC5510, April 2009,
.
+ [RFC6681] Watson, M., Stockhammer, T., and M. Luby, "Raptor Forward
+ Error Correction (FEC) Schemes for FECFRAME", RFC 6681,
+ DOI 10.17487/RFC6681, August 2012,
+ .
+
[RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen,
"FLUTE - File Delivery over Unidirectional Transport",
RFC 6726, DOI 10.17487/RFC6726, November 2012,
.
[RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density
Parity Check (LDPC) Staircase Forward Error Correction
(FEC) Scheme for FECFRAME", RFC 6816,
DOI 10.17487/RFC6816, December 2012,
.
@@ -1338,55 +1366,56 @@
Appendix A. TinyMT32 Validation Criteria (Normative)
PRNG determinism, for a given seed, is a requirement. Consequently,
in order to validate an implementation of the TinyMT32 PRNG, the
following criteria MUST be met.
The first criterion focusses on the tinymt32_rand256(), where the
32-bit integer of the core TinyMT32 PRNG is scaled down to an 8-bit
integer. Using a seed value of 1, the first 50 values returned by:
tinymt32_rand256() as 8-bit unsigned integers MUST be equal to values
- provided in Figure 9.
+ provided in Figure 9, to be read line by line.
37 225 177 176 21
246 54 139 168 237
211 187 62 190 104
135 210 99 176 11
207 35 40 113 179
214 254 101 212 211
226 41 234 232 203
29 194 211 112 107
217 104 197 135 23
89 210 252 109 166
- Figure 9: First 50 decimal values returned by tinymt32_rand256() as
- 8-bit unsigned integers, with a seed value of 1.
+ Figure 9: First 50 decimal values (to be read per line) returned by
+ tinymt32_rand256() as 8-bit unsigned integers, with a seed value of
+ 1.
The second criterion focusses on the tinymt32_rand16(), where the
32-bit integer of the core TinyMT32 PRNG is scaled down to a 4-bit
integer. Using a seed value of 1, the first 50 values returned by:
tinymt32_rand16() as 4-bit unsigned integers MUST be equal to values
- provided in Figure 10.
+ provided in Figure 10, to be read line by line.
5 1 1 0 5
6 6 11 8 13
3 11 14 14 8
7 2 3 0 11
15 3 8 1 3
6 14 5 4 3
2 9 10 8 11
13 2 3 0 11
9 8 5 7 7
9 2 12 13 6
- Figure 10: First 50 decimal values returned by tinymt32_rand16() as
- 4-bit unsigned integers, with a seed value of 1.
+ Figure 10: First 50 decimal values (to be read per line) returned by
+ tinymt32_rand16() as 4-bit unsigned integers, with a seed value of 1.
Appendix B. Assessing the PRNG Adequacy (Informational)
This annex discusses the adequacy of the TinyMT32 PRNG and the
tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC
Schemes. The goal is to assess the adequacy of these two functions
in producing coding coefficients that are sufficiently different from
one another, across various repair symbols with repair key values in
sequence (we can expect this approach to be commonly used by
implementers, see Section 6.1). This section is purely informational