draft-ietf-tsvwg-rlc-fec-scheme-09.txt | draft-ietf-tsvwg-rlc-fec-scheme-10.txt | |||
---|---|---|---|---|

TSVWG V. Roca | TSVWG V. Roca | |||

Internet-Draft B. Teibi | Internet-Draft B. Teibi | |||

Intended status: Standards Track INRIA | Intended status: Standards Track E. Baccelli | |||

Expires: March 23, 2019 September 19, 2018 | Expires: July 21, 2019 INRIA | |||

January 17, 2019 | ||||

Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) | Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) | |||

Schemes for FECFRAME | Schemes for FECFRAME | |||

draft-ietf-tsvwg-rlc-fec-scheme-09 | draft-ietf-tsvwg-rlc-fec-scheme-10 | |||

Abstract | Abstract | |||

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

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

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

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

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

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

extended to sliding window FEC codes, as defined in [fecframe-ext]. | extended to sliding window FEC codes, as defined in [fecframe-ext]. | |||

skipping to change at page 1, line 43 ¶ | skipping to change at page 1, line 44 ¶ | |||

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

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

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

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

Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

This Internet-Draft will expire on March 23, 2019. | This Internet-Draft will expire on July 21, 2019. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2018 IETF Trust and the persons identified as the | Copyright (c) 2019 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | document authors. All rights reserved. | |||

This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||

