draft-ietf-tsvwg-rlc-fec-scheme-14.txt   draft-ietf-tsvwg-rlc-fec-scheme-15.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: November 28, 2019 May 27, 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-14 draft-ietf-tsvwg-rlc-fec-scheme-15
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. These sliding window FEC codes
These sliding window FEC codes rely on an encoding window that slides rely on an encoding window that slides over the source symbols,
over the source symbols, generating new repair symbols whenever generating new repair symbols whenever needed. Compared to block FEC
needed. Compared to block FEC codes, these sliding window FEC codes codes, these sliding window FEC codes offer key advantages with real-
offer key advantages with real-time flows in terms of reduced FEC- time flows in terms of reduced FEC-related latency while often
related latency while often providing improved packet erasure providing improved packet erasure recovery capabilities.
recovery capabilities.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
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 November 28, 2019. This Internet-Draft will expire on December 20, 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 2, line 31 skipping to change at page 2, line 31
1.3. Small Transmission Overheads with the Sliding Window RLC 1.3. Small Transmission Overheads with the Sliding Window RLC
FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5 FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Document Organization . . . . . . . . . . . . . . . . . . 6 1.4. Document Organization . . . . . . . . . . . . . . . . . . 6
2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6 2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6
3. Common Procedures . . . . . . . . . . . . . . . . . . . . . . 7 3. Common Procedures . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Codec Parameters . . . . . . . . . . . . . . . . . . . . 7 3.1. Codec Parameters . . . . . . . . . . . . . . . . . . . . 7
3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9
3.3. Encoding Window Management . . . . . . . . . . . . . . . 10 3.3. Encoding Window Management . . . . . . . . . . . . . . . 10
3.4. Source Symbol Identification . . . . . . . . . . . . . . 11 3.4. Source Symbol Identification . . . . . . . . . . . . . . 11
3.5. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 11 3.5. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 11
3.6. Coding Coefficients Generation Function . . . . . . . . . 12 3.6. Coding Coefficients Generation Function . . . . . . . . . 13
3.7. Finite Fields Operations . . . . . . . . . . . . . . . . 15 3.7. Finite Fields Operations . . . . . . . . . . . . . . . . 15
3.7.1. Finite Field Definitions . . . . . . . . . . . . . . 15 3.7.1. Finite Field Definitions . . . . . . . . . . . . . . 15
3.7.2. Linear Combination of Source Symbols Computation . . 15 3.7.2. Linear Combination of Source Symbols Computation . . 15
4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary
Packet Flows . . . . . . . . . . . . . . . . . . . . . . . . 16 Packet Flows . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 16 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 16
4.1.1. FEC Framework Configuration Information . . . . . . . 16 4.1.1. FEC Framework Configuration Information . . . . . . . 16
4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 17 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 18
4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 18 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 18
4.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 19 4.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 20
5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 20 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 20
5.1.1. FEC Framework Configuration Information . . . . . . . 20 5.1.1. FEC Framework Configuration Information . . . . . . . 20
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 20 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 20
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20
5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 20 5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 21
6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 20 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 21
6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 20 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 21
6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 21 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 22
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 22 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 22
8. Security Considerations . . . . . . . . . . . . . . . . . . . 22 8. Security Considerations . . . . . . . . . . . . . . . . . . . 23
8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 23 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 23
8.1.1. Access to Confidential Content . . . . . . . . . . . 23 8.1.1. Access to Confidential Content . . . . . . . . . . . 23
8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 23 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 23
8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 23 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 23
8.3. When Several Source Flows are to be Protected Together . 25 8.3. When Several Source Flows are to be Protected Together . 25
8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25 8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25
8.5. Additional Security Considerations for Numerical 8.5. Additional Security Considerations for Numerical
Computations . . . . . . . . . . . . . . . . . . . . . . 25 Computations . . . . . . . . . . . . . . . . . . . . . . 25
9. Operations and Management Considerations . . . . . . . . . . 25 9. Operations and Management Considerations . . . . . . . . . . 26
9.1. Operational Recommendations: Finite Field GF(2) Versus 9.1. Operational Recommendations: Finite Field GF(2) Versus
GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 25 GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2. Operational Recommendations: Coding Coefficients Density 9.2. Operational Recommendations: Coding Coefficients Density
Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26 Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27
12.1. Normative References . . . . . . . . . . . . . . . . . . 27 12.1. Normative References . . . . . . . . . . . . . . . . . . 27
12.2. Informative References . . . . . . . . . . . . . . . . . 28 12.2. Informative References . . . . . . . . . . . . . . . . . 28
Appendix A. TinyMT32 Validation Criteria (Normative) . . . . . . 30 Appendix A. TinyMT32 Validation Criteria (Normative) . . . . . . 30
Appendix B. Assessing the PRNG Adequacy (Informational) . . . . 31 Appendix B. Assessing the PRNG Adequacy (Informational) . . . . 31
Appendix C. Possible Parameter Derivation (Informational) . . . 33 Appendix C. Possible Parameter Derivation (Informational) . . . 33
C.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . . . 34 C.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . . . 34
C.2. Other Types of Real-Time Flow . . . . . . . . . . . . . . 36 C.2. Other Types of Real-Time Flow . . . . . . . . . . . . . . 36
C.3. Case of a Non Real-Time Flow . . . . . . . . . . . . . . 37 C.3. Case of a Non Real-Time Flow . . . . . . . . . . . . . . 37
skipping to change at page 3, line 41 skipping to change at page 3, line 41
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 38 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 38
1. Introduction 1. Introduction
Application-Level Forward Erasure Correction (AL-FEC) codes, or Application-Level Forward Erasure Correction (AL-FEC) codes, or
simply FEC codes, are a key element of communication systems. They simply FEC codes, are a key element of communication systems. They
are used to recover from packet losses (or erasures) during content are used to recover from packet losses (or erasures) during content
delivery sessions to a potentially large number of receivers delivery sessions to a potentially large number of receivers
(multicast/broadcast transmissions). This is the case with the (multicast/broadcast transmissions). This is the case with the
FLUTE/ALC protocol [RFC6726] when used for reliable file transfers FLUTE/ALC protocol [RFC6726] when used for reliable file transfers
over lossy networks, and the FECFRAME protocol when used for reliable over lossy networks, and the FECFRAME protocol [RFC6363] when used
continuous media transfers over lossy networks. for reliable continuous media transfers over lossy networks.
The present document only focuses on the FECFRAME protocol, used in The present document only focuses on the FECFRAME protocol, used in
multicast/broadcast delivery mode, in particular for contents that multicast/broadcast delivery mode, in particular for contents that
feature stringent real-time constraints: each source packet has a feature stringent real-time constraints: each source packet has a
maximum validity period after which it will not be considered by the maximum validity period after which it will not be considered by the
destination application. destination application.
1.1. Limits of Block Codes with Real-Time Flows 1.1. Limits of Block Codes with Real-Time Flows
With FECFRAME, there is a single FEC encoding point (either a end- With FECFRAME, there is a single FEC encoding point (either an end-
host/server (source) or a middlebox) and a single FEC decoding point host/server (source) or a middlebox) and a single FEC decoding point
per receiver (either a end-host (receiver) or middlebox). In this per receiver (either an end-host (receiver) or middlebox). In this
context, currently standardized AL-FEC codes for FECFRAME like Reed- context, currently standardized AL-FEC codes for FECFRAME like Reed-
Solomon [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ, are Solomon [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ
all linear block codes: they require the data flow to be segmented [RFC6681], are all linear block codes: they require the data flow to
into blocks of a predefined maximum size. be segmented into blocks of a predefined maximum size.
To define this block size, it is required to find an appropriate To define this block size, it is required to find an appropriate
balance between robustness and decoding latency: the larger the block balance between robustness and decoding latency: the larger the block
size, the higher the robustness (e.g., in case of long packet erasure size, the higher the robustness (e.g., in case of long packet erasure
bursts), but also the higher the maximum decoding latency (i.e., the bursts), but also the higher the maximum decoding latency (i.e., the
maximum time required to recover a lost (erased) packet thanks to FEC maximum time required to recover a lost (erased) packet thanks to FEC
protection). Therefore, with a multicast/broadcast session where protection). Therefore, with a multicast/broadcast session where
different receivers experience different packet loss rates, the block different receivers experience different packet loss rates, the block
size should be chosen by considering the worst communication size should be chosen by considering the worst communication
conditions one wants to support, but without exceeding the desired conditions one wants to support, but without exceeding the desired
skipping to change at page 5, line 11 skipping to change at page 5, line 11
window). Repair symbols are generated on-the-fly, by computing a window). Repair symbols are generated on-the-fly, by computing a
random linear combination of the source symbols present in the random linear combination of the source symbols present in the
current encoding window, and passed to the transport layer. current encoding window, and passed to the transport layer.
At the receiver, a linear system is managed from the set of received At the receiver, a linear system is managed from the set of received
source and repair packets. New variables (representing source source and repair packets. New variables (representing source
symbols) and equations (representing the linear combination carried symbols) and equations (representing the linear combination carried
by each repair symbol received) are added upon receiving new packets. by each repair symbol received) are added upon receiving new packets.
Variables and the equations they are involved in are removed when Variables and the equations they are involved in are removed when
they are too old with respect to their validity period (real-time they are too old with respect to their validity period (real-time
constraints) . Lost source symbols are then recovered thanks to this constraints). Lost source symbols are then recovered thanks to this
linear system whenever its rank permits to solve it (at least linear system whenever its rank permits to solve it (at least
partially). partially).
The protection of any multicast/broadcast session needs to be The protection of any multicast/broadcast session needs to be
dimensioned by considering the worst communication conditions one dimensioned by considering the worst communication conditions one
wants to support. This is also true with RLC (more generally any wants to support. This is also true with RLC (more generally any
sliding window) code. However, the receivers experiencing a good to sliding window) code. However, the receivers experiencing a good to
medium communication quality will observe a reduced FEC-related medium communication quality will observe a reduced FEC-related
latency compared to block codes [Roca17] since an isolated lost latency compared to block codes [Roca17] since an isolated lost
source packet is quickly recovered with the following repair packet. source packet is quickly recovered with the following repair packet.
skipping to change at page 6, line 24 skipping to change at page 6, line 24
1.4. Document Organization 1.4. Document Organization
This fully-specified FEC Scheme follows the structure required by This fully-specified FEC Scheme follows the structure required by
[RFC6363], section 5.6. "FEC Scheme Requirements", namely: [RFC6363], section 5.6. "FEC Scheme Requirements", namely:
3. Procedures: This section describes procedures specific to this 3. Procedures: This section describes procedures specific to this
FEC Scheme, namely: RLC parameters derivation, ADUI and source FEC Scheme, namely: RLC parameters derivation, ADUI and source
symbols mapping, pseudo-random number generator, and coding symbols mapping, pseudo-random number generator, and coding
coefficients generation function; coefficients generation function;
4. Formats and Codes: This section defines the Source FEC Payload 4. Formats and Codes: This section defines the Source FEC Payload
ID and Repair FEC Payload ID formats, carrying the signalling ID and Repair FEC Payload ID formats, carrying the signaling
information associated to each source or repair symbol. It also information associated to each source or repair symbol. It also
defines the FEC Framework Configuration Information (FFCI) defines the FEC Framework Configuration Information (FFCI)
carrying signalling information for the session; carrying signaling information for the session;
5. FEC Code Specification: Finally this section provides the code 5. FEC Code Specification: Finally this section provides the code
specification. specification.
2. Definitions and Abbreviations 2. Definitions and Abbreviations
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP "OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
skipping to change at page 8, line 48 skipping to change at page 8, line 48
source plus repair symbols and by definition: 0 < cr <= 1. This source plus repair symbols and by definition: 0 < cr <= 1. This
is an input parameter that enables a FECFRAME sender to derive is an input parameter that enables a FECFRAME sender to derive
other internal parameters, as explained below. However, there is other internal parameters, as explained below. However, there is
no need to communicate the cr parameter per see (it's not required no need to communicate the cr parameter per see (it's not required
to process a repair symbol at a receiver). This code rate to process a repair symbol at a receiver). This code rate
parameter can be static. However, in specific use-cases (e.g., parameter can be static. However, in specific use-cases (e.g.,
with unicast transmissions in presence of a feedback mechanism with unicast transmissions in presence of a feedback mechanism
that estimates the communication quality, out of scope of that estimates the communication quality, out of scope of
FECFRAME), the code rate may be adjusted dynamically. FECFRAME), the code rate may be adjusted dynamically.
Appendix C proposes non normative technics to derive those Appendix C proposes non normative techniques to derive those
parameters, depending on the use-case specificities. parameters, depending on the use-case specificities.
3.2. ADU, ADUI and Source Symbols Mappings 3.2. ADU, ADUI and Source Symbols Mappings
At a sender, an ADU coming from the application is not directly At a sender, an ADU coming from the application is not directly
mapped to source symbols. When multiple source flows (e.g., media mapped to source symbols. When multiple source flows (e.g., media
streams) are mapped onto the same FECFRAME instance, each flow is streams) are mapped onto the same FECFRAME instance, each flow is
assigned its own Flow ID value (see below). This Flow ID is then assigned its own Flow ID value (see below). This Flow ID is then
prepended to each ADU before FEC encoding. This way, FEC decoding at prepended to each ADU before FEC encoding. This way, FEC decoding at
a receiver also recovers this Flow ID and the recovered ADU can be a receiver also recovers this Flow ID and the recovered ADU can be
skipping to change at page 11, line 31 skipping to change at page 11, line 31
This PRNG MUST first be initialized with a 32-bit unsigned integer, This PRNG MUST first be initialized with a 32-bit unsigned integer,
used as a seed, with: used as a seed, with:
void tinymt32_init (tinymt32_t * s, uint32_t seed); void tinymt32_init (tinymt32_t * s, uint32_t seed);
With the FEC Schemes defined in this document, the seed is in With the FEC Schemes defined in this document, the seed is in
practice restricted to a value between 0 and 0xFFFF inclusive (note practice restricted to a value between 0 and 0xFFFF inclusive (note
that this PRNG accepts a seed value equal to 0), since this is the that this PRNG accepts a seed value equal to 0), since this is the
Repair_Key 16-bit field value of the Repair FEC Payload ID Repair_Key 16-bit field value of the Repair FEC Payload ID
(Section 4.1.3). In addition to the seed, this function takes as (Section 4.1.3). In practice, how to manage the seed and Repair_Key
parameter a pointer to an instance of a tinymt32_t structure that is values (both are equal) is left to the implementer, using a
used to keep the internal state of the PRNG. monotonically increasing counter being one possibility (Section 6.1).
In addition to the seed, this function takes as parameter a pointer
to an instance of a tinymt32_t structure that is used to keep the
internal state of the PRNG.
Then, each time a new pseudo-random integer between 0 and 15 Then, each time a new pseudo-random integer between 0 and 15
inclusive (4-bit pseudo-random integer) is needed, the following inclusive (4-bit pseudo-random integer) is needed, the following
function is used: function is used:
uint32_t tinymt32_rand16 (tinymt32_t * s); uint32_t tinymt32_rand16 (tinymt32_t * s);
This function takes as parameter a pointer to the same tinymt32_t This function takes as parameter a pointer to the same tinymt32_t
structure (that is left unchanged between successive calls to the structure (that is left unchanged between successive calls to the
function). function).
skipping to change at page 12, line 8 skipping to change at page 12, line 11
function is used: function is used:
uint32_t tinymt32_rand256 (tinymt32_t * s); uint32_t tinymt32_rand256 (tinymt32_t * s);
These two functions keep respectively the 4 or 8 less significant These two functions keep respectively the 4 or 8 less significant
bits of the 32-bit pseudo-random number generated by the bits of the 32-bit pseudo-random number generated by the
tinymt32_generate_uint32() function of [tinymt32]. This is done by tinymt32_generate_uint32() function of [tinymt32]. This is done by
computing the result of a binary AND between the computing the result of a binary AND between the
tinymt32_generate_uint32() output and respectively the 0xF or 0xFF tinymt32_generate_uint32() output and respectively the 0xF or 0xFF
constants, using 32-bit unsigned integer operations. Figure 2 shows constants, using 32-bit unsigned integer operations. Figure 2 shows
a possible implementation. Test results discussed in Appendix B show a possible implementation. This is a C language implementation,
written for C99 [C99]. Test results discussed in Appendix B show
that this simple technique, applied to this PRNG, is in line with the that this simple technique, applied to this PRNG, is in line with the
RLC FEC Schemes needs. RLC FEC Schemes needs.
<CODE BEGINS> <CODE BEGINS>
/** /**
* This function outputs a pseudo-random integer in [0 .. 15] range. * This function outputs a pseudo-random integer in [0 .. 15] range.
* *
* @param s pointer to tinymt internal state. * @param s pointer to tinymt internal state.
* @return unsigned integer between 0 and 15 inclusive. * @return unsigned integer between 0 and 15 inclusive.
*/ */
skipping to change at page 12, line 38 skipping to change at page 12, line 42
* @return unsigned integer between 0 and 255 inclusive. * @return unsigned integer between 0 and 255 inclusive.
*/ */
uint32_t tinymt32_rand256(tinymt32_t *s) uint32_t tinymt32_rand256(tinymt32_t *s)
{ {
return (tinymt32_generate_uint32(s) & 0xFF); return (tinymt32_generate_uint32(s) & 0xFF);
} }
<CODE ENDS> <CODE ENDS>
Figure 2: 4-bit and 8-bit mapping functions for TinyMT32 Figure 2: 4-bit and 8-bit mapping functions for TinyMT32
Any implementation of this PRNG MUST fulfill three validation Any implementation of this PRNG MUST have the same output as that
criteria: the one described in [tinymt32] (for the TinyMT32 32-bit provided by the reference implementation of [tinymt32]. In order to
unsigned integer generator), and the two others detailed in increase the compliancy confidence, three criteria are proposed: the
Appendix A (for the mapping to 4-bit and 8-bit intervals). Because one described in [tinymt32] (for the TinyMT32 32-bit unsigned integer
of the way the mapping functions work, it is unlikely that an generator), and the two others detailed in Appendix A (for the
implementation that fulfills the first criterion fails to fulfill the mapping to 4-bit and 8-bit intervals). Because of the way the
two others. 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 3.6. Coding Coefficients Generation Function
The coding coefficients, used during the encoding process, are The coding coefficients, used during the encoding process, are
generated at the RLC encoder by the generate_coding_coefficients() generated at the RLC encoder by the generate_coding_coefficients()
function each time a new repair symbol needs to be produced. The function each time a new repair symbol needs to be produced. The
fraction of coefficients that are non zero (i.e., the density) is fraction of coefficients that are non zero (i.e., the density) is
controlled by the DT (Density Threshold) parameter. DT has values controlled by the DT (Density Threshold) parameter. DT has values
between 0 (the minimum value) and 15 (the maximum value), and the between 0 (the minimum value) and 15 (the maximum value), and the
average probability of having a non zero coefficient equals (DT + 1) average probability of having a non zero coefficient equals (DT + 1)
/ 16. In particular, when DT equals 15 the function guaranties that / 16. In particular, when DT equals 15 the function guaranties that
all coefficients are non zero (i.e., maximum density). all coefficients are non zero (i.e., maximum density).
These considerations apply to both the RLC over GF(2) and RLC over 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. 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 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. 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].
<CODE BEGINS> <CODE BEGINS>
#include <string.h>
/* /*
* Fills in the table of coding coefficients (of the right size) * Fills in the table of coding coefficients (of the right size)
* provided with the appropriate number of coding coefficients to * provided with the appropriate number of coding coefficients to
* use for the repair symbol key provided. * use for the repair symbol key provided.
* *
* (in) repair_key key associated to this repair symbol. This * (in) repair_key key associated to this repair symbol. This
* parameter is ignored (useless) if m=1 and dt=15 * 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 * coding coefficients. All coefficients are
* stored as bytes, regardless of the m parameter, * stored as bytes, regardless of the m parameter,
* upon return of this function. * upon return of this function.
* (in) cc_nb number of entries in the table. This value is * (in) cc_nb number of entries in the cc_tab table. This
* equal to the current encoding window size. * value is equal to the current encoding window
* size.
* (in) dt integer between 0 and 15 (inclusive) that * (in) dt integer between 0 and 15 (inclusive) that
* controls the density. With value 15, all * controls the density. With value 15, all
* coefficients are guaranteed to be non zero * coefficients are guaranteed to be non zero
* (i.e. equal to 1 with GF(2) and equal to a * (i.e. equal to 1 with GF(2) and equal to a
* value in {1,... 255} with GF(2^^8)), otherwise * value in {1,... 255} with GF(2^^8)), otherwise
* a fraction of them will be 0. * a fraction of them will be 0.
* (in) m Finite Field GF(2^^m) parameter. In this * (in) m Finite Field GF(2^^m) parameter. In this
* document only values 1 and 8 are considered. * document only values 1 and 8 are considered.
* (out) returns 0 in case of success, an error code * (out) returns 0 in case of success, an error code
* different than 0 otherwise. * different than 0 otherwise.
skipping to change at page 13, line 39 skipping to change at page 14, line 4
* (in) dt integer between 0 and 15 (inclusive) that * (in) dt integer between 0 and 15 (inclusive) that
* controls the density. With value 15, all * controls the density. With value 15, all
* coefficients are guaranteed to be non zero * coefficients are guaranteed to be non zero
* (i.e. equal to 1 with GF(2) and equal to a * (i.e. equal to 1 with GF(2) and equal to a
* value in {1,... 255} with GF(2^^8)), otherwise * value in {1,... 255} with GF(2^^8)), otherwise
* a fraction of them will be 0. * a fraction of them will be 0.
* (in) m Finite Field GF(2^^m) parameter. In this * (in) m Finite Field GF(2^^m) parameter. In this
* document only values 1 and 8 are considered. * document only values 1 and 8 are considered.
* (out) returns 0 in case of success, an error code * (out) returns 0 in case of success, an error code
* different than 0 otherwise. * different than 0 otherwise.
*/ */
int generate_coding_coefficients (uint16_t repair_key, int generate_coding_coefficients (uint16_t repair_key,
uint8_t cc_tab[], uint8_t* cc_tab,
uint16_t cc_nb, uint16_t cc_nb,
uint8_t dt, uint8_t dt,
uint8_t m) uint8_t m)
{ {
uint32_t i; uint32_t i;
tinymt32_t s; /* PRNG internal state */ tinymt32_t s; /* PRNG internal state */
if (dt > 15) { if (dt > 15) {
return -1; /* error, bad dt parameter */ return -1; /* error, bad dt parameter */
} }
skipping to change at page 14, line 39 skipping to change at page 15, line 4
/* here a certain number of coefficients should be 0 */ /* here a certain number of coefficients should be 0 */
for (i = 0 ; i < cc_nb ; i++) { for (i = 0 ; i < cc_nb ; i++) {
if (tinymt32_rand16(&s) <= dt) { if (tinymt32_rand16(&s) <= dt) {
do { do {
cc_tab[i] = (uint8_t) tinymt32_rand256(&s); cc_tab[i] = (uint8_t) tinymt32_rand256(&s);
} while (cc_tab[i] == 0); } while (cc_tab[i] == 0);
} else { } else {
cc_tab[i] = 0; cc_tab[i] = 0;
} }
} }
} }
break; break;
default: default:
return -2; /* error, bad parameter m */ return -2; /* error, bad parameter m */
} }
return 0 /* success */ return 0; /* success */
} }
<CODE ENDS> <CODE ENDS>
Figure 3: Coding Coefficients Generation Function Reference Figure 3: Coding Coefficients Generation Function Reference
Implementation Implementation
3.7. Finite Fields Operations 3.7. Finite Fields Operations
3.7.1. Finite Field Definitions 3.7.1. Finite Field Definitions
The two RLC FEC Schemes specified in this document reuse the Finite The two RLC FEC Schemes specified in this document reuse the Finite
Fields defined in [RFC5510], section 8.1. More specifically, the Fields defined in [RFC5510], section 8.1. More specifically, the
elements of the field GF(2^^m) are represented by polynomials with 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 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 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 binary polynomials in GF(2), which is equivalent to a bitwise XOR
operation on the binary representation of these elements. operation on the binary representation of these elements.
With GF(2^^8), multiplication between two elements is the With GF(2^^8), multiplication between two elements is the
multiplication modulo a given irreducible polynomial of degree 8. 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 x^^8 + x^^4 + x^^3 + x^^2 + 1
With GF(2), multiplication corresponds to a logical AND operation. With GF(2), multiplication corresponds to a logical AND operation.
3.7.2. Linear Combination of Source Symbols Computation 3.7.2. Linear Combination of Source Symbols Computation
The two RLC FEC Schemes require the computation of a linear The two RLC FEC Schemes require the computation of a linear
combination of source symbols, using the coding coefficients produced combination of source symbols, using the coding coefficients produced
by the generate_coding_coefficients() function and stored in the by the generate_coding_coefficients() function and stored in the
cc_tab[] array. cc_tab[] array.
With the RLC over GF(2^^8) FEC Scheme, a linear combination of the 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 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 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 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 ... 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] XOR cc_tab[ew_size - 1] * src_ew_size_1[i]
where * is the multiplication over GF(2^^8). In practice various where * is the multiplication over GF(2^^8). In practice various
optimizations need to be used in order to make this computation optimizations need to be used in order to make this computation
efficient (see in particular [PGM13]). efficient (see in particular [PGM13]).
With the RLC over GF(2) FEC Scheme (binary case), a linear With the RLC over GF(2) FEC Scheme (binary case), a linear
combination is computed as follows. The repair symbol is the XOR sum combination is computed as follows. The repair symbol is the XOR sum
of all the source symbols corresponding to a coding coefficient of all the source symbols corresponding to a coding coefficient
cc_tab[j] equal to 1 (i.e., the source symbols corresponding to zero 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 coding coefficients are ignored). The XOR sum of the byte of
position i in each source is computed and stored in the corresponding 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 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 bit words, or on arrays of 16 or more bytes when using SIMD CPU
extensions). extensions).
With both FEC Schemes, the details of how to optimize the computation With both FEC Schemes, the details of how to optimize the computation
of these linear combinations are of high practical importance but out of these linear combinations are of high practical importance but out
of scope of this document. of scope of this document.
4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary Packet 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary Packet
Flows Flows
skipping to change at page 21, line 26 skipping to change at page 21, line 43
carried in the Repair FEC Payload ID. The FEC Repair Packet can then carried in the Repair FEC Payload ID. The FEC Repair Packet can then
be passed to the transport layer for transmission. The source versus be passed to the transport layer for transmission. The source versus
repair FEC packet transmission order is out of scope of this document repair FEC packet transmission order is out of scope of this document
and several approaches exist that are implementation-specific. and several approaches exist that are implementation-specific.
Other solutions are possible to select a repair key value when a new Other solutions are possible to select a repair key value when a new
FEC Repair Packet is needed, for instance, by choosing a random FEC Repair Packet is needed, for instance, by choosing a random
integer between 0 and 65535. However, selecting the same repair key integer between 0 and 65535. However, selecting the same repair key
as before (which may happen in case of a random process) is only as before (which may happen in case of a random process) is only
meaningful if the encoding window has changed, otherwise the same FEC 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 6.2. Decoding Side
This section provides a high level description of a Sliding Window This section provides a high level description of a Sliding Window
RLC decoder. RLC decoder.
A FECFRAME receiver needs to maintain a linear system whose variables A FECFRAME receiver needs to maintain a linear system whose variables
are the received and lost source symbols. Upon receiving a FEC are the received and lost source symbols. Upon receiving a FEC
Repair Packet, a receiver first extracts all the repair symbols it Repair Packet, a receiver first extracts all the repair symbols it
contains (in case several repair symbols are packed together). For contains (in case several repair symbols are packed together). For
each repair symbol, when at least one of the corresponding source each repair symbol, when at least one of the corresponding source
symbols it protects has been lost, the receiver adds an equation to symbols it protects has been lost, the receiver adds an equation to
the linear system (or no equation if this repair packet does not the linear system (or no equation if this repair packet does not
change the linear system rank). This equation of course re-uses the change the linear system rank). This equation of course re-uses the
ew_size coding coefficients that are computed by the same coefficient ew_size coding coefficients that are computed by the same coefficient
generation function (Section Section 3.6), using the repair key and generation function (Section 3.6), using the repair key and encoding
encoding window descriptions carried in the Repair FEC Payload ID. window descriptions carried in the Repair FEC Payload ID. Whenever
Whenever possible (i.e., when a sub-system covering one or more lost possible (i.e., when a sub-system covering one or more lost source
source symbols is of full rank), decoding is performed in order to symbols is of full rank), decoding is performed in order to recover
recover lost source symbols. Gaussian elimination is one possible lost source symbols. Gaussian elimination is one possible algorithm
algorithm to solve this linear system. Each time an ADUI can be to solve this linear system. Each time an ADUI can be totally
totally recovered, padding is removed (thanks to the Length field, L, recovered, padding is removed (thanks to the Length field, L, of the
of the ADUI) and the ADU is assigned to the corresponding application ADUI) and the ADU is assigned to the corresponding application flow
flow (thanks to the Flow ID field, F, of the ADUI). This ADU is (thanks to the Flow ID field, F, of the ADUI). This ADU is finally
finally passed to the corresponding upper application. Received FEC passed to the corresponding upper application. Received FEC Source
Source Packets, containing an ADU, MAY be passed to the application Packets, containing an ADU, MAY be passed to the application either
either immediately or after some time to guaranty an ordered delivery immediately or after some time to guaranty an ordered delivery to the
to the application. This document does not mandate any approach as application. This document does not mandate any approach as this is
this is an operational and management decision. an operational and management decision.
With real-time flows, a lost ADU that is decoded after the maximum 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 latency or an ADU received after this delay has no value to the
application. This raises the question of deciding whether or not an application. This raises the question of deciding whether or not an
ADU is late. This decision MAY be taken within the FECFRAME receiver 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 (e.g., using the decoding window, see Section 3.1) or within the
application (e.g., using RTP timestamps within the ADU). Deciding application (e.g., using RTP timestamps within the ADU). Deciding
which option to follow and whether or not to pass all ADUs, including which option to follow and whether or not to pass all ADUs, including
those assumed late, to the application are operational decisions that those assumed late, to the application are operational decisions that
depend on the application and are therefore out of scope of this depend on the application and are therefore out of scope of this
skipping to change at page 26, line 5 skipping to change at page 26, line 22
topics. topics.
9.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^^8) 9.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^^8)
The present document specifies two FEC Schemes that differ on the The present document specifies two FEC Schemes that differ on the
Finite Field used for the coding coefficients. It is expected that 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 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 warrants a higher packet loss protection. In case of small encoding
windows, the associated processing overhead is not an issue (e.g., we 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 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 Cortex-A15 embedded board in [Roca17] depending on the code rate and
18 or 23 symbols). Of course the CPU overhead will increase with the the channel conditions, using an encoding window of size 18 or 23
encoding window size, because more operations in the GF(2^^8) finite symbols; see the above article for the details). Of course the CPU
field will be needed. 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 The RLC over GF(2) FEC Scheme offers an alternative. In that case
operations symbols can be directly XOR-ed together which warrants operations symbols can be directly XOR-ed together which warrants
high bitrate encoding and decoding operations, and can be an high bitrate encoding and decoding operations, and can be an
advantage with large encoding windows. However, packet loss advantage with large encoding windows. However, packet loss
protection is significantly reduced by using this FEC Scheme. protection is significantly reduced by using this FEC Scheme.
9.2. Operational Recommendations: Coding Coefficients Density Threshold 9.2. Operational Recommendations: Coding Coefficients Density Threshold
In addition to the choice of the Finite Field, the two FEC Schemes In addition to the choice of the Finite Field, the two FEC Schemes
skipping to change at page 27, line 14 skipping to change at page 27, line 30
11. Acknowledgments 11. Acknowledgments
The authors would like to thank the three TSVWG chairs, Wesley Eddy, The authors would like to thank the three TSVWG chairs, Wesley Eddy,
our shepherd, David Black and Gorry Fairhurst, as well as Spencer our shepherd, David Black and Gorry Fairhurst, as well as Spencer
Dawkins, our responsible AD, and all those who provided comments, Dawkins, our responsible AD, and all those who provided comments,
namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ
Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner. Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner.
Last but not least, the authors are really grateful to the IESG Last but not least, the authors are really grateful to the IESG
members, in particular Benjamin Kaduk, Mirja Kuhlewind, Eric members, in particular Benjamin Kaduk, Mirja Kuhlewind, Eric
Rescorla, and Adam Roach for their highly valuable feedbacks that Rescorla, Adam Roach, and Roman Danyliw for their highly valuable
greatly contributed to improve this specification. feedbacks that greatly contributed to improve this specification.
12. References 12. References
12.1. Normative 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] [fecframe-ext]
Roca, V. and A. Begen, "Forward Error Correction (FEC) Roca, V. and A. Begen, "Forward Error Correction (FEC)
Framework Extension to Sliding Window Codes", Transport Framework Extension to Sliding Window Codes", Transport
Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext
(Work in Progress), January 2019, (Work in Progress), January 2019,
<https://tools.ietf.org/html/ <https://tools.ietf.org/html/
draft-ietf-tsvwg-fecframe-ext>. draft-ietf-tsvwg-fecframe-ext>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
skipping to change at page 28, line 33 skipping to change at page 29, line 5
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Staircase and Triangle Forward Error Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
June 2008, <https://www.rfc-editor.org/info/rfc5170>. June 2008, <https://www.rfc-editor.org/info/rfc5170>.
[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"Reed-Solomon Forward Error Correction (FEC) Schemes", "Reed-Solomon Forward Error Correction (FEC) Schemes",
RFC 5510, DOI 10.17487/RFC5510, April 2009, RFC 5510, DOI 10.17487/RFC5510, April 2009,
<https://www.rfc-editor.org/info/rfc5510>. <https://www.rfc-editor.org/info/rfc5510>.
[RFC6681] Watson, M., Stockhammer, T., and M. Luby, "Raptor Forward
Error Correction (FEC) Schemes for FECFRAME", RFC 6681,
DOI 10.17487/RFC6681, August 2012,
<https://www.rfc-editor.org/info/rfc6681>.
[RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, [RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen,
"FLUTE - File Delivery over Unidirectional Transport", "FLUTE - File Delivery over Unidirectional Transport",
RFC 6726, DOI 10.17487/RFC6726, November 2012, RFC 6726, DOI 10.17487/RFC6726, November 2012,
<https://www.rfc-editor.org/info/rfc6726>. <https://www.rfc-editor.org/info/rfc6726>.
[RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density [RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density
Parity Check (LDPC) Staircase Forward Error Correction Parity Check (LDPC) Staircase Forward Error Correction
(FEC) Scheme for FECFRAME", RFC 6816, (FEC) Scheme for FECFRAME", RFC 6816,
DOI 10.17487/RFC6816, December 2012, DOI 10.17487/RFC6816, December 2012,
<https://www.rfc-editor.org/info/rfc6816>. <https://www.rfc-editor.org/info/rfc6816>.
skipping to change at page 30, line 15 skipping to change at page 30, line 15
Appendix A. TinyMT32 Validation Criteria (Normative) Appendix A. TinyMT32 Validation Criteria (Normative)
PRNG determinism, for a given seed, is a requirement. Consequently, PRNG determinism, for a given seed, is a requirement. Consequently,
in order to validate an implementation of the TinyMT32 PRNG, the in order to validate an implementation of the TinyMT32 PRNG, the
following criteria MUST be met. following criteria MUST be met.
The first criterion focusses on the tinymt32_rand256(), where the 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 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: 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 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 37 225 177 176 21
246 54 139 168 237 246 54 139 168 237
211 187 62 190 104 211 187 62 190 104
135 210 99 176 11 135 210 99 176 11
207 35 40 113 179 207 35 40 113 179
214 254 101 212 211 214 254 101 212 211
226 41 234 232 203 226 41 234 232 203
29 194 211 112 107 29 194 211 112 107
217 104 197 135 23 217 104 197 135 23
89 210 252 109 166 89 210 252 109 166
Figure 9: First 50 decimal values returned by tinymt32_rand256() as Figure 9: First 50 decimal values (to be read per line) returned by
8-bit unsigned integers, with a seed value of 1. tinymt32_rand256() as 8-bit unsigned integers, with a seed value of
1.
The second criterion focusses on the tinymt32_rand16(), where the 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 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: 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 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 5 1 1 0 5
6 6 11 8 13 6 6 11 8 13
3 11 14 14 8 3 11 14 14 8
7 2 3 0 11 7 2 3 0 11
15 3 8 1 3 15 3 8 1 3
6 14 5 4 3 6 14 5 4 3
2 9 10 8 11 2 9 10 8 11
13 2 3 0 11 13 2 3 0 11
9 8 5 7 7 9 8 5 7 7
9 2 12 13 6 9 2 12 13 6
Figure 10: First 50 decimal values returned by tinymt32_rand16() as Figure 10: First 50 decimal values (to be read per line) returned by
4-bit unsigned integers, with a seed value of 1. tinymt32_rand16() as 4-bit unsigned integers, with a seed value of 1.
Appendix B. Assessing the PRNG Adequacy (Informational) Appendix B. Assessing the PRNG Adequacy (Informational)
This annex discusses the adequacy of the TinyMT32 PRNG and the This annex discusses the adequacy of the TinyMT32 PRNG and the
tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC
Schemes. The goal is to assess the adequacy of these two functions Schemes. The goal is to assess the adequacy of these two functions
in producing coding coefficients that are sufficiently different from in producing coding coefficients that are sufficiently different from
one another, across various repair symbols with repair key values in one another, across various repair symbols with repair key values in
sequence (we can expect this approach to be commonly used by sequence (we can expect this approach to be commonly used by
implementers, see Section 6.1). This section is purely informational implementers, see Section 6.1). This section is purely informational
 End of changes. 44 change blocks. 
78 lines changed or deleted 106 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/