draft-ietf-tsvwg-rlc-fec-scheme-02.txt | draft-ietf-tsvwg-rlc-fec-scheme-03.txt | |||
---|---|---|---|---|

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

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

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

Expires: September 5, 2018 March 4, 2018 | Expires: November 7, 2018 May 6, 2018 | |||

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-02 | draft-ietf-tsvwg-rlc-fec-scheme-03 | |||

Abstract | Abstract | |||

This document describes two fully-specified FEC Schemes for Sliding | This document describes two fully-specified Forward Erasure | |||

Window Random Linear Codes (RLC), one for RLC over GF(2) (binary | Correction (FEC) Schemes for Sliding Window Random Linear Codes | |||

case), a second one for RLC over GF(2^^8), both of them with the | (RLC), one for RLC over GF(2) (binary case), a second one for RLC | |||

possibility of controlling the code density. They are meant to | over GF(2^^8), both of them with the possibility of controlling the | |||

protect arbitrary media streams along the lines defined by FECFRAME | code density. They can protect arbitrary media streams along the | |||

extended to sliding window FEC codes. These sliding window FEC codes | lines defined by FECFRAME extended to sliding window FEC codes. | |||

rely on an encoding window that slides over the source symbols, | These sliding window FEC codes rely on an encoding window that slides | |||

generating new repair symbols whenever needed. Compared to block FEC | over the source symbols, generating new repair symbols whenever | |||

codes, these sliding window FEC codes offer key advantages with real- | needed. Compared to block FEC codes, these sliding window FEC codes | |||

time flows in terms of reduced FEC-related latency while often | offer key advantages with real-time flows in terms of reduced FEC- | |||

providing improved erasure recovery capabilities. | related latency while often providing improved packet erasure | |||

recovery capabilities. | ||||

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

This Internet-Draft is submitted in full conformance with the | This Internet-Draft is submitted in full conformance with the | |||

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

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

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

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

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

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

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

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

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

This Internet-Draft will expire on September 5, 2018. | This Internet-Draft will expire on November 7, 2018. | |||

Copyright Notice | Copyright Notice | |||

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

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

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

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

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

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

skipping to change at page 2, line 20 ¶ | skipping to change at page 2, line 23 ¶ | |||

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

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 . . . . . . . . . . . . . . . . . . 5 | 1.4. Document Organization . . . . . . . . . . . . . . . . . . 6 | |||

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

3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 6 | 3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

3.1. Parameters Derivation . . . . . . . . . . . . . . . . . . 7 | 3.1. Possible Parameter Derivation . . . . . . . . . . . . . . 7 | |||

3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9 | 3.1.1. Detailed Parameter Derivation for CBR Real-Time Flows 8 | |||

3.3. Encoding Window Management . . . . . . . . . . . . . . . 10 | 3.1.2. Parameter Derivation for Other Real-Time Flows . . . 10 | |||

3.4. Pseudo-Random Number Generator . . . . . . . . . . . . . 11 | 3.1.3. Parameter Derivation for Non Real-Time Flows . . . . 10 | |||

3.5. Coding Coefficients Generation Function . . . . . . . . . 12 | 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11 | |||

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

3.4. Pseudo-Random Number Generator . . . . . . . . . . . . . 13 | ||||

3.5. Coding Coefficients Generation Function . . . . . . . . . 14 | ||||

3.6. Linear Combination of Source Symbols Computation . . . . 16 | ||||

4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU | 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU | |||

Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 | Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 | |||

4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 14 | 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 17 | |||

4.1.1. FEC Framework Configuration Information . . . . . . . 14 | 4.1.1. FEC Framework Configuration Information . . . . . . . 17 | |||

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

4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 16 | 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 19 | |||

4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 17 | 4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 20 | |||

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

Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 | Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 | |||

5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18 | 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 21 | |||

5.1.1. FEC Framework Configuration Information . . . . . . . 18 | 5.1.1. FEC Framework Configuration Information . . . . . . . 21 | |||

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

5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 18 | 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 21 | |||

5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 18 | 5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21 | |||

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

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

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

7. Implementation Status . . . . . . . . . . . . . . . . . . . . 20 | 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 23 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 23 | |||

8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 20 | 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24 | |||

8.1.1. Access to Confidential Content . . . . . . . . . . . 20 | 8.1.1. Access to Confidential Content . . . . . . . . . . . 24 | |||

8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 21 | 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 24 | |||

8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 21 | 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 24 | |||

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

8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 21 | 8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25 | |||

9. Operations and Management Considerations . . . . . . . . . . 22 | 9. Operations and Management Considerations . . . . . . . . . . 25 | |||

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

GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 22 | GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

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

Threshold . . . . . . . . . . . . . . . . . . . . . . . . 22 | Threshold . . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 | 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 | |||

11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 23 | 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 26 | |||

12. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 | 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 | |||

12.1. Normative References . . . . . . . . . . . . . . . . . . 23 | 12.1. Normative References . . . . . . . . . . . . . . . . . . 26 | |||

