draft-ietf-tsvwg-rlc-fec-scheme-16.txt | rfc8681.txt | |||
---|---|---|---|---|

TSVWG V. Roca | Internet Engineering Task Force (IETF) V. Roca | |||

Internet-Draft B. Teibi | Request for Comments: 8681 B. Teibi | |||

Intended status: Standards Track INRIA | Category: Standards Track INRIA | |||

Expires: December 20, 2019 June 18, 2019 | ISSN: 2070-1721 January 2020 | |||

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

Abstract | Abstract | |||

This document describes two fully-specified Forward Erasure | This document describes two fully specified Forward Erasure | |||

Correction (FEC) Schemes for Sliding Window Random Linear Codes | Correction (FEC) Schemes for Sliding Window Random Linear Codes | |||

(RLC), one for RLC over the Galois Field (A.K.A. Finite Field) | (RLC), one for RLC over the Galois Field (a.k.a., Finite Field) | |||

GF(2), a second one for RLC over the Galois Field GF(2^^8), each time | GF(2), a second one for RLC over the Galois Field GF(2^(8)), each | |||

with the possibility of controlling the code density. They can | time with the possibility of controlling the code density. They can | |||

protect arbitrary media streams along the lines defined by FECFRAME | protect arbitrary media streams along the lines defined by FECFRAME | |||

extended to sliding window FEC codes. These sliding window FEC codes | extended to Sliding Window FEC Codes. These Sliding Window FEC Codes | |||

rely on an encoding window that slides over the source symbols, | rely on an encoding window that slides over the source symbols, | |||

generating new repair symbols whenever needed. Compared to block FEC | generating new repair symbols whenever needed. Compared to block FEC | |||

codes, these sliding window FEC codes offer key advantages with real- | codes, these Sliding Window FEC Codes offer key advantages with real- | |||

time flows in terms of reduced FEC-related latency while often | time flows in terms of reduced FEC-related latency while often | |||

providing improved packet erasure recovery capabilities. | providing improved packet erasure recovery capabilities. | |||

Status of This Memo | Status of This Memo | |||

This Internet-Draft is submitted in full conformance with the | This is an Internet Standards Track document. | |||

provisions of BCP 78 and BCP 79. | ||||

Internet-Drafts are working documents of the Internet Engineering | ||||

Task Force (IETF). Note that other groups may also distribute | ||||

working documents as Internet-Drafts. The list of current Internet- | ||||

Drafts is at https://datatracker.ietf.org/drafts/current/. | ||||

Internet-Drafts are draft documents valid for a maximum of six months | This document is a product of the Internet Engineering Task Force | |||

and may be updated, replaced, or obsoleted by other documents at any | (IETF). It represents the consensus of the IETF community. It has | |||

time. It is inappropriate to use Internet-Drafts as reference | received public review and has been approved for publication by the | |||

material or to cite them other than as "work in progress." | Internet Engineering Steering Group (IESG). Further information on | |||

Internet Standards is available in Section 2 of RFC 7841. | ||||

This Internet-Draft will expire on December 20, 2019. | Information about the current status of this document, any errata, | |||

and how to provide feedback on it may be obtained at | ||||

https://www.rfc-editor.org/info/rfc8681. | ||||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2019 IETF Trust and the persons identified as the | Copyright (c) 2020 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 | |||

carefully, as they describe your rights and restrictions with respect | carefully, as they describe your rights and restrictions with respect | |||

to this document. Code Components extracted from this document must | to this document. Code Components extracted from this document must | |||

include Simplified BSD License text as described in Section 4.e of | include Simplified BSD License text as described in Section 4.e of | |||

the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1. Introduction | |||

1.1. Limits of Block Codes with Real-Time Flows . . . . . . . 4 | 1.1. Limits of Block Codes with Real-Time Flows | |||

1.2. Lower Latency and Better Protection of Real-Time Flows | 1.2. Lower Latency and Better Protection of Real-Time Flows with | |||

with the Sliding Window RLC Codes . . . . . . . . . . . . 4 | the Sliding Window RLC Codes | |||

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

1.4. Document Organization . . . . . . . . . . . . . . . . . . 6 | 1.4. Document Organization | |||

2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6 | 2. Definitions and Abbreviations | |||

3. Common Procedures . . . . . . . . . . . . . . . . . . . . . . 7 | 3. Common Procedures | |||

3.1. Codec Parameters . . . . . . . . . . . . . . . . . . . . 7 | 3.1. Codec Parameters | |||

3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9 | 3.2. ADU, ADUI, and Source Symbols Mappings | |||

3.3. Encoding Window Management . . . . . . . . . . . . . . . 10 | 3.3. Encoding Window Management | |||

3.4. Source Symbol Identification . . . . . . . . . . . . . . 11 | 3.4. Source Symbol Identification | |||

3.5. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 11 | 3.5. Pseudorandom Number Generator (PRNG) | |||

3.6. Coding Coefficients Generation Function . . . . . . . . . 13 | 3.6. Coding Coefficients Generation Function | |||

3.7. Finite Fields Operations . . . . . . . . . . . . . . . . 15 | 3.7. Finite Field Operations | |||

3.7.1. Finite Field Definitions . . . . . . . . . . . . . . 15 | 3.7.1. Finite Field Definitions | |||

3.7.2. Linear Combination of Source Symbols Computation . . 15 | 3.7.2. Linear Combination of Source Symbol Computation | |||

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

4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 16 | 4.1. Formats and Codes | |||

4.1.1. FEC Framework Configuration Information . . . . . . . 16 | 4.1.1. FEC Framework Configuration Information | |||

4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 18 | 4.1.2. Explicit Source FEC Payload ID | |||

4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 18 | 4.1.3. Repair FEC Payload ID | |||

4.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 20 | 4.2. Procedures | |||

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

5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 20 | 5.1. Formats and Codes | |||

5.1.1. FEC Framework Configuration Information . . . . . . . 20 | 5.1.1. FEC Framework Configuration Information | |||

5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 20 | 5.1.2. Explicit Source FEC Payload ID | |||

5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20 | 5.1.3. Repair FEC Payload ID | |||

5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 21 | 5.2. Procedures | |||

6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 21 | 6. FEC Code Specification | |||

6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 21 | 6.1. Encoding Side | |||

6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 22 | 6.2. Decoding Side | |||

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 22 | 7. Security Considerations | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 23 | 7.1. Attacks Against the Data Flow | |||

8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 23 | 7.1.1. Access to Confidential Content | |||

8.1.1. Access to Confidential Content . . . . . . . . . . . 23 | 7.1.2. Content Corruption | |||

8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 23 | 7.2. Attacks Against the FEC Parameters | |||

8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 23 | 7.3. When Several Source Flows are to be Protected Together | |||

8.3. When Several Source Flows are to be Protected Together . 25 | 7.4. Baseline Secure FEC Framework Operation | |||

8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25 | 7.5. Additional Security Considerations for Numerical | |||

8.5. Additional Security Considerations for Numerical | Computations | |||

Computations . . . . . . . . . . . . . . . . . . . . . . 25 | 8. Operations and Management Considerations | |||

9. Operations and Management Considerations . . . . . . . . . . 26 | 8.1. Operational Recommendations: Finite Field GF(2) Versus | |||

9.1. Operational Recommendations: Finite Field GF(2) Versus | GF(2^(8)) | |||

GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26 | 8.2. Operational Recommendations: Coding Coefficients Density | |||

9.2. Operational Recommendations: Coding Coefficients Density | Threshold | |||

Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26 | 9. IANA Considerations | |||

10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 | 10. References | |||

11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 | 10.1. Normative References | |||

12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 | 10.2. Informative References | |||

12.1. Normative References . . . . . . . . . . . . . . . . . . 27 | Appendix A. TinyMT32 Validation Criteria (Normative) | |||

12.2. Informative References . . . . . . . . . . . . . . . . . 28 | Appendix B. Assessing the PRNG Adequacy (Informational) | |||

Appendix A. TinyMT32 Validation Criteria (Normative) . . . . . . 30 | Appendix C. Possible Parameter Derivation (Informational) | |||

Appendix B. Assessing the PRNG Adequacy (Informational) . . . . 31 | C.1. Case of a CBR Real-Time Flow | |||

Appendix C. Possible Parameter Derivation (Informational) . . . 33 | C.2. Other Types of Real-Time Flow | |||

C.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . . . 34 | C.3. Case of a Non-Real-Time Flow | |||

C.2. Other Types of Real-Time Flow . . . . . . . . . . . . . . 36 | ||||

C.3. Case of a Non Real-Time Flow . . . . . . . . . . . . . . 37 | ||||

Appendix D. Decoding Beyond Maximum Latency Optimization | Appendix D. Decoding Beyond Maximum Latency Optimization | |||

(Informational) . . . . . . . . . . . . . . . . . . 37 | (Informational) | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 38 | Acknowledgments | |||

Authors' Addresses | ||||

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

FLUTE/ALC protocol [RFC6726] when used for reliable file transfers | Delivery over Unidirectional Transport (FLUTE)/Asynchronous Layered | |||

Coding (ALC) protocol [RFC6726] when used for reliable file transfers | ||||

over lossy networks, and the FECFRAME protocol [RFC6363] when used | over lossy networks, and the FECFRAME protocol [RFC6363] when used | |||

for reliable 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, which is | |||

multicast/broadcast delivery mode, in particular for contents that | used in multicast/broadcast delivery mode, particularly for content | |||

feature stringent real-time constraints: each source packet has a | that features stringent real-time constraints: each source packet has | |||

maximum validity period after which it will not be considered by the | a maximum validity period after which it will not be considered by | |||