(https://trustee.ietf.org/license-info) in effect on the date of | (https://trustee.ietf.org/license-info) in effect on the date of | |||

publication of this document. Please review these documents | publication of this document. Please review these documents | |||

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

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

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

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

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

FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5 | FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

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

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

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

3.1. Possible Parameter Derivations . . . . . . . . . . . . . 7 | 3.1. Codec Parameters . . . . . . . . . . . . . . . . . . . . 7 | |||

3.1.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . 8 | 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9 | |||

3.1.2. Other Types of Real-Time Flow . . . . . . . . . . . . 10 | 3.3. Encoding Window Management . . . . . . . . . . . . . . . 10 | |||

3.1.3. Case of a Non Real-Time Flow . . . . . . . . . . . . 11 | 3.4. Source Symbol Identification . . . . . . . . . . . . . . 11 | |||

3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11 | 3.5. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 11 | |||

3.3. Encoding Window Management . . . . . . . . . . . . . . . 13 | 3.6. Coding Coefficients Generation Function . . . . . . . . . 17 | |||

3.4. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 13 | 3.7. Finite Fields Operations . . . . . . . . . . . . . . . . 19 | |||

3.5. Coding Coefficients Generation Function . . . . . . . . . 15 | 3.7.1. Finite Field Definitions . . . . . . . . . . . . . . 19 | |||

3.6. Finite Fields Operations . . . . . . . . . . . . . . . . 17 | 3.7.2. Linear Combination of Source Symbols Computation . . 19 | |||

3.6.1. Finite Field Definitions . . . . . . . . . . . . . . 17 | ||||

3.6.2. Linear Combination of Source Symbols Computation . . 17 | ||||

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 . . . . . . . . . . . . . . . . . . . . . . . . 18 | Packet Flows . . . . . . . . . . . . . . . . . . . . . . . . 20 | |||

4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18 | 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 20 | |||

4.1.1. FEC Framework Configuration Information . . . . . . . 18 | 4.1.1. FEC Framework Configuration Information . . . . . . . 20 | |||

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

4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20 | 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22 | |||

4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21 | 4.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 | Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 21 | 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 24 | |||

5.1.1. FEC Framework Configuration Information . . . . . . . 22 | 5.1.1. FEC Framework Configuration Information . . . . . . . 24 | |||

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

5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22 | 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 24 | |||

5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 22 | ||||

6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 22 | 5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 22 | 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 25 | |||

6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 23 | 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 25 | |||

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 24 | 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 25 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 24 | 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 26 | |||

8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 27 | |||

8.1.1. Access to Confidential Content . . . . . . . . . . . 24 | 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 27 | |||

8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 25 | 8.1.1. Access to Confidential Content . . . . . . . . . . . 27 | |||

8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 25 | 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 27 | |||

8.3. When Several Source Flows are to be Protected Together . 26 | 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 27 | |||

8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 26 | 8.3. When Several Source Flows are to be Protected Together . 29 | |||

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

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

Computations . . . . . . . . . . . . . . . . . . . . . . 27 | Computations . . . . . . . . . . . . . . . . . . . . . . 29 | |||

9. Operations and Management Considerations . . . . . . . . . . 27 | 9. Operations and Management Considerations . . . . . . . . . . 30 | |||

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

GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 27 | GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 30 | |||

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

Threshold . . . . . . . . . . . . . . . . . . . . . . . . 28 | Threshold . . . . . . . . . . . . . . . . . . . . . . . . 30 | |||

10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 | 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 | |||

11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28 | 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 31 | |||

12. References . . . . . . . . . . . . . . . . . . . . . . . . . 28 | 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 31 | |||

12.1. Normative References . . . . . . . . . . . . . . . . . . 28 | 12.1. Normative References . . . . . . . . . . . . . . . . . . 31 | |||

12.2. Informative References . . . . . . . . . . . . . . . . . 29 | 12.2. Informative References . . . . . . . . . . . . . . . . . 32 | |||

Appendix A. TinyMT32 Pseudo-Random Number Generator . . . . . . 31 | Appendix A. TinyMT32 Validation Criteria (Normative) . . . . . . 34 | |||

Appendix B. Decoding Beyond Maximum Latency Optimization . . . . 35 | Appendix B. Assessing the PRNG Adequacy (Informational) . . . . 35 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 36 | Appendix C. Possible Parameter Derivation (Informational) . . . 37 | |||

C.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . . . 38 | ||||

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

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

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

(Informational) . . . . . . . . . . . . . . . . . . 41 | ||||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 42 | ||||

1. Introduction | 1. Introduction | |||

Application-Level Forward Erasure Correction (AL-FEC) codes, or | Application-Level Forward Erasure Correction (AL-FEC) codes, or | |||

simply FEC codes, are a key element of communication systems. They | simply FEC codes, are a key element of communication systems. They | |||

are used to recover from packet losses (or erasures) during content | are used to recover from packet losses (or erasures) during content | |||

delivery sessions to a potentially large number of receivers | delivery sessions to a potentially large number of receivers | |||

(multicast/broadcast transmissions). This is the case with the | (multicast/broadcast transmissions). This is the case with the | |||

FLUTE/ALC protocol [RFC6726] when used for reliable file transfers | FLUTE/ALC protocol [RFC6726] when used for reliable file transfers | |||

over lossy networks, and the FECFRAME protocol when used for reliable | over lossy networks, and the FECFRAME protocol when used for reliable | |||

skipping to change at page 3, line 50 ¶ | skipping to change at page 4, line 11 ¶ | |||

The present document only focuses on the FECFRAME protocol, used in | The present document only focuses on the FECFRAME protocol, used in | |||

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

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

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

destination application. | destination application. | |||

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

With FECFRAME, there is a single FEC encoding point (either a end- | With FECFRAME, there is a single FEC encoding point (either a 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 | |||

(either a end-host (receiver) or middlebox). In this context, | per receiver (either a end-host (receiver) or middlebox). In this | |||

currently standardized AL-FEC codes for FECFRAME like Reed-Solomon | context, currently standardized AL-FEC codes for FECFRAME like Reed- | |||

Solomon [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ, are | ||||

[RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ, are all | all linear block codes: they require the data flow to be segmented | |||

linear block codes: they require the data flow to be segmented into | into blocks of a predefined maximum size. | |||

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 front of long packet | size, the higher the robustness (e.g., in case of long packet erasure | |||

erasure bursts), but also the higher the maximum decoding latency | bursts), but also the higher the maximum decoding latency (i.e., the | |||

(i.e., the maximum time required to recover a lost (erased) packet | maximum time required to recover a lost (erased) packet thanks to FEC | |||

thanks to FEC protection). Therefore, with a multicast/broadcast | protection). Therefore, with a multicast/broadcast session where | |||

session where different receivers experience different packet loss | different receivers experience different packet loss rates, the block | |||

rates, the block size should be chosen by considering the worst | size should be chosen by considering the worst communication | |||

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

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

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 follow | This document introduces two fully-specified FEC Schemes that do not | |||

a totally different approach: the Sliding Window Random Linear Codes | follow the block code approach: the Sliding Window Random Linear | |||

(RLC) over either Galois Fields (A.K.A. Finite Fields) GF(2) (the | Codes (RLC) over either Galois Fields (A.K.A. Finite Fields) GF(2) | |||

"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 [fecframe-ext]. These FEC Schemes, and | |||

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

with media that feature real-time constraints sent within a | instance, 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 elastic | |||

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

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

current encoding window, and passed to the transport layer. | current encoding window, and passed to the transport layer. | |||

At the receiver, a linear system is managed from the set of received | At the receiver, a linear system is managed from the set of received | |||

source and repair packets. New variables (representing source | source and repair packets. New variables (representing source | |||

skipping to change at page 5, line 11 ¶ | skipping to change at page 5, line 20 ¶ | |||

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

skipping to change at page 5, line 45 ¶ | skipping to change at page 6, line 7 ¶ | |||

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 | o 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 | o the seed and density threshold parameters used by a coding | |||

coefficients generation function (Section 3.5). 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 7). 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 5), 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, pseudo-random number generator, and coding | |||

skipping to change at page 6, line 49 ¶ | skipping to change at page 7, line 12 ¶ | |||

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 (in seconds) | max_lat: maximum FEC-related latency within FECFRAME (a decimal | |||

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

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

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

tinymt32_rand(maxv): PRNG defined in Section 3.4 and used in this | TinyMT32: PRNG defined in Section 3.5 and used in this | |||

specification, that returns a new random integer in [0; maxv-1] | 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 | non zero | |||

3. 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. Possible Parameter Derivations | 3.1. Codec Parameters | |||

The Sliding Window RLC FEC Scheme relies on several parameters: | A codec implementing the Sliding Window RLC FEC Scheme relies on | |||

several parameters: | ||||

Maximum FEC-related latency budget, max_lat (in seconds) with real- | Maximum FEC-related latency budget, max_lat (a decimal number | |||

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 B 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 | [RFC6363], Section 10.2, item 6, for recommendations when several | |||

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

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

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

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

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

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

as the latency budget permitted for all FEC-related operations. | as the latency budget permitted for all FEC-related operations. | |||

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

derive other internal parameters as explained below; | derive other internal parameters (see Appendix C); | |||

Encoding window current (resp. maximum) size, ew_size (resp. | Encoding window current (resp. maximum) size, ew_size (resp. | |||

ew_max_size) (in symbols): | ew_max_size) (in symbols): | |||

at a FECFRAME sender, during FEC encoding, a repair symbol is | at a FECFRAME sender, during FEC encoding, a repair symbol is | |||

computed as a linear combination of the ew_size source symbols | computed as a linear combination of the ew_size source symbols | |||

present in the encoding window. The ew_max_size is the maximum | present in the encoding window. The ew_max_size is the maximum | |||

size of this window, while ew_size is the current size. For | size of this window, while ew_size is the current size. For | |||

instance, at session start, upon receiving new source ADUs, the | instance, at session start, upon receiving new source ADUs, the | |||

ew_size progressively increases until it reaches its maximum | ew_size progressively increases until it reaches its maximum | |||

value, ew_max_size. We have: | value, ew_max_size. We have: | |||

skipping to change at page 8, line 18 ¶ | skipping to change at page 8, line 32 ¶ | |||

or lost source symbols that are still within their latency budget; | or lost source symbols that are still within their latency budget; | |||

Linear system maximum size, ls_max_size (in symbols): at a FECFRAME | Linear system maximum size, ls_max_size (in symbols): at a FECFRAME | |||

receiver, the linear system maximum size, ls_max_size, is the | receiver, the linear system maximum size, ls_max_size, is the | |||

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

system (i.e., the variables). It SHOULD NOT be smaller than | system (i.e., the variables). It SHOULD NOT be smaller than | |||

dw_max_size since it would mean that, even after receiving a | dw_max_size since it would mean that, even after receiving a | |||

sufficient number of FEC Repair Packets, a lost ADU may not be | sufficient number of FEC Repair Packets, a lost ADU may not be | |||

recovered just because the associated source symbols have been | recovered just because the associated source symbols have been | |||

prematurely removed from the linear system, which is usually | prematurely removed from the linear system, which is usually | |||

counter-productive. On the opposite, the linear system MAY grow | counter-productive. On the opposite, the linear system MAY grow | |||

beyond the dw_max_size (Appendix B); | beyond the dw_max_size (Appendix D); | |||

Symbol size, E (in bytes): the E parameter determines the source and | Symbol size, E (in bytes): the E parameter determines the source and | |||

repair symbol sizes (necessarily equal). This is an input | repair symbol sizes (necessarily equal). 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. An implementation at a sender | |||

SHOULD fix the E parameter and communicate it as part of the FEC | MUST fix the E parameter and MUST communicate it as part of the | |||

Scheme-Specific Information (Section 4.1.1.2). | FEC Scheme-Specific Information (Section 4.1.1.2). | |||

Code rate, cr: The code rate parameter determines the amount of | Code rate, cr: The code rate parameter determines the amount of | |||

redundancy added to the flow. More precisely the cr is the ratio | redundancy added to the flow. More precisely the cr is the ratio | |||

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

source plus repair symbols and by definition: 0 < cr <= 1. This | source plus repair symbols and by definition: 0 < cr <= 1. This | |||

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

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

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

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

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

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

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

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

The FEC Schemes can be used in various manners. They can be used to | Appendix C proposes non normative technics to derive those | |||

protect a source ADU flow having real-time constraints, or a non- | parameters, depending on the use-case specificities. | |||

realtime source ADU flow. The source ADU flow may be a Constant | ||||

Bitrate (CBR) or Variable BitRate (VBR) flow. The flow's minimum/ | ||||

maximum bitrate might or might not be known. The FEC Schemes can | ||||

also be used over the Internet or over a CBR communication path. It | ||||

follows that the FEC Scheme parameters can be derived in different | ||||

ways, as described in the following sections. | ||||

3.1.1. Case of a CBR Real-Time Flow | ||||

In the following, we consider a real-time flow with max_lat latency | ||||

budget. The encoding symbol size, E, is constant. The code rate, | ||||

cr, is also constant, its value depending on the expected | ||||

communication loss model (this choice is out of scope of this | ||||

document). | ||||

In a first configuration, the source ADU flow bitrate at the input of | ||||

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

transmission bitrate at the output of the FECFRAME sender will be | ||||

higher, depending on the added repair flow overhead. In order to | ||||

comply with the maximum FEC-related latency budget, we have: | ||||

dw_max_size = (max_lat * br_in) / (8 * E) | ||||

In a second configuration, the FECFRAME sender generates a fixed | ||||

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

as in [Roca17]. The maximum source flow bitrate needs to be such | ||||

that, with the added repair flow overhead, the total transmission | ||||

bitrate remains inferior or equal to br_out. We have: | ||||

dw_max_size = (max_lat * br_out * cr) / (8 * E) | ||||

For decoding to be possible within the latency budget, it is required | ||||

that the encoding window maximum size be smaller than or at most | ||||

equal to the decoding window maximum size, the exact value having no | ||||

impact on the the FEC-related latency budget. For the FEC Schemes | ||||

specified in this document, in line with [Roca17], the ew_max_size | ||||

SHOULD be computed with: | ||||

ew_max_size = dw_max_size * 0.75 | ||||

The ew_max_size is the main parameter at a FECFRAME sender. It is | ||||

RECOMMENDED to check that the ew_max_size value stays within | ||||

reasonnable bounds in order to avoid hazardous behaviours. | ||||

The dw_max_size is computed by a FECFRAME sender but not explicitly | ||||

communicated to a FECFRAME receiver. However a FECFRAME receiver 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 | ||||

received FEC Repair Packets (Section 4.1.3). A receiver can then | ||||

easily compute dw_max_size: | ||||

dw_max_size = max_NSS_observed / 0.75 | ||||

A receiver can then chose an appropriate linear system maximum size: | ||||

ls_max_size >= dw_max_size | ||||

It is good practice to use a larger value for ls_max_size as | ||||

explained in Appendix B, which does not impact maximum latency nor | ||||

interoperability. However the linear system size should not be too | ||||

large for practical reasons (e.g., in order to limit computation | ||||

complexity). It is RECOMMENDED to check that the ls_max_size value | ||||

stays within reasonnable bounds in order to avoid hazardous | ||||

behaviours. | ||||

The particular case of session start needs to be managed | ||||

appropriately. Here ew_size increases each time a new source ADU is | ||||

received by the FECFRAME sender, until it reaches the ew_max_size | ||||

value. A FECFRAME receiver SHOULD continuously observe the received | ||||

FEC Repair Packets, since the NSS value carried in the Repair FEC | ||||

Payload ID will increase too, and adjust its ls_max_size accordingly | ||||

if need be. | ||||

3.1.2. Other Types of Real-Time Flow | ||||

In other configurations, a real-time source ADU flow, with a max_lat | ||||

latency budget, features a variable bitrate (VBR). A first approach | ||||

consists in considering the smallest instantaneous bitrate of the | ||||

source ADU flow, when this parameter is known, and to reuse the | ||||

derivation of Section 3.1.1. Considering the smallest bitrate means | ||||

that the encoding window and decoding window maximum sizes estimation | ||||

are pessimistic: these windows have the smallest size required to | ||||

enable a decoding on-time at a FECFRAME receiver. If the | ||||

instantaneous bitrate is higher than this smallest bitrate, this | ||||

approach leads to an encoding window that is unnecessarily small, | ||||

which reduces robustness in front of long erasure bursts. | ||||

Another approach consists in using ADU timing information (e.g., | ||||

using the timestamp field of an RTP packet header, or registering the | ||||

time upon receiving a new ADU). From the global FEC-related latency | ||||

budget the FECFRAME sender can derive a practical maximum latency | ||||

budget for encoding operations, max_lat_for_encoding. For the FEC | ||||

Schemes specified in this document, this latency budget SHOULD be | ||||

computed with: | ||||

max_lat_for_encoding = max_lat * 0.75 | ||||

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

the encoding window. With this approach there is no pre-determined | ||||

ew_size value: this value fluctuates over the time according to the | ||||

instantaneous source ADU flow bitrate. For practical reasons, a | ||||

FECFRAME sender may still require that ew_size does not increase | ||||

beyond a maximum value (Section 3.1.3). | ||||

With both approaches, and no matter the choice of the FECFRAME | ||||

sender, a FECFRAME receiver can still easily evaluate the ew_max_size | ||||

by observing the maximum Number of Source Symbols (NSS) value | ||||

contained in the Repair FEC Payload ID of received FEC Repair | ||||

Packets. A receiver can then compute dw_max_size and derive an | ||||

appropriate ls_max_size as explained in Section 3.1.1. | ||||

When the observed NSS fluctuates significantly, a FECFRAME receiver | ||||

may want to adapt its ls_max_size accordingly. In particular when | ||||

the NSS is significantly reduced, a FECFRAME receiver may want to | ||||

reduce the ls_max_size too in order to limit computation complexity. | ||||

However it is usually preferable to use a ls_max_size "too large" | ||||

(which can increase computation complexity and memory requirements) | ||||

than the opposite (which can reduce recovery performance). | ||||

Beyond these general guidelines, the details of how to manage these | ||||

situations at a FECFRAME sender and receiver can depend on additional | ||||

considerations that are out of scope of this document. | ||||

3.1.3. Case of a Non Real-Time Flow | ||||

Finally there are configurations where a source ADU flow has no real- | ||||

time constraints. FECFRAME and the FEC Schemes defined in this | ||||

document can still be used. The choice of appropriate parameter | ||||

values can be directed by practical considerations. For instance it | ||||

can derive from an estimation of the maximum memory amount that could | ||||

be dedicated to the linear system at a FECFRAME receiver, or the | ||||

maximum computation complexity at a FECFRAME receiver, both of them | ||||

depending on the ls_max_size parameter. The same considerations also | ||||

apply to the FECFRAME sender, where the maximum memory amount and | ||||

computation complexity depend on the ew_max_size parameter. | ||||

Here also, the NSS value contained in FEC Repair Packets is used by a | ||||

FECFRAME receiver to determine the current coding window size and | ||||

ew_max_size by observing its maximum value over the time. | ||||

Beyond these general guidelines, the details of how to manage these | ||||

situations at a FECFRAME sender and receiver can depend on additional | ||||

considerations that are out of scope of this document. | ||||

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 cannot directly be | 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). At a sender, this | assigned its own Flow ID value (see below). This Flow ID is then | |||

identifier is prepended to each ADU before FEC encoding. This way, | prepended to each ADU before FEC encoding. This way, FEC decoding at | |||

FEC decoding at a receiver also recovers this Flow ID and a recovered | a receiver also recovers this Flow ID and the recovered ADU can be | |||

ADU can be assigned to the right source flow (note that transport | assigned to the right source flow (note that the 5-tuple used to | |||

port numbers and IP addresses cannot be used to that purpose as they | identify the right source flow of a received ADU is absent with a | |||

are not recovered during FEC decoding). | 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 created as follows. First of | |||

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

skipping to change at page 12, line 36 ¶ | skipping to change at page 9, line 48 ¶ | |||

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

The data unit resulting from the ADU and the F, L, and Pad fields is | The data unit resulting from the ADU and the F, L, and Pad fields is | |||

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 (here 3 source symbols are created | |||

for this ADUI). | for this ADUI). | |||

skipping to change at page 13, line 25 ¶ | skipping to change at page 10, line 39 ¶ | |||

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

Note that a FEC codec may feature practical limits in the number of | Note that a FEC codec may feature practical limits in the number of | |||

source symbols in the encoding window (e.g., for computational | source symbols in the encoding window (e.g., for computational | |||

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. Pseudo-Random Number Generator (PRNG) | 3.4. Source Symbol Identification | |||

The RLC FEC Schemes defined in this document rely on the TinyMT32 | Each source symbol is identified by an Encoding Symbol ID (ESI), an | |||

PRNG, a small-sized variant of the Mersenne Twister PRNG, as defined | unsigned integer. The ESI of source symbols MUST start with value 0 | |||

in the reference implementation version 1.1 (2015/04/24) by Mutsuo | for the first source symbol and MUST be managed sequentially. | |||

Saito (Hiroshima University) and Makoto Matsumoto (The University of | Wrapping to zero happens after reaching the maximum value made | |||

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

dependant, for instance, 2^32-1 with FEC Schemes XXX and YYY). | ||||

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

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

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

FEC Schemes defined in this document rely on the TinyMT32 PRNG (a | ||||

small-sized variant of the Mersenne Twister PRNG), as defined in the | ||||

reference implementation version 1.1 (2015/04/24) by Mutsuo Saito | ||||

(Hiroshima University) and Makoto Matsumoto (The University of | ||||

Tokyo). | Tokyo). | |||

o Official web site: <http://www.math.sci.hiroshima-u.ac.jp/~m- | o Official web site: <http://www.math.sci.hiroshima-u.ac.jp/~m- | |||

mat/MT/TINYMT/> | mat/MT/TINYMT/> | |||

o Official github site and reference implementation: | o Official github site and reference implementation: | |||

<https://github.com/MersenneTwister-Lab/TinyMT> | <https://github.com/MersenneTwister-Lab/TinyMT> | |||

For the RLC FEC Schemes defined in this document, the tinymt32 32-bit | For the RLC FEC Schemes defined in this document, the TinyMT32 32-bit | |||

version (rather than the 64-bit version) MUST be used. This PRNG | version (rather than the 64-bit version) MUST be used. This PRNG | |||

requires a parameter set that needs to be pre-calculated. For the | requires a parameter set that needs to be pre-calculated. For the | |||

RLC FEC Schemes defined in this document, the following parameter set | RLC FEC Schemes defined in this document, the following parameter set | |||

MUST be used: | MUST be used: | |||

o mat1 = 0x8f7011ee = 2406486510; | o mat1 = 0x8f7011ee = 2406486510 | |||

o mat2 = 0xfc78ff1f = 4235788063; | o mat2 = 0xfc78ff1f = 4235788063 | |||

o tmat = 0x3793fdff = 932445695. | o tmat = 0x3793fdff = 932445695 | |||

This parameter set is the first entry of the precalculated parameter | This parameter set is the first entry of the precalculated parameter | |||

sets in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, and | sets in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, and | |||

available at: | available at <https://github.com/jj1bdx/tinymtdc- | |||

longbatch/blob/master/tinymt32dc/tinymt32dc.0.1048576.txt>. This is | ||||

o <https://github.com/jj1bdx/tinymtdc- | also the parameter set used in [KR12]. | |||

longbatch/blob/master/tinymt32dc/tinymt32dc.0.1048576.txt>. | ||||

This is also the parameter set used in [KR12]. | ||||

The PRNG reference implementation is distributed under a BSD license | ||||

and excerpts of it are reproduced in Appendix A. In order to | ||||

validate an implementation of this PRNG, using seed 1, the 10,000th | ||||

value returned by: tinymt32_rand(s, 0xffff) MUST be equal to 0x7c37. | ||||

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. The following function is used to this purpose: | used as a seed. The following function is used to this purpose: | |||

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 equal to 0), since this is the | that this PRNG accepts a seed value equal to 0), since this is the | |||

Repair_Key 16-bit field value of the Repair FEC Payload ID | Repair_Key 16-bit field value of the Repair FEC Payload ID | |||

(Section 4.1.3). In addition to the seed, this function takes as | (Section 4.1.3). In addition to the seed, this function takes as | |||

parameter a pointer to an instance of a tinymt32_t structure that is | parameter a pointer to an instance of a tinymt32_t structure that is | |||

used to keep the internal state of the PRNG. | used to keep the internal state of the PRNG. | |||

Then, each time a new pseudo-random integer between 0 and maxv-1 | Then, each time a new pseudo-random integer between 0 and 15 | |||

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

function is used: | ||||

uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv); | uint32_t tinymt32_rand16 (tinymt32_t * s); | |||

This function takes as parameter both a pointer to the same | This function takes as parameter a pointer to the same tinymt32_t | |||

tinymt32_t structure (that needs to be left unchanged between | structure (that needs to be left unchanged between successive calls | |||

successive calls to the function) and the maxv value. | to the function). Similarly, each time a new pseudo-random integer | |||

between 0 and 255 inclusive (8-bit pseudo-random integer) is needed, | ||||

the following function is used: | ||||

3.5. Coding Coefficients Generation Function | uint32_t tinymt32_rand256 (tinymt32_t * s); | |||

These two functions keep respectively the 4 or 8 less significant | ||||

bits of the 32-bit pseudo-random number generated by the | ||||

tinymt32_generate_uint32() TinyMT32 function. Test results discussed | ||||

in Appendix B show that this simple technique, applied to this PRNG, | ||||

is in line with the RLC FEC Schemes needs. | ||||

The TinyMT32 PRNG reference implementation is reproduced in Figure 2, | ||||

with the following differences with respect to the original source | ||||

code: | ||||

o the source code initially spread over the tinymt32.h and | ||||

tinymt32.c files has been merged; | ||||

o the unused parts of the original source code have been removed; | ||||

o the unused constants TINYMT32_MEXP and TINYMT32_MUL have been | ||||

removed; | ||||

o the appropriate parameter set has been added to the initialization | ||||

function; | ||||

o the function order has been changed; | ||||

o certain internal variables have been renamed for compactness | ||||

purposes; | ||||

o the constant definitions use the const qualifier; | ||||

o the tinymt32_rand16() and tinymt32_rand256() functions have been | ||||

added in order to scale the initial 32-bit value over a smaller | ||||

interval; | ||||

o the IETF Trusteed copyright has been added to this derived work. | ||||

<CODE BEGINS> | ||||

/** | ||||

* Tiny Mersenne Twister only 127 bit internal state | ||||

* | ||||

* Authors : Mutsuo Saito (Hiroshima University) | ||||

* Makoto Matsumoto (University of Tokyo) | ||||

* | ||||

* Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto, | ||||

* Hiroshima University and The University of Tokyo. | ||||

* All rights reserved. | ||||

* | ||||

* Redistribution and use in source and binary forms, with or without | ||||

* modification, are permitted provided that the following conditions | ||||

* are met: | ||||

* | ||||

* - Redistributions of source code must retain the above copyright | ||||

* notice, this list of conditions and the following disclaimer. | ||||

* - Redistributions in binary form must reproduce the above | ||||

* copyright notice, this list of conditions and the following | ||||

* disclaimer in the documentation and/or other materials | ||||

* provided with the distribution. | ||||

* - Neither the name of the Hiroshima University nor the names of | ||||

* its contributors may be used to endorse or promote products | ||||

* derived from this software without specific prior written | ||||

* permission. | ||||

* | ||||

* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND | ||||

* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, | ||||

* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF | ||||

* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | ||||

* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS | ||||

* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | ||||

* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED | ||||

* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||||

* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON | ||||

* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR | ||||

* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF | ||||

* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||||

* SUCH DAMAGE. | ||||

*/ | ||||

/** | ||||

* The derived work of this document is: | ||||

* Copyright (c) 2018 IETF Trust and the persons identified as the | ||||

* document authors. All rights reserved. | ||||

*/ | ||||

#include <stdint.h> | ||||

/** | ||||

* tinymt32 internal state vector and parameters | ||||

*/ | ||||

typedef struct { | ||||

uint32_t status[4]; | ||||

uint32_t mat1; | ||||

uint32_t mat2; | ||||

uint32_t tmat; | ||||

} tinymt32_t; | ||||

static void tinymt32_next_state (tinymt32_t * s); | ||||

static uint32_t tinymt32_temper (tinymt32_t * s); | ||||

static uint32_t tinymt32_generate_uint32 (tinymt32_t * s); | ||||

/** | ||||

* Parameter set to use for the IETF RLC FEC Schemes specification. | ||||

* Do not change. | ||||

* This parameter set is the first entry of the precalculated | ||||

* parameter sets in file tinymt32dc.0.1048576.txt, by Kenji | ||||

* Rikitake, available at: | ||||

* https://github.com/jj1bdx/tinymtdc-longbatch/blob/master/ | ||||

* tinymt32dc/tinymt32dc.0.1048576.txt | ||||

* It is also the parameter set used: | ||||

* Rikitake, K., "TinyMT Pseudo Random Number Generator for | ||||

* Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), | ||||

* September, 2012. | ||||

*/ | ||||

const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee); | ||||

const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f); | ||||

const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff); | ||||

/** | ||||

* This function initializes the internal state array with a 32-bit | ||||

* unsigned integer seed. | ||||

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

* @param seed a 32-bit unsigned integer used as a seed. | ||||

*/ | ||||

void tinymt32_init (tinymt32_t * s, uint32_t seed) | ||||

{ | ||||

const uint32_t MIN_LOOP = 8; | ||||

const uint32_t PRE_LOOP = 8; | ||||

s->status[0] = seed; | ||||

s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM; | ||||

s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM; | ||||

s->status[3] = s->tmat = TINYMT32_TMAT_PARAM; | ||||

for (int i = 1; i < MIN_LOOP; i++) { | ||||

s->status[i & 3] ^= i + UINT32_C(1812433253) | ||||

* (s->status[(i - 1) & 3] | ||||

^ (s->status[(i - 1) & 3] >> 30)); | ||||

} | ||||

for (int i = 0; i < PRE_LOOP; i++) { | ||||

tinymt32_next_state(s); | ||||

} | ||||

} | ||||

/** | ||||

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

* | ||||

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

* @return unsigned integer between 0 and 15 inclusive. | ||||

*/ | ||||

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

{ | ||||

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

} | ||||

/** | ||||

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

* | ||||

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

* @return unsigned integer between 0 and 255 inclusive. | ||||

*/ | ||||

uint32_t tinymt32_rand256(tinymt32_t *s) | ||||

{ | ||||

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

} | ||||

/** | ||||

* Internal tinymt32 constants and functions. | ||||

* Users should not call these functions directly. | ||||

*/ | ||||

const uint32_t TINYMT32_SH0 = 1; | ||||

const uint32_t TINYMT32_SH1 = 10; | ||||

const uint32_t TINYMT32_SH8 = 8; | ||||

const uint32_t TINYMT32_MASK = UINT32_C(0x7fffffff); | ||||

/** | ||||

* This function changes internal state of tinymt32. | ||||

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

*/ | ||||

static void tinymt32_next_state (tinymt32_t * s) | ||||

{ | ||||

uint32_t x; | ||||

uint32_t y; | ||||

y = s->status[3]; | ||||

x = (s->status[0] & TINYMT32_MASK) | ||||

^ s->status[1] | ||||

^ s->status[2]; | ||||

x ^= (x << TINYMT32_SH0); | ||||

y ^= (y >> TINYMT32_SH0) ^ x; | ||||

s->status[0] = s->status[1]; | ||||

s->status[1] = s->status[2]; | ||||

s->status[2] = x ^ (y << TINYMT32_SH1); | ||||

s->status[3] = y; | ||||

s->status[1] ^= -((int32_t)(y & 1)) & s->mat1; | ||||

s->status[2] ^= -((int32_t)(y & 1)) & s->mat2; | ||||

} | ||||

/** | ||||

* This function outputs 32-bit unsigned integer from internal state. | ||||

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

* @return 32-bit unsigned pseudos number | ||||

*/ | ||||

static uint32_t tinymt32_temper (tinymt32_t * s) | ||||

{ | ||||

uint32_t t0, t1; | ||||

t0 = s->status[3]; | ||||

t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8); | ||||

t0 ^= t1; | ||||

t0 ^= -((int32_t)(t1 & 1)) & s->tmat; | ||||

return t0; | ||||

} | ||||