12.2. Informative References . . . . . . . . . . . . . . . . . 24 | 12.2. Informative References . . . . . . . . . . . . . . . . . 27 | |||

Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 26 | Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 29 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 26 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30 | |||

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 large number of receivers (multicast/broadcast | delivery sessions to a large number of receivers (multicast/broadcast | |||

transmissions). This is the case with the FLUTE/ALC protocol | transmissions). This is the case with the FLUTE/ALC protocol | |||

[RFC6726] in case of reliable file transfers over lossy networks, and | [RFC6726] when used for reliable file transfers over lossy networks, | |||

the FECFRAME protocol for reliable continuous media transfers over | and the FECFRAME protocol when used for reliable continuous media | |||

lossy networks. | transfers over lossy networks. | |||

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

multicast/broadcast delivery mode, with contents that feature | multicast/broadcast delivery mode, with contents that feature | |||

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

validity period after which it will not be considered by the | 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, | (either a end-host (receiver) or middlebox). In this context, | |||

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

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

linear block codes: they require the data flow to be segmented into | linear block codes: they require the data flow to be segmented into | |||

blocks of a predefined maximum size. | blocks of a predefined maximum size. | |||

Defining this block size requires to find an appropriate balance | To define this block size, it is required to find an appropriate | |||

between robustness and decoding latency: the larger the block size, | balance between robustness and decoding latency: the larger the block | |||

the higher the robustness (e.g., in front of long packet erasure | size, the higher the robustness (e.g., in front of long packet | |||

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

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

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

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

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

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

maximum decoding latency. This choice will impact all receivers. | the desired maximum decoding latency. This choice then impacts the | |||

FEC-related latency of all receivers, even those experiencing a good | ||||

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

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

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

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

(RLC) over either Finite Field GF(2) or GF(8). These FEC Schemes are | (RLC) over either Finite Field GF(2) or GF(8). These FEC Schemes are | |||

used to protect arbitrary media streams along the lines defined by | used to protect arbitrary media streams along the lines defined by | |||

FECFRAME extended to sliding window FEC codes [fecframe-ext]. These | FECFRAME extended to sliding window FEC codes [fecframe-ext]. These | |||

FEC Schemes are extremely efficient for instance with media that | FEC Schemes, and more generally Sliding Window FEC codes, are | |||

feature real-time constraints sent within a multicast/broadcast | recommended for instance with media that feature real-time | |||

session. | constraints sent within a 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). The encoding process is based on | codes (A.K.A. convolutional codes). The encoding process is based on | |||

an encoding window that slides over the set of source packets (in | an encoding window that slides over the set of source packets (in | |||

fact source symbols as we will see in Section 3.2), and which is | fact source symbols as we will see in Section 3.2), and which is | |||

either of fixed or variable size (elastic window). Repair packets | either of fixed or variable size (elastic window). Repair packets | |||

(symbols) are generated and sent on-the-fly, after computing a random | (symbols) are generated on-the-fly, computing a random linear | |||

linear combination of the source symbols present in the current | combination of the source symbols present in the current encoding | |||

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

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

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

symbols) and equations (representing the linear combination of each | symbols) and equations (representing the linear combination of each | |||

repair symbol received) are added upon receiving new packets. | repair symbol received) are added upon receiving new packets. | |||

Variables are removed when they are too old with respect to their | Variables are removed when they are too old with respect to their | |||

validity period (real-time constraints), as well as the associated | validity period (real-time constraints), as well as the associated | |||

equations they are involved in (Appendix A introduces an optimization | equations they are involved in (Appendix A introduces an optimization | |||

that extends the time a variable is considered in the system). Lost | that extends the time a variable is considered in the system). Lost | |||

source symbols are then recovered thanks to this linear system | source symbols are then recovered thanks to this linear system | |||

whenever its rank permits it. | whenever its rank permits it. | |||

With RLC codes (more generally with sliding window codes), the | With RLC codes (more generally with sliding window codes), the | |||

protection of a multicast/broadcast session also needs to be | protection of a multicast/broadcast session also needs to be | |||

dimensioned by considering the worst communication conditions one | dimensioned by considering the worst communication conditions one | |||

wants to support. However the receivers experiencing a good to | wants to support. However the receivers experiencing a good to | |||

medium communication quality will observe a FEC-related latency close | medium communication quality will observe a reduced FEC-related | |||

to zero [Roca17] since an isolated lost source packet is quickly | latency compared to block codes [Roca17] since an isolated lost | |||

recovered with the following repair packet. On the opposite, with a | source packet is quickly recovered with the following repair packet. | |||

block code, recovering an isolated lost source packet always requires | On the opposite, with a block code, recovering an isolated lost | |||

waiting the end of the block for the first repair packet to arrive. | source packet always requires waiting for the first repair packet to | |||

Additionally, under certain situations (e.g., with a limited FEC- | arrive after the end of the block. Additionally, under certain | |||

related latency budget and with constant bit rate transmissions after | situations (e.g., with a limited FEC-related latency budget and with | |||

FECFRAME encoding), sliding window codes achieve more easily a target | constant bitrate transmissions after FECFRAME encoding), sliding | |||

