draft-ietf-tsvwg-rlc-fec-scheme-03.txt   draft-ietf-tsvwg-rlc-fec-scheme-04.txt 
TSVWG V. Roca TSVWG V. Roca
Internet-Draft B. Teibi Internet-Draft B. Teibi
Intended status: Standards Track INRIA Intended status: Standards Track INRIA
Expires: November 7, 2018 May 6, 2018 Expires: November 18, 2018 May 17, 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-03 draft-ietf-tsvwg-rlc-fec-scheme-04
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 GF(2) (binary case), a second one for RLC (RLC), one for RLC over GF(2) (binary case), a second one for RLC
over GF(2^^8), both of them with the possibility of controlling the over GF(2^^8), both of them with the possibility of controlling the
code density. They can protect arbitrary media streams along the code density. They can protect arbitrary media streams along the
lines defined by FECFRAME extended to sliding window FEC codes. lines defined by FECFRAME extended to sliding window FEC codes.
These sliding window FEC codes rely on an encoding window that slides These sliding window FEC codes rely on an encoding window that slides
skipping to change at page 1, line 42 skipping to change at page 1, line 42
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 7, 2018. This Internet-Draft will expire on November 18, 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 26 skipping to change at page 2, line 26
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 . . . . . . . . . . . . . . . . . . 6 1.4. Document Organization . . . . . . . . . . . . . . . . . . 6
2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6 2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6
3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Possible Parameter Derivation . . . . . . . . . . . . . . 7 3.1. Possible Parameter Derivations . . . . . . . . . . . . . 7
3.1.1. Detailed Parameter Derivation for CBR Real-Time Flows 8 3.1.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . 8
3.1.2. Parameter Derivation for Other Real-Time Flows . . . 10 3.1.2. Other Types of Real-Time Flow . . . . . . . . . . . . 10
3.1.3. Parameter Derivation for Non Real-Time Flows . . . . 10 3.1.3. Case of a Non Real-Time Flow . . . . . . . . . . . . 11
3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11
3.3. Encoding Window Management . . . . . . . . . . . . . . . 12 3.3. Encoding Window Management . . . . . . . . . . . . . . . 12
3.4. Pseudo-Random Number Generator . . . . . . . . . . . . . 13 3.4. Pseudo-Random Number Generator . . . . . . . . . . . . . 13
3.5. Coding Coefficients Generation Function . . . . . . . . . 14 3.5. Coding Coefficients Generation Function . . . . . . . . . 14
3.6. Linear Combination of Source Symbols Computation . . . . 16 3.6. Finite Fields Operations . . . . . . . . . . . . . . . . 17
3.6.1. Linear Combination of Source Symbols Computation . . 17
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 17 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18
4.1.1. FEC Framework Configuration Information . . . . . . . 17 4.1.1. FEC Framework Configuration Information . . . . . . . 18
4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 18 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 19
4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 19 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20
4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 20 4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 21 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 22
5.1.1. FEC Framework Configuration Information . . . . . . . 21 5.1.1. FEC Framework Configuration Information . . . . . . . 22
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 21 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 22
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 21 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22
5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21 5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 22
6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 21 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 22
6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 21 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 22
6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 22 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 23
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 23
8. Security Considerations . . . . . . . . . . . . . . . . . . . 23 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 24
8. Security Considerations . . . . . . . . . . . . . . . . . . . 24
8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24
8.1.1. Access to Confidential Content . . . . . . . . . . . 24 8.1.1. Access to Confidential Content . . . . . . . . . . . 24
8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 24 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 25
8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 24 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 25
8.3. When Several Source Flows are to be Protected Together . 25 8.3. When Several Source Flows are to be Protected Together . 25
8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25 8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25
9. Operations and Management Considerations . . . . . . . . . . 25 9. Operations and Management Considerations . . . . . . . . . . 26
9.1. Operational Recommendations: Finite Field GF(2) Versus 9.1. Operational Recommendations: Finite Field GF(2) Versus
GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 25 GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2. Operational Recommendations: Coding Coefficients Density 9.2. Operational Recommendations: Coding Coefficients Density
Threshold . . . . . . . . . . . . . . . . . . . . . . . . 25 Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 26 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27
12.1. Normative References . . . . . . . . . . . . . . . . . . 26 12.1. Normative References . . . . . . . . . . . . . . . . . . 27
12.2. Informative References . . . . . . . . . . . . . . . . . 27 12.2. Informative References . . . . . . . . . . . . . . . . . 28
Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 29 Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 30
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 31
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] when used for reliable file transfers over lossy networks, [RFC6726] when used for reliable file transfers over lossy networks,
and the FECFRAME protocol when used for reliable continuous media and the FECFRAME protocol when used for reliable continuous media
skipping to change at page 4, line 25 skipping to change at page 4, line 25
FEC-related latency of all receivers, even those experiencing a good FEC-related 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 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(2^^8). These FEC Schemes
used to protect arbitrary media streams along the lines defined by are used to protect arbitrary media streams along the lines defined
FECFRAME extended to sliding window FEC codes [fecframe-ext]. These by FECFRAME extended to sliding window FEC codes [fecframe-ext].
FEC Schemes, and more generally Sliding Window FEC codes, are These FEC Schemes, and more generally Sliding Window FEC codes, are
recommended for instance with media that feature real-time recommended for instance with media that feature real-time
constraints sent within a multicast/broadcast session [Roca17]. 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 on-the-fly, computing a random linear (symbols) are generated on-the-fly, computing a random linear
combination of the source symbols present in the current encoding combination of the source symbols present in the current encoding
skipping to change at page 7, line 15 skipping to change at page 7, line 15
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 these FEC This section introduces the procedures that are used by these FEC
Schemes. Schemes.
3.1. Possible Parameter Derivation 3.1. Possible Parameter Derivations
The Sliding Window RLC FEC Scheme relies on several 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) with real-
ADU flow can have real-time constraints, and therefore any time flows:
FECFRAME related operation must take place within the validity a source ADU flow can have real-time constraints, and therefore
any 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).
Other sources of latency (e.g., added by network communications) Other sources of latency (e.g., added by network communications)
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 a
to derive other internal parameters as explained below; FECFRAME sender 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 at a FECFRAME sender, during FEC encoding, a repair symbol is
precisely, each repair symbol is a linear combination of the computed as a linear combination of the ew_size source symbols
ew_size source symbols present in the encoding window when RLC present in the encoding window. The ew_max_size is the maximum
encoding took place. At session start, the encoding window will size of this window, while ew_size is the current size. For
probably be small and then progressively increase until it reaches instance, at session start, upon receiving new source ADUs, the
its maximum value. At any time: ew_size progressively increases until it reaches its maximum
value, ew_max_size. We have:
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 denotes the maximum number of received or FECFRAME receiver, dw_max_size is the maximum number of received
lost source symbols in the linear system (i.e., the variables) or lost source symbols that are still within their latency budget;
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): The linear receiver, the linear system maximum size, ls_max_size, is the
system maximum size managed by a receiver SHOULD NOT be smaller maximum number of received or lost source symbols in the linear
than this decoding window maximum size, since it would mean that, system (i.e., the variables). It SHOULD NOT be smaller than
after receiving a sufficient number of FEC Repair Packets, an ADU dw_max_size since it would mean that, even after receiving a
may not be recovered just because it has been removed from the sufficient number of FEC Repair Packets, a lost ADU may not be
linear system, and not because it has timed-out. This would be recovered just because the associated source symbols have been
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 this value with old source symbols kept in the linear beyond the dw_max_size (Appendix A);
system whereas their associated ADUs timed-out (Appendix A); Symbol size, E (in bytes): the E parameter determines the source and
Symbol size, E (in bytes) and RLC code rate (cr): the E parameter repair symbol sizes (necessarily equal). This is an input
determines the source and repair symbol sizes (necessarily equal). parameter that enables a FECFRAME sender to derive other internal
The cr parameter determines the code rate, i.e., the amount of parameters, as explained below. An implementation at a sender
redundancy added to the flow (i.e., cr is the ratio between the SHOULD fix the E parameter and communicate it as part of the FEC
total number of source symbols and the total number of source plus Scheme-Specific Information (Section 4.1.1.2).
repair symbols). These two parameters are input parameters that Code rate, cr: The code rate parameter determines the amount of
enable to derive other internal parameters as explained below. An redundancy added to the flow. More precisely the cr is the ratio
implementation at a sender SHOULD fix the E parameter and between the total number of source symbols and the total number of
communicate it as part of the FEC Scheme-Specific Information source plus repair symbols and by definition: 0 < cr <= 1. This
(Section 4.1.1.2). However there is no need to communicate the cr is an input parameter that enables a FECFRAME sender to derive
parameter per see (it's not required to process a repair packet at other internal parameters, as explained below. However there is
a receiver). This code rate parameter can be fixed. However, in no need to communicate the cr parameter per see (it's not required
specific use-cases (e.g., with unicast transmissions in presence to process a repair symbol at a receiver). This code rate
of a feedback mechanism that estimates the communication quality, parameter can be fixed. However, in specific use-cases (e.g.,
out-of-scope of FECFRAME), the code rate may be adjusted with unicast transmissions in presence of a feedback mechanism
dynamically. that estimates the communication quality, out of scope of
FECFRAME), the code rate may be adjusted dynamically.
The FEC Schemes specified in this document can be used in various The FEC Schemes can be used in various manners. They can be used to
manners. They can protect one or more source ADU flows having real- protect a source ADU flow having real-time constraints, or a non-
time constraints, or they can protect non-realtime source ADU flows. realtime source ADU flow. The source ADU flow may be a Constant
The source ADU flows may be Constant Bitrate (CBR) flows, while other Bitrate (CBR) or Variable BitRate (VBR) flow. The features of the
may be of Variable Bitrate (VBR). The FEC Schemes can be used in flow (in particular its minimum/maximum bitrate) may be known or not.
various environments like the Internet or over a CBR channel. It The FEC Schemes can also be used over the Internet or over a CBR
follows that the FEC Scheme parameters can be derived in different communication path. It follows that the FEC Scheme parameters can be
ways, as described in the following sections. derived in different ways, as described in the following sections.
3.1.1. Detailed Parameter Derivation for CBR Real-Time Flows 3.1.1. Case of a CBR Real-Time Flow
In the following, we consider a real-time flow with max_lat latency In the following, we consider a real-time flow with max_lat latency
budget. The encoding symbol size (E, in bytes) is constant. The budget. The encoding symbol size, E, is constant. The code rate,
code rate (cr) is also constant, in line with the expected cr, is also constant, its value depending on the expected
communication loss model. However the choice of this cr value is out communication loss model (this choice is out of scope of this
of scope for this document. document).
In a first configuration, the source ADU flow bitrate at the input of 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 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 transmission bitrate at the output of the FECFRAME sender will be
higher, depending on the added repair flow overhead. In order to higher, depending on the added repair flow overhead. In order to
comply with the maximum FEC-related latency budget, we have: comply with the maximum FEC-related latency budget, we have:
dw_max_size = (max_lat * br_in) / (8 * E) dw_max_size = (max_lat * br_in) / (8 * E)
In a second configuration, the FECFRAME sender generates a fixed In a second configuration, the FECFRAME sender generates a fixed
bitrate flow, equal to the CBR channel bitrate (br_out, in bits/s), 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 as in [Roca17]. The maximum source flow bitrate needs to be such
that, with the added repair flow overhead, the total transmission that, with the added repair flow overhead, the total transmission
bitrate remains (inferior or) equal to br_out. Here we have: bitrate remains inferior or equal to br_out. We have:
dw_max_size = (max_lat * br_out * cr) / (8 * E) dw_max_size = (max_lat * br_out * cr) / (8 * E)
For decoding to be possible, it is required that the encoding window For decoding to be possible within the latency budget, it is required
maximum size be at most equal to the decoding window maximum size. that the encoding window maximum size be smaller than or at most
So, once the dw_max_size has been determined, the ew_max_size SHOULD equal to the decoding window maximum size, the exact value having no
be computed with ([Roca17]): 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 ew_max_size = dw_max_size * 0.75
The ew_max_size is the main parameter, used by a FECFRAME sender. The ew_max_size is the main parameter at a FECFRAME sender.
Whenever the FEC protection (i.e., cr value) is sufficient in front
of the packet loss model, the ew_max_size guaranties that the
recovery of lost ADUs will happen at a FECFRAME receiver on time.
The dw_max_size is computed by a FECFRAME sender but not explicitly The dw_max_size is computed by a FECFRAME sender but not explicitly
communicated to a FECFRAME receiver. However a FECFRAME receiver can communicated to a FECFRAME receiver. However a FECFRAME receiver can
easily evaluate the ew_max_size by observing the maximum Number of easily evaluate the ew_max_size by observing the maximum Number of
Source Symbols (NSS) value contained in the Repair FEC Payload ID of Source Symbols (NSS) value contained in the Repair FEC Payload ID of
received FEC Repair Packets (Section 4.1.3). A receiver can then received FEC Repair Packets (Section 4.1.3). A receiver can then
easily compute dw_max_size: easily compute dw_max_size:
dw_max_size = max_NSS_observed / 0.75 dw_max_size = max_NSS_observed / 0.75
and chose an appropriate maximum linear system size. Having a A receiver can then chose an appropriate linear system maximum size:
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 It is good practice to use a larger value for ls_max_size as
to use a larger value for ls_max_size as explained in Appendix A, explained in Appendix A, which does not impact maximum latency nor
without impacting maximum latency nor interoperability. interoperability. However the linear system size should not be too
large for practical reasons (e.g., in order to limit computation
complexity).
The particular case of session start needs to be managed The particular case of session start needs to be managed
appropriately. Here the ew_size progressively increases, upon appropriately. Here ew_size increases each time a new source ADU is
receiving new source ADUs at the FECFRAME sender, until it reaches received by the FECFRAME sender, until it reaches the ew_max_size
the ew_max_size value, A FECFRAME receiver SHOULD continuously value. A FECFRAME receiver SHOULD continuously observe the received
observe the received FEC Repair Packets, since the NSS value carried FEC Repair Packets, since the NSS value carried in the Repair FEC
in the Repair FEC Payload ID will increase too, and adjust the Payload ID will increase too, and adjust its ls_max_size accordingly
ls_max_size accordingly. if need be.
3.1.2. Parameter Derivation for Other Real-Time Flows 3.1.2. Other Types of Real-Time Flow
There are situations where the real-time source ADU flow is of In other configurations, a real-time source ADU flow, with a max_lat
variable bitrate (VBR). A first possibility is to consider the peak latency budget, features a variable bitrate (VBR). A first approach
bitrate of the source ADU flow, when this parameter is known, and to consists in considering the smallest instantaneous bitrate of the
reuse the derivation of Section 3.1.1. 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.
There are also situations where the peak bitrate is not know. In Another approach consists in using ADU timing information (e.g.,
that case the previous parameter derivation cannot be directly using the timestamp field of an RTP packet header, or registering the
applied. An approach in that case consists in using ADU timing time upon receiving a new ADU). From the global FEC-related latency
information when present (e.g., using the timestamp field of an RTP budget the FECFRAME sender can derive a practical maximum latency
packet header) to manage the encoding window accordingly, in budget for encoding operations, max_lat_for_encoding. For the FEC
particular removing old symbols whose associated ADUs timed-out. Schemes specified in this document, this latency budget SHOULD be
computed with:
No matter the choice of the FECFRAME sender, a FECFRAME receiver can max_lat_for_encoding = max_lat * 0.75
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 It follows that any source symbols associated to an ADU that has
FECFRAME receiver may want to adapt its ls_max_size accordingly in timed-out with respect to max_lat_for_encoding SHOULD be removed from
order to avoid managing linear systems that would be significantly the encoding window. With this approach there is no pre-determined
too large. It is worth noticing however that it is preferable to use ew_size value: this value fluctuates over the time according to the
an ls_max_size too large than the opposite. 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 significanlty 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 Beyond these general guidelines, the details of how to manage these
situations at a FECFRAME sender and receiver remain out of scope of situations at a FECFRAME sender and receiver can depend on additional
this document. considerations that are out of scope of this document.
3.1.3. Parameter Derivation for Non Real-Time Flows 3.1.3. Case of a Non Real-Time Flow
Finally there are situations where there is no known real-time Finally there are configurations where a source ADU flow has no real-
constraints. FECFRAME and the FEC Schemes defined in this document time constraints. FECFRAME and the FEC Schemes defined in this
can still be used. The choice of appropriate parameter values can be document can still be used. The choice of appropriate parameter
directed by practical considerations. It can be an estimation of the values can be directed by practical considerations. For instance it
maximum memory amount that could be dedicated to the linear system at can derive from an estimation of the maximum memory amount that could
a FECFRAME receiver, or CPU computation requirements at a FECFRAME be dedicated to the linear system at a FECFRAME receiver, or the
receiver, both of them depending on the ls_max_size. The same maximum computation complexity at a FECFRAME receiver, both of them
considerations can also apply to the FECFRAME sender, where maximum depending on the ls_max_size parameter. The same considerations also
memory and CPU computation requirements depend on the ew_max_size. apply to the FECFRAME sender, where the maximum memory amount and
Here also, the NSS value contained in FEC Repair Packets is used to computation complexity depend on the ew_max_size parameter.
inform a FECFRAME receiver of the current coding window size (and
ew_max_size by observing its maximum value over the time). 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 Beyond these general guidelines, the details of how to manage these
situations at a FECFRAME sender and receiver remain out of scope of situations at a FECFRAME sender and receiver can depend on additional
this document. 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 cannot directly be
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). At a sender, this
identifier is prepended to each ADU before FEC encoding. This way, identifier is prepended to each ADU before FEC encoding. This way,
FEC decoding at a receiver also recovers this Flow ID and a recovered 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 ADU can be assigned to the right source flow (note that transport
skipping to change at page 15, line 20 skipping to change at page 15, line 43
UINT8 cc_tab[], UINT8 cc_tab[],
UINT16 cc_nb, UINT16 cc_nb,
UINT8 dt, UINT8 dt,
UINT8 m) UINT8 m)
{ {
UINT32 i; UINT32 i;
if (dt > 15) { if (dt > 15) {
return SOMETHING_WENT_WRONG; /* bad dt parameter */ return SOMETHING_WENT_WRONG; /* bad dt parameter */
} }
if (repair_key == 0 && dt != 15 && m != 2) {
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 */
if (repair_key == 0) {
return SOMETHING_WENT_WRONG; /* bad repair_key */
}
pmms_srand(repair_key); pmms_srand(repair_key);
pmms_rand(16); /* skip the first PRNG value */ 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:
if (repair_key == 0) {
return SOMETHING_WENT_WRONG; /* bad repair_key */
}
pmms_srand(repair_key); pmms_srand(repair_key);
pmms_rand(256); /* skip the first PRNG value */ 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);
} }
skipping to change at page 16, line 42 skipping to change at page 17, line 19
motivated by a possible bias in the first value generated depending motivated by a possible bias in the first value generated depending
on the way the repair key is managed by a FECFRAME implementation. on the way the repair key is managed by a FECFRAME implementation.
Indeed, the PRNG sequences produced by two seeds in sequence have a Indeed, the PRNG sequences produced by two seeds in sequence have a
high probability of starting with the same value since I1 = A * seed high probability of starting with the same value since I1 = A * seed
(modulo M) which is further scaled to a small range (either {0, ... (modulo M) which is further scaled to a small range (either {0, ...
15} or {0, ... 255}). Producing several times the same first coding 15} or {0, ... 255}). Producing several times the same first coding
coefficient could reduce the protection of the first source symbol if coefficient could reduce the protection of the first source symbol if
multiple repair symbols are produced with the same coding window's multiple repair symbols are produced with the same coding window's
left edge. The extra call avoids such side effects. left edge. The extra call avoids such side effects.
3.6. Linear Combination of Source Symbols Computation 3.6. Finite Fields Operations
The two RLC FEC Schemes specified in this document reuse the Finite
Fields defined in [RFC5510], section 8.1. More specifically, the
elements of the field GF(2^^m) are represented by polynomials with
binary coefficients (i.e., over GF(2)) and degree lower or equal to
m-1. The addition between two elements is defined as the addition of
binary polynomials in GF(2), which is equivalent to a bitwise XOR
operation on the binary representation of these elements.
With GF(2^^8), multiplication between two elements is the
multiplication modulo a given irreducible polynomial of degree 8.
The following irreducible polynomial MUST be used for GF(2^^8):
x^^8 + x^^4 + x^^3 + x^^2 + 1
With GF(2), multiplication corresponds to a logical AND operation.
3.6.1. 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
skipping to change at page 23, line 38 skipping to change at page 24, line 34
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 Lincensing: 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 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
skipping to change at page 26, line 32 skipping to change at page 27, line 22
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 Marie-Jose Montpetit for her valuable The authors would like to thank Jonathan Detchart, Gorry Fairhurst,
feedbacks on this document. and Marie-Jose Montpetit for their valuable feedbacks on this
document.
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), March 2018, (Work in Progress), March 2018,
skipping to change at page 27, line 48 skipping to change at page 28, line 38
[rand31pmc] [rand31pmc]
Whittle, R., "31 bit pseudo-random number generator", Whittle, R., "31 bit pseudo-random number generator",
September 2005, <http://www.firstpr.com.au/dsp/rand31/ September 2005, <http://www.firstpr.com.au/dsp/rand31/
rand31-park-miller-carta.cc.txt>. rand31-park-miller-carta.cc.txt>.
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Staircase and Triangle Forward Error Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
June 2008, <https://www.rfc-editor.org/info/rfc5170>. June 2008, <https://www.rfc-editor.org/info/rfc5170>.
[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"Reed-Solomon Forward Error Correction (FEC) Schemes",
RFC 5510, DOI 10.17487/RFC5510, April 2009,
<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>.
[RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density [RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density
Parity Check (LDPC) Staircase Forward Error Correction Parity Check (LDPC) Staircase Forward Error Correction
(FEC) Scheme for FECFRAME", RFC 6816, (FEC) Scheme for FECFRAME", RFC 6816,
DOI 10.17487/RFC6816, December 2012, DOI 10.17487/RFC6816, December 2012,
<https://www.rfc-editor.org/info/rfc6816>. <https://www.rfc-editor.org/info/rfc6816>.
skipping to change at page 29, line 11 skipping to change at page 30, line 11
[WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number [WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number
Generator", http://www.firstpr.com.au/dsp/rand31/, Generator", http://www.firstpr.com.au/dsp/rand31/,
January 2008, <http://www.firstpr.com.au/dsp/rand31/>. January 2008, <http://www.firstpr.com.au/dsp/rand31/>.
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 With a real-time source ADU flow, it is possible to improve the
codes without impacting maximum latency, at the cost of extra CPU decoding performance of sliding window codes without impacting
overhead. The optimization consists, for a receiver, to extend the maximum latency, at the cost of extra CPU overhead. The optimization
linear system beyond the decoding window, by keeping a certain number consists, for a FECFRAME receiver, to extend the linear system beyond
of old source symbols. the decoding window maximum size, by keeping a certain number of old
source symbols whereas their associated ADUs timed-out:
ls_max_size > dw_max_size ls_max_size > dw_max_size
Usually the following choice is a good trade-off between decoding Usually the following choice is a good trade-off between decoding
performance and extra CPU overhead: performance and extra CPU overhead:
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).
skipping to change at page 30, line 14 skipping to change at page 31, line 15
conditions and is therefore recommended for receivers experiencing conditions and is therefore recommended for receivers experiencing
bad communication conditions [Roca16]. In any case whether or not to bad communication conditions [Roca16]. In any case whether or not to
use this optimization and what exact value to use for the ls_max_size use this 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 Univ. Grenoble Alpes
France France
EMail: vincent.roca@inria.fr EMail: vincent.roca@inria.fr
Belkacem Teibi Belkacem Teibi
INRIA INRIA
Grenoble Univ. Grenoble Alpes
France France
EMail: belkacem.teibi@inria.fr EMail: belkacem.teibi@inria.fr
 End of changes. 48 change blocks. 
168 lines changed or deleted 226 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/