/** | ||||

* This function outputs 32-bit unsigned integer from internal state. | ||||

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

* @return 32-bit unsigned integer r (0 <= r < 2^32) | ||||

*/ | ||||

static uint32_t tinymt32_generate_uint32 (tinymt32_t * s) { | ||||

tinymt32_next_state(s); | ||||

return tinymt32_temper(s); | ||||

} | ||||

<CODE ENDS> | ||||

Figure 2: TinyMT32 Reference Implementation | ||||

In addition to that, any implementation of this TinyMT32 PRNG MUST | ||||

fulfill three validation criteria detailed in Appendix A. These | ||||

criteria consist in several random number sequences that MUST be | ||||

matched. The first criteria focusses on the internal TinyMT32 | ||||

unsigned 32-bit integer generator, the two others include the mapping | ||||

to 4-bit and 8-bit intervals. | ||||

Finally, the deterministic behavior of the implementation of Figure 2 | ||||

has been checked across several platforms, from high-end 64-bit Mac | ||||

OSX and Linux/Ubuntu laptops, to various low-end embedded cards based | ||||

on 32-bit, 16-bit and 8-bit microcontrollers running RIOT | ||||

[Baccelli18] (details in Appendix A). | ||||

3.6. Coding Coefficients Generation Function | ||||