transmission quality (e.g., measured by the residual loss after FEC | window codes can more efficiently achieve a target transmission | |||

decoding) by sending fewer repair packets (i.e., higher code rate) | quality (e.g., measured by the residual loss after FEC decoding) by | |||

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

codes. | ||||

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

Scheme | Scheme | |||

The Sliding Window RLC FEC Scheme is designed so as to reduce the | The Sliding Window RLC FEC Scheme is designed to limit the packet | |||

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

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

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

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

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

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

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

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

o the Encoding Symbol Identifier (ESI) of the first source symbol in | 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 easily reconstruct | pieces of information enable each receiver to reconstruct the set | |||

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

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

o the seed used by a coding coefficients generation function | o the seed used by a coding coefficients generation function | |||

(Section 3.5). This information enables each receiver to generate | (Section 3.5). This information enables each receiver to generate | |||

the same set of coding coefficients over GF(2^^m) as the sender; | the same set of 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 7). 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 5), that contains the ESI of the first | |||

source symbol (see the ADUI and source symbol mapping, Section 3.2). | source symbol (see the ADUI and source symbol mapping, Section 3.2). | |||

skipping to change at page 6, line 32 ¶ | skipping to change at page 6, line 46 ¶ | |||

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

plr: packet loss rate on the packet erasure channel | ||||

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

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

pmms_rand(maxv): PRNG defined in Section 3.4 and used in this | pmms_rand(maxv): PRNG defined in Section 3.4 and used in this | |||

specification, that returns a new random integer in [0; maxv-1] | specification, that returns a new random integer in [0; maxv-1] | |||

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

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

Scheme. | Schemes. | |||

3.1. Parameters Derivation | 3.1. Possible Parameter Derivation | |||

The Sliding Window RLC FEC Scheme relies on several key parameters: | The Sliding Window RLC FEC Scheme relies on several parameters: | |||

Maximum FEC-related latency budget, max_lat (in seconds) A source | Maximum FEC-related latency budget, max_lat (in seconds) A source | |||

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

FECFRAME related operation must take place within the validity | FECFRAME related operation must take place within the validity | |||

period of each ADU. When there are multiple flows with different | period of each ADU. When there are multiple flows with different | |||

real-time constraints, we consider the most stringent constraints | real-time constraints, we consider the most stringent constraints | |||