destination application. | the 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 an 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 an 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 | Solomon [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ | |||

[RFC6681], are all linear block codes: they require the data flow to | [RFC6681], are all linear block codes: they require the data flow to | |||

be segmented 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 | |||

skipping to change at page 4, line 33 ¶ | skipping to change at line 166 ¶ | |||

conditions one wants to support, but without exceeding the desired | conditions one wants to support, but without exceeding the desired | |||

maximum decoding latency. This choice then impacts the FEC-related | maximum decoding latency. This choice then impacts the FEC-related | |||

latency of all receivers, even those experiencing a good | latency of all receivers, even those experiencing a good | |||

communication quality, since no FEC encoding can happen until all the | communication quality, since no FEC encoding can happen until all the | |||

source data of the block is available at the sender, which directly | source data of the block is available at the sender, which directly | |||

depends on the block size. | depends on the block size. | |||

1.2. Lower Latency and Better Protection of Real-Time Flows with the | 1.2. Lower Latency and Better Protection of Real-Time Flows with the | |||

Sliding Window RLC Codes | Sliding Window RLC Codes | |||

This document introduces two fully-specified FEC Schemes that do not | This document introduces two fully specified FEC schemes that do not | |||

follow the block code approach: the Sliding Window Random Linear | follow the block code approach: the Sliding Window Random Linear | |||

Codes (RLC) over either Galois Fields (A.K.A. Finite Fields) GF(2) | Codes (RLC) over either Galois Fields (a.k.a., Finite Fields) GF(2) | |||

(the "binary case") or GF(2^^8), each time with the possibility of | (the "binary case") or GF(2^(8)), each time with the possibility of | |||

controlling the code density. These FEC Schemes are used to protect | controlling the code density. These FEC schemes are used to protect | |||

arbitrary media streams along the lines defined by FECFRAME extended | arbitrary media streams along the lines defined by FECFRAME extended | |||

to sliding window FEC codes [fecframe-ext]. These FEC Schemes, and | to Sliding Window FEC Codes [RFC8680]. These FEC schemes and, more | |||

more generally Sliding Window FEC codes, are recommended for | generally, Sliding Window FEC Codes are recommended, for instance, | |||

instance, with media that feature real-time constraints sent within a | with media that feature real-time constraints sent within a | |||

multicast/broadcast session [Roca17]. | multicast/broadcast session [Roca17]. | |||

The RLC codes belong to the broad class of sliding-window AL-FEC | The RLC codes belong to the broad class of Sliding Window AL-FEC | |||

codes (A.K.A. convolutional codes) [RFC8406]. The encoding process | Codes (a.k.a., convolutional codes) [RFC8406]. The encoding process | |||

is based on an encoding window that slides over the set of source | is based on an encoding window that slides over the set of source | |||

packets (in fact source symbols as we will see in Section 3.2), this | packets (in fact source symbols as we will see in Section 3.2), this | |||

window being either of fixed size or variable size (A.K.A. an elastic | window being either of fixed size or variable size (a.k.a., an | |||

window). Repair symbols are generated on-the-fly, by computing a | elastic window). Repair symbols are generated on-the-fly, by | |||

random linear combination of the source symbols present in the | computing a random linear combination of the source symbols present | |||

current encoding window, and passed to the transport layer. | in the 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. | |||

On the opposite, with a block code, recovering an isolated lost | On the opposite, with a block code, recovering an isolated lost | |||

source packet always requires waiting for the first repair packet to | source packet always requires waiting for the first repair packet to | |||

arrive after the end of the block. Additionally, under certain | arrive after the end of the block. Additionally, under certain | |||

situations (e.g., with a limited FEC-related latency budget and with | situations (e.g., with a limited FEC-related latency budget and with | |||

constant bitrate transmissions after FECFRAME encoding), sliding | constant bitrate transmissions after FECFRAME encoding), Sliding | |||

window codes can more efficiently achieve a target transmission | Window Codes can more efficiently achieve a target transmission | |||

quality (e.g., measured by the residual loss after FEC decoding) by | quality (e.g., measured by the residual loss after FEC decoding) by | |||

sending fewer repair packets (i.e., higher code rate) than block | sending fewer repair packets (i.e., higher code rate) than block | |||

codes. | codes. | |||

1.3. Small Transmission Overheads with the Sliding Window RLC FEC | 1.3. Small Transmission Overheads with the Sliding Window RLC FEC | |||

Scheme | Scheme | |||

The Sliding Window RLC FEC Scheme is designed to limit the packet | The Sliding Window RLC FEC scheme is designed to limit the packet | |||

header overhead. The main requirement is that each repair packet | header overhead. The main requirement is that each repair packet | |||

header must enable a receiver to reconstruct the set of source | header must enable a receiver to reconstruct the set of source | |||

symbols plus the associated coefficients used during the encoding | symbols plus the associated coefficients used during the encoding | |||

process. In order to minimize packet overhead, the set of source | process. In order to minimize packet overhead, the set of source | |||

symbols in the encoding window as well as the set of coefficients | symbols in the encoding window as well as the set of coefficients | |||

over GF(2^^m) (where m is 1 or 8, depending on the FEC Scheme) used | over GF(2^(m)) (where m is 1 or 8, depending on the FEC scheme) used | |||

in the linear combination are not individually listed in the repair | in the linear combination are not individually listed in the repair | |||

packet header. Instead, each FEC Repair Packet header contains: | packet header. Instead, each FEC Repair Packet header contains: | |||

o the Encoding Symbol Identifier (ESI) of the first source symbol in | * the Encoding Symbol Identifier (ESI) of the first source symbol in | |||

the encoding window as well as the number of symbols (since this | the encoding window as well as the number of symbols (since this | |||

number may vary with a variable size, elastic window). These two | number may vary with a variable size, elastic window). These two | |||

pieces of information enable each receiver to reconstruct the set | pieces of information enable each receiver to reconstruct the set | |||

of source symbols considered during encoding, the only constraint | of source symbols considered during encoding, the only constraint | |||

being that there cannot be any gap; | being that there cannot be any gap; | |||

o the seed and density threshold parameters used by a coding | ||||

* the seed and density threshold parameters used by a coding | ||||

coefficients generation function (Section 3.6). These two pieces | coefficients generation function (Section 3.6). These two pieces | |||

of information enable each receiver to generate the same set of | of information enable each receiver to generate the same set of | |||

coding coefficients over GF(2^^m) as the sender; | coding coefficients over GF(2^(m)) as the sender; | |||

Therefore, no matter the number of source symbols present in the | Therefore, no matter the number of source symbols present in the | |||

encoding window, each FEC Repair Packet features a fixed 64-bit long | encoding window, each FEC Repair Packet features a fixed 64-bit long | |||

header, called Repair FEC Payload ID (Figure 8). Similarly, each FEC | header, called Repair FEC Payload ID (Figure 8). Similarly, each FEC | |||

Source Packet features a fixed 32-bit long trailer, called Explicit | Source Packet features a fixed 32-bit long trailer, called Explicit | |||

Source FEC Payload ID (Figure 6), that contains the ESI of the first | Source FEC Payload ID (Figure 6), that contains the ESI of the first | |||

source symbol (Section 3.2). | source symbol (Section 3.2). | |||

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, pseudorandom number generator, and coding | |||

coefficients generation function; | coefficients generation function; | |||

4. Formats and Codes: This section defines the Source FEC Payload | ||||

ID and Repair FEC Payload ID formats, carrying the signaling | 4. Formats and Codes: This section defines the Source FEC Payload ID | |||

information associated to each source or repair symbol. It also | and Repair FEC Payload ID formats, carrying the signaling | |||

defines the FEC Framework Configuration Information (FFCI) | information associated to each source or repair symbol. It also | |||

carrying signaling information for the session; | defines the FEC Framework Configuration Information (FFCI) | |||

5. FEC Code Specification: Finally this section provides the code | carrying signaling information for the session; | |||

specification. | ||||

5. FEC Code Specification: Finally this section provides the code | ||||

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

This document uses the following definitions and abbreviations: | This document uses the following definitions and abbreviations: | |||

a^^b a to the power of b | a^(b) a to the power of b | |||

GF(q) denotes a finite field (also known as the Galois Field) with q | GF(q) denotes a finite field (also known as the Galois Field) with q | |||

elements. We assume that q = 2^^m in this document | elements. We assume that q = 2^(m) in this document | |||

m defines the length of the elements in the finite field, in bits. | m defines the length of the elements in the finite field, in bits. | |||

In this document, m is equal to 1 or 8 | In this document, m is equal to 1 or 8 | |||

ADU: Application Data Unit | ADU: Application Data Unit | |||

ADUI: Application Data Unit Information (includes the F, L and | ADUI: Application Data Unit Information (includes the F, L and | |||

padding fields in addition to the ADU) | padding fields in addition to the ADU) | |||

E: size of an encoding symbol (i.e., source or repair symbol), | ||||

E: size of an encoding symbol (i.e., source or repair symbol), | ||||

assumed fixed (in bytes) | assumed fixed (in bytes) | |||

br_in: transmission bitrate at the input of the FECFRAME sender, | br_in: transmission bitrate at the input of the FECFRAME sender, | |||

assumed fixed (in bits/s) | assumed fixed (in bits/s) | |||

br_out: transmission bitrate at the output of the FECFRAME sender, | br_out: transmission bitrate at the output of the FECFRAME sender, | |||

assumed fixed (in bits/s) | assumed fixed (in bits/s) | |||

max_lat: maximum FEC-related latency within FECFRAME (a decimal | max_lat: maximum FEC-related latency within FECFRAME (a decimal | |||

number expressed in seconds) | number expressed in seconds) | |||

cr: RLC coding rate, ratio between the total number of source | cr: RLC coding rate, ratio between the total number of source | |||

symbols and the total number of source plus repair symbols | symbols and the total number of source plus repair symbols | |||

ew_size: encoding window current size at a sender (in symbols) | ew_size: encoding window current size at a sender (in symbols) | |||

ew_max_size: encoding window maximum size at a sender (in symbols) | ew_max_size: encoding window maximum size at a sender (in symbols) | |||

dw_max_size: decoding window maximum size at a receiver (in symbols) | dw_max_size: decoding window maximum size at a receiver (in symbols) | |||

ls_max_size: linear system maximum size (or width) at a receiver (in | ls_max_size: linear system maximum size (or width) at a receiver (in | |||

symbols) | symbols) | |||

WSR: window size ratio parameter used to derive ew_max_size | WSR: window size ratio parameter used to derive ew_max_size | |||

(encoder) and ls_max_size (decoder). | (encoder) and ls_max_size (decoder). | |||

PRNG: pseudo-random number generator | ||||

PRNG: pseudorandom number generator | ||||

TinyMT32: PRNG used in this specification. | TinyMT32: PRNG used in this specification. | |||

DT: coding coefficients density threshold, an integer between 0 and | DT: coding coefficients density threshold, an integer between 0 and | |||

15 (inclusive) the controls the fraction of coefficients that are | 15 (inclusive) the controls the fraction of coefficients that are | |||

non zero | nonzero | |||

3. Common Procedures | 3. Common Procedures | |||

This section introduces the procedures that are used by these FEC | This section introduces the procedures that are used by these FEC | |||

Schemes. | schemes. | |||

3.1. Codec Parameters | 3.1. Codec Parameters | |||

A codec implementing the Sliding Window RLC FEC Scheme relies on | A codec implementing the Sliding Window RLC FEC scheme relies on | |||

several parameters: | several parameters: | |||

Maximum FEC-related latency budget, max_lat (a decimal number | Maximum FEC-related latency budget, max_lat (a decimal number | |||

expressed in seconds) with real-time flows: | expressed in seconds) with real-time flows: | |||

a source ADU flow can have real-time constraints, and therefore | a source ADU flow can have real-time constraints, and therefore | |||

any FECFRAME related operation should take place within the | any FECFRAME related operation should take place within the | |||

validity period of each ADU (Appendix D describes an exception to | validity period of each ADU (Appendix D describes an exception to | |||

this rule). When there are multiple flows with different real- | this rule). When there are multiple flows with different real- | |||

time constraints, we consider the most stringent constraints (see | time constraints, we consider the most stringent constraints (see | |||

[RFC6363], Section 10.2, item 6, for recommendations when several | item 6 in Section 10.2 of [RFC6363], for recommendations when | |||

flows are globally protected). The maximum FEC-related latency | several flows are globally protected). The maximum FEC-related | |||

budget, max_lat, accounts for all sources of latency added by FEC | latency budget, max_lat, accounts for all sources of latency added | |||

encoding (at a sender) and FEC decoding (at a receiver). Other | by FEC encoding (at a sender) and FEC decoding (at a receiver). | |||

sources of latency (e.g., added by network communications) are out | Other sources of latency (e.g., added by network communications) | |||

of scope and must be considered separately (said differently, they | are out of scope and must be considered separately (said | |||

have already been deducted from max_lat). max_lat can be regarded | differently, they have already been deducted from max_lat). | |||

as the latency budget permitted for all FEC-related operations. | max_lat can be regarded as the latency budget permitted for all | |||

This is an input parameter that enables a FECFRAME sender to | FEC-related operations. This is an input parameter that enables a | |||

derive other internal parameters (see Appendix C); | FECFRAME sender to 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 | |||

example, in the common case at session start, upon receiving new | example, in the common case at session start, upon receiving new | |||

source ADUs, the ew_size progressively increases until it reaches | source ADUs, the ew_size progressively increases until it reaches | |||

its maximum 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 | ||||

FECFRAME receiver, dw_max_size is the maximum number of received | Decoding window maximum size, dw_max_size (in symbols): | |||

or lost source symbols that are still within their latency budget; | at a FECFRAME receiver, dw_max_size is the maximum number of | |||

Linear system maximum size, ls_max_size (in symbols): at a FECFRAME | received or lost source symbols that are still within their | |||

receiver, the linear system maximum size, ls_max_size, is the | latency budget; | |||

maximum number of received or lost source symbols in the linear | ||||

system (i.e., the variables). It SHOULD NOT be smaller than | Linear system maximum size, ls_max_size (in symbols): | |||

dw_max_size since it would mean that, even after receiving a | at a FECFRAME receiver, the linear system maximum size, | |||

sufficient number of FEC Repair Packets, a lost ADU may not be | ls_max_size, is the maximum number of received or lost source | |||

recovered just because the associated source symbols have been | symbols in the linear system (i.e., the variables). It SHOULD NOT | |||

prematurely removed from the linear system, which is usually | be smaller than dw_max_size since it would mean that, even after | |||

counter-productive. On the opposite, the linear system MAY grow | receiving a sufficient number of FEC Repair Packets, a lost ADU | |||

beyond the dw_max_size (Appendix D); | may not be recovered just because the associated source symbols | |||

Symbol size, E (in bytes): the E parameter determines the source and | have been prematurely removed from the linear system, which is | |||

repair symbol sizes (necessarily equal). This is an input | usually counter-productive. On the opposite, the linear system | |||

MAY grow beyond the dw_max_size (Appendix D); | ||||

Symbol size, E (in bytes): | ||||

the E parameter determines the source and repair symbol sizes | ||||

(necessarily equal). This is an input parameter that enables a | ||||

FECFRAME sender to derive other internal parameters, as explained | ||||

below. An implementation at a sender MUST fix the E parameter and | ||||

MUST communicate it as part of the FEC Scheme-Specific Information | ||||

(Section 4.1.1.2). | ||||

Code rate, cr: | ||||

The code rate parameter determines the amount of redundancy added | ||||

to the flow. More precisely the cr is the ratio between the total | ||||

number of source symbols and the total number of source plus | ||||

repair symbols and by definition: 0 < cr <= 1. This is an input | ||||

parameter that enables a FECFRAME sender to derive other internal | parameter that enables a FECFRAME sender to derive other internal | |||

parameters, as explained below. An implementation at a sender | parameters, as explained below. However, there is no need to | |||

MUST fix the E parameter and MUST communicate it as part of the | communicate the cr parameter per see (it's not required to process | |||

FEC Scheme-Specific Information (Section 4.1.1.2). | a repair symbol at a receiver). This code rate parameter can be | |||

Code rate, cr: The code rate parameter determines the amount of | static. However, in specific use-cases (e.g., with unicast | |||

redundancy added to the flow. More precisely the cr is the ratio | transmissions in presence of a feedback mechanism that estimates | |||

between the total number of source symbols and the total number of | the communication quality, out of scope of FECFRAME), the code | |||

source plus repair symbols and by definition: 0 < cr <= 1. This | rate may be adjusted dynamically. | |||

is an input parameter that enables a FECFRAME sender to derive | ||||

other internal parameters, as explained below. However, there is | ||||

no need to communicate the cr parameter per see (it's not required | ||||

to process a repair symbol at a receiver). This code rate | ||||

parameter can be static. However, in specific use-cases (e.g., | ||||

with unicast transmissions in presence of a feedback mechanism | ||||

that estimates the communication quality, out of scope of | ||||

FECFRAME), the code rate may be adjusted dynamically. | ||||

Appendix C proposes non normative techniques 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 | |||

assigned to the right source flow (note that the 5-tuple used to | assigned to the right source flow (note that the 5-tuple used to | |||

identify the right source flow of a received ADU is absent with a | identify the right source flow of a received ADU is absent with a | |||

recovered ADU since it is not FEC protected). | recovered ADU since it is not FEC protected). | |||

Additionally, since ADUs are of variable size, padding is needed so | Additionally, since ADUs are of variable size, padding is needed so | |||

that each ADU (with its flow identifier) contribute to an integral | that each ADU (with its flow identifier) contribute to an integral | |||

number of source symbols. This requires adding the original ADU | number of source symbols. This requires adding the original ADU | |||

length to each ADU before doing FEC encoding. Because of these | length to each ADU before doing FEC encoding. Because of these | |||

requirements, an intermediate format, the ADUI, or ADU Information, | requirements, an intermediate format, the ADUI, or ADU Information, | |||

is considered [RFC6363]. | is considered [RFC6363]. | |||

For each incoming ADU, an ADUI MUST created as follows. First of | For each incoming ADU, an ADUI MUST be created as follows. First of | |||

all, 3 bytes are prepended (Figure 1): | all, 3 bytes are prepended (Figure 1): | |||

Flow ID (F) (8-bit field): this unsigned byte contains the integer | Flow ID (F) (8-bit field): this unsigned byte contains the integer | |||

identifier associated to the source ADU flow to which this ADU | identifier associated to the source ADU flow to which this ADU | |||

belongs. It is assumed that a single byte is sufficient, which | belongs. It is assumed that a single byte is sufficient, which | |||

implies that no more than 256 flows will be protected by a single | implies that no more than 256 flows will be protected by a single | |||

FECFRAME session instance. | FECFRAME session instance. | |||

Length (L) (16-bit field): this unsigned integer contains the length | Length (L) (16-bit field): this unsigned integer contains the length | |||

of this ADU, in network byte order (i.e., big endian). This | of this ADU, in network byte order (i.e., big endian). This | |||

length is for the ADU itself and does not include the F, L, or Pad | length is for the ADU itself and does not include the F, L, or Pad | |||

fields. | fields. | |||

Then, zero padding is added to the ADU if needed: | Then, zero padding is added to the ADU if needed: | |||

Padding (Pad) (variable size field): this field contains zero | Padding (Pad) (variable size field): this field contains zero | |||

padding to align the F, L, ADU and padding up to a size that is | padding to align the F, L, ADU and padding up to a size that is | |||

multiple of E bytes (i.e., the source and repair symbol length). | multiple of E bytes (i.e., the source and repair symbol length). | |||

skipping to change at page 10, line 11 ¶ | skipping to change at line 454 ¶ | |||

called ADUI. Since ADUs can have different sizes, this is also the | called ADUI. Since ADUs can have different sizes, this is also the | |||

case for ADUIs. However, an ADUI always contributes to an integral | case for ADUIs. However, an ADUI always contributes to an integral | |||

number of source symbols. | number of source symbols. | |||

symbol length, E E E | symbol length, E E E | |||

< ------------------ >< ------------------ >< ------------------ > | < ------------------ >< ------------------ >< ------------------ > | |||

+-+--+---------------------------------------------+-------------+ | +-+--+---------------------------------------------+-------------+ | |||

|F| L| ADU | Pad | | |F| L| ADU | Pad | | |||

+-+--+---------------------------------------------+-------------+ | +-+--+---------------------------------------------+-------------+ | |||

Figure 1: ADUI Creation example (here 3 source symbols are created | Figure 1: ADUI Creation Example, Resulting in Three Source Symbols | |||

for this ADUI). | ||||

Note that neither the initial 3 bytes nor the optional padding are | Note that neither the initial 3 bytes nor the optional padding are | |||

sent over the network. However, they are considered during FEC | sent over the network. However, they are considered during FEC | |||

encoding, and a receiver who lost a certain FEC Source Packet (e.g., | encoding, and a receiver that lost a certain FEC Source Packet (e.g., | |||

the UDP datagram containing this FEC Source Packet when UDP is used | the UDP datagram containing this FEC Source Packet when UDP is used | |||

as the transport protocol) will be able to recover the ADUI if FEC | as the transport protocol) will be able to recover the ADUI if FEC | |||

decoding succeeds. Thanks to the initial 3 bytes, this receiver will | decoding succeeds. Thanks to the initial 3 bytes, this receiver will | |||

get rid of the padding (if any) and identify the corresponding ADU | get rid of the padding (if any) and identify the corresponding ADU | |||

flow. | flow. | |||

3.3. Encoding Window Management | 3.3. Encoding Window Management | |||

Source symbols and the corresponding ADUs are removed from the | Source symbols and the corresponding ADUs are removed from the | |||

encoding window: | encoding window: | |||

o when the sliding encoding window has reached its maximum size, | * when the sliding encoding window has reached its maximum size, | |||

ew_max_size. In that case the oldest symbol MUST be removed | ew_max_size. In that case the oldest symbol MUST be removed | |||

before adding a new symbol, so that the current encoding window | before adding a new symbol, so that the current encoding window | |||

size always remains inferior or equal to the maximum size: ew_size | size always remains inferior or equal to the maximum size: ew_size | |||

<= ew_max_size; | <= ew_max_size; | |||

o when an ADU has reached its maximum validity duration in case of a | ||||

* when an ADU has reached its maximum validity duration in case of a | ||||

real-time flow. When this happens, all source symbols | real-time flow. When this happens, all source symbols | |||

corresponding to the ADUI that expired SHOULD be removed from the | corresponding to the ADUI that expired SHOULD be removed from the | |||

encoding window; | encoding window; | |||

Source symbols are added to the sliding encoding window each time a | Source symbols are added to the sliding encoding window each time a | |||

new ADU arrives, once the ADU-to-source symbols mapping has been | new ADU arrives, once the ADU-to-source symbols mapping has been | |||

performed (Section 3.2). The current size of the encoding window, | performed (Section 3.2). The current size of the encoding window, | |||

ew_size, is updated after adding new source symbols. This process | ew_size, is updated after adding new source symbols. This process | |||

may require to remove old source symbols so that: ew_size <= | may require to remove old source symbols so that: ew_size <= | |||

ew_max_size. | ew_max_size. | |||

skipping to change at page 11, line 11 ¶ | skipping to change at line 500 ¶ | |||

complexity reasons). This factor may further limit the ew_max_size | complexity reasons). This factor may further limit the ew_max_size | |||

