--- 1/draft-ietf-tsvwg-rlc-fec-scheme-03.txt 2018-05-18 00:13:09.269814799 -0700
+++ 2/draft-ietf-tsvwg-rlc-fec-scheme-04.txt 2018-05-18 00:13:09.333816337 -0700
@@ -1,19 +1,19 @@
TSVWG V. Roca
Internet-Draft B. Teibi
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)
Schemes for FECFRAME
- draft-ietf-tsvwg-rlc-fec-scheme-03
+ draft-ietf-tsvwg-rlc-fec-scheme-04
Abstract
This document describes two fully-specified Forward Erasure
Correction (FEC) Schemes for Sliding Window Random Linear Codes
(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
code density. They can protect arbitrary media streams along the
lines defined by FECFRAME extended to sliding window FEC codes.
These sliding window FEC codes rely on an encoding window that slides
@@ -31,21 +31,21 @@
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
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 (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
@@ -59,66 +59,68 @@
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Limits of Block Codes with Real-Time Flows . . . . . . . 3
1.2. Lower Latency and Better Protection of Real-Time Flows
with the Sliding Window RLC Codes . . . . . . . . . . . . 4
1.3. Small Transmission Overheads with the Sliding Window RLC
FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Document Organization . . . . . . . . . . . . . . . . . . 6
2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6
3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7
- 3.1. Possible Parameter Derivation . . . . . . . . . . . . . . 7
- 3.1.1. Detailed Parameter Derivation for CBR Real-Time Flows 8
- 3.1.2. Parameter Derivation for Other Real-Time Flows . . . 10
- 3.1.3. Parameter Derivation for Non Real-Time Flows . . . . 10
+ 3.1. Possible Parameter Derivations . . . . . . . . . . . . . 7
+ 3.1.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . 8
+ 3.1.2. Other Types of Real-Time Flow . . . . . . . . . . . . 10
+ 3.1.3. Case of a Non Real-Time Flow . . . . . . . . . . . . 11
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
+ 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
- Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
- 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 17
- 4.1.1. FEC Framework Configuration Information . . . . . . . 17
- 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 18
- 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 19
- 4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 20
+ Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
+ 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18
+ 4.1.1. FEC Framework Configuration Information . . . . . . . 18
+ 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 19
+ 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20
+ 4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21
5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
- 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 21
- 5.1.1. FEC Framework Configuration Information . . . . . . . 21
- 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 21
- 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 21
- 5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21
- 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 21
- 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 21
- 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 22
- 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 23
- 8. Security Considerations . . . . . . . . . . . . . . . . . . . 23
+ 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 22
+ 5.1.1. FEC Framework Configuration Information . . . . . . . 22
+ 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 22
+ 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22
+ 5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 22
+ 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 22
+ 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 22
+ 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 23
+
+ 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 24
+ 8. Security Considerations . . . . . . . . . . . . . . . . . . . 24
8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24
8.1.1. Access to Confidential Content . . . . . . . . . . . 24
- 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 24
- 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 24
+ 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 25
+ 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 25
8.3. When Several Source Flows are to be Protected Together . 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
- GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 25
+ GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2. Operational Recommendations: Coding Coefficients Density
- Threshold . . . . . . . . . . . . . . . . . . . . . . . . 25
- 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
- 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 26
- 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
- 12.1. Normative References . . . . . . . . . . . . . . . . . . 26
- 12.2. Informative References . . . . . . . . . . . . . . . . . 27
- Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 29
- Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30
+ Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26
+ 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27
+ 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
+ 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27
+ 12.1. Normative References . . . . . . . . . . . . . . . . . . 27
+ 12.2. Informative References . . . . . . . . . . . . . . . . . 28
+ Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 30
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 31
1. Introduction
Application-Level Forward Erasure Correction (AL-FEC) codes, or
simply FEC codes, are a key element of communication systems. They
are used to recover from packet losses (or erasures) during content
delivery sessions to a large number of receivers (multicast/broadcast
transmissions). This is the case with the FLUTE/ALC protocol
[RFC6726] when used for reliable file transfers over lossy networks,
and the FECFRAME protocol when used for reliable continuous media
@@ -153,24 +155,24 @@
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
Sliding Window RLC Codes
This document introduces two fully-specified FEC Schemes that follow
a totally different approach: the Sliding Window Random Linear Codes
- (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
- FECFRAME extended to sliding window FEC codes [fecframe-ext]. These
- FEC Schemes, and more generally Sliding Window FEC codes, are
+ (RLC) over either Finite Field GF(2) or GF(2^^8). These FEC Schemes
+ are used to protect arbitrary media streams along the lines defined
+ by FECFRAME extended to sliding window FEC codes [fecframe-ext].
+ These FEC Schemes, and more generally Sliding Window FEC codes, are
recommended for instance with media that feature real-time
constraints sent within a multicast/broadcast session [Roca17].
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
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
either of fixed or variable size (elastic window). Repair packets
(symbols) are generated on-the-fly, computing a random linear
combination of the source symbols present in the current encoding
@@ -285,200 +287,228 @@
specification, that returns a new random integer in [0; maxv-1]
DT: coding coefficients density threshold, an integer between 0 and
15 (inclusive) the controls the fraction of coefficients that are
non zero
3. Procedures
This section introduces the procedures that are used by these FEC
Schemes.
-3.1. Possible Parameter Derivation
+3.1. Possible Parameter Derivations
The Sliding Window RLC FEC Scheme relies on several parameters:
- Maximum FEC-related latency budget, max_lat (in seconds) A source
- ADU flow can have real-time constraints, and therefore any
- FECFRAME related operation must take place within the validity
+ Maximum FEC-related latency budget, max_lat (in seconds) with real-
+ time flows:
+ 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
real-time constraints, we consider the most stringent constraints
(see [RFC6363], Section 10.2, item 6, for recommendations when
several flows are globally protected). The maximum FEC-related
latency budget, max_lat, accounts for all sources of latency added
by FEC encoding (at a sender) and FEC decoding (at a receiver).
Other sources of latency (e.g., added by network communications)
are out of scope and must be considered separately (said
differently, they have already been deducted from max_lat).
max_lat can be regarded as the latency budget permitted for all
- FEC-related operations. This is an input parameter that enables
- to derive other internal parameters as explained below;
+ FEC-related operations. This is an input parameter that enables a
+ FECFRAME sender to derive other internal parameters as explained
+ below;
Encoding window current (resp. maximum) size, ew_size (resp.
ew_max_size) (in symbols):
- these parameters are used by a sender during FEC encoding. More
- precisely, each repair symbol is a linear combination of the
- ew_size source symbols present in the encoding window when RLC
- 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:
+ at a FECFRAME sender, during FEC encoding, a repair symbol is
+ computed as a linear combination of the ew_size source symbols
+ present in the encoding window. The ew_max_size is the maximum
+ size of this window, while ew_size is the current size. For
+ instance, at session start, upon receiving new source ADUs, the
+ ew_size progressively increases until it reaches its maximum
+ value, ew_max_size. We have:
ew_size <= ew_max_size
Decoding window maximum size, dw_max_size (in symbols): at a
- receiver, this parameter denotes the maximum number of received or
- lost source symbols in the linear system (i.e., the variables)
- that are still within their latency budget;
- Linear system maximum size, ls_max_size (in symbols): The linear
- system maximum size managed by a receiver SHOULD NOT be smaller
- than this decoding window maximum size, since it would mean that,
- after receiving a sufficient number of FEC Repair Packets, an ADU
- may not be recovered just because it has been removed from the
- linear system, and not because it has timed-out. This would be
+ FECFRAME receiver, dw_max_size is the maximum number of received
+ or lost source symbols that are still within their latency budget;
+ Linear system maximum size, ls_max_size (in symbols): at a FECFRAME
+ receiver, the linear system maximum size, ls_max_size, is the
+ maximum number of received or lost source symbols in the linear
+ system (i.e., the variables). It SHOULD NOT be smaller than
+ dw_max_size since it would mean that, even after receiving a
+ sufficient number of FEC Repair Packets, a lost ADU may not 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
- 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
- determines the source and repair symbol sizes (necessarily equal).
- The cr parameter determines the code rate, i.e., the amount of
- redundancy added to the flow (i.e., cr is the ratio between the
- total number of source symbols and the total number of source plus
- repair symbols). These two parameters are input parameters that
- enable to derive other internal parameters as explained below. An
- implementation at a sender SHOULD fix the E parameter and
- communicate it as part of the FEC Scheme-Specific Information
- (Section 4.1.1.2). However there is no need to communicate the cr
- parameter per see (it's not required to process a repair packet at
- 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.
+ beyond the dw_max_size (Appendix A);
+ Symbol size, E (in bytes): the E parameter determines the source and
+ repair symbol sizes (necessarily equal). This is an input
+ parameter that enables a FECFRAME sender to derive other internal
+ parameters, as explained below. An implementation at a sender
+ SHOULD fix the E parameter and communicate it as part of the FEC
+ Scheme-Specific Information (Section 4.1.1.2).
+ Code rate, cr: The code rate parameter determines the amount of
+ redundancy added to the flow. More precisely the cr is the ratio
+ between the total number of source symbols and the total number of
+ source plus repair symbols and by definition: 0 < cr <= 1. This
+ is an input parameter that enables a FECFRAME sender to derive
+ other internal parameters, as explained below. However there is
+ no need to communicate the cr parameter per see (it's not required
+ to process a repair symbol at a receiver). This code rate
+ parameter can be 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.
- The FEC Schemes specified in this document can be used in various
- manners. They can protect one or more source ADU flows having real-
- time constraints, or they can protect non-realtime source ADU flows.
- The source ADU flows may be Constant Bitrate (CBR) flows, while other
- may be of Variable Bitrate (VBR). The FEC Schemes can be used in
- various environments like the Internet or over a CBR channel. It
- follows that the FEC Scheme parameters can be derived in different
- ways, as described in the following sections.
+ The FEC Schemes can be used in various manners. They can be used to
+ protect a source ADU flow having real-time constraints, or a non-
+ realtime source ADU flow. The source ADU flow may be a Constant
+ Bitrate (CBR) or Variable BitRate (VBR) flow. The features of the
+ flow (in particular its minimum/maximum bitrate) may be known or not.
+ The FEC Schemes can also be used over the Internet or over a CBR
+ communication path. It follows that the FEC Scheme parameters can be
+ derived in different ways, as described in the following sections.
-3.1.1. 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
- budget. The encoding symbol size (E, in bytes) is constant. The
- code rate (cr) is also constant, in line with the expected
- communication loss model. However the choice of this cr value is out
- of scope for this document.
+ budget. The encoding symbol size, E, is constant. The code rate,
+ cr, is also constant, its value depending on the expected
+ communication loss model (this choice is out of scope of this
+ document).
In a first configuration, the source ADU flow bitrate at the input of
- the FECFRAME sender is fixed (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
higher, depending on the added repair flow overhead. In order to
comply with the maximum FEC-related latency budget, we have:
dw_max_size = (max_lat * br_in) / (8 * E)
In a second configuration, the FECFRAME sender generates a fixed
- bitrate flow, equal to the CBR 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
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)
- For decoding to be possible, it is required that the encoding window
- 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]):
+ For decoding to be possible within the latency budget, it is required
+ that the encoding window maximum size be smaller than or at most
+ equal to the decoding window maximum size, the exact value having no
+ impact on the the FEC-related latency budget. For the FEC Schemes
+ specified in this document, in line with [Roca17], the ew_max_size
+ SHOULD be computed with:
ew_max_size = dw_max_size * 0.75
- The ew_max_size is the main parameter, used by 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 ew_max_size is the main parameter at a FECFRAME sender.
The dw_max_size is computed by a FECFRAME sender but not explicitly
communicated to a FECFRAME receiver. However a FECFRAME receiver can
easily evaluate the ew_max_size by observing the maximum Number of
Source Symbols (NSS) value contained in the Repair FEC Payload ID of
received FEC Repair Packets (Section 4.1.3). A receiver can then
easily compute dw_max_size:
dw_max_size = max_NSS_observed / 0.75
- 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:
+ A receiver can then chose an appropriate linear system maximum 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.
+ It is good practice to use a larger value for ls_max_size as
+ explained in Appendix A, which does not impact maximum latency nor
+ interoperability. However the linear system size should not be too
+ large for practical reasons (e.g., in order to limit computation
+ complexity).
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.
+ appropriately. Here ew_size increases each time a new source ADU is
+ received by the FECFRAME sender, until it reaches the ew_max_size
+ value. A FECFRAME receiver SHOULD continuously observe the received
+ FEC Repair Packets, since the NSS value carried in the Repair FEC
+ Payload ID will increase too, and adjust its ls_max_size accordingly
+ if need be.
-3.1.2. 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
- 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.
+ In other configurations, a real-time source ADU flow, with a max_lat
+ latency budget, features a variable bitrate (VBR). A first approach
+ consists in considering the smallest instantaneous bitrate of the
+ source ADU flow, when this parameter is known, and to reuse the
+ derivation of Section 3.1.1. Considering the smallest bitrate means
+ that the encoding window and decoding window maximum sizes estimation
+ are pessimistic: these windows have the smallest size required to
+ enable a decoding on-time at a FECFRAME receiver. If the
+ instantaneous bitrate is higher than this smallest bitrate, this
+ approach leads to an encoding window that is unnecessarily small,
+ which reduces robustness in front of long erasure bursts.
- 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.
+ Another approach consists in using ADU timing information (e.g.,
+ using the timestamp field of an RTP packet header, or registering the
+ time upon receiving a new ADU). From the global FEC-related latency
+ budget the FECFRAME sender can derive a practical maximum latency
+ budget for encoding operations, max_lat_for_encoding. For the FEC
+ Schemes specified in this document, this latency budget SHOULD be
+ computed with:
- 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.
+ max_lat_for_encoding = max_lat * 0.75
- 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.
+ It follows that any source symbols associated to an ADU that has
+ timed-out with respect to max_lat_for_encoding SHOULD be removed from
+ the encoding window. With this approach there is no pre-determined
+ ew_size value: this value fluctuates over the time according to the
+ instantaneous source ADU flow bitrate. For practical reasons, a
+ FECFRAME sender may still require that ew_size does not increase
+ beyond a maximum value (Section 3.1.3).
+
+ With both approaches, and no matter the choice of the FECFRAME
+ sender, a FECFRAME receiver can still easily evaluate the ew_max_size
+ by observing the maximum Number of Source Symbols (NSS) value
+ contained in the Repair FEC Payload ID of received FEC Repair
+ Packets. A receiver can then compute dw_max_size and derive an
+ appropriate ls_max_size as explained in Section 3.1.1.
+
+ When the observed NSS fluctuates significantly, a FECFRAME receiver
+ may want to adapt its ls_max_size accordingly. In particular when
+ the NSS is 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
- situations at a FECFRAME sender and receiver remain out of scope of
- this document.
+ situations at a FECFRAME sender and receiver can depend on additional
+ 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
- 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).
+ Finally there are configurations where a source ADU flow has no real-
+ time constraints. FECFRAME and the FEC Schemes defined in this
+ document can still be used. The choice of appropriate parameter
+ values can be directed by practical considerations. For instance it
+ can derive from an estimation of the maximum memory amount that could
+ be dedicated to the linear system at a FECFRAME receiver, or the
+ maximum computation complexity at a FECFRAME receiver, both of them
+ depending on the ls_max_size parameter. The same considerations also
+ apply to the FECFRAME sender, where the maximum memory amount and
+ computation complexity depend on the ew_max_size parameter.
+
+ Here also, the NSS value contained in FEC Repair Packets is used by a
+ FECFRAME receiver to determine the current coding window size and
+ ew_max_size by observing its maximum value over the time.
Beyond these general guidelines, the details of how to manage these
- situations at a FECFRAME sender and receiver remain out of scope of
- this document.
+ situations at a FECFRAME sender and receiver can depend on additional
+ considerations that are out of scope of this document.
3.2. ADU, ADUI and Source Symbols Mappings
At a sender, an ADU coming from the application cannot directly be
mapped to source symbols. When multiple source flows (e.g., media
streams) are mapped onto the same FECFRAME instance, each flow is
assigned its own Flow ID value (see below). At a sender, this
identifier is prepended to each ADU before FEC encoding. This way,
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
@@ -666,43 +696,46 @@
UINT8 cc_tab[],
UINT16 cc_nb,
UINT8 dt,
UINT8 m)
{
UINT32 i;
if (dt > 15) {
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) {
case 1:
if (dt == 15) {
/* all coefficients are 1 */
memset(cc_tab, 1, cc_nb);
} else {
/* here coefficients are either 0 or 1 */
+ if (repair_key == 0) {
+ return SOMETHING_WENT_WRONG; /* bad repair_key */
+ }
pmms_srand(repair_key);
pmms_rand(16); /* skip the first PRNG value */
for (i = 0 ; i < cc_nb ; i++) {
if (pmms_rand(16) <= dt) {
cc_tab[i] = (UINT8) 1;
} else {
cc_tab[i] = (UINT8) 0;
}
}
}
break;
case 8:
+ if (repair_key == 0) {
+ return SOMETHING_WENT_WRONG; /* bad repair_key */
+ }
pmms_srand(repair_key);
pmms_rand(256); /* skip the first PRNG value */
if (dt == 15) {
/* coefficient 0 is avoided here in order to include
* all the source symbols */
for (i = 0 ; i < cc_nb ; i++) {
do {
cc_tab[i] = (UINT8) pmms_rand(256);
} while (cc_tab[i] == 0);
}
@@ -737,21 +768,39 @@
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
+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
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
@@ -1068,21 +1117,21 @@
exists:
o Organisation: Inria
o Description: This is an implementation of the Sliding Window RLC
FEC Scheme limited to GF(2^^8). It relies on a modified version
of our OpenFEC (http://openfec.org) FEC code library. It is
integrated in our FECFRAME software (see [fecframe-ext]).
o Maturity: prototype.
o Coverage: this software complies with the Sliding Window RLC FEC
Scheme.
- o Lincensing: proprietary.
+ o Licensing: proprietary.
o Contact: vincent.roca@inria.fr
8. Security Considerations
The FEC Framework document [RFC6363] provides a comprehensive
analysis of security considerations applicable to FEC Schemes.
Therefore, the present section follows the security considerations
section of [RFC6363] and only discusses specific topics.
8.1. Attacks Against the Data Flow
@@ -1201,22 +1250,23 @@
o YYYY refers to the Sliding Window Random Linear Codes (RLC) over
GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in
Section 5 of this document.
o XXXX refers to the Sliding Window Random Linear Codes (RLC) over
GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in
Section 4 of this document.
11. Acknowledgments
- The authors would like to thank Marie-Jose Montpetit for her valuable
- feedbacks on this document.
+ The authors would like to thank Jonathan Detchart, Gorry Fairhurst,
+ and Marie-Jose Montpetit for their valuable feedbacks on this
+ document.
12. References
12.1. Normative References
[fecframe-ext]
Roca, V. and A. Begen, "Forward Error Correction (FEC)
Framework Extension to Sliding Window Codes", Transport
Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext
(Work in Progress), March 2018,
@@ -1264,20 +1314,25 @@
[rand31pmc]
Whittle, R., "31 bit pseudo-random number generator",
September 2005, .
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
June 2008, .
+ [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,
+ .
+
[RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen,
"FLUTE - File Delivery over Unidirectional Transport",
RFC 6726, DOI 10.17487/RFC6726, November 2012,
.
[RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density
Parity Check (LDPC) Staircase Forward Error Correction
(FEC) Scheme for FECFRAME", RFC 6816,
DOI 10.17487/RFC6816, December 2012,
.
@@ -1307,25 +1362,26 @@
[WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number
Generator", http://www.firstpr.com.au/dsp/rand31/,
January 2008, .
Appendix A. Decoding Beyond Maximum Latency Optimization
This annex introduces non normative considerations. They are
provided as suggestions, without any impact on interoperability. For
more information see [Roca16].
- It is possible to improve the decoding performance of sliding window
- codes without impacting maximum latency, at the cost of extra CPU
- overhead. The optimization consists, for a receiver, to extend the
- linear system beyond the decoding window, by keeping a certain number
- of old source symbols.
+ With a real-time source ADU flow, it is possible to improve the
+ decoding performance of sliding window codes without impacting
+ maximum latency, at the cost of extra CPU overhead. The optimization
+ consists, for a FECFRAME receiver, to extend the linear system beyond
+ 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
Usually the following choice is a good trade-off between decoding
performance and extra CPU overhead:
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).
@@ -1359,21 +1415,21 @@
conditions and is therefore recommended for receivers experiencing
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
parameter are decisions made by each receiver independently, without
any impact on the other receivers nor on the source.
Authors' Addresses
Vincent Roca
INRIA
- Grenoble
+ Univ. Grenoble Alpes
France
EMail: vincent.roca@inria.fr
Belkacem Teibi
INRIA
- Grenoble
+ Univ. Grenoble Alpes
France
EMail: belkacem.teibi@inria.fr