(see [RFC6363], Section 10.2, item 6, for recommendations when | (see [RFC6363], Section 10.2, item 6, for recommendations when | |||

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

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

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

skipping to change at page 7, line 29 ¶ | skipping to change at page 7, line 39 ¶ | |||

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

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

max_lat can be regarded as the latency budget permitted for all | max_lat can be regarded as the latency budget permitted for all | |||

FEC-related operations. This is an input parameter that enables | FEC-related operations. This is an input parameter that enables | |||

to derive other internal parameters as explained below; | to derive other internal parameters as explained below; | |||

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

these parameters are used by a sender during FEC encoding. More | these parameters are used by a sender during FEC encoding. More | |||

precisely, each repair symbol is a linear combination of the | precisely, each repair symbol is a linear combination of the | |||

ew_size source symbols present in the encoding window when RLC | ew_size source symbols present in the encoding window when RLC | |||

encoding took place. In all situations, we MUST have: | encoding took place. At session start, the encoding window will | |||

probably be small and then progressively increase until it reaches | ||||

its maximum value. At any time: | ||||

ew_size <= ew_max_size | ew_size <= ew_max_size | |||

Decoding window maximum size, dw_max_size (in symbols): at a | Decoding window maximum size, dw_max_size (in symbols): at a | |||

receiver, this parameter determines the maximum size of the | receiver, this parameter denotes the maximum number of received or | |||

decoding window. Said differently, this is the maximum number of | lost source symbols in the linear system (i.e., the variables) | |||

received or lost source symbols in the linear system (i.e., the | that are still within their latency budget; | |||

variables) that are still within their latency budget. In | Linear system maximum size, ls_max_size (in symbols): The linear | |||

situations where packets are sent with a fixed period, the | system maximum size managed by a receiver SHOULD NOT be smaller | |||

dw_max_size parameter directly determines the maximum decoding | than this decoding window maximum size, since it would mean that, | |||

latency experienced by the receiver, which necessarily needs to be | after receiving a sufficient number of FEC Repair Packets, an ADU | |||

in line with the maximum FEC-related latency budget. Note also | may not be recovered just because it has been removed from the | |||

that the optimization detailed in Appendix A can extend the linear | linear system, and not because it has timed-out. This would be | |||

system with additional old source symbols (that timed-out) beyond | counter-productive. On the opposite, the linear system MAY grow | |||

dw_max_size; | beyond this value with old source symbols kept in the linear | |||

system whereas their associated ADUs timed-out (Appendix A); | ||||

Symbol size, E (in bytes) and RLC code rate (cr): the E parameter | Symbol size, E (in bytes) and RLC code rate (cr): the E parameter | |||

determines the (source or repair) symbol sizes. The cr parameter | determines the source and repair symbol sizes (necessarily equal). | |||

determines the code rate, i.e., the amount of redundancy added to | The cr parameter determines the code rate, i.e., the amount of | |||

the flow (it is the ratio between the total number of source | redundancy added to the flow (i.e., cr is the ratio between the | |||

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

These two parameters are input parameters that enable to derive | repair symbols). These two parameters are input parameters that | |||

other internal parameters as explained below. In practice they | enable to derive other internal parameters as explained below. An | |||

will usually be fixed, especially with multicast/broadcast | implementation at a sender SHOULD fix the E parameter and | |||

transmissions. In specific use-cases, in particular with unicast | communicate it as part of the FEC Scheme-Specific Information | |||

transmissions in presence of a feedback mechanism that estimates | (Section 4.1.1.2). However there is no need to communicate the cr | |||

the communication quality (out-of-scope of FECFRAME), the code | parameter per see (it's not required to process a repair packet at | |||

rate may be adjusted dynamically. | a receiver). This code rate parameter can be fixed. However, in | |||

specific use-cases (e.g., with unicast transmissions in presence | ||||

of a feedback mechanism that estimates the communication quality, | ||||

out-of-scope of FECFRAME), the code rate may be adjusted | ||||

dynamically. | ||||

Let us assume that the encoding symbol size (E, in bytes) and code | The FEC Schemes specified in this document can be used in various | |||

rate (cr) are constant. Let us also assume a constant transmission | manners. They can protect one or more source ADU flows having real- | |||

bitrate (br_out, in bits/s) at the output of the FECFRAME sender (as | time constraints, or they can protect non-realtime source ADU flows. | |||

in [Roca17]). It means that the source flow bitrate needs to be | The source ADU flows may be Constant Bitrate (CBR) flows, while other | |||

adjusted according to the added repair flow overhead in order to keep | may be of Variable Bitrate (VBR). The FEC Schemes can be used in | |||

the total transmission bitrate fixed and equal to br_out. In order | various environments like the Internet or over a CBR channel. It | |||

to comply with the maximum FEC-related latency budget we need: | follows that the FEC Scheme parameters can be derived in different | |||

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

dw_max_size = (max_lat * br_out * cr) / (8 * E) | 3.1.1. Detailed Parameter Derivation for CBR Real-Time Flows | |||

Sometimes the opposite can happen: the source flow bitrate at the | In the following, we consider a real-time flow with max_lat latency | |||

input of the FECFRAME sender is fixed (br_in, in bits/s). It means | budget. The encoding symbol size (E, in bytes) is constant. The | |||

that the transmission bitrate at the output of the FECFRAME sender | code rate (cr) is also constant, in line with the expected | |||

will be higher, depending on the added repair flow overhead. In | communication loss model. However the choice of this cr value is out | |||

order to comply with the maximum FEC-related latency budget we need: | of scope for this document. | |||

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

the FECFRAME sender is fixed (br_in, in bits/s). It means 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) | dw_max_size = (max_lat * br_in) / (8 * E) | |||

Finally, there are situations where no such assumption can be made | In a second configuration, the FECFRAME sender generates a fixed | |||

(e.g., with a variable bit rate input flow). In that case the | bitrate flow, equal to the CBR channel bitrate (br_out, in bits/s), | |||

encoding and decoding window maximum sizes may be initialized, based | as in [Roca17]. The maximum source flow bitrate needs to be such | |||

on the input flow features (e.g., the peak bitrate if it is known) | that, with the added repair flow overhead, the total transmission | |||

and great care must be taken on timing aspects at a sender (see | bitrate remains (inferior or) equal to br_out. Here we have: | |||

Section 3.3) and receiver. The details of how to manage these | ||||

situations are use-case dependent and out of scope of this document. | ||||

Then, once the dw_max_size has been determined, the ew_max_size can | dw_max_size = (max_lat * br_out * cr) / (8 * E) | |||

be defined. For decoding to be possible, it is required that the | ||||

encoding window maximum size be at most equal to the decoding window | For decoding to be possible, it is required that the encoding window | |||

maximum size. It is often good practice to choose [Roca17]: | maximum size be at most equal to the decoding window maximum size. | |||

So, once the dw_max_size has been determined, the ew_max_size SHOULD | ||||

be computed with ([Roca17]): | ||||

ew_max_size = dw_max_size * 0.75 | ew_max_size = dw_max_size * 0.75 | |||

However any value ew_max_size < dw_max_size can be used without | The ew_max_size is the main parameter, used by a FECFRAME sender. | |||

impact on the FEC-related latency budget. Finding the optimal value | Whenever the FEC protection (i.e., cr value) is sufficient in front | |||

will depend on the use-case details and should be determined after | of the packet loss model, the ew_max_size guaranties that the | |||

simulations or field trials. This is of course out of scope of this | recovery of lost ADUs will happen at a FECFRAME receiver on time. | |||

document. | ||||

Note that the decoding beyond maximum latency optimization | The dw_max_size is computed by a FECFRAME sender but not explicitly | |||

(Appendix A) enables an old source symbol to be kept in the linear | communicated to a FECFRAME receiver. However a FECFRAME receiver can | |||

system beyond the FEC-related latency budget, but not delivered to | easily evaluate the ew_max_size by observing the maximum Number of | |||

the receiving application. In any case, the linear system maximum | Source Symbols (NSS) value contained in the Repair FEC Payload ID of | |||

size is greater than (with the decoding optimization) or equal to | received FEC Repair Packets (Section 4.1.3). A receiver can then | |||

(without) the decoding window maximum size: | easily compute dw_max_size: | |||

dw_max_size = max_NSS_observed / 0.75 | ||||

and chose an appropriate maximum linear system size. Having a | ||||

limited linear system size is a practical requirement that enables to | ||||

forget old source symbols, no longer needed. We have: | ||||

ls_max_size >= dw_max_size | ls_max_size >= dw_max_size | |||

Using the same maximum size is the minimum. But it is good practice | ||||

to use a larger value for ls_max_size as explained in Appendix A, | ||||

without impacting maximum latency nor interoperability. | ||||

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

appropriately. Here the ew_size progressively increases, upon | ||||

receiving new source ADUs at 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 the | ||||

ls_max_size accordingly. | ||||

3.1.2. Parameter Derivation for Other Real-Time Flows | ||||

There are situations where the real-time source ADU flow is of | ||||

variable bitrate (VBR). A first possibility is to consider the peak | ||||

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

reuse the derivation of Section 3.1.1. | ||||

There are also situations where the peak bitrate is not know. In | ||||

that case the previous parameter derivation cannot be directly | ||||

applied. An approach in that case consists in using ADU timing | ||||

information when present (e.g., using the timestamp field of an RTP | ||||

packet header) to manage the encoding window accordingly, in | ||||

particular removing old symbols whose associated ADUs timed-out. | ||||

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 maximum linear system size, | ||||

ls_max_size. | ||||

When the observed NSS fluctuates significantly and perhaps slowly, a | ||||

FECFRAME receiver may want to adapt its ls_max_size accordingly in | ||||

order to avoid managing linear systems that would be significantly | ||||

too large. It is worth noticing however that it is preferable to use | ||||

an ls_max_size too large than the opposite. | ||||

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

situations at a FECFRAME sender and receiver remain out of scope of | ||||

this document. | ||||

3.1.3. Parameter Derivation for Non Real-Time Flows | ||||

Finally there are situations where there is no known 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. It can be an estimation of the | ||||

maximum memory amount that could be dedicated to the linear system at | ||||

a FECFRAME receiver, or CPU computation requirements at a FECFRAME | ||||

receiver, both of them depending on the ls_max_size. The same | ||||

considerations can also apply to the FECFRAME sender, where maximum | ||||

memory and CPU computation requirements depend on the ew_max_size. | ||||

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

inform a FECFRAME receiver of 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 remain out of scope of | ||||

this document. | ||||

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

An ADU, coming from the application, cannot be mapped to source | At a sender, an ADU coming from the application cannot directly be | |||

symbols directly. Indeed, a lost ADU recovered at a receiver must | mapped to source symbols. When multiple source flows (e.g., media | |||

contain enough information to be assigned to the right application | streams) are mapped onto the same FECFRAME instance, each flow is | |||

flow (UDP port numbers and IP addresses cannot be used to that | assigned its own Flow ID value (see below). At a sender, this | |||

purpose as they are not protected by FEC encoding). This requires | identifier is prepended to each ADU before FEC encoding. This way, | |||

adding the flow identifier to each ADU before doing FEC encoding. | FEC decoding at a receiver also recovers this Flow ID and a recovered | |||

ADU can be assigned to the right source flow (note that transport | ||||

port numbers and IP addresses cannot be used to that purpose as they | ||||

are not recovered during FEC decoding). | ||||

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 is created as follows. First of all, | For each incoming ADU, an ADUI MUST created as follows. First of | |||

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

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

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

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

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

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

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

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

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

fields. | fields. | |||

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

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

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

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

skipping to change at page 10, line 17 ¶ | skipping to change at page 12, line 17 ¶ | |||

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

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

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

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

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

the UDP datagram containing this FEC Source Packet) will be able to | the UDP datagram containing this FEC Source Packet when UDP is used | |||

recover the ADUI if FEC decoding succeeds. Thanks to the initial 3 | as the transport protocol) will be able to recover the ADUI if FEC | |||