value, in addition to the maximum FEC-related latency budget | value, in addition to the maximum FEC-related latency budget | |||

(Section 3.1). | (Section 3.1). | |||

3.4. Source Symbol Identification | 3.4. Source Symbol Identification | |||

Each source symbol is identified by an Encoding Symbol ID (ESI), an | Each source symbol is identified by an Encoding Symbol ID (ESI), an | |||

unsigned integer. The ESI of source symbols MUST start with value 0 | unsigned integer. The ESI of source symbols MUST start with value 0 | |||

for the first source symbol and MUST be managed sequentially. | for the first source symbol and MUST be managed sequentially. | |||

Wrapping to zero happens after reaching the maximum value made | Wrapping to zero happens after reaching the maximum value made | |||

possible by the ESI field size (this maximum value is FEC Scheme | possible by the ESI field size (this maximum value is FEC scheme | |||

dependant, for instance, 2^32-1 with FEC Schemes XXX and YYY). | dependent, for instance, 2^(32)-1 with FEC schemes 9 and 10). | |||

No such consideration applies to repair symbols. | No such consideration applies to repair symbols. | |||

3.5. Pseudo-Random Number Generator (PRNG) | 3.5. Pseudorandom Number Generator (PRNG) | |||

In order to compute coding coefficients (see Section 3.6), the RLC | In order to compute coding coefficients (see Section 3.6), the RLC | |||

FEC Schemes rely on the TinyMT32 PRNG defined in [tinymt32] with two | FEC schemes rely on the TinyMT32 PRNG defined in [RFC8682] with two | |||

additional functions defined in this section. | additional functions defined in this section. | |||

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 practice, how to manage the seed and Repair_Key | (Section 4.1.3). In practice, how to manage the seed and Repair_Key | |||

values (both are equal) is left to the implementer, using a | values (both are equal) is left to the implementer, using a | |||

monotonically increasing counter being one possibility (Section 6.1). | monotonically increasing counter being one possibility (Section 6.1). | |||

In addition to the seed, this function takes as parameter a pointer | 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 | to an instance of a tinymt32_t structure that is used to keep the | |||

internal state of the PRNG. | internal state of the PRNG. | |||

Then, each time a new pseudo-random integer between 0 and 15 | Then, each time a new pseudorandom integer between 0 and 15 inclusive | |||

inclusive (4-bit pseudo-random integer) is needed, the following | (4-bit pseudorandom integer) is needed, the following function is | |||

function is used: | 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). | |||

Similarly, each time a new pseudo-random integer between 0 and 255 | Similarly, each time a new pseudorandom integer between 0 and 255 | |||

inclusive (8-bit pseudo-random integer) is needed, the following | inclusive (8-bit pseudorandom integer) is needed, the following | |||

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 pseudorandom number generated by the | |||

tinymt32_generate_uint32() function of [tinymt32]. This is done by | tinymt32_generate_uint32() function of [RFC8682]. 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. This is a C language implementation, | a possible implementation. This is a C language implementation, | |||

written for C99 [C99]. Test results discussed in Appendix B show | 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 pseudorandom 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. | |||

*/ | */ | |||

uint32_t tinymt32_rand16(tinymt32_t *s) | uint32_t tinymt32_rand16(tinymt32_t *s) | |||

{ | { | |||

return (tinymt32_generate_uint32(s) & 0xF); | return (tinymt32_generate_uint32(s) & 0xF); | |||

} | } | |||