The coding coefficients, used during the encoding process, are | The coding coefficients, used during the encoding process, are | |||

generated at the RLC encoder by the generate_coding_coefficients() | generated at the RLC encoder by the generate_coding_coefficients() | |||

function each time a new repair symbol needs to be produced. The | function each time a new repair symbol needs to be produced. The | |||

fraction of coefficients that are non zero (i.e., the density) is | fraction of coefficients that are non zero (i.e., the density) is | |||

controlled by the DT (Density Threshold) parameter. When DT equals | controlled by the DT (Density Threshold) parameter. DT has values | |||

15, the maximum value, the function guaranties that all coefficients | between 0 (the minimum value) and 15 (the maximum value), and the | |||

are non zero (i.e., maximum density). When DT is between 0 (minimum | average probability of having a non zero coefficient equals (DT + 1) | |||

value) and strictly inferior to 15, the average probability of having | / 16. In particular, when DT equals 15 the function guaranties that | |||

a non zero coefficient equals (DT +1) / 16. | all coefficients are non zero (i.e., maximum density). | |||

These considerations apply 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 MUST be 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 MUST be equal to 8. | With RLC over GF(2^^8) FEC Scheme (Section 4), m is equal to 8. | |||

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

/* | /* | |||

* Fills in the table of coding coefficients (of the right size) | * Fills in the table of coding coefficients (of the right size) | |||

* provided with the appropriate number of coding coefficients to | * provided with the appropriate number of coding coefficients to | |||

* use for the repair symbol key provided. | * use for the repair symbol key provided. | |||

* | * | |||

* (in) repair_key key associated to this repair symbol. This | * (in) repair_key key associated to this repair symbol. This | |||

* parameter is ignored (useless) if m=2 and dt=15 | * parameter is ignored (useless) if m=1 and dt=15 | |||

* (in) cc_tab[] pointer to a table of the right size to store | * (in/out) cc_tab[] pointer to a table of the right size to store | |||

* coding coefficients. All coefficients are | * coding coefficients. All coefficients are | |||

* stored as bytes, regardless of the m parameter, | * stored as bytes, regardless of the m parameter, | |||

* upon return of this function. | * upon return of this function. | |||

* (in) cc_nb number of entries in the table. This value is | * (in) cc_nb number of entries in the table. This value is | |||

* equal to the current encoding window size. | * equal to the current encoding window size. | |||

* (in) dt integer between 0 and 15 (inclusive) that | * (in) dt integer between 0 and 15 (inclusive) that | |||

* controls the density. With value 15, all | * controls the density. With value 15, all | |||

* coefficients are guaranteed to be non zero | * coefficients are guaranteed to be non zero | |||

* (i.e. equal to 1 with GF(2) and equal to a | * (i.e. equal to 1 with GF(2) and equal to a | |||

* value in {1,... 255} with GF(2^^8)), otherwise | * value in {1,... 255} with GF(2^^8)), otherwise | |||

* a fraction of them will be 0. | * a fraction of them will be 0. | |||

* (in) m Finite Field GF(2^^m) parameter. In this | * (in) m Finite Field GF(2^^m) parameter. In this | |||

* document only values 1 and 8 are considered. | * document only values 1 and 8 are considered. | |||

* (out) returns an error code | * (out) returns 0 in case of success, an error code | |||

* different than 0 otherwise. | ||||

*/ | */ | |||

int generate_coding_coefficients (uint16_t repair_key, | int generate_coding_coefficients (uint16_t repair_key, | |||

uint8_t cc_tab[], | uint8_t cc_tab[], | |||

uint16_t cc_nb, | uint16_t cc_nb, | |||

uint8_t dt, | uint8_t dt, | |||

uint8_t m) | uint8_t m) | |||

{ | { | |||

uint32_t i; | uint32_t i; | |||

tinymt32_t s; /* PRNG internal state */ | tinymt32_t s; /* PRNG internal state */ | |||

if (dt > 15) { | if (dt > 15) { | |||

return SOMETHING_WENT_WRONG; /* bad dt parameter */ | return -1; /* error, bad dt parameter */ | |||

} | } | |||

switch (m) { | switch (m) { | |||

case 1: | case 1: | |||

if (dt == 15) { | if (dt == 15) { | |||

/* all coefficients are 1 */ | /* all coefficients are 1 */ | |||

memset(cc_tab, 1, cc_nb); | memset(cc_tab, 1, cc_nb); | |||

} else { | } else { | |||

/* here coefficients are either 0 or 1 */ | /* here coefficients are either 0 or 1 */ | |||

tinymt32_init(&s, repair_key); | tinymt32_init(&s, repair_key); | |||

for (i = 0 ; i < cc_nb ; i++) { | for (i = 0 ; i < cc_nb ; i++) { | |||

if (tinymt32_rand(&s, 16) <= dt) { | cc_tab[i] = (tinymt32_rand16(&s) <= dt) ? 1 : 0; | |||

cc_tab[i] = (uint8_t) 1; | ||||

} else { | ||||

cc_tab[i] = (uint8_t) 0; | ||||

} | ||||

} | } | |||

} | } | |||

break; | break; | |||

case 8: | case 8: | |||

tinymt32_init(&s, repair_key); | tinymt32_init(&s, repair_key); | |||

if (dt == 15) { | if (dt == 15) { | |||

/* coefficient 0 is avoided here in order to include | /* coefficient 0 is avoided here in order to include | |||

* all the source symbols */ | * all the source symbols */ | |||

for (i = 0 ; i < cc_nb ; i++) { | for (i = 0 ; i < cc_nb ; i++) { | |||

do { | do { | |||

cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256); | cc_tab[i] = (uint8_t) tinymt32_rand256(&s); | |||

} while (cc_tab[i] == 0); | } while (cc_tab[i] == 0); | |||

} | } | |||

} else { | } else { | |||

/* here a certain fraction of coefficients should be 0 */ | /* here a certain number of coefficients should be 0 */ | |||

for (i = 0 ; i < cc_nb ; i++) { | for (i = 0 ; i < cc_nb ; i++) { | |||

if (tinymt32_rand(&s, 16) <= dt) { | if (tinymt32_rand16(&s) <= dt) { | |||

do { | do { | |||

cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256); | cc_tab[i] = (uint8_t) tinymt32_rand256(&s); | |||

} while (cc_tab[i] == 0); | } while (cc_tab[i] == 0); | |||

} else { | } else { | |||

cc_tab[i] = 0; | cc_tab[i] = 0; | |||

} | } | |||

} | } | |||

} | } | |||

break; | break; | |||

default: | default: | |||

return -2; /* error, bad parameter m */ | ||||

/* bad parameter m */ | ||||

return SOMETHING_WENT_WRONG; | ||||

} | } | |||

return EVERYTHING_IS_OKAY; | return 0 /* success */ | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

Figure 2: Coding Coefficients Generation Function pseudo-code | Figure 3: Coding Coefficients Generation Function Reference | |||

Implementation | ||||

3.6. Finite Fields Operations | 3.7. Finite Fields Operations | |||

3.6.1. Finite Field Definitions | 3.7.1. Finite Field Definitions | |||

The two RLC FEC Schemes specified in this document reuse the Finite | The two RLC FEC Schemes specified in this document reuse the Finite | |||

Fields defined in [RFC5510], section 8.1. More specifically, the | Fields defined in [RFC5510], section 8.1. More specifically, the | |||

elements of the field GF(2^^m) are represented by polynomials with | elements of the field GF(2^^m) are represented by polynomials with | |||

binary coefficients (i.e., over GF(2)) and degree lower or equal to | binary coefficients (i.e., over GF(2)) and degree lower or equal to | |||

m-1. The addition between two elements is defined as the addition of | m-1. The addition between two elements is defined as the addition of | |||

binary polynomials in GF(2), which is equivalent to a bitwise XOR | binary polynomials in GF(2), which is equivalent to a bitwise XOR | |||

operation on the binary representation of these elements. | operation on the binary representation of these elements. | |||

With GF(2^^8), multiplication between two elements is the | With GF(2^^8), multiplication between two elements is the | |||

multiplication modulo a given irreducible polynomial of degree 8. | multiplication modulo a given irreducible polynomial of degree 8. | |||