bytes, this receiver will get rid of the padding (if any) and | decoding succeeds. Thanks to the initial 3 bytes, this receiver will | |||

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

flow. | ||||

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

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

encoding window: | encoding window: | |||

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

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

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

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

skipping to change at page 11, line 23 ¶ | skipping to change at page 13, line 23 ¶ | |||

(modulo M), with the following choices: A = 7^^5 = 16807 and M = | (modulo M), with the following choices: A = 7^^5 = 16807 and M = | |||

2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the | 2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the | |||

following: if seed = 1, then the 10,000th value returned MUST be | following: if seed = 1, then the 10,000th value returned MUST be | |||

equal to 1043618065. | equal to 1043618065. | |||

Several implementations of this PRNG are known and discussed in the | Several implementations of this PRNG are known and discussed in the | |||

literature. An optimized implementation of this algorithm, using | literature. An optimized implementation of this algorithm, using | |||

only 32-bit mathematics, and which does not require any division, can | only 32-bit mathematics, and which does not require any division, can | |||

be found in [rand31pmc]. It uses the Park and Miller algorithm | be found in [rand31pmc]. It uses the Park and Miller algorithm | |||

[PM88] with the optimization suggested by D. Carta in [CA90]. The | [PM88] with the optimization suggested by D. Carta in [CA90]. The | |||