/** | /** | |||

* This function outputs a pseudo-random integer in [0 .. 255] range. | * This function outputs a pseudorandom integer in [0 .. 255] range. | |||

* | * | |||

* @param s pointer to tinymt internal state. | * @param s pointer to tinymt internal state. | |||

* @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 have the same output as that | Any implementation of this PRNG MUST have the same output as that | |||

provided by the reference implementation of [tinymt32]. In order to | provided by the reference implementation of [RFC8682]. In order to | |||

increase the compliancy confidence, three criteria are proposed: the | increase the compliance confidence, three criteria are proposed: the | |||

one described in [tinymt32] (for the TinyMT32 32-bit unsigned integer | one described in [RFC8682] (for the TinyMT32 32-bit unsigned integer | |||

generator), and the two others detailed in Appendix A (for the | 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 to 4-bit and 8-bit intervals). Because of the way the | |||

mapping functions work, it is unlikely that an implementation that | mapping functions work, it is unlikely that an implementation that | |||

fulfills the first criterion fails to fulfill the two others. | 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 nonzero (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 nonzero 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 nonzero (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() | Figure 3 shows the reference generate_coding_coefficients() | |||

implementation. This is a C language implementation, written for C99 | implementation. This is a C language implementation, written for C99 | |||

[C99]. | [C99]. | |||

<CODE BEGINS> | <CODE BEGINS> | |||

#include <string.h> | #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) | |||

skipping to change at page 13, line 45 ¶ | skipping to change at line 629 ¶ | |||

* 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 cc_tab table. This | * (in) cc_nb number of entries in the cc_tab table. This | |||

* value is equal to the current encoding window | * value is equal to the current encoding window | |||

* size. | * 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 nonzero | |||

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

skipping to change at page 15, line 15 ¶ | skipping to change at line 695 ¶ | |||

} | } | |||

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: Reference Implementation of the Coding Coefficients | |||

Implementation | Generation Function | |||

3.7. Finite Fields Operations | 3.7. Finite Field 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 is 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 Symbol 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 | |||

This fully-specified FEC Scheme defines the Sliding Window Random | This fully-specified FEC scheme defines the Sliding Window Random | |||

Linear Codes (RLC) over GF(2^^8). | Linear Codes (RLC) over GF(2^(8)). | |||

4.1. Formats and Codes | 4.1. Formats and Codes | |||

4.1.1. FEC Framework Configuration Information | 4.1.1. FEC Framework Configuration Information | |||

Following the guidelines of [RFC6363], section 5.6, this section | Following the guidelines of Section 5.6 of [RFC6363], this section | |||

provides the FEC Framework Configuration Information (or FFCI). This | provides the FEC Framework Configuration Information (or FFCI). This | |||

FCCI needs to be shared (e.g., using SDP) between the FECFRAME sender | FCCI needs to be shared (e.g., using SDP) between the FECFRAME sender | |||

and receiver instances in order to synchronize them. It includes a | and receiver instances in order to synchronize them. It includes a | |||

FEC Encoding ID, mandatory for any FEC Scheme specification, plus | FEC Encoding ID, mandatory for any FEC scheme specification, plus | |||

scheme-specific elements. | scheme-specific elements. | |||

4.1.1.1. FEC Encoding ID | 4.1.1.1. FEC Encoding ID | |||

o FEC Encoding ID: the value assigned to this fully specified FEC | FEC Encoding ID: the value assigned to this fully specified FEC | |||

Scheme MUST be XXXX, as assigned by IANA (Section 10). | scheme MUST be 10, as assigned by IANA (Section 9). | |||

When SDP is used to communicate the FFCI, this FEC Encoding ID is | When SDP is used to communicate the FFCI, this FEC Encoding ID is | |||

carried in the 'encoding-id' parameter. | carried in the 'encoding-id' parameter. | |||

4.1.1.2. FEC Scheme-Specific Information | 4.1.1.2. FEC Scheme-Specific Information | |||

The FEC Scheme-Specific Information (FSSI) includes elements that are | The FEC Scheme-Specific Information (FSSI) includes elements that are | |||

specific to the present FEC Scheme. More precisely: | specific to the present FEC scheme. More precisely: | |||

Encoding symbol size (E): a non-negative integer that indicates the | Encoding symbol size (E): a non-negative integer that indicates the | |||

size of each encoding symbol in bytes; | size of each encoding symbol in bytes; | |||

Window Size Ratio (WSR) parameter: a non-negative integer between 0 | ||||

Window Size Ratio (WSR) parameter: a non-negative integer between 0 | ||||

and 255 (both inclusive) used to initialize window sizes. A value | and 255 (both inclusive) used to initialize window sizes. A value | |||

of 0 indicates this parameter is not considered (e.g., a fixed | of 0 indicates this parameter is not considered (e.g., a fixed | |||

encoding window size may be chosen). A value between 1 and 255 | encoding window size may be chosen). A value between 1 and 255 | |||

inclusive is required by certain of the parameter derivation | inclusive is required by certain of the parameter derivation | |||

techniques described in Appendix C; | techniques described in Appendix C; | |||

This element is required both by the sender (RLC encoder) and the | This element is required both by the sender (RLC encoder) and the | |||

receiver(s) (RLC decoder). | receiver(s) (RLC decoder). | |||

When SDP is used to communicate the FFCI, this FEC Scheme-specific | When SDP is used to communicate the FFCI, this FEC Scheme-Specific | |||

information is carried in the 'fssi' parameter in textual | Information is carried in the 'fssi' parameter in textual | |||

representation as specified in [RFC6364]. For instance: | representation as specified in [RFC6364]. For instance: | |||

fssi=E:1400,WSR:191 | fssi=E:1400,WSR:191 | |||

In that case the name values "E" and "WSR" are used to convey the E | In that case the name values "E" and "WSR" are used to convey the E | |||

and WSR parameters respectively. | and WSR parameters respectively. | |||

If another mechanism requires the FSSI to be carried as an opaque | If another mechanism requires the FSSI to be carried as an opaque | |||

octet string, the encoding format consists of the following three | octet string, the encoding format consists of the following three | |||

octets, where the E field is carried in "big-endian" or "network | octets, where the E field is carried in "big-endian" or "network | |||

order" format, that is, most significant byte first: | order" format, that is, most significant byte first: | |||

Encoding symbol length (E): 16-bit field; | Encoding symbol length (E): 16-bit field; | |||

skipping to change at page 17, line 48 ¶ | skipping to change at line 823 ¶ | |||

These three octets can be communicated as such, or for instance, be | These three octets can be communicated as such, or for instance, be | |||

subject to an additional Base64 encoding. | subject to an additional Base64 encoding. | |||

0 1 2 | 0 1 2 | |||

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Encoding Symbol Length (E) | WSR | | | Encoding Symbol Length (E) | WSR | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 4: FSSI Encoding Format | Figure 4: FSSI Encoding Format | |||

4.1.2. Explicit Source FEC Payload ID | 4.1.2. Explicit Source FEC Payload ID | |||

A FEC Source Packet MUST contain an Explicit Source FEC Payload ID | A FEC Source Packet MUST contain an Explicit Source FEC Payload ID | |||

that is appended to the end of the packet as illustrated in Figure 5. | that is appended to the end of the packet as illustrated in Figure 5. | |||

+--------------------------------+ | +--------------------------------+ | |||

| IP Header | | | IP Header | | |||

+--------------------------------+ | +--------------------------------+ | |||

| Transport Header | | | Transport Header | | |||

+--------------------------------+ | +--------------------------------+ | |||

| ADU | | | ADU | | |||

+--------------------------------+ | +--------------------------------+ | |||

| Explicit Source FEC Payload ID | | | Explicit Source FEC Payload ID | | |||

+--------------------------------+ | +--------------------------------+ | |||

Figure 5: Structure of an FEC Source Packet with the Explicit Source | Figure 5: Structure of an FEC Source Packet with the Explicit | |||

FEC Payload ID | Source FEC Payload ID | |||

More precisely, the Explicit Source FEC Payload ID is composed of the | More precisely, the Explicit Source FEC Payload ID is composed of the | |||

following field, carried in "big-endian" or "network order" format, | following field, carried in "big-endian" or "network order" format, | |||

that is, most significant byte first (Figure 6): | that is, most significant byte first (Figure 6): | |||

Encoding Symbol ID (ESI) (32-bit field): this unsigned integer | Encoding Symbol ID (ESI) (32-bit field): this unsigned integer | |||

identifies the first source symbol of the ADUI corresponding to | identifies the first source symbol of the ADUI corresponding to | |||

this FEC Source Packet. The ESI is incremented for each new | this FEC Source Packet. The ESI is incremented for each new | |||

source symbol, and after reaching the maximum value (2^32-1), | source symbol, and after reaching the maximum value (2^(32)-1), | |||

wrapping to zero occurs. | wrapping to zero occurs. | |||

0 1 2 3 | 0 1 2 3 | |||

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Encoding Symbol ID (ESI) | | | Encoding Symbol ID (ESI) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 6: Source FEC Payload ID Encoding Format | Figure 6: Source FEC Payload ID Encoding Format | |||

skipping to change at page 19, line 19 ¶ | skipping to change at line 886 ¶ | |||

| IP Header | | | IP Header | | |||

+--------------------------------+ | +--------------------------------+ | |||

| Transport Header | | | Transport Header | | |||

+--------------------------------+ | +--------------------------------+ | |||

| Repair FEC Payload ID | | | Repair FEC Payload ID | | |||

+--------------------------------+ | +--------------------------------+ | |||

| Repair Symbol | | | Repair Symbol | | |||

+--------------------------------+ | +--------------------------------+ | |||

Figure 7: Structure of an FEC Repair Packet with the Repair FEC | Figure 7: Structure of an FEC Repair Packet with the Repair FEC | |||

Payload ID | Payload ID | |||

More precisely, the Repair FEC Payload ID is composed of the | More precisely, the Repair FEC Payload ID is composed of the | |||

following fields where all integer fields are carried in "big-endian" | following fields where all integer fields are carried in "big-endian" | |||

or "network order" format, that is, most significant byte first | or "network order" format, that is, most significant byte first | |||

(Figure 8): | (Figure 8): | |||

Repair_Key (16-bit field): this unsigned integer is used as a seed | Repair_Key (16-bit field): this unsigned integer is used as a seed | |||

by the coefficient generation function (Section 3.6) in order to | by the coefficient generation function (Section 3.6) in order to | |||

generate the desired number of coding coefficients. This repair | generate the desired number of coding coefficients. This repair | |||

key may be a monotonically increasing integer value that loops | key may be a monotonically increasing integer value that loops | |||

skipping to change at page 19, line 35 ¶ | skipping to change at line 902 ¶ | |||

Repair_Key (16-bit field): this unsigned integer is used as a seed | Repair_Key (16-bit field): this unsigned integer is used as a seed | |||

by the coefficient generation function (Section 3.6) in order to | by the coefficient generation function (Section 3.6) in order to | |||

generate the desired number of coding coefficients. This repair | generate the desired number of coding coefficients. This repair | |||

key may be a monotonically increasing integer value that loops | key may be a monotonically increasing integer value that loops | |||

back to 0 after reaching 65535 (see Section 6.1). When a FEC | back to 0 after reaching 65535 (see Section 6.1). When a FEC | |||

Repair Packet contains several repair symbols, this repair key | Repair Packet contains several repair symbols, this repair key | |||

value is that of the first repair symbol. The remaining repair | value is that of the first repair symbol. The remaining repair | |||

keys can be deduced by incrementing by 1 this value, up to a | keys can be deduced by incrementing by 1 this value, up to a | |||

maximum value of 65535 after which it loops back to 0. | maximum value of 65535 after which it loops back to 0. | |||

Density Threshold for the coding coefficients, DT (4-bit field): | Density Threshold for the coding coefficients, DT (4-bit field): | |||

this unsigned integer carries the Density Threshold (DT) used by | this unsigned integer carries the Density Threshold (DT) used by | |||

the coding coefficient generation function Section 3.6. More | the coding coefficient generation function Section 3.6. More | |||

precisely, it controls the probability of having a non zero coding | precisely, it controls the probability of having a nonzero coding | |||

coefficient, which equals (DT+1) / 16. When a FEC Repair Packet | coefficient, which equals (DT+1) / 16. When a FEC Repair Packet | |||

contains several repair symbols, the DT value applies to all of | contains several repair symbols, the DT value applies to all of | |||

them; | them; | |||

Number of Source Symbols in the encoding window, NSS (12-bit field): | ||||

Number of Source Symbols in the encoding window, NSS (12-bit | ||||

field): | ||||

this unsigned integer indicates the number of source symbols in | this unsigned integer indicates the number of source symbols in | |||

the encoding window when this repair symbol was generated. When a | the encoding window when this repair symbol was generated. When a | |||

FEC Repair Packet contains several repair symbols, this NSS value | FEC Repair Packet contains several repair symbols, this NSS value | |||

applies to all of them; | applies to all of them; | |||

ESI of First Source Symbol in the encoding window, FSS_ESI (32-bit | ESI of First Source Symbol in the encoding window, FSS_ESI (32-bit | |||

field): | field): | |||

this unsigned integer indicates the ESI of the first source symbol | this unsigned integer indicates the ESI of the first source symbol | |||

in the encoding window when this repair symbol was generated. | in the encoding window when this repair symbol was generated. | |||

When a FEC Repair Packet contains several repair symbols, this | When a FEC Repair Packet contains several repair symbols, this | |||

FSS_ESI value applies to all of them; | FSS_ESI value applies to all of them; | |||

0 1 2 3 | 0 1 2 3 | |||

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Repair_Key | DT |NSS (# src symb in ew) | | | Repair_Key | DT |NSS (# src symb in ew) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| FSS_ESI | | | FSS_ESI | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

skipping to change at page 20, line 20 ¶ | skipping to change at line 937 ¶ | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Repair_Key | DT |NSS (# src symb in ew) | | | Repair_Key | DT |NSS (# src symb in ew) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| FSS_ESI | | | FSS_ESI | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 8: Repair FEC Payload ID Encoding Format | Figure 8: Repair FEC Payload ID Encoding Format | |||

4.2. Procedures | 4.2. Procedures | |||

All the procedures of Section 3 apply to this FEC Scheme. | All the procedures of Section 3 apply to this FEC scheme. | |||

5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet Flows | 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary Packet Flows | |||

This fully-specified FEC Scheme defines the Sliding Window Random | This fully-specified FEC scheme defines the Sliding Window Random | |||

Linear Codes (RLC) over GF(2) (binary case). | Linear Codes (RLC) over GF(2) (binary case). | |||

5.1. Formats and Codes | 5.1. Formats and Codes | |||

5.1.1. FEC Framework Configuration Information | 5.1.1. FEC Framework Configuration Information | |||

5.1.1.1. FEC Encoding ID | 5.1.1.1. FEC Encoding ID | |||

o FEC Encoding ID: the value assigned to this fully specified FEC | FEC Encoding ID: the value assigned to this fully specified FEC | |||

Scheme MUST be YYYY, as assigned by IANA (Section 10). | scheme MUST be 9, as assigned by IANA (Section 9). | |||

When SDP is used to communicate the FFCI, this FEC Encoding ID is | When SDP is used to communicate the FFCI, this FEC Encoding ID is | |||

carried in the 'encoding-id' parameter. | carried in the 'encoding-id' parameter. | |||

5.1.1.2. FEC Scheme-Specific Information | 5.1.1.2. FEC Scheme-Specific Information | |||

All the considerations of Section 4.1.1.2 apply here. | All the considerations of Section 4.1.1.2 apply here. | |||

5.1.2. Explicit Source FEC Payload ID | 5.1.2. Explicit Source FEC Payload ID | |||

skipping to change at page 21, line 9 ¶ | skipping to change at line 975 ¶ | |||

All the considerations of Section 4.1.3 apply here, with the only | All the considerations of Section 4.1.3 apply here, with the only | |||

exception that the Repair_Key field is useless if DT = 15 (indeed, in | exception that the Repair_Key field is useless if DT = 15 (indeed, in | |||

that case all the coefficients are necessarily equal to 1 and the | that case all the coefficients are necessarily equal to 1 and the | |||

coefficient generation function does not use any PRNG). When DT = 15 | coefficient generation function does not use any PRNG). When DT = 15 | |||

the FECFRAME sender MUST set the Repair_Key field to zero on | the FECFRAME sender MUST set the Repair_Key field to zero on | |||

transmission and a receiver MUST ignore it on receipt. | transmission and a receiver MUST ignore it on receipt. | |||

5.2. Procedures | 5.2. Procedures | |||

All the procedures of Section 3 apply to this FEC Scheme. | All the procedures of Section 3 apply to this FEC scheme. | |||

6. FEC Code Specification | 6. FEC Code Specification | |||

6.1. Encoding Side | 6.1. Encoding Side | |||

This section provides a high level description of a Sliding Window | This section provides a high level description of a Sliding Window | |||

RLC encoder. | RLC encoder. | |||

Whenever a new FEC Repair Packet is needed, the RLC encoder instance | Whenever a new FEC Repair Packet is needed, the RLC encoder instance | |||

first gathers the ew_size source symbols currently in the sliding | first gathers the ew_size source symbols currently in the sliding | |||

skipping to change at page 22, line 47 ¶ | skipping to change at line 1057 ¶ | |||

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

document. Additionally, Appendix D discusses a backward compatible | document. Additionally, Appendix D discusses a backward compatible | |||

optimization whereby late source symbols MAY still be used within the | optimization whereby late source symbols MAY still be used within the | |||

FECFRAME receiver in order to improve transmission robustness. | FECFRAME receiver in order to improve transmission robustness. | |||

7. Implementation Status | 7. Security Considerations | |||

Editor's notes: RFC Editor, please remove this section motivated by | ||||

RFC 6982 before publishing the RFC. Thanks. | ||||

An implementation of the Sliding Window RLC FEC Scheme for FECFRAME | ||||

exists: | ||||

o Organisation: Inria | ||||

o Description: This is an implementation of the Sliding Window RLC | ||||

FEC Scheme limited to GF(2^^8). It relies on a modified version | ||||

of our OpenFEC (http://openfec.org) FEC code library. It is | ||||

integrated in our FECFRAME software (see [fecframe-ext]). | ||||

o Maturity: prototype. | ||||

o Coverage: this software complies with the Sliding Window RLC FEC | ||||

Scheme. | ||||

o Licensing: proprietary. | ||||

o Contact: vincent.roca@inria.fr | ||||

8. Security Considerations | ||||

The FEC Framework document [RFC6363] provides a fairly comprehensive | The FEC Framework document [RFC6363] provides a fairly comprehensive | |||

analysis of security considerations applicable to FEC Schemes. | analysis of security considerations applicable to FEC schemes. | |||

Therefore, the present section follows the security considerations | Therefore, the present section follows the security considerations | |||

section of [RFC6363] and only discusses specific topics. | section of [RFC6363] and only discusses specific topics. | |||

8.1. Attacks Against the Data Flow | 7.1. Attacks Against the Data Flow | |||

8.1.1. Access to Confidential Content | 7.1.1. Access to Confidential Content | |||

The Sliding Window RLC FEC Scheme specified in this document does not | The Sliding Window RLC FEC scheme specified in this document does not | |||

change the recommendations of [RFC6363]. To summarize, if | change the recommendations of [RFC6363]. To summarize, if | |||

confidentiality is a concern, it is RECOMMENDED that one of the | confidentiality is a concern, it is RECOMMENDED that one of the | |||

solutions mentioned in [RFC6363] is used with special considerations | solutions mentioned in [RFC6363] is used with special considerations | |||

to the way this solution is applied (e.g., is encryption applied | to the way this solution is applied (e.g., is encryption applied | |||

before or after FEC protection, within the end-system or in a | before or after FEC protection, within the end system or in a | |||

middlebox), to the operational constraints (e.g., performing FEC | middlebox), to the operational constraints (e.g., performing FEC | |||

decoding in a protected environment may be complicated or even | decoding in a protected environment may be complicated or even | |||

impossible) and to the threat model. | impossible) and to the threat model. | |||

8.1.2. Content Corruption | 7.1.2. Content Corruption | |||

The Sliding Window RLC FEC Scheme specified in this document does not | The Sliding Window RLC FEC scheme specified in this document does not | |||

change the recommendations of [RFC6363]. To summarize, it is | change the recommendations of [RFC6363]. To summarize, it is | |||

RECOMMENDED that one of the solutions mentioned in [RFC6363] is used | RECOMMENDED that one of the solutions mentioned in [RFC6363] is used | |||

on both the FEC Source and Repair Packets. | on both the FEC Source and Repair Packets. | |||

8.2. Attacks Against the FEC Parameters | 7.2. Attacks Against the FEC Parameters | |||

The FEC Scheme specified in this document defines parameters that can | The FEC scheme specified in this document defines parameters that can | |||

be the basis of attacks. More specifically, the following parameters | be the basis of attacks. More specifically, the following parameters | |||

of the FFCI may be modified by an attacker who targets receivers | of the FFCI may be modified by an attacker who targets receivers | |||

(Section 4.1.1.2): | (Section 4.1.1.2): | |||

o FEC Encoding ID: changing this parameter leads a receiver to | FEC Encoding ID: changing this parameter leads a receiver to | |||

consider a different FEC Scheme. The consequences are severe, the | consider a different FEC scheme. The consequences are severe, the | |||

format of the Explicit Source FEC Payload ID and Repair FEC | format of the Explicit Source FEC Payload ID and Repair FEC | |||

Payload ID of received packets will probably differ, leading to | Payload ID of received packets will probably differ, leading to | |||

various malfunctions. Even if the original and modified FEC | various malfunctions. Even if the original and modified FEC | |||

Schemes share the same format, FEC decoding will either fail or | schemes share the same format, FEC decoding will either fail or | |||

lead to corrupted decoded symbols. This will happen if an | lead to corrupted decoded symbols. This will happen if an | |||

attacker turns value YYYY (i.e., RLC over GF(2)) to value XXXX | attacker turns value 9 (i.e., RLC over GF(2)) to value 10 (RLC | |||

(RLC over GF(2^^8)), an additional consequence being a higher | over GF(2^(8))), an additional consequence being a higher | |||

processing overhead at the receiver. In any case, the attack | processing overhead at the receiver. In any case, the attack | |||

results in a form of Denial of Service (DoS) or corrupted content. | results in a form of Denial of Service (DoS) or corrupted content. | |||

o Encoding symbol length (E): setting this E parameter to a | ||||

different value will confuse a receiver. If the size of a | Encoding symbol length (E): setting this E parameter to a different | |||

received FEC Repair Packet is no longer multiple of the modified E | value will confuse a receiver. If the size of a received FEC | |||

value, a receiver quickly detects a problem and SHOULD reject the | Repair Packet is no longer multiple of the modified E value, a | |||

packet. If the new E value is a sub-multiple of the original E | receiver quickly detects a problem and SHOULD reject the packet. | |||

value (e.g., half the original value), then receivers may not | If the new E value is a sub-multiple of the original E value | |||

detect the problem immediately. For instance, a receiver may | (e.g., half the original value), then receivers may not detect the | |||

think that a received FEC Repair Packet contains more repair | problem immediately. For instance, a receiver may think that a | |||

symbols (e.g., twice as many if E is reduced by half), leading to | received FEC Repair Packet contains more repair symbols (e.g., | |||

malfunctions whose nature depends on implementation details. Here | twice as many if E is reduced by half), leading to malfunctions | |||

also, the attack always results in a form of DoS or corrupted | whose nature depends on implementation details. Here also, the | |||

content. | attack always results in a form of DoS or corrupted content. | |||

It is therefore RECOMMENDED that security measures be taken to | It is therefore RECOMMENDED that security measures be taken to | |||

guarantee the FFCI integrity, as specified in [RFC6363]. How to | guarantee the FFCI integrity, as specified in [RFC6363]. How to | |||

achieve this depends on the way the FFCI is communicated from the | achieve this depends on the way the FFCI is communicated from the | |||

sender to the receiver, which is not specified in this document. | sender to the receiver, which is not specified in this document. | |||

Similarly, attacks are possible against the Explicit Source FEC | Similarly, attacks are possible against the Explicit Source FEC | |||

Payload ID and Repair FEC Payload ID. More specifically, in case of | Payload ID and Repair FEC Payload ID. More specifically, in case of | |||

a FEC Source Packet, the following value can be modified by an | a FEC Source Packet, the following value can be modified by an | |||

attacker who targets receivers: | attacker who targets receivers: | |||

o Encoding Symbol ID (ESI): changing the ESI leads a receiver to | Encoding Symbol ID (ESI): changing the ESI leads a receiver to | |||

consider a wrong ADU, resulting in severe consequences, including | consider a wrong ADU, resulting in severe consequences, including | |||

corrupted content passed to the receiving application; | corrupted content passed to the receiving application; | |||

And in case of a FEC Repair Packet: | And in case of a FEC Repair Packet: | |||

o Repair Key: changing this value leads a receiver to generate a | Repair Key: changing this value leads a receiver to generate a wrong | |||

wrong coding coefficient sequence, and therefore any source symbol | coding coefficient sequence, and therefore any source symbol | |||

decoded using the repair symbols contained in this packet will be | decoded using the repair symbols contained in this packet will be | |||

corrupted; | corrupted; | |||

o DT: changing this value also leads a receiver to generate a wrong | ||||

DT: changing this value also leads a receiver to generate a wrong | ||||

coding coefficient sequence, and therefore any source symbol | coding coefficient sequence, and therefore any source symbol | |||

decoded using the repair symbols contained in this packet will be | decoded using the repair symbols contained in this packet will be | |||

corrupted. In addition, if the DT value is significantly | corrupted. In addition, if the DT value is significantly | |||

increased, it will generate a higher processing overhead at a | increased, it will generate a higher processing overhead at a | |||

receiver. In case of very large encoding windows, this may impact | receiver. In case of very large encoding windows, this may impact | |||

the terminal performance; | the terminal performance; | |||

o NSS: changing this value leads a receiver to consider a different | ||||

NSS: changing this value leads a receiver to consider a different | ||||

set of source symbols, and therefore any source symbol decoded | set of source symbols, and therefore any source symbol decoded | |||

using the repair symbols contained in this packet will be | using the repair symbols contained in this packet will be | |||

corrupted. In addition, if the NSS value is significantly | corrupted. In addition, if the NSS value is significantly | |||

increased, it will generate a higher processing overhead at a | increased, it will generate a higher processing overhead at a | |||

receiver, which may impact the terminal performance; | receiver, which may impact the terminal performance; | |||

o FSS_ESI: changing this value also leads a receiver to consider a | ||||

FSS_ESI: changing this value also leads a receiver to consider a | ||||

different set of source symbols and therefore any source symbol | different set of source symbols and therefore any source symbol | |||

decoded using the repair symbols contained in this packet will be | decoded using the repair symbols contained in this packet will be | |||

corrupted. | corrupted. | |||

It is therefore RECOMMENDED that security measures are taken to | It is therefore RECOMMENDED that security measures are taken to | |||

guarantee the FEC Source and Repair Packets as stated in [RFC6363]. | guarantee the FEC Source and Repair Packets as stated in [RFC6363]. | |||

8.3. When Several Source Flows are to be Protected Together | 7.3. When Several Source Flows are to be Protected Together | |||

The Sliding Window RLC FEC Scheme specified in this document does not | The Sliding Window RLC FEC scheme specified in this document does not | |||

change the recommendations of [RFC6363]. | change the recommendations of [RFC6363]. | |||

8.4. Baseline Secure FEC Framework Operation | 7.4. Baseline Secure FEC Framework Operation | |||

The Sliding Window RLC FEC Scheme specified in this document does not | The Sliding Window RLC FEC scheme specified in this document does not | |||

change the recommendations of [RFC6363] concerning the use of the | change the recommendations of [RFC6363] concerning the use of the | |||

IPsec/ESP security protocol as a mandatory to implement (but not | IPsec/Encapsulating Security Payload (ESP) security protocol as a | |||

mandatory to use) security scheme. This is well suited to situations | mandatory-to-implement (but not mandatory-to-use) security scheme. | |||

where the only insecure domain is the one over which the FEC | This is well suited to situations where the only insecure domain is | |||

Framework operates. | the one over which the FEC Framework operates. | |||

8.5. Additional Security Considerations for Numerical Computations | 7.5. Additional Security Considerations for Numerical Computations | |||

In addition to the above security considerations, inherited from | In addition to the above security considerations, inherited from | |||

[RFC6363], the present document introduces several formulae, in | [RFC6363], the present document introduces several formulae, in | |||

particular in Appendix C.1. It is RECOMMENDED to check that the | particular in Appendix C.1. It is RECOMMENDED to check that the | |||

computed values stay within reasonable bounds since numerical | computed values stay within reasonable bounds since numerical | |||

overflows, caused by an erroneous implementation or an erroneous | overflows, caused by an erroneous implementation or an erroneous | |||

input value, may lead to hazardous behaviours. However, what | input value, may lead to hazardous behaviors. However, what | |||

"reasonable bounds" means is use-case and implementation dependent | "reasonable bounds" means is use-case and implementation dependent | |||

and is not detailed in this document. | and is not detailed in this document. | |||

Appendix C.2 also mentions the possibility of "using the timestamp | Appendix C.2 also mentions the possibility of "using the timestamp | |||

field of an RTP packet header" when applicable. A malicious attacker | field of an RTP packet header" when applicable. A malicious attacker | |||

may deliberately corrupt this header field in order to trigger | may deliberately corrupt this header field in order to trigger | |||

hazardous behaviours at a FECFRAME receiver. Protection against this | hazardous behaviors at a FECFRAME receiver. Protection against this | |||

type of content corruption can be addressed with the above | type of content corruption can be addressed with the above | |||

recommendations on a baseline secure operation. In addition, it is | recommendations on a baseline secure operation. In addition, it is | |||

also RECOMMENDED to check that the timestamp value be within | also RECOMMENDED to check that the timestamp value be within | |||

reasonable bounds. | reasonable bounds. | |||

9. Operations and Management Considerations | 8. Operations and Management Considerations | |||

The FEC Framework document [RFC6363] provides a fairly comprehensive | The FEC Framework document [RFC6363] provides a fairly comprehensive | |||

analysis of operations and management considerations applicable to | analysis of operations and management considerations applicable to | |||

FEC Schemes. Therefore, the present section only discusses specific | FEC schemes. Therefore, the present section only discusses specific | |||

topics. | topics. | |||

9.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^^8) | 8.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] depending on the code rate and | Cortex-A15 embedded board in [Roca17] depending on the code rate and | |||

the channel conditions, using an encoding window of size 18 or 23 | the channel conditions, using an encoding window of size 18 or 23 | |||

symbols; see the above article for the details). Of course the CPU | symbols; see the above article for the details). Of course the CPU | |||

overhead will increase with the encoding window size, because more | overhead will increase with the encoding window size, because more | |||

operations in the GF(2^^8) finite field will be needed. | 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 | 8.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 | |||

define a coding coefficient density threshold (DT) parameter. This | define a coding coefficient density threshold (DT) parameter. This | |||

parameter enables a sender to control the code density, i.e., the | parameter enables a sender to control the code density, i.e., the | |||

proportion of coefficients that are non zero on average. With RLC | proportion of coefficients that are nonzero on average. With RLC | |||

over GF(2^^8), it is usually appropriate that small encoding windows | over GF(2^(8)), it is usually appropriate that small encoding windows | |||

be associated to a density threshold equal to 15, the maximum value, | be associated to a density threshold equal to 15, the maximum value, | |||

in order to warrant a high loss protection. | in order to warrant a high loss protection. | |||

On the opposite, with larger encoding windows, it is usually | On the opposite, with larger encoding windows, it is usually | |||

appropriate that the density threshold be reduced. With large | appropriate that the density threshold be reduced. With large | |||

encoding windows, an alternative can be to use RLC over GF(2) and a | encoding windows, an alternative can be to use RLC over GF(2) and a | |||

density threshold equal to 7 (i.e., an average density equal to 1/2) | density threshold equal to 7 (i.e., an average density equal to 1/2) | |||

or smaller. | or smaller. | |||

Note that using a density threshold equal to 15 with RLC over GF(2) | Note that using a density threshold equal to 15 with RLC over GF(2) | |||

is equivalent to using an XOR code that computes the XOR sum of all | is equivalent to using an XOR code that computes the XOR sum of all | |||

the source symbols in the encoding window. In that case: (1) only a | the source symbols in the encoding window. In that case: (1) only a | |||

single repair symbol can be produced for any encoding window, and (2) | single repair symbol can be produced for any encoding window, and (2) | |||

the repair_key parameter becomes useless (the coding coefficients | the repair_key parameter becomes useless (the coding coefficients | |||

generation function does not rely on the PRNG). | generation function does not rely on the PRNG). | |||

10. IANA Considerations | 9. IANA Considerations | |||

This document registers two values in the "FEC Framework (FECFRAME) | This document registers two values in the "FEC Framework (FECFRAME) | |||

FEC Encoding IDs" registry [RFC6363] as follows: | FEC Encoding IDs" registry [RFC6363] as follows: | |||

o YYYY refers to the Sliding Window Random Linear Codes (RLC) over | * 9 refers to the Sliding Window Random Linear Codes (RLC) over | |||

GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in | GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in | |||

Section 5 of this document. | Section 5 of this document. | |||

o XXXX refers to the Sliding Window Random Linear Codes (RLC) over | ||||

GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in | ||||

Section 4 of this document. | ||||

11. Acknowledgments | * 10 refers to the Sliding Window Random Linear Codes (RLC) over | |||

GF(2^(8)) FEC Scheme for Arbitrary Packet Flows, as defined in | ||||

The authors would like to thank the three TSVWG chairs, Wesley Eddy, | Section 4 of this document. | |||

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, Adam Roach, and Roman Danyliw for their highly valuable | ||||

feedbacks that greatly contributed to improve this specification. | ||||

12. References | ||||

12.1. Normative References | 10. References | |||

[C99] "Programming languages - C: C99, correction 3:2007", | 10.1. Normative References | |||

International Organization for Standardization, ISO/IEC | ||||

9899:1999/Cor 3:2007, November 2007. | ||||

[fecframe-ext] | [C99] International Organization for Standardization, | |||

Roca, V. and A. Begen, "Forward Error Correction (FEC) | "Programming languages - C: C99, correction 3:2007", ISO/ | |||

Framework Extension to Sliding Window Codes", Transport | IEC 9899:1999/Cor 3:2007, November 2007. | |||

Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext | ||||

(Work in Progress), January 2019, | ||||

<https://tools.ietf.org/html/ | ||||

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

DOI 10.17487/RFC2119, March 1997, | DOI 10.17487/RFC2119, March 1997, | |||

<https://www.rfc-editor.org/info/rfc2119>. | <https://www.rfc-editor.org/info/rfc2119>. | |||

[RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error | [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error | |||

Correction (FEC) Framework", RFC 6363, | Correction (FEC) Framework", RFC 6363, | |||

DOI 10.17487/RFC6363, October 2011, | DOI 10.17487/RFC6363, October 2011, | |||

<https://www.rfc-editor.org/info/rfc6363>. | <https://www.rfc-editor.org/info/rfc6363>. | |||

[RFC6364] Begen, A., "Session Description Protocol Elements for the | [RFC6364] Begen, A., "Session Description Protocol Elements for the | |||

Forward Error Correction (FEC) Framework", RFC 6364, | Forward Error Correction (FEC) Framework", RFC 6364, | |||

DOI 10.17487/RFC6364, October 2011, | DOI 10.17487/RFC6364, October 2011, | |||

<https://www.rfc-editor.org/info/rfc6364>. | <https://www.rfc-editor.org/info/rfc6364>. | |||

[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | |||

2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | |||

May 2017, <https://www.rfc-editor.org/info/rfc8174>. | May 2017, <https://www.rfc-editor.org/info/rfc8174>. | |||

[tinymt32] | [RFC8680] Roca, V. and A. Begen, "Forward Error Correction (FEC) | |||

Saito, M., Matsumoto, M., Roca, V., and E. Baccelli, | Framework Extension to Sliding Window Codes", RFC 8680, | |||

"TinyMT32 Pseudo Random Number Generator (PRNG)", | DOI 10.17487/RFC8680, January 2020, | |||

Transport Area Working Group (TSVWG) draft-roca-tsvwg- | <https://www.rfc-editor.org/info/rfc8680>. | |||

tinymt32 (Work in Progress), February 2019, | ||||

<https://tools.ietf.org/html/draft-roca-tsvwg-tinymt32>. | ||||

12.2. Informative References | [RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli, | |||

"TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682, | ||||

DOI 10.17487/RFC8682, January 2020, | ||||

<https://www.rfc-editor.org/info/rfc8682>. | ||||

10.2. Informative References | ||||

[PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete | [PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete | |||

Treatment of Software Implementations of Finite Field | Treatment of Software Implementations of Finite Field | |||

Arithmetic for Erasure Coding Applications", University of | Arithmetic for Erasure Coding Applications", University of | |||

Tennessee Technical Report UT-CS-13-717, | Tennessee Technical Report UT-CS-13-717, October 2013, | |||

http://web.eecs.utk.edu/~plank/plank/papers/ | <http://web.eecs.utk.edu/~plank/plank/papers/UT-CS- | |||

UT-CS-13-717.html, October 2013, | 13-717.html>. | |||

<http://web.eecs.utk.edu/~plank/plank/papers/ | ||||

UT-CS-13-717.html>. | ||||

[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>. | |||

skipping to change at page 29, line 34 ¶ | skipping to change at line 1342 ¶ | |||

DOI 10.17487/RFC6865, February 2013, | DOI 10.17487/RFC6865, February 2013, | |||

<https://www.rfc-editor.org/info/rfc6865>. | <https://www.rfc-editor.org/info/rfc6865>. | |||

[RFC8406] Adamson, B., Adjih, C., Bilbao, J., Firoiu, V., Fitzek, | [RFC8406] Adamson, B., Adjih, C., Bilbao, J., Firoiu, V., Fitzek, | |||

F., Ghanem, S., Lochin, E., Masucci, A., Montpetit, M-J., | F., Ghanem, S., Lochin, E., Masucci, A., Montpetit, M-J., | |||

Pedersen, M., Peralta, G., Roca, V., Ed., Saxena, P., and | Pedersen, M., Peralta, G., Roca, V., Ed., Saxena, P., and | |||

S. Sivakumar, "Taxonomy of Coding Techniques for Efficient | S. Sivakumar, "Taxonomy of Coding Techniques for Efficient | |||

Network Communications", RFC 8406, DOI 10.17487/RFC8406, | Network Communications", RFC 8406, DOI 10.17487/RFC8406, | |||

June 2018, <https://www.rfc-editor.org/info/rfc8406>. | June 2018, <https://www.rfc-editor.org/info/rfc8406>. | |||

[Roca16] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C. | [Roca16] Roca, V., Teibi, B., Burdinat, C., Tran-Thai, T., and C. | |||

Thienot, "Block or Convolutional AL-FEC Codes? A | Thienot, "Block or Convolutional AL-FEC Codes? A | |||

Performance Comparison for Robust Low-Latency | Performance Comparison for Robust Low-Latency | |||

Communications", HAL open-archive document,hal-01395937 | Communications", HAL ID hal-01395937v2, February 2017, | |||

https://hal.inria.fr/hal-01395937/en/, November 2016, | ||||

<https://hal.inria.fr/hal-01395937/en/>. | <https://hal.inria.fr/hal-01395937/en/>. | |||

[Roca17] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C. | [Roca17] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C. | |||

Thienot, "Less Latency and Better Protection with AL-FEC | Thienot, "Less Latency and Better Protection with AL-FEC | |||

Sliding Window Codes: a Robust Multimedia CBR Broadcast | Sliding Window Codes: a Robust Multimedia CBR Broadcast | |||

Case Study", 13th IEEE International Conference on | Case Study", 13th IEEE International Conference on | |||

Wireless and Mobile Computing, Networking and | Wireless and Mobile Computing, Networking and | |||

Communications (WiMob17), October | Communications (WiMob17), HAL ID hal-01571609, October | |||

2017 https://hal.inria.fr/hal-01571609v1/en/, October | ||||

2017, <https://hal.inria.fr/hal-01571609v1/en/>. | 2017, <https://hal.inria.fr/hal-01571609v1/en/>. | |||

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 focuses 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, to be read line by line. | 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 (to be read per line) returned by | 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 | tinymt32_rand256() as 8-bit unsigned integers, with a seed value of 1 | |||

1. | ||||

The second criterion focusses on the tinymt32_rand16(), where the | The second criterion focuses 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, to be read line by line. | 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 (to be read per line) returned by | 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. | 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 | |||

and does not claim to be a solid evaluation. | and does not claim to be a solid evaluation. | |||

The two RLC FEC Schemes use the PRNG to produce pseudo-random coding | The two RLC FEC schemes use the PRNG to produce pseudorandom coding | |||

coefficients (Section 3.6), each time a new repair symbol is needed. | coefficients (Section 3.6), each time a new repair symbol is needed. | |||

A different repair key is used for each repair symbol, usually by | A different repair key is used for each repair symbol, usually by | |||

incrementing the repair key value (Section 6.1). For each repair | incrementing the repair key value (Section 6.1). For each repair | |||

symbol, a limited number of pseudo-random numbers is needed, | symbol, a limited number of pseudorandom numbers is needed, depending | |||

depending on the DT and encoding window size (Section 3.6), using | on the DT and encoding window size (Section 3.6), using either | |||

either tinymt32_rand16() or tinymt32_rand256(). Therefore we are | tinymt32_rand16() or tinymt32_rand256(). Therefore, we are more | |||

more interested in the randomness of small sequences of random | interested in the randomness of small sequences of random numbers | |||

numbers mapped to 4-bit or 8-bit integers, than in the randomness of | mapped to 4-bit or 8-bit integers, than in the randomness of a very | |||

a very large sequence of random numbers which is not representative | large sequence of random numbers which is not representative of the | |||

of the usage of the PRNG. | usage of the PRNG. | |||

Evaluation of tinymt32_rand16(): We first generate a huge number | Evaluation of tinymt32_rand16(): We first generate a huge number | |||

(1,000,000,000) of small sequences (20 pseudo-random numbers per | (1,000,000,000) of small sequences (20 pseudorandom numbers per | |||

sequence), increasing the seed value for each sequence, and perform | sequence), increasing the seed value for each sequence, and perform | |||

statistics on the number of occurrences of each of the 16 possible | statistics on the number of occurrences of each of the 16 possible | |||

values across all sequences. In this first test we consider 32-bit | values across all sequences. In this first test we consider 32-bit | |||

seed values in order to assess the PRNG quality after output | seed values in order to assess the PRNG quality after output | |||

truncation to 4 bits. | truncation to 4 bits. | |||

value occurrences percentage (%) (total of 20000000000) | +-------+-------------+----------------+ | |||

0 1250036799 6.2502 | | Value | Occurrences | Percentage (%) | | |||

1 1249995831 6.2500 | +=======+=============+================+ | |||

2 1250038674 6.2502 | | 0 | 1250036799 | 6.2502 | | |||

3 1250000881 6.2500 | +-------+-------------+----------------+ | |||

4 1250023929 6.2501 | | 1 | 1249995831 | 6.2500 | | |||

5 1249986320 6.2499 | +-------+-------------+----------------+ | |||

6 1249995587 6.2500 | | 2 | 1250038674 | 6.2502 | | |||

7 1250020363 6.2501 | +-------+-------------+----------------+ | |||

8 1249995276 6.2500 | | 3 | 1250000881 | 6.2500 | | |||

9 1249982856 6.2499 | +-------+-------------+----------------+ | |||

10 1249984111 6.2499 | | 4 | 1250023929 | 6.2501 | | |||

11 1250009551 6.2500 | +-------+-------------+----------------+ | |||

12 1249955768 6.2498 | | 5 | 1249986320 | 6.2499 | | |||

13 1249994654 6.2500 | +-------+-------------+----------------+ | |||

14 1250000569 6.2500 | | 6 | 1249995587 | 6.2500 | | |||

15 1249978831 6.2499 | +-------+-------------+----------------+ | |||

| 7 | 1250020363 | 6.2501 | | ||||

+-------+-------------+----------------+ | ||||

| 8 | 1249995276 | 6.2500 | | ||||

+-------+-------------+----------------+ | ||||

| 9 | 1249982856 | 6.2499 | | ||||

+-------+-------------+----------------+ | ||||

| 10 | 1249984111 | 6.2499 | | ||||

+-------+-------------+----------------+ | ||||

| 11 | 1250009551 | 6.2500 | | ||||

+-------+-------------+----------------+ | ||||

| 12 | 1249955768 | 6.2498 | | ||||

+-------+-------------+----------------+ | ||||

| 13 | 1249994654 | 6.2500 | | ||||

+-------+-------------+----------------+ | ||||

| 14 | 1250000569 | 6.2500 | | ||||

+-------+-------------+----------------+ | ||||

| 15 | 1249978831 | 6.2499 | | ||||

+-------+-------------+----------------+ | ||||

Figure 11: tinymt32_rand16(): occurrence statistics across a huge | Table 1: tinymt32_rand16() | |||

number (1,000,000,000) of small sequences (20 pseudo-random numbers | Occurrence Statistics | |||

per sequence), with 0 as the first PRNG seed. | ||||

The results (Figure 11) show that all possible values are almost | Evaluation of tinymt32_rand16(): We first generate a huge number | |||

(1,000,000,000) of small sequences (20 pseudorandom numbers per | ||||

sequence), increasing the seed value for each sequence, and perform | ||||

statistics on the number of occurrences of each of the 16 possible | ||||

values across the 20,000,000,000 numbers of all sequences. In this | ||||

first test, we consider 32-bit seed values in order to assess the | ||||

PRNG quality after output truncation to 4 bits. | ||||

The results (Table 1) show that all possible values are almost | ||||

equally represented, or said differently, that the tinymt32_rand16() | equally represented, or said differently, that the tinymt32_rand16() | |||

output converges to a uniform distribution where each of the 16 | output converges to a uniform distribution where each of the 16 | |||

possible values would appear exactly 1 / 16 * 100 = 6.25% of times. | possible values would appear exactly 1 / 16 * 100 = 6.25% of times. | |||

Since the RLC FEC Schemes use of this PRNG will be limited to 16-bit | Since the RLC FEC schemes use of this PRNG will be limited to 16-bit | |||

seed values, we carried out the same test for the first 2^^16 seed | seed values, we carried out the same test for the first 2^(16) seed | |||

values only. The distribution (not shown) is of course less uniform, | values only. The distribution (not shown) is of course less uniform, | |||

with value occurences ranging between 6.2121% (i.e., 81,423 | with value occurrences ranging between 6.2121% (i.e., 81,423 | |||

occurences out of a total of 65536*20=1,310,720) and 6.2948% (i.e., | occurrences out of a total of 65536*20=1,310,720) and 6.2948% (i.e., | |||

82,507 occurences). However, we do not believe it significantly | 82,507 occurrences). However, we do not believe it significantly | |||

impacts the RLC FEC Scheme behavior. | impacts the RLC FEC scheme behavior. | |||

Other types of biases may exist that may be visible with smaller | Other types of biases may exist that may be visible with smaller | |||

tests, for instance to evaluate the convergence speed to a uniform | tests, for instance to evaluate the convergence speed to a uniform | |||

distribution. We therefore perform 200 tests, each of them | distribution. We therefore perform 200 tests, each of them producing | |||

consisting in producing 200 sequences, keeping only the first value | 200 sequences, keeping only the first value of each sequence. We use | |||

of each sequence. We use non overlapping repair keys for each | non-overlapping repair keys for each sequence, starting with value 0 | |||

sequence, starting with value 0 and increasing it after each use. | and increasing it after each use. | |||

value min occurrences max occurrences average occurrences | +-------+-----------------+-----------------+---------------------+ | |||

0 4 21 6.3675 | | Value | Min Occurrences | Max Occurrences | Average Occurrences | | |||

1 4 22 6.0200 | +=======+=================+=================+=====================+ | |||

2 4 20 6.3125 | | 0 | 4 | 21 | 6.3675 | | |||

3 5 23 6.1775 | +-------+-----------------+-----------------+---------------------+ | |||

4 5 24 6.1000 | | 1 | 4 | 22 | 6.0200 | | |||

5 4 21 6.5925 | +-------+-----------------+-----------------+---------------------+ | |||

6 5 30 6.3075 | | 2 | 4 | 20 | 6.3125 | | |||

7 6 22 6.2225 | +-------+-----------------+-----------------+---------------------+ | |||

8 5 26 6.1750 | | 3 | 5 | 23 | 6.1775 | | |||

9 3 21 5.9425 | +-------+-----------------+-----------------+---------------------+ | |||

10 5 24 6.3175 | | 4 | 5 | 24 | 6.1000 | | |||

11 4 22 6.4300 | +-------+-----------------+-----------------+---------------------+ | |||

12 5 21 6.1600 | | 5 | 4 | 21 | 6.5925 | | |||

13 5 22 6.3100 | +-------+-----------------+-----------------+---------------------+ | |||

14 4 26 6.3950 | | 6 | 5 | 30 | 6.3075 | | |||

15 4 21 6.1700 | +-------+-----------------+-----------------+---------------------+ | |||

| 7 | 6 | 22 | 6.2225 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 8 | 5 | 26 | 6.1750 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 9 | 3 | 21 | 5.9425 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 10 | 5 | 24 | 6.3175 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 11 | 4 | 22 | 6.4300 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 12 | 5 | 21 | 6.1600 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 13 | 5 | 22 | 6.3100 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 14 | 4 | 26 | 6.3950 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

| 15 | 4 | 21 | 6.1700 | | ||||

+-------+-----------------+-----------------+---------------------+ | ||||

Figure 12: tinymt32_rand16(): occurrence statistics across 200 tests, | Table 2: tinymt32_rand16() Occurrence Statistics | |||

each of them consisting in 200 sequences of 1 pseudo-random number | ||||

each, with non overlapping PRNG seeds in sequence starting from 0. | ||||

Figure 12 shows across all 200 tests, for each of the 16 possible | Table 2 shows across all 200 tests, for each of the 16 possible | |||

pseudo-random number values, the minimum (resp. maximum) number of | pseudorandom number values, the minimum (resp. maximum) number of | |||

times it appeared in a test, 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 contrary, 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, systematically returns 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 | |||

256 possible values 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) | |||

skipping to change at page 34, line 9 ¶ | skipping to change at line 1569 ¶ | |||

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

of a real-time flow, an inappropriate parameter derivation may lead | of a real-time flow, an inappropriate parameter derivation may lead | |||

to the decoding of erased source packets after their validity period, | to the decoding of erased source packets after their validity period, | |||

making them useless to the target application. This annex proposes | making them useless to the target application. This annex proposes | |||

an approach to reduce this risk, among other things. | an approach to reduce this risk, among other things. | |||

The FEC Schemes defined in this document can be used in various | The FEC schemes defined in this document can be used in various | |||

manners, depending on the target use-case: | manners, depending on the target use-case: | |||

o the source ADU flow they protect may or may not have real-time | * the source ADU flow they protect may or may not have real-time | |||

constraints; | constraints; | |||

o the source ADU flow may be a Constant Bitrate (CBR) or Variable | ||||

BitRate (VBR) flow; | * the source ADU flow may be a Constant Bitrate (CBR) or Variable | |||

o with a VBR source ADU flow, the flow's minimum and maximum | Bitrate (VBR) flow; | |||

* with a VBR source ADU flow, the flow's minimum and maximum | ||||

bitrates may or may not be known; | bitrates may or may not be known; | |||

o and the communication path between encoder and decoder may be a | ||||

* and the communication path between encoder and decoder may be a | ||||

CBR communication path (e.g., as with certain LTE-based broadcast | CBR communication path (e.g., as with certain LTE-based broadcast | |||

channels) or not (general case, e.g., with Internet). | channels) or not (general case, e.g., with Internet). | |||

The parameter derivation technique should be suited to the use-case, | The parameter derivation technique should be suited to the use-case, | |||

as described in the following sections. | as described in the following sections. | |||

C.1. Case of a CBR Real-Time Flow | C.1. Case of a CBR Real-Time Flow | |||

In the following, we consider a real-time flow with max_lat latency | In the following, we consider a real-time flow with max_lat latency | |||

budget. The encoding symbol size, E, is constant. The code rate, | budget. The encoding symbol size, E, is constant. The code rate, | |||

skipping to change at page 34, line 44 ¶ | skipping to change at line 1607 ¶ | |||

the FECFRAME sender is fixed and equal to br_in (in bits/s), and this | the FECFRAME sender is fixed and equal to br_in (in bits/s), and this | |||

value is known by the FECFRAME sender. It follows that the | value is known by the FECFRAME sender. It follows that the | |||

transmission bitrate at the output of the FECFRAME sender will be | transmission bitrate at the output of the FECFRAME sender will be | |||

higher, depending on the added repair flow overhead. In order to | higher, depending on the added repair flow overhead. In order to | |||

comply with the maximum FEC-related latency budget, we have: | comply with the maximum FEC-related latency budget, we have: | |||

dw_max_size = (max_lat * br_in) / (8 * E) | dw_max_size = (max_lat * br_in) / (8 * E) | |||

assuming that the encoding and decoding times are negligible with | assuming that the encoding and decoding times are negligible with | |||

respect to the target max_lat. This is a reasonable assumption in | respect to the target max_lat. This is a reasonable assumption in | |||

many situations (e.g., see Section 9.1 in case of small window | many situations (e.g., see Section 8.1 in case of small window | |||

sizes). Otherwise the max_lat parameter should be adjusted in order | sizes). Otherwise the max_lat parameter should be adjusted in order | |||

to avoid the problem. In any case, interoperability will never be | to avoid the problem. In any case, interoperability will never be | |||

compromized by choosing a too large value. | compromised by choosing a too large value. | |||

In a second configuration, the FECFRAME sender generates a fixed | In a second configuration, the FECFRAME sender generates a fixed | |||

bitrate flow, equal to the CBR communication path bitrate equal to | bitrate flow, equal to the CBR communication path bitrate equal to | |||

br_out (in bits/s), and this value is known by the FECFRAME sender, | br_out (in bits/s), and this value is known by the FECFRAME sender, | |||

as in [Roca17]. The maximum source flow bitrate needs to be such | as in [Roca17]. The maximum source flow bitrate needs to be such | |||

that, with the added repair flow overhead, the total transmission | that, with the added repair flow overhead, the total transmission | |||

bitrate remains inferior or equal to br_out. We have: | bitrate remains inferior or equal to br_out. We have: | |||

dw_max_size = (max_lat * br_out * cr) / (8 * E) | dw_max_size = (max_lat * br_out * cr) / (8 * E) | |||

assuming here also that the encoding and decoding times are | assuming here also that the encoding and decoding times are | |||

negligible with respect to the target max_lat. | negligible with respect to the target max_lat. | |||

For decoding to be possible within the latency budget, it is required | For decoding to be possible within the latency budget, it is required | |||

that the encoding window maximum size be smaller than or at most | that the encoding window maximum size be smaller than or at most | |||

equal to the decoding window maximum size. The ew_max_size is the | equal to the decoding window maximum size. The ew_max_size is the | |||

main parameter at a FECFRAME sender, but its exact value has no | main parameter at a FECFRAME sender, but its exact value has no | |||

impact on the the FEC-related latency budget. The ew_max_size | impact on the FEC-related latency budget. The ew_max_size parameter | |||

parameter is computed as follows: | is computed as follows: | |||

ew_max_size = dw_max_size * WSR / 255 | ew_max_size = dw_max_size * WSR / 255 | |||

In line with [Roca17], WSR = 191 is considered as a reasonable value | In line with [Roca17], WSR = 191 is considered as a reasonable value | |||

(the resulting encoding to decoding window size ratio is then close | (the resulting encoding to decoding window size ratio is then close | |||

to 0.75), but other values between 1 and 255 inclusive are possible, | to 0.75), but other values between 1 and 255 inclusive are possible, | |||

depending on the use-case. | depending on the use-case. | |||

The dw_max_size is computed by a FECFRAME sender but not explicitly | The dw_max_size is computed by a FECFRAME sender but not explicitly | |||

communicated to a FECFRAME receiver. However, a FECFRAME receiver | communicated to a FECFRAME receiver. However, a FECFRAME receiver | |||

can easily evaluate the ew_max_size by observing the maximum Number | can easily evaluate the ew_max_size by observing the maximum Number | |||

of Source Symbols (NSS) value contained in the Repair FEC Payload ID | of Source Symbols (NSS) value contained in the Repair FEC Payload ID | |||

of received FEC Repair Packets (Section 4.1.3). A receiver can then | of received FEC Repair Packets (Section 4.1.3). A receiver can then | |||

easily compute dw_max_size: | easily compute dw_max_size: | |||

dw_max_size = max_NSS_observed * 255 / WSR | dw_max_size = max_NSS_observed * 255 / WSR | |||

A receiver can then chose an appropriate linear system maximum size: | A receiver can then choose an appropriate linear system maximum size: | |||

ls_max_size >= dw_max_size | ls_max_size >= dw_max_size | |||

It is good practice to use a larger value for ls_max_size as | It is good practice to use a larger value for ls_max_size as | |||

explained in Appendix D, which does not impact maximum latency nor | explained in Appendix D, which does not impact maximum latency nor | |||

interoperability. | interoperability. | |||

In any case, for a given use-case (i.e., for target encoding and | In any case, for a given use-case (i.e., for target encoding and | |||

decoding devices and desired protection levels in front of | decoding devices and desired protection levels in front of | |||

communication impairments) and for the computed ew_max_size, | communication impairments) and for the computed ew_max_size, | |||

skipping to change at page 36, line 10 ¶ | skipping to change at line 1669 ¶ | |||

the maximum encoding time and maximum memory requirements at a | the maximum encoding time and maximum memory requirements at a | |||

FECFRAME sender, and maximum decoding time and maximum memory | FECFRAME sender, and maximum decoding time and maximum memory | |||

requirements at a FECFRAME receiver, stay within reasonable bounds. | requirements at a FECFRAME receiver, stay within reasonable bounds. | |||

When assuming that the encoding and decoding times are negligible | When assuming that the encoding and decoding times are negligible | |||

with respect to the target max_lat, this should be verified as well, | with respect to the target max_lat, this should be verified as well, | |||

otherwise the max_lat SHOULD be adjusted accordingly. | otherwise the max_lat SHOULD be adjusted accordingly. | |||

The particular case of session start needs to be managed | The particular case of session start needs to be managed | |||

appropriately since the ew_size, starting at zero, increases each | appropriately since the ew_size, starting at zero, increases each | |||

time a new source ADU is received by the FECFRAME sender, until it | time a new source ADU is received by the FECFRAME sender, until it | |||

reaches the ew_max_size value. Therefore a FECFRAME receiver SHOULD | reaches the ew_max_size value. Therefore, a FECFRAME receiver SHOULD | |||

continuously observe the received FEC Repair Packets, since the NSS | continuously observe the received FEC Repair Packets, since the NSS | |||

value carried in the Repair FEC Payload ID will increase too, and | value carried in the Repair FEC Payload ID will increase too, and | |||

adjust its ls_max_size accordingly if need be. With a CBR flow, | adjust its ls_max_size accordingly if need be. With a CBR flow, | |||

session start is expected to be the only moment when the encoding | session start is expected to be the only moment when the encoding | |||

window size will increase. Similarly, with a CBR real-time flow, the | window size will increase. Similarly, with a CBR real-time flow, the | |||

session end is expected to be the only moment when the encoding | session end is expected to be the only moment when the encoding | |||

window size will progressively decrease. No adjustment of the | window size will progressively decrease. No adjustment of the | |||

ls_max_size is required at the FECFRAME receiver in that case. | ls_max_size is required at the FECFRAME receiver in that case. | |||

C.2. Other Types of Real-Time Flow | C.2. Other Types of Real-Time Flow | |||

skipping to change at page 36, line 40 ¶ | skipping to change at line 1699 ¶ | |||

on-time decoding at a FECFRAME receiver. If the instantaneous | on-time decoding at a FECFRAME receiver. If the instantaneous | |||

bitrate is higher than this smallest bitrate, this approach leads to | bitrate is higher than this smallest bitrate, this approach leads to | |||

an encoding window that is unnecessarily small, which reduces | an encoding window that is unnecessarily small, which reduces | |||

robustness in front of long erasure bursts. | robustness in front of long erasure bursts. | |||

Another approach consists in using ADU timing information (e.g., | Another approach consists in using ADU timing information (e.g., | |||

using the timestamp field of an RTP packet header, or registering the | using the timestamp field of an RTP packet header, or registering the | |||

time upon receiving a new ADU). From the global FEC-related latency | time upon receiving a new ADU). From the global FEC-related latency | |||

budget, the FECFRAME sender can derive a practical maximum latency | budget, the FECFRAME sender can derive a practical maximum latency | |||

budget for encoding operations, max_lat_for_encoding. For the FEC | budget for encoding operations, max_lat_for_encoding. For the FEC | |||

Schemes specified in this document, this latency budget SHOULD be | schemes specified in this document, this latency budget SHOULD be | |||

computed with: | computed with: | |||

max_lat_for_encoding = max_lat * WSR / 255 | max_lat_for_encoding = max_lat * WSR / 255 | |||

It follows that any source symbols associated to an ADU that has | It follows that any source symbols associated to an ADU that has | |||

timed-out with respect to max_lat_for_encoding SHOULD be removed from | timed-out with respect to max_lat_for_encoding SHOULD be removed from | |||

the encoding window. With this approach there is no pre-determined | the encoding window. With this approach there is no pre-determined | |||

ew_size value: this value fluctuates over the time according to the | ew_size value: this value fluctuates over the time according to the | |||

instantaneous source ADU flow bitrate. For practical reasons, a | instantaneous source ADU flow bitrate. For practical reasons, a | |||

FECFRAME sender may still require that ew_size does not increase | FECFRAME sender may still require that ew_size does not increase | |||

skipping to change at page 37, line 20 ¶ | skipping to change at line 1727 ¶ | |||

appropriate ls_max_size as explained in Appendix C.1. | appropriate ls_max_size as explained in Appendix C.1. | |||

When the observed NSS fluctuates significantly, a FECFRAME receiver | When the observed NSS fluctuates significantly, a FECFRAME receiver | |||

may want to adapt its ls_max_size accordingly. In particular when | may want to adapt its ls_max_size accordingly. In particular when | |||

the NSS is significantly reduced, a FECFRAME receiver may want to | the NSS is significantly reduced, a FECFRAME receiver may want to | |||

reduce the ls_max_size too in order to limit computation complexity. | reduce the ls_max_size too in order to limit computation complexity. | |||

A balance must be found between using an ls_max_size "too large" | A balance must be found between using an ls_max_size "too large" | |||

(which increases computation complexity and memory requirements) and | (which increases computation complexity and memory requirements) and | |||

the opposite (which reduces recovery performance). | the opposite (which reduces recovery performance). | |||

C.3. Case of a Non Real-Time Flow | C.3. Case of a Non-Real-Time Flow | |||

Finally there are configurations where a source ADU flow has no real- | Finally there are configurations where a source ADU flow has no real- | |||

time constraints. FECFRAME and the FEC Schemes defined in this | time constraints. FECFRAME and the FEC schemes defined in this | |||

document can still be used. The choice of appropriate parameter | document can still be used. The choice of appropriate parameter | |||

values can be directed by practical considerations. For instance, it | values can be directed by practical considerations. For instance, it | |||

can derive from an estimation of the maximum memory amount that could | can derive from an estimation of the maximum memory amount that could | |||

be dedicated to the linear system at a FECFRAME receiver, or the | be dedicated to the linear system at a FECFRAME receiver, or the | |||

maximum computation complexity at a FECFRAME receiver, both of them | maximum computation complexity at a FECFRAME receiver, both of them | |||

depending on the ls_max_size parameter. The same considerations also | depending on the ls_max_size parameter. The same considerations also | |||

apply to the FECFRAME sender, where the maximum memory amount and | apply to the FECFRAME sender, where the maximum memory amount and | |||

computation complexity depend on the ew_max_size parameter. | computation complexity depend on the ew_max_size parameter. | |||

Here also, the NSS value contained in FEC Repair Packets is used by a | Here also, the NSS value contained in FEC Repair Packets is used by a | |||

FECFRAME receiver to determine the current coding window size and | FECFRAME receiver to determine the current coding window size and | |||

ew_max_size by observing its maximum value over the time. | ew_max_size by observing its maximum value over the time. | |||

Appendix D. Decoding Beyond Maximum Latency Optimization | Appendix D. Decoding Beyond Maximum Latency Optimization | |||

(Informational) | (Informational) | |||

This annex introduces non normative considerations. It is provided | This annex introduces non-normative considerations. It is provided | |||

as suggestions, without any impact on interoperability. For more | as suggestions, without any impact on interoperability. For more | |||

information see [Roca16]. | information see [Roca16]. | |||

With a real-time source ADU flow, it is possible to improve the | With a real-time source ADU flow, it is possible to improve the | |||

decoding performance of sliding window codes without impacting | decoding performance of Sliding Window Codes without impacting | |||

maximum latency, at the cost of extra memory and CPU overhead. The | maximum latency, at the cost of extra memory and CPU overhead. The | |||

optimization consists, for a FECFRAME receiver, to extend the linear | optimization consists, for a FECFRAME receiver, to extend the linear | |||

system beyond the decoding window maximum size, by keeping a certain | system beyond the decoding window maximum size, by keeping a certain | |||

number of old source symbols whereas their associated ADUs timed-out: | number of old source symbols whereas their associated ADUs timed-out: | |||

ls_max_size > dw_max_size | ls_max_size > dw_max_size | |||

Usually the following choice is a good trade-off between decoding | Usually the following choice is a good trade-off between decoding | |||

performance and extra CPU overhead: | performance and extra CPU overhead: | |||

skipping to change at page 38, line 30 ¶ | skipping to change at line 1785 ¶ | |||

lost ADUs will be recovered without relying on this optimization. | lost ADUs will be recovered without relying on this optimization. | |||

ls_max_size | ls_max_size | |||

/---------------------------------^-------------------------------\ | /---------------------------------^-------------------------------\ | |||

late source symbols | late source symbols | |||

(pot. decoded but not delivered) dw_max_size | (pot. decoded but not delivered) dw_max_size | |||

/--------------^-----------------\ /--------------^---------------\ | /--------------^-----------------\ /--------------^---------------\ | |||

src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 | src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 | |||

Figure 13: Relationship between parameters to decode beyond maximum | Figure 11: Relationship between Parameters to Decode beyond | |||

latency. | Maximum Latency | |||

It means that source symbols, and therefore ADUs, may be decoded even | It means that source symbols, and therefore ADUs, may be decoded even | |||

if the added latency exceeds the maximum value permitted by the | if the added latency exceeds the maximum value permitted by the | |||

application (the "late source symbols" of Figure 13). It follows | application (the "late source symbols" of Figure 11). It follows | |||

that the corresponding ADUs will not be useful to the application. | that the corresponding ADUs will not be useful to the application. | |||

However, decoding these "late symbols" significantly improves the | However, decoding these "late symbols" significantly improves the | |||

global robustness in bad reception conditions and is therefore | global robustness in bad reception conditions and is therefore | |||

recommended for receivers experiencing bad communication conditions | recommended for receivers experiencing bad communication conditions | |||

[Roca16]. In any case whether or not to use this optimization and | [Roca16]. In any case whether or not to use this optimization and | |||

what exact value to use for the ls_max_size parameter are local | what exact value to use for the ls_max_size parameter are local | |||

decisions made by each receiver independently, without any impact on | decisions made by each receiver independently, without any impact on | |||

the other receivers nor on the source. | the other receivers nor on the source. | |||

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 (in 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 Kuehlewind, Eric | ||||

Rescorla, Adam Roach, and Roman Danyliw for their highly valuable | ||||

feedback that greatly contributed to improving this specification. | ||||

Authors' Addresses | Authors' Addresses | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

Univ. Grenoble Alpes | Univ. Grenoble Alpes | |||

France | France | |||

EMail: vincent.roca@inria.fr | Email: vincent.roca@inria.fr | |||

Belkacem Teibi | Belkacem Teibi | |||

INRIA | INRIA | |||

Univ. Grenoble Alpes | Univ. Grenoble Alpes | |||

France | France | |||

EMail: belkacem.teibi@gmail.com | Email: belkacem.teibi@gmail.com | |||

End of changes. 206 change blocks. | ||||

470 lines changed or deleted | | 516 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/ |