The following irreducible polynomial MUST be used for GF(2^^8): | The following irreducible polynomial MUST be 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.6.2. Linear Combination of Source Symbols Computation | 3.7.2. Linear Combination of Source Symbols Computation | |||

The two RLC FEC Schemes require the computation of a linear | The two RLC FEC Schemes require the computation of a linear | |||

combination of source symbols, using the coding coefficients produced | combination of source symbols, using the coding coefficients produced | |||

by the generate_coding_coefficients() function and stored in the | by the generate_coding_coefficients() function and stored in the | |||

cc_tab[] array. | cc_tab[] array. | |||

With the RLC over GF(2^^8) FEC Scheme, a linear combination of the | With the RLC over GF(2^^8) FEC Scheme, a linear combination of the | |||

ew_size source symbol present in the encoding window, say src_0 to | ew_size source symbol present in the encoding window, say src_0 to | |||

src_ew_size_1, in order to generate a repair symbol, is computed as | src_ew_size_1, in order to generate a repair symbol, is computed as | |||

follows. For each byte of position i in each source and the repair | follows. For each byte of position i in each source and the repair | |||

symbol, where i belongs to {0; E-1}, compute: | symbol, where i belongs to {0; E-1}, compute: | |||

repair[i] = cc_tab[0] * src_0[i] + cc_tab[1] * src_1[i] + ... + | repair[i] = cc_tab[0] * src_0[i] XOR cc_tab[1] * src_1[i] 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) and + is an XOR | where * is the multiplication over GF(2^^8). In practice various | |||

operation. In practice various optimizations need to be used in | optimizations need to be used in order to make this computation | |||

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

skipping to change at page 19, line 4 ¶ | skipping to change at page 21, line 12 ¶ | |||

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

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

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

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

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

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 | fssi=E:1400,WSR:191 | |||

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

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 (for instance, after a Base64 encoding), the encoding | octet string, the encoding format consists of the following three | |||

format consists of the following 2 octets: | octets, where the E field is carried in "big-endian" or "network | |||

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

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

Window Size Ratio Parameter (WSR): 8-bit field. | ||||

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

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | subject to an additional Base64 encoding. | |||

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

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

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

Figure 3: FSSI Encoding Format | 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 | ||||

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

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

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

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 4. | 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 4: Structure of an FEC Source Packet with the Explicit Source | Figure 5: Structure of an FEC Source Packet with the Explicit Source | |||

FEC Payload ID | 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 (Figure 5): | following field, carried in "big-endian" or "network order" format, | |||

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 5: Source FEC Payload ID Encoding Format | Figure 6: Source FEC Payload ID Encoding Format | |||

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

A FEC Repair Packet MAY contain one or more repair symbols. When | A FEC Repair Packet MAY contain one or more repair symbols. When | |||

there are several repair symbols, all of them MUST have been | there are several repair symbols, all of them MUST have been | |||

generated from the same encoding window, using Repair_Key values that | generated from the same encoding window, using Repair_Key values that | |||

are managed as explained below. A receiver can easily deduce the | are managed as explained below. A receiver can easily deduce the | |||

number of repair symbols within a FEC Repair Packet by comparing the | number of repair symbols within a FEC Repair Packet by comparing the | |||

received FEC Repair Packet size (equal to the UDP payload size when | received FEC Repair Packet size (equal to the UDP payload size when | |||

UDP is the underlying transport protocol) and the symbol size, E, | UDP is the underlying transport protocol) and the symbol size, E, | |||

communicated in the FFCI. | communicated in the FFCI. | |||

A FEC Repair Packet MUST contain a Repair FEC Payload ID that is | A FEC Repair Packet MUST contain a Repair FEC Payload ID that is | |||

prepended to the repair symbol as illustrated in Figure 6. | prepended to the repair symbol as illustrated in Figure 7. | |||

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

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

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

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

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

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

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

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

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

Figure 6: 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 (Figure 7): | following fields where all integer fields are carried in "big-endian" | |||

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

(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.5) in order to | by the coefficient generation function (Section 3.6) in order to | |||

generate the desired number of coding coefficients. When a FEC | generate the desired number of coding coefficients. This repair | |||

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

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.5. 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 non zero 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; | |||

skipping to change at page 21, line 33 ¶ | skipping to change at page 24, line 16 ¶ | |||

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

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

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

4.1.4. Additional Procedures | ||||

The following procedure applies: | 4.2. Procedures | |||

o The ESI of source symbols MUST start with value 0 for the first | All the procedures of Section 3 apply to this FEC Scheme. | |||

source symbol and MUST be managed sequentially. Wrapping to zero | ||||

happens after reaching the maximum 32-bit value. | ||||

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 | o FEC Encoding ID: the value assigned to this fully specified FEC | |||

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

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

skipping to change at page 22, line 20 ¶ | skipping to change at page 24, line 45 ¶ | |||

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

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

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

All the considerations of Section 4.1.1.2 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 | |||

it is RECOMMENDED that the sender use value 0 for the Repair_Key | the FECFRAME sender MUST set the Repair_Key field to zero on | |||

field, but a receiver SHALL ignore this field. | transmission and a receiver MUST ignore it on receipt. | |||

5.1.4. Additional Procedures | 5.2. Procedures | |||

All the considerations of Section 4.1.1.2 apply here. | 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 | |||

encoding window. Then it chooses a repair key, which can be a | encoding window. Then it chooses a repair key, which can be a | |||

monotonically increasing integer value, incremented for each repair | monotonically increasing integer value, incremented for each repair | |||

symbol up to a maximum value of 65535 (as it is carried within a | symbol up to a maximum value of 65535 (as it is carried within a | |||

16-bit field) after which it loops back to 0. This repair key is | 16-bit field) after which it loops back to 0. This repair key is | |||

communicated to the coefficient generation function (Section 3.5) in | communicated to the coefficient generation function (Section 3.6) in | |||

order to generate ew_size coding coefficients. Finally, the FECFRAME | order to generate ew_size coding coefficients. Finally, the FECFRAME | |||

sender computes the repair symbol as a linear combination of the | sender computes the repair symbol as a linear combination of the | |||

ew_size source symbols using the ew_size coding coefficients | ew_size source symbols using the ew_size coding coefficients | |||

(Section 3.6). When E is small and when there is an incentive to | (Section 3.7). When E is small and when there is an incentive to | |||

pack several repair symbols within the same FEC Repair Packet, the | pack several repair symbols within the same FEC Repair Packet, the | |||

appropriate number of repair symbols are computed. In that case the | appropriate number of repair symbols are computed. In that case the | |||

repair key for each of them MUST be incremented by 1, keeping the | repair key for each of them MUST be incremented by 1, keeping the | |||

same ew_size source symbols, since only the first repair key will be | same ew_size source symbols, since only the first repair key will be | |||

carried in the Repair FEC Payload ID. The FEC Repair Packet can then | carried in the Repair FEC Payload ID. The FEC Repair Packet can then | |||

be passed to the transport layer for transmission. The source versus | be passed to the transport layer for transmission. The source versus | |||

repair FEC packet transmission order is out of scope of this document | repair FEC packet transmission order is out of scope of this document | |||

and several approaches exist that are implementation specific. | and several approaches exist that are implementation-specific. | |||

Other solutions are possible to select a repair key value when a new | Other solutions are possible to select a repair key value when a new | |||

FEC Repair Packet is needed, for instance by choosing a random | FEC Repair Packet is needed, for instance, by choosing a random | |||

integer between 0 and 65535. However, selecting the same repair key | integer between 0 and 65535. However, selecting the same repair key | |||

as before (which may happen in case of a random process) is only | as before (which may happen in case of a random process) is only | |||

meaningful if the encoding window has changed, otherwise the same FEC | meaningful if the encoding window has changed, otherwise the same FEC | |||

Repair Packet will be generated. | Repair Packet will be generated. | |||

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

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

RLC decoder. | RLC decoder. | |||

A FECFRAME receiver needs to maintain a linear system whose variables | A FECFRAME receiver needs to maintain a linear system whose variables | |||

are the received and lost source symbols. Upon receiving a FEC | are the received and lost source symbols. Upon receiving a FEC | |||

Repair Packet, a receiver first extracts all the repair symbols it | Repair Packet, a receiver first extracts all the repair symbols it | |||

contains (in case several repair symbols are packed together). For | contains (in case several repair symbols are packed together). For | |||

each repair symbol, when at least one of the corresponding source | each repair symbol, when at least one of the corresponding source | |||

symbols it protects has been lost, the receiver adds an equation to | symbols it protects has been lost, the receiver adds an equation to | |||

the linear system (or no equation if this repair packet does not | the linear system (or no equation if this repair packet does not | |||

change the linear system rank). This equation of course re-uses the | change the linear system rank). This equation of course re-uses the | |||

ew_size coding coefficients that are computed by the same coefficient | ew_size coding coefficients that are computed by the same coefficient | |||

generation function (Section Section 3.5), using the repair key and | generation function (Section Section 3.6), using the repair key and | |||

encoding window descriptions carried in the Repair FEC Payload ID. | encoding window descriptions carried in the Repair FEC Payload ID. | |||

Whenever possible (i.e., when a sub-system covering one or more lost | Whenever possible (i.e., when a sub-system covering one or more lost | |||

source symbols is of full rank), decoding is performed in order to | source symbols is of full rank), decoding is performed in order to | |||

recover lost source symbols. Each time an ADUI can be totally | recover lost source symbols. Gaussian elimination is one possible | |||

recovered, padding is removed (thanks to the Length field, L, of the | algorithm to solve this linear system. Each time an ADUI can be | |||

ADUI) and the ADU is assigned to the corresponding application flow | totally recovered, padding is removed (thanks to the Length field, L, | |||

(thanks to the Flow ID field, F, of the ADUI). This ADU is finally | of the ADUI) and the ADU is assigned to the corresponding application | |||

passed to the corresponding upper application. Received FEC Source | flow (thanks to the Flow ID field, F, of the ADUI). This ADU is | |||

Packets, containing an ADU, MAY be passed to the application either | finally passed to the corresponding upper application. Received FEC | |||

immediately or after some time to guaranty an ordered delivery to the | Source Packets, containing an ADU, MAY be passed to the application | |||

application. This document does not mandate any approach as this is | either immediately or after some time to guaranty an ordered delivery | |||

an operational and management decision. | to the application. This document does not mandate any approach as | |||

this is an operational and management decision. | ||||

With real-time flows, a lost ADU that is decoded after the maximum | With real-time flows, a lost ADU that is decoded after the maximum | |||

latency or an ADU received after this delay has no value to the | latency or an ADU received after this delay has no value to the | |||

application. This raises the question of deciding whether or not an | application. This raises the question of deciding whether or not an | |||

ADU is late. This decision MAY be taken within the FECFRAME receiver | ADU is late. This decision MAY be taken within the FECFRAME receiver | |||