history behind this algorithm is detailed in [WI08]. Yet, any other | history behind this algorithm is detailed in [WI08]. | |||

implementation of the PRNG algorithm that matches the above | ||||

validation criteria, like the ones detailed in [PM88], is | ||||

appropriate. | ||||

This PRNG produces, natively, a 31-bit value between 1 and 0x7FFFFFFE | This PRNG produces, natively, a 31-bit value between 1 and 0x7FFFFFFE | |||

(2^^31-2) inclusive. Since it is desired to scale the pseudo-random | (2^^31-2) inclusive. Since it is desired to scale the pseudo-random | |||

number between 0 and maxv-1 inclusive, one must keep the most | number between 0 and maxv-1 inclusive, one must keep the most | |||

significant bits of the value returned by the PRNG (the least | significant bits of the value returned by the PRNG (the least | |||

significant bits are known to be less random, and modulo-based | significant bits are known to be less random, and modulo-based | |||

solutions should be avoided [PTVF92]). The following algorithm MUST | solutions should be avoided [PTVF92]). The following algorithm MUST | |||

be used: | be used: | |||

Input: | Input: | |||

skipping to change at page 13, line 32 ¶ | skipping to change at page 15, line 31 ¶ | |||

return SOMETHING_WENT_WRONG; /* bad repair_key parameter */ | return SOMETHING_WENT_WRONG; /* bad repair_key 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 */ | |||

pmms_srand(repair_key); | pmms_srand(repair_key); | |||

pmms_rand(16); /* skip the first PRNG value */ | ||||

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

if (pmms_rand(16) <= dt) { | if (pmms_rand(16) <= dt) { | |||

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

} else { | } else { | |||

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

} | } | |||

} | } | |||

} | } | |||

break; | break; | |||

case 8: | case 8: | |||

pmms_srand(repair_key); | pmms_srand(repair_key); | |||

pmms_rand(256); /* skip the first PRNG value */ | ||||

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) pmms_rand(256); | cc_tab[i] = (UINT8) pmms_rand(256); | |||

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

} | } | |||

} else { | } else { | |||

skipping to change at page 14, line 29 ¶ | skipping to change at page 16, line 29 ¶ | |||

default: | default: | |||

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

return SOMETHING_WENT_WRONG; | return SOMETHING_WENT_WRONG; | |||

} | } | |||

return EVERYTHING_IS_OKAY; | return EVERYTHING_IS_OKAY; | |||

} | } | |||

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

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

One can note in the above function that each call to pmms_srand() | ||||

(PRNG initialisation) is immediately followed by a call to | ||||

pmms_rand() whose return value is ignored. This extra call is | ||||

motivated by a possible bias in the first value generated depending | ||||

on the way the repair key is managed by a FECFRAME implementation. | ||||

Indeed, the PRNG sequences produced by two seeds in sequence have a | ||||

high probability of starting with the same value since I1 = A * seed | ||||

(modulo M) which is further scaled to a small range (either {0, ... | ||||

15} or {0, ... 255}). Producing several times the same first coding | ||||

coefficient could reduce the protection of the first source symbol if | ||||

multiple repair symbols are produced with the same coding window's | ||||

left edge. The extra call avoids such side effects. | ||||

3.6. Linear Combination of Source Symbols Computation | ||||

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

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

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

cc_tab[] array. | ||||

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

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

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

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

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

repair[i] = cc_tab[0] * src_0[i] + cc_tab[1] * src_1[i] + ... + | ||||

cc_tab[ew_size - 1] * src_ew_size_1[i] | ||||

where * is the multiplication over GF(2^^8) and + is an XOR | ||||

operation. In practice various optimizations need to be used in | ||||

order to make this computation efficient (see in particular [PGM13]). | ||||

With the RLC over GF(2) FEC Scheme (binary case), a linear | ||||

combination is computed as follows. The repair symbol is the XOR sum | ||||

of all the source symbols corresponding to a coding coefficient | ||||

cc_tab[j] equal to 1 (i.e., the source symbols corresponding to zero | ||||

coding coefficients are ignored). The XOR sum of the byte of | ||||

position i in each source is computed and stored in the corresponding | ||||

byte of the repair symbol, where i belongs to {0; E-1}. In practice, | ||||

the XOR sums will be computed several bytes at a time (e.g., on 64 | ||||

bit words, or on arrays of 16 or more bytes when using SIMD CPU | ||||

extensions). | ||||

With both FEC Schemes, the details of how to optimize the computation | ||||