(e.g., using the decoding window, see Section 3.1) or within the | (e.g., using the decoding window, see Section 3.1) or within the | |||

application (e.g., using RTP timestamps within the ADU). Deciding | application (e.g., using RTP timestamps within the ADU). Deciding | |||

which option to follow and whether or not to pass all ADUs, including | which option to follow and whether or not to pass all ADUs, including | |||

those assumed late, to the application are operational decisions that | those assumed late, to the application are operational decisions that | |||

depend on the application and are therefore out of scope of this | depend on the application and are therefore out of scope of this | |||

document. Additionally, Appendix B 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. Implementation Status | |||

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

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

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

exists: | exists: | |||

skipping to change at page 24, line 27 ¶ | skipping to change at page 27, line 4 ¶ | |||

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

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

exists: | exists: | |||

o Organisation: Inria | o Organisation: Inria | |||

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

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

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

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

o Maturity: prototype. | o Maturity: prototype. | |||

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

Scheme. | Scheme. | |||

o Licensing: proprietary. | o Licensing: proprietary. | |||

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

8. Security Considerations | 8. Security Considerations | |||

The FEC Framework document [RFC6363] provides a 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 | 8.1. Attacks Against the Data Flow | |||

8.1.1. Access to Confidential Content | 8.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 | |||

skipping to change at page 25, line 31 ¶ | skipping to change at page 28, line 7 ¶ | |||

o FEC Encoding ID: changing this parameter leads a receiver to | o 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 YYYY (i.e., RLC over GF(2)) to value XXXX | |||

(RLC over GF(2^^8)), an additional consequence being a higher | (RLC 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); | results in a form of Denial of Service (DoS) or corrupted content. | |||

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

different value will confuse a receiver. If the size of a | different value will confuse a receiver. If the size of a | |||

received FEC Repair Packet is no longer multiple of the modified E | received FEC Repair Packet is no longer multiple of the modified E | |||

value, a receiver quickly detects a problem and SHOULD reject the | value, a receiver quickly detects a problem and SHOULD reject the | |||

packet. If the new E value is a sub-multiple of the original E | packet. If the new E value is a sub-multiple of the original E | |||

value (e.g., half the original value), then receivers may not | value (e.g., half the original value), then receivers may not | |||

detect the problem immediately. For instance a receiver may think | detect the problem immediately. For instance, a receiver may | |||

that a received FEC Repair Packet contains more repair symbols | think that a received FEC Repair Packet contains more repair | |||

(e.g., twice as many if E is reduced by half), leading to | symbols (e.g., twice as many if E is reduced by half), leading to | |||

malfunctions whose nature depends on implementation details. Here | malfunctions whose nature depends on implementation details. Here | |||

also, the attack always results in a form of DoS; | also, the 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: | |||

skipping to change at page 27, line 9 ¶ | skipping to change at page 29, line 32 ¶ | |||

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/ESP security protocol as a mandatory to implement (but not | |||

mandatory to use) security scheme. This is well suited to situations | mandatory to use) security scheme. This is well suited to situations | |||

where the only insecure domain is the one over which the FEC | where the only insecure domain is the one over which the FEC | |||

Framework operates. | Framework operates. | |||

8.5. Additional Security Considerations for Numerical Computations | 8.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 Section 3.1.1. It is RECOMMENDED to check that the | particular in Appendix C.1. It is RECOMMENDED to check that the | |||

computed values stay within reasonnable 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 behaviours. However, what | |||

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

Section 3.1.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 behaviours 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 | |||

reasonnable bounds. | reasonable bounds. | |||

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

The FEC Framework document [RFC6363] provides a 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) | 9.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^^8) | |||

The present document specifies two FEC Schemes that differ on the | The present document specifies two FEC Schemes that differ on the | |||

Finite Field used for the coding coefficients. It is expected that | Finite Field used for the coding coefficients. It is expected that | |||

the RLC over GF(2^^8) FEC Scheme will be mostly used since it | the RLC over GF(2^^8) FEC Scheme will be mostly used since it | |||

warrants a higher packet loss protection. In case of small encoding | warrants a higher packet loss protection. In case of small encoding | |||

windows, the associated processing overhead is not an issue (e.g., we | windows, the associated processing overhead is not an issue (e.g., we | |||

measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM | measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM | |||

Cortex-A15 embedded board in [Roca17]). Of course the CPU overhead | Cortex-A15 embedded board in [Roca17] for an encoding window of size | |||

will increase with the encoding window size, because more operations | 18 or 23 symbols). Of course the CPU overhead will increase with the | |||

in the GF(2^^8) finite field will be needed. | encoding window size, because more operations in the GF(2^^8) finite | |||

field will be needed. | ||||

The RLC over GF(2) FEC Scheme offers an alternative. In that case | The RLC over GF(2) FEC Scheme offers an alternative. In that case | |||

operations symbols can be directly XOR-ed together which warrants | operations symbols can be directly XOR-ed together which warrants | |||

high bitrate encoding and decoding operations, and can be an | high bitrate encoding and decoding operations, and can be an | |||

advantage with large encoding windows. However packet loss | advantage with large encoding windows. However, packet loss | |||

protection is significantly reduced by using this FEC Scheme. | protection is significantly reduced by using this FEC Scheme. | |||

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

In addition to the choice of the Finite Field, the two FEC Schemes | In addition to the choice of the Finite Field, the two FEC Schemes | |||

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 non zero 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 compute 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) 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 | 10. 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 | o YYYY 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 | o XXXX refers to the Sliding Window Random Linear Codes (RLC) over | |||

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

Section 4 of this document. | Section 4 of this document. | |||

11. Acknowledgments | 11. Acknowledgments | |||

The authors would like to thank Russ Housley, Alan DeKok, Spencer | The authors would like to thank the three TSVWG chairs, Wesley Eddy, | |||

Dawkins, Gorry Fairhurst, Jonathan Detchart, Emmanuel Lochin, and | our shepherd, David Black and Gorry Fairhurst, as well as Spencer | |||

Marie-Jose Montpetit for their valuable feedbacks on this document. | Dawkins, our responsible AD, and all those who provided comments, | |||

namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ | ||||

Housley, Emmanuel Lochin, and Marie-Jose Montpetit. Last but not | ||||

least, the authors are really grateful to the IESG members, in | ||||

particular Benjamin Kaduk, Mirja Kuhlewind, Eric Rescorla, and Adam | ||||

Roach for their highly valuable feedbacks that greatly contributed to | ||||

improve this specification. | ||||

12. References | 12. References | |||

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

[fecframe-ext] | [fecframe-ext] | |||

Roca, V. and A. Begen, "Forward Error Correction (FEC) | Roca, V. and A. Begen, "Forward Error Correction (FEC) | |||

Framework Extension to Sliding Window Codes", Transport | Framework Extension to Sliding Window Codes", Transport | |||

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

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

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

draft-ietf-tsvwg-fecframe-ext>. | draft-ietf-tsvwg-fecframe-ext>. | |||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

Requirement Levels", BCP 14, RFC 2119, | Requirement Levels", BCP 14, RFC 2119, | |||

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

skipping to change at page 29, line 34 ¶ | skipping to change at page 32, line 16 ¶ | |||

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

12.2. Informative References | 12.2. Informative References | |||

[Baccelli18] | ||||

Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P., | ||||

Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and | ||||

M. Wahlisch, "RIOT: An Open Source Operating System for | ||||

Low-End Embedded Devices in the IoT", IEEE Internet of | ||||

Things Journal (Volume 5, Issue 6), DOI: | ||||

10.1109/JIOT.2018.2815038, December 2018. | ||||

[KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for | [KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for | |||

Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), | Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), | |||

September 14, 2012, Copenhagen, Denmark, DOI: | September 14, 2012, Copenhagen, Denmark, DOI: | |||

http://dx.doi.org/10.1145/2364489.2364504, September 2012. | http://dx.doi.org/10.1145/2364489.2364504, September 2012. | |||

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

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

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

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

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

[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | ||||

Check (LDPC) Staircase and Triangle Forward Error | ||||

Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, | ||||

June 2008, <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>. | |||

[RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, | [RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, | |||

"FLUTE - File Delivery over Unidirectional Transport", | "FLUTE - File Delivery over Unidirectional Transport", | |||

RFC 6726, DOI 10.17487/RFC6726, November 2012, | RFC 6726, DOI 10.17487/RFC6726, November 2012, | |||

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

skipping to change at page 31, line 5 ¶ | skipping to change at page 34, line 5 ¶ | |||

[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), October | |||

2017 https://hal.inria.fr/hal-01571609v1/en/, 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 Pseudo-Random Number Generator | Appendix A. TinyMT32 Validation Criteria (Normative) | |||

The TinyMT32 PRNG reference implementation is distributed under a BSD | PRNG determinism, for a given seed, is a requirement. Consequently, | |||

license by the authors and excerpts of it are reproduced in Figure 8. | in order to validate an implementation of the TinyMT32 PRNG, the | |||

The differences with respect to the original source code are: | following criterias MUST be met. | |||

o the unused parts of the original source code have been removed; | The first criteria focusses on the core TinyMT32 PRNG, that produces | |||

o the appropriate parameter set has been added to the initialization | 32-bit pseudo-random numbers. Using a seed value of 1, the first 50 | |||

function; | values returned by: tinymt32_generate_uint32(s) as 32-bit unsigned | |||

o the tinymt32_rand() function has been added; | integers MUST be equal to values provided in Figure 9. Note that | |||

o the function order has been changed; | these values come from the tinymt/check32.out.txt file provided by | |||

o certain internal variables have been renamed for compactness | the authors to validate implementations of TinyMT32, as part of the | |||

purposes. | MersenneTwister-Lab/TinyMT Github repository. | |||

<CODE BEGINS> | 2545341989 981918433 3715302833 2387538352 3591001365 | |||

/** | 3820442102 2114400566 2196103051 2783359912 764534509 | |||

* Tiny Mersenne Twister only 127 bit internal state | 643179475 1822416315 881558334 4207026366 3690273640 | |||

* | 3240535687 2921447122 3984931427 4092394160 44209675 | |||

* Authors : Mutsuo Saito (Hiroshima University) | 2188315343 2908663843 1834519336 3774670961 3019990707 | |||

* Makoto Matsumoto (University of Tokyo) | 4065554902 1239765502 4035716197 3412127188 552822483 | |||

* | 161364450 353727785 140085994 149132008 2547770827 | |||

* Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto, | 4064042525 4078297538 2057335507 622384752 2041665899 | |||

* Hiroshima University and The University of Tokyo. | 2193913817 1080849512 33160901 662956935 642999063 | |||

* All rights reserved. | 3384709977 1723175122 3866752252 521822317 2292524454 | |||

* | ||||

* Redistribution and use in source and binary forms, with or without | ||||

* modification, are permitted provided that the following conditions | ||||

* are met: | ||||

* | ||||

* - Redistributions of source code must retain the above copyright | ||||

* notice, this list of conditions and the following disclaimer. | ||||

* - Redistributions in binary form must reproduce the above | ||||

* copyright notice, this list of conditions and the following | ||||

* disclaimer in the documentation and/or other materials | ||||

* provided with the distribution. | ||||

* - Neither the name of the Hiroshima University nor the names of | ||||

* its contributors may be used to endorse or promote products | ||||

* derived from this software without specific prior written | ||||

* permission. | ||||

* | ||||

* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND | ||||

* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, | ||||

* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF | ||||

* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | ||||

* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS | ||||

* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | ||||

* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED | ||||

* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||||

* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON | ||||

* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR | ||||

* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF | ||||

* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||||

* SUCH DAMAGE. | ||||

*/ | ||||

#include <stdint.h> | Figure 9: First 50 decimal values returned by | |||

tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed | ||||

value of 1. | ||||

/** | The second criteria focusses on the tinymt32_rand256(), where the | |||

* tinymt32 internal state vector and parameters | 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: | |||

typedef struct { | tinymt32_rand256() as 8-bit unsigned integers MUST be equal to values | |||

uint32_t status[4]; | provided in Figure 10. | |||

uint32_t mat1; | ||||

uint32_t mat2; | ||||

uint32_t tmat; | ||||

} tinymt32_t; | ||||

static void tinymt32_next_state (tinymt32_t * s); | 37 225 177 176 21 | |||

static uint32_t tinymt32_temper (tinymt32_t * s); | 246 54 139 168 237 | |||

static double tinymt32_generate_32double (tinymt32_t * s); | 211 187 62 190 104 | |||

135 210 99 176 11 | ||||

207 35 40 113 179 | ||||

214 254 101 212 211 | ||||

226 41 234 232 203 | ||||

29 194 211 112 107 | ||||

217 104 197 135 23 | ||||

89 210 252 109 166 | ||||

/** | Figure 10: First 50 decimal values returned by tinymt32_rand256() as | |||

* Parameter set to use for the IETF RLC FEC Schemes specification. | 8-bit unsigned integers, with a seed value of 1. | |||

* Do not change. | ||||

* This parameter set is the first entry of the precalculated parameter | ||||

* sets in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, available | ||||

* at: https://github.com/jj1bdx/tinymtdc-longbatch/blob/master/ | ||||

* tinymt32dc/tinymt32dc.0.1048576.txt | ||||

* It is also the parameter set used: | ||||

* Rikitake, K., "TinyMT Pseudo Random Number Generator for | ||||

* Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), | ||||

* September, 2012. | ||||

*/ | ||||

#define TINYMT32_MAT1_PARAM 0x8f7011ee | ||||

#define TINYMT32_MAT2_PARAM 0xfc78ff1f | ||||

#define TINYMT32_TMAT_PARAM 0x3793fdff | ||||

/** | The third criteria focusses on the tinymt32_rand16(), where the | |||

* This function initializes the internal state array with a 32-bit | 32-bit integer of the core TinyMT32 PRNG is scaled down to a 4-bit | |||

* unsigned integer seed. | integer. Using a seed value of 1, the first 50 values returned by: | |||

* @param s pointer to tinymt internal state. | tinymt32_rand16() as 4-bit unsigned integers MUST be equal to values | |||

* @param seed a 32-bit unsigned integer used as a seed. | provided in Figure 11. | |||

*/ | ||||

void tinymt32_init (tinymt32_t * s, uint32_t seed) | ||||

{ | ||||

#define MIN_LOOP 8 | ||||

#define PRE_LOOP 8 | ||||

s->status[0] = seed; | ||||

s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM; | ||||

s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM; | ||||

s->status[3] = s->tmat = TINYMT32_TMAT_PARAM; | ||||

for (int i = 1; i < MIN_LOOP; i++) { | ||||

s->status[i & 3] ^= i + UINT32_C(1812433253) | ||||

* (s->status[(i - 1) & 3] | ||||

^ (s->status[(i - 1) & 3] >> 30)); | ||||

} | ||||

for (int i = 0; i < PRE_LOOP; i++) { | ||||

tinymt32_next_state(s); | ||||

} | ||||

} | ||||

/** | 5 1 1 0 5 | |||

* This function outputs an integer in the [0 .. maxv-1] range. | 6 6 11 8 13 | |||

* @param s pointer to tinymt internal state. | 3 11 14 14 8 | |||

* @return 32-bit unsigned integer between 0 and maxv-1 inclusive. | 7 2 3 0 11 | |||

*/ | 15 3 8 1 3 | |||

uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv) | 6 14 5 4 3 | |||

{ | 2 9 10 8 11 | |||

return (uint32_t)(tinymt32_generate_32double(s) * (double)maxv); | 13 2 3 0 11 | |||

} | 9 8 5 7 7 | |||

9 2 12 13 6 | ||||

/** | Figure 11: First 50 decimal values returned by tinymt32_rand16() as | |||

* Internal tinymt32 constants and functions. | 4-bit unsigned integers, with a seed value of 1. | |||

* Users should not call these functions directly. | ||||

*/ | ||||

#define TINYMT32_MEXP 127 | ||||

#define TINYMT32_SH0 1 | ||||

#define TINYMT32_SH1 10 | ||||

#define TINYMT32_SH8 8 | ||||

#define TINYMT32_MASK UINT32_C(0x7fffffff) | ||||

#define TINYMT32_MUL (1.0f / 16777216.0f) | ||||

/** | The deterministic behavior of the implementation of Figure 2 has been | |||

* This function changes internal state of tinymt32. | checked across several platforms: high-end laptops running 64-bits | |||

* @param s pointer to tinymt internal state. | Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM Cortex-A15 | |||

*/ | and running 32-bit Linux/Ubuntu; several embedded cards featuring | |||

static void tinymt32_next_state (tinymt32_t * s) | either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit | |||

{ | microcontroller, all of them running RIOT [Baccelli18]; two low-end | |||

uint32_t x; | embedded cards featuring either a 16-bit microcontroller (TI MSP430) | |||

uint32_t y; | or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running | |||

RIOT. | ||||

y = s->status[3]; | Appendix B. Assessing the PRNG Adequacy (Informational) | |||

x = (s->status[0] & TINYMT32_MASK) | ||||

^ s->status[1] | ||||

^ s->status[2]; | ||||

x ^= (x << TINYMT32_SH0); | ||||

y ^= (y >> TINYMT32_SH0) ^ x; | ||||

s->status[0] = s->status[1]; | ||||

s->status[1] = s->status[2]; | ||||

s->status[2] = x ^ (y << TINYMT32_SH1); | ||||

s->status[3] = y; | ||||

s->status[1] ^= -((int32_t)(y & 1)) & s->mat1; | ||||

s->status[2] ^= -((int32_t)(y & 1)) & s->mat2; | ||||

} | ||||

/** | This annex discusses the adequacy of the TinyMT32 PRNG and the | |||

* This function outputs 32-bit unsigned integer from internal state. | tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC | |||

* @param s pointer to tinymt internal state. | Schemes. The goal is to assess the adequacy of these two functions | |||

* @return 32-bit unsigned pseudos number | in producing coding coefficients that are sufficiently different from | |||

*/ | one another, across various repair symbols with repair key values in | |||

static uint32_t tinymt32_temper (tinymt32_t * s) | sequence (we can expect this approach to be commonly used by | |||

{ | implementers Section 6.1). This section is purely informational and | |||

uint32_t t0, t1; | does not claim to be a solid evaluation. | |||

t0 = s->status[3]; | ||||

t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8); | ||||

t0 ^= t1; | ||||

t0 ^= -((int32_t)(t1 & 1)) & s->tmat; | ||||

return t0; | ||||

} | ||||

/** | The two RLC FEC Schemes use the PRNG to produce pseudo-random coding | |||

* This function outputs double precision floating point number from | coefficients (Section 3.6), each time a new repair symbol is needed. | |||

* internal state. The returned value has 32-bit precision. | A different repair key is used for each repair symbol, usually by | |||

* In other words, this function makes one double precision floating | incrementing the repair key value (Section 6.1). For each repair | |||

* point number from one 32-bit unsigned integer. | symbol, a limited number of pseudo-random numbers is needed, | |||

* @param s pointer to tinymt internal state. | depending on the DT and encoding window size (Section 3.6), using | |||

* @return floating point number r (0.0 <= r < 1.0) | either tinymt32_rand16() or tinymt32_rand256(). Therefore we are | |||

*/ | more interested in the randomness of small sequences of random | |||

static double tinymt32_generate_32double (tinymt32_t * s) | numbers mapped to 4-bit or 8-bit integers, than in the randomness of | |||

{ | a very large sequence of random nmbers which is not representative of | |||

tinymt32_next_state(s); | the usage of the PRNG. | |||

return (double)tinymt32_temper(s) * (1.0 / 4294967296.0); | ||||

} | ||||

<CODE ENDS> | ||||

Figure 8: TinyMT32 pseudo-code | Evaluation of tinymt32_rand16(): We first generate a huge number | |||

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

sequence), and perform statistics on the number of occurrences of | ||||

each of the 16 possible values across all sequences. | ||||

Appendix B. Decoding Beyond Maximum Latency Optimization | value occurrences percentage (%) (total of 20000000000) | |||

0 1250036799 6.2502 | ||||

1 1249995831 6.2500 | ||||

2 1250038674 6.2502 | ||||

3 1250000881 6.2500 | ||||

4 1250023929 6.2501 | ||||

5 1249986320 6.2499 | ||||

6 1249995587 6.2500 | ||||

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 12: tinymt32_rand16(): occurrence statistics across a huge | ||||

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

per sequence), with 0 as the first PRNG seed. | ||||

The results (Figure 12) show that all possible values are almost | ||||

equally represented, or said differently, that the tinymt32_rand16() | ||||

output converges to a uniform distribution where each of the 16 | ||||

possible value would appear exactly 1 / 16 * 100 = 6.25% of times. | ||||

Other types of biases may exist that may be visible with smaller | ||||

tests (e.g., to evaluation the convergence speed to a uniform | ||||

distribution). We therefore perform 200 tests, each of them | ||||

consisting in producing 200 sequences, keeping ony the first value of | ||||

each sequence. We use non overlapping repair keys for each sequence, | ||||

starting with value 0 and increasing it after each use. | ||||

value min occurrences max occurrences average occurrences | ||||

0 4 21 6.3675 | ||||

1 4 22 6.0200 | ||||

2 4 20 6.3125 | ||||

3 5 23 6.1775 | ||||

4 5 24 6.1000 | ||||

5 4 21 6.5925 | ||||

6 5 30 6.3075 | ||||

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 13: tinymt32_rand16(): occurrence statistics across 200 tests, | ||||

each of them consisting in 200 sequences of 1 pseudo-random number | ||||

each, with non overlapping PRNG seeds in sequence starting from 0. | ||||

Figure 13 shows across all 200 tests, for each of the 16 possible | ||||