of these linear combinations are of high practical importance but out | ||||

of scope of this document. | ||||

4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU Flows | 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU Flows | |||

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

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

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

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

The FEC Framework Configuration Information (or FFCI) includes | Following the guidelines of [RFC6363], section 5.6, this section | |||

information that MUST be communicated between the sender and | provides the FEC Framework Configuration Information (or FFCI). This | |||

receiver(s). More specifically, it enables the synchronization of | FCCI needs to be shared (e.g., using SDP) between the FECFRAME sender | |||

the FECFRAME sender and receiver instances. It includes both | and receiver instances in order to synchronize them. It includes a | |||

mandatory elements and scheme-specific elements, as detailed below. | FEC Encoding ID, mandatory for any FEC Scheme specification, plus | |||

scheme-specific elements. | ||||

4.1.1.1. Mandatory Information | 4.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 XXXX, as assigned by IANA (Section 10). | Scheme MUST be XXXX, 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. | |||

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

skipping to change at page 16, line 24 ¶ | skipping to change at page 19, line 24 ¶ | |||

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

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

A FEC Repair Packet can 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 6. | |||

skipping to change at page 17, line 14 ¶ | skipping to change at page 20, line 14 ¶ | |||

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.5) in order to | |||

generate the desired number of coding coefficients. Value 0 MUST | generate the desired number of coding coefficients. Value 0 MUST | |||

NOT be used. When a FEC Repair Packet contains several repair | NOT be used. When a FEC Repair Packet contains several repair | |||

symbols, this repair key value is that of the first repair symbol. | symbols, this repair key value is that of the first repair symbol. | |||

The remaining repair keys can be deduced by incrementing by 1 this | The remaining repair keys can be deduced by incrementing by 1 this | |||

value, up to a maximum value of 65535 after which it loops back to | value, up to a maximum value of 65535 after which it loops back to | |||

1 (note that 0 is not a valid value). | 1 (note that 0 is not a valid value). | |||

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

this unsigned integer carried 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.5. 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 | |||

skipping to change at page 18, line 14 ¶ | skipping to change at page 21, line 14 ¶ | |||

5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU Flows | 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU 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. Mandatory Information | 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. | |||

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

skipping to change at page 19, line 14 ¶ | skipping to change at page 22, line 14 ¶ | |||

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

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

a 16-bit field) after which it loops back to 1 (indeed, being used as | a 16-bit field) after which it loops back to 1 (indeed, being used as | |||

a PRNG seed, value 0 is prohibited). This repair key is communicated | a PRNG seed, value 0 is prohibited). This repair key is communicated | |||

to the coefficient generation function (Section Section 3.5) in order | to the coefficient generation function (Section Section 3.5) in order | |||

to generate ew_size coding coefficients. Finally, the FECFRAME | 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. When E | ew_size source symbols using the ew_size coding coefficients. When E | |||

is small and when there is an incentive to pack several repair | is small and when there is an incentive to pack several repair | |||

symbols within the same FEC Repair Packet, the appropriate number of | symbols within the same FEC Repair Packet, the appropriate number of | |||

repair symbols are computed. The only constraint is to increment by | repair symbols are computed. In that case the repair key for each of | |||

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

symbols, since only the first repair key will be carried in the | symbols, since only the first repair key will be carried in the | |||

Repair FEC Payload ID. The FEC Repair Packet can then be sent. The | Repair FEC Payload ID. The FEC Repair Packet can then be passed to | |||

source versus repair FEC packet transmission order is out of scope of | the transport layer for transmission. The source versus repair FEC | |||

this document and several approaches exist that are implementation | packet transmission order is out of scope of this document and | |||

specific. | 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 1 and 65535. However, selecting the same repair key | integer between 1 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 | |||

skipping to change at page 20, line 4 ¶ | skipping to change at page 23, line 4 ¶ | |||

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.5), 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. Each time an ADUI can be totally | |||

recovered, padding is removed (thanks to the Length field, L, of the | recovered, padding is removed (thanks to the Length field, L, of the | |||

ADUI) and the ADU is assigned to the corresponding application flow | ADUI) and the ADU is assigned to the corresponding application flow | |||

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

passed to the corresponding upper application. Received FEC Source | passed to the corresponding upper application. Received FEC Source | |||

Packets, containing an ADU, can be passed to the application either | Packets, containing an ADU, MAY be passed to the application either | |||

immediately or after some time to guaranty an ordered delivery to the | immediately or after some time to guaranty an ordered delivery to the | |||

application. This document does not mandate any approach as this is | application. This document does not mandate any approach as this is | |||

an operational and management decision. | an operational and management decision. | |||

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

latency or an ADU received after this delay should not be passed to | latency or an ADU received after this delay has no value to the | |||

the application. Instead the associated source symbols should be | application. This raises the question of deciding whether or not an | |||

removed from the linear system maintained by the receiver(s). | ADU is late. This decision MAY be taken within the FECFRAME receiver | |||

Appendix A discusses a backward compatible optimization whereby those | (e.g., using the decoding window, see Section 3.1) or within the | |||