pseudo-random number values, the minimum (resp. maximum) number of | ||||

times it appeared in a tests, as well as the average number of | ||||

occurrences across the 200 tests. Although the distribution is not | ||||

perfect, there is no major bias. On the opposite, in the same | ||||

conditions, the Park Miller linear congruential PRNG of [RFC5170] | ||||

with a result scaled down to 4-bit values, using seeds in sequence | ||||

starting from 1, returns systematically 0 as the first value during | ||||

some time, then after a certain repair key value threshold, it | ||||

systematically returns 1, etc. | ||||

Evaluation of tinymt32_rand256(): The same approach is used here. | ||||

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

convergence to the theoretical uniform distribution where each of the | ||||

possible value would appear exactly 1 / 256 * 100 = 0.390625% of | ||||

times. | ||||

Appendix C. Possible Parameter Derivation (Informational) | ||||

Section 3.1 defines several parameters to control the encoder or | ||||

decoder. This annex proposes techniques to derive these parameters | ||||

according to the target use-case. This annex is informational, in | ||||

the sense that using a different derivation technique will not | ||||

prevent the encoder and decoder to interoperate: a decoder can still | ||||

recover an erased source symbol without any error. However, in case | ||||

of a real-time flow, an inappropriate parameter derivation may lead | ||||

to the decoding of erased source packets after their validity period, | ||||

making them useless to the target application. This annex proposes | ||||

an approach to reduce this risk, among other things. | ||||

The FEC Schemes defined in this document can be used in various | ||||

manners, depending on the target use-case: | ||||

o the source ADU flow they protect may or may not have real-time | ||||

constraints; | ||||

o the source ADU flow may be a Constant Bitrate (CBR) or Variable | ||||

BitRate (VBR) flow; | ||||

o with a VBR source ADU flow, the flow's minimum and maximum | ||||

bitrates may or may not be known; | ||||

o and the communication path between encoder and decoder may be a | ||||

CBR communication path (e.g., as with certain LTE-based broadcast | ||||

channels) or not (general case, e.g., with Internet). | ||||

The parameter derivation technique should be suited to the use-case, | ||||

as described in the following sections. | ||||

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

In the following, we consider a real-time flow with max_lat latency | ||||

budget. The encoding symbol size, E, is constant. The code rate, | ||||

cr, is also constant, its value depending on the expected | ||||

communication loss model (this choice is out of scope of this | ||||

document). | ||||

In a first configuration, the source ADU flow bitrate at the input of | ||||

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

transmission bitrate at the output of the FECFRAME sender will be | ||||

higher, depending on the added repair flow overhead. In order to | ||||

comply with the maximum FEC-related latency budget, we have: | ||||

dw_max_size = (max_lat * br_in) / (8 * E) | ||||

assuming that the encoding and decoding times are negligible with | ||||

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

sizes). Otherwise the max_lat parameter should be adjusted in order | ||||

to avoid the problem. In any case, interoperability will never be | ||||

compromized by choosing a too large value. | ||||

In a second configuration, the FECFRAME sender generates a fixed | ||||

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

as in [Roca17]. The maximum source flow bitrate needs to be such | ||||

that, with the added repair flow overhead, the total transmission | ||||

bitrate remains inferior or equal to br_out. We have: | ||||

dw_max_size = (max_lat * br_out * cr) / (8 * E) | ||||

assuming here also that the encoding and decoding times are | ||||

negligible with respect to the target max_lat. | ||||

For decoding to be possible within the latency budget, it is required | ||||

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

main parameter at a FECFRAME sender, but its exact value has no | ||||

impact on the the FEC-related latency budget. The ew_max_size | ||||

parameter is computed as follows: | ||||

ew_max_size = dw_max_size * WSR / 255 | ||||

In line with [Roca17], WSR = 191 is considered as a reasonable value | ||||

(the resulting encoding to decoding window size ratio is then close | ||||

to 0.75), but other values between 1 and 255 inclusive are possible, | ||||

depending on the use-case. | ||||

The dw_max_size is computed by a FECFRAME sender but not explicitly | ||||

communicated to a FECFRAME receiver. However, a FECFRAME receiver | ||||

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 received FEC Repair Packets (Section 4.1.3). A receiver can then | ||||

easily compute dw_max_size: | ||||

dw_max_size = max_NSS_observed * 255 / WSR | ||||

A receiver can then chose an appropriate linear system maximum size: | ||||

ls_max_size >= dw_max_size | ||||

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

interoperability. | ||||

In any case, for a given use-case (i.e., for target encoding and | ||||

decoding devices and desired protection levels in front of | ||||

communication impairments) and for the computed ew_max_size, | ||||

dw_max_size and ls_max_size values, it is RECOMMENDED to check that | ||||

the maximum encoding time and maximum memory requirements at a | ||||

FECFRAME sender, and maximum decoding time and maximum memory | ||||

requirements at a FECFRAME receiver, stay within reasonable bounds. | ||||

When assuming that the encoding and decoding times are negligible | ||||

with respect to the target max_lat, this should be verified as well, | ||||

otherwise the max_lat SHOULD be adjusted accordingly. | ||||

The particular case of session start needs to be managed | ||||

appropriately since the ew_size, starting at zero, increases each | ||||

time a new source ADU is received by the FECFRAME sender, until it | ||||

reaches the ew_max_size value. Therefore a FECFRAME receiver SHOULD | ||||

continuously observe the received FEC Repair Packets, since the NSS | ||||

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

session start is expected to be the only moment when the encoding | ||||

window size will increase. Similarly, with a CBR real-time flow, the | ||||

session end is expected to be the only moment when the encoding | ||||

window size will progressively decrease. No adjustment of the | ||||

ls_max_size is required at the FECFRAME receiver in that case. | ||||

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

In the following, we consider a real-time source ADU flow with a | ||||

max_lat latency budget and a variable bitrate (VBR) measured at the | ||||

entry of the FECFRAME sender. A first approach consists in | ||||

considering the smallest instantaneous bitrate of the source ADU | ||||

flow, when this parameter is known, and to reuse the derivation of | ||||

Appendix C.1. Considering the smallest bitrate means that the | ||||

encoding and decoding window maximum size estimations are | ||||

pessimistic: these windows have the smallest size required to enable | ||||

on-time decoding at a FECFRAME receiver. If the instantaneous | ||||

bitrate is higher than this smallest bitrate, this approach leads to | ||||

an encoding window that is unnecessarily small, which reduces | ||||

robustness in front of long erasure bursts. | ||||

Another approach consists in using ADU timing information (e.g., | ||||

using the timestamp field of an RTP packet header, or registering the | ||||

time upon receiving a new ADU). From the global FEC-related latency | ||||

budget, the FECFRAME sender can derive a practical maximum latency | ||||

budget for encoding operations, max_lat_for_encoding. For the FEC | ||||

Schemes specified in this document, this latency budget SHOULD be | ||||

computed with: | ||||

max_lat_for_encoding = max_lat * WSR / 255 | ||||

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

the encoding window. With this approach there is no pre-determined | ||||

ew_size value: this value fluctuates over the time according to the | ||||

instantaneous source ADU flow bitrate. For practical reasons, a | ||||

FECFRAME sender may still require that ew_size does not increase | ||||

beyond a maximum value (Appendix C.3). | ||||

With both approaches, and no matter the choice of the FECFRAME | ||||

sender, a FECFRAME receiver can still easily evaluate the ew_max_size | ||||

by observing the maximum Number of Source Symbols (NSS) value | ||||

contained in the Repair FEC Payload ID of received FEC Repair | ||||

Packets. A receiver can then compute dw_max_size and derive an | ||||

appropriate ls_max_size as explained in Appendix C.1. | ||||

When the observed NSS fluctuates significantly, a FECFRAME receiver | ||||

may want to adapt its ls_max_size accordingly. In particular when | ||||

the NSS is significantly reduced, a FECFRAME receiver may want to | ||||

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

(which increases computation complexity and memory requirements) and | ||||

the opposite (which reduces recovery performance). | ||||

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

Finally there are configurations where a source ADU flow has no real- | ||||

time constraints. FECFRAME and the FEC Schemes defined in this | ||||

document can still be used. The choice of appropriate parameter | ||||

values can be directed by practical considerations. For instance, it | ||||

can derive from an estimation of the maximum memory amount that could | ||||

be dedicated to the linear system at a FECFRAME receiver, or the | ||||

maximum computation complexity at a FECFRAME receiver, both of them | ||||

depending on the ls_max_size parameter. The same considerations also | ||||

apply to the FECFRAME sender, where the maximum memory amount and | ||||

computation complexity depend on the ew_max_size parameter. | ||||

Here also, the NSS value contained in FEC Repair Packets is used by a | ||||

FECFRAME receiver to determine the current coding window size and | ||||

ew_max_size by observing its maximum value over the time. | ||||

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

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

skipping to change at page 35, line 32 ¶ | skipping to change at page 42, line 17 ¶ | |||

ls_max_size = 2 * dw_max_size | ls_max_size = 2 * dw_max_size | |||

When the dw_max_size is very small, it may be preferable to keep a | When the dw_max_size is very small, it may be preferable to keep a | |||

minimum ls_max_size value (e.g., LS_MIN_SIZE_DEFAULT = 40 symbols). | minimum ls_max_size value (e.g., LS_MIN_SIZE_DEFAULT = 40 symbols). | |||

Going below this threshold will not save a significant amount of | Going below this threshold will not save a significant amount of | |||

memory nor CPU cycles. Therefore: | memory nor CPU cycles. Therefore: | |||

ls_max_size = max(2 * dw_max_size, LS_MIN_SIZE_DEFAULT) | ls_max_size = max(2 * dw_max_size, LS_MIN_SIZE_DEFAULT) | |||

Finally, it is worth noting that a good receiver, i.e., a receiver | Finally, it is worth noting that a receiver that benefits from an FEC | |||

that benefits from an FEC protection significantly higher than what | protection significantly higher than what is required to recover from | |||

is required to recover from packet losses, can choose to reduce the | packet losses, can choose to reduce the ls_max_size. In that case | |||

ls_max_size. In that case lost ADUs will be recovered without | lost ADUs will be recovered without relying on this optimization. | |||

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 9: Relationship between parameters to decode beyond maximum | Figure 14: Relationship between parameters to decode beyond maximum | |||

latency. | 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 9). It follows that | application (the "late source symbols" of Figure 14). It follows | |||

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

Authors' Addresses | Authors' Addresses | |||

skipping to change at page 36, line 21 ¶ | skipping to change at page 43, line 4 ¶ | |||

the other receivers nor on the source. | the other receivers nor on the source. | |||

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@inria.fr | EMail: belkacem.teibi@gmail.com | |||

Emmanuel Baccelli | ||||

INRIA | ||||

France | ||||

EMail: emmanuel.baccelli@inria.fr | ||||

End of changes. 138 change blocks. | ||||

567 lines changed or deleted | | 873 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/ |