late source symbols may still be used in order to improve the global | application (e.g., using RTP timestamps within the ADU). Deciding | |||

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

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

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

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

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

FECFRAME receiver in order to improve the global 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: | |||

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

skipping to change at page 24, line 11 ¶ | skipping to change at page 27, line 21 ¶ | |||

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

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

[CA90] Carta, D., "Two Fast Implementations of the Minimal | [CA90] Carta, D., "Two Fast Implementations of the Minimal | |||

Standard Random Number Generator", Communications of the | Standard Random Number Generator", Communications of the | |||

ACM, Vol. 33, No. 1, pp.87-88, January 1990. | ACM, Vol. 33, No. 1, pp.87-88, January 1990. | |||

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

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

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

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

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

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

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

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

[PM88] Park, S. and K. Miller, "Random Number Generators: Good | [PM88] Park, S. and K. Miller, "Random Number Generators: Good | |||

Ones are Hard to Find", Communications of the ACM, Vol. | Ones are Hard to Find", Communications of the ACM, Vol. | |||

31, No. 10, pp.1192-1201, 1988. | 31, No. 10, pp.1192-1201, 1988. | |||

[PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | |||

"Numerical Recipies in C; Second Edition", Cambridge | "Numerical Recipies in C; Second Edition", Cambridge | |||

University Press, ISBN: 0-521-43108-5, 1992. | University Press, ISBN: 0-521-43108-5, 1992. | |||

[rand31pmc] | [rand31pmc] | |||

Whittle, R., "31 bit pseudo-random number generator", | Whittle, R., "31 bit pseudo-random number generator", | |||

skipping to change at page 26, line 15 ¶ | skipping to change at page 29, line 15 ¶ | |||

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

This annex introduces non normative considerations. They are | This annex introduces non normative considerations. They are | |||

provided as suggestions, without any impact on interoperability. For | provided as suggestions, without any impact on interoperability. For | |||

more information see [Roca16]. | more information see [Roca16]. | |||

It is possible to improve the decoding performance of sliding window | It is possible to improve the decoding performance of sliding window | |||

codes without impacting maximum latency, at the cost of extra CPU | codes without impacting maximum latency, at the cost of extra CPU | |||

overhead. The optimization consists, for a receiver, to extend the | overhead. The optimization consists, for a receiver, to extend the | |||

linear system beyond the decoding window, by keeping a certain number | linear system beyond the decoding window, by keeping a certain number | |||

of old source symbols: | of old source symbols. | |||

ls_max_size > dw_max_size | ls_max_size > dw_max_size | |||

Usually the following choice is a good trade-off between decoding | Usually the following choice is a good trade-off between decoding | |||

performance and extra CPU overhead: | performance and extra CPU overhead: | |||

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

minimum ls_max_size value (e.g., LS_MIN_SIZE_DEFAULT = 40 symbols). | ||||

Going below this threshold will not save a significant amount of | ||||

memory nor CPU cycles. Therefore: | ||||

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

that benefits from a protection that is significantly sufficient to | ||||

recover from the packet losses, can choose to reduce its ls_max_size | ||||

significantly. In that case lost ADUs will be recovered rapidly, | ||||

without relying on this optimization. | ||||

ls_max_size | ls_max_size | |||

/---------------------------------^-------------------------------\ | /---------------------------------^-------------------------------\ | |||

late source symbols | late source symbols | |||

(pot. decoded but not delivered) dw_max_size | (pot. decoded but not delivered) dw_max_size | |||

/--------------^-----------------\ /--------------^---------------\ | /--------------^-----------------\ /--------------^---------------\ | |||

src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 | src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 | |||

Figure 8: Relationship between parameters to decode beyond maximum | Figure 8: 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. It follows that the corresponding ADUs SHOULD NOT be | application. It follows that the corresponding ADUs will not be | |||

delivered to the application and SHOULD be dropped once they are no | useful to the application. However, decoding these "late symbols" | |||

longer needed. However, decoding these "late symbols" significantly | significantly improves the global robustness in bad reception | |||

improves the global robustness in bad reception conditions and is | conditions and is therefore recommended for receivers experiencing | |||

therefore recommended for receivers experiencing bad communication | bad communication conditions [Roca16]. In any case whether or not to | |||

conditions [Roca16]. In any case whether or not to use this | use this optimization and what exact value to use for the ls_max_size | |||

optimization and what exact value to use for the ls_max_size | ||||

parameter are decisions made by each receiver independently, without | parameter are decisions made by each receiver independently, without | |||

any impact on the other receivers nor on the source. | any impact on the other receivers nor on the source. | |||

Authors' Addresses | Authors' Addresses | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

Grenoble | Grenoble | |||

France | France | |||

EMail: vincent.roca@inria.fr | EMail: vincent.roca@inria.fr | |||

Belkacem Teibi | Belkacem Teibi | |||

INRIA | INRIA | |||

Grenoble | Grenoble | |||

End of changes. 54 change blocks. | ||||

200 lines changed or deleted | | 369 lines changed or added | ||

This html diff was produced by rfcdiff 1.46. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |