```
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
This fully-specified FEC Scheme defines the Sliding Window Random
Linear Codes (RLC) over GF(2^^8).
4.1. Formats and Codes
4.1.1. FEC Framework Configuration Information
- The FEC Framework Configuration Information (or FFCI) includes
- information that MUST be communicated between the sender and
- receiver(s). More specifically, it enables the synchronization of
- the FECFRAME sender and receiver instances. It includes both
- mandatory elements and scheme-specific elements, as detailed below.
+ Following the guidelines of [RFC6363], section 5.6, this section
+ provides the FEC Framework Configuration Information (or FFCI). This
+ FCCI needs to be shared (e.g., using SDP) between the FECFRAME sender
+ and receiver instances in order to synchronize them. It includes a
+ 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
Scheme MUST be XXXX, as assigned by IANA (Section 10).
When SDP is used to communicate the FFCI, this FEC Encoding ID is
carried in the 'encoding-id' parameter.
4.1.1.2. FEC Scheme-Specific Information
The FEC Scheme-Specific Information (FSSI) includes elements that are
@@ -722,21 +864,21 @@
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol ID (ESI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: Source FEC Payload ID Encoding Format
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
generated from the same encoding window, using Repair_Key values that
are managed as explained below. A receiver can easily deduce 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
UDP is the underlying transport protocol) and the symbol size, E,
communicated in the FFCI.
A FEC Repair Packet MUST contain a Repair FEC Payload ID that is
prepended to the repair symbol as illustrated in Figure 6.
@@ -759,21 +901,21 @@
Repair_Key (16-bit field): this unsigned integer is used as a seed
by the coefficient generation function (Section 3.5) in order to
generate the desired number of coding coefficients. Value 0 MUST
NOT be used. When a FEC Repair Packet contains several repair
symbols, this repair key value is that of the first repair symbol.
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
1 (note that 0 is not a valid value).
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
precisely, it controls the probability of having a non zero coding
coefficient, which equals (DT+1) / 16. When a FEC Repair Packet
contains several repair symbols, the DT value applies to all of
them;
Number of Source Symbols in the encoding window, NSS (12-bit field):
this unsigned integer indicates the number of source symbols in
the encoding window when this repair symbol was generated. When a
FEC Repair Packet contains several repair symbols, this NSS value
@@ -805,21 +947,21 @@
5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU Flows
This fully-specified FEC Scheme defines the Sliding Window Random
Linear Codes (RLC) over GF(2) (binary case).
5.1. Formats and Codes
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
Scheme MUST be YYYY, as assigned by IANA (Section 10).
When SDP is used to communicate the FFCI, this FEC Encoding ID is
carried in the 'encoding-id' parameter.
5.1.1.2. FEC Scheme-Specific Information
All the considerations of Section 4.1.1.2 apply here.
@@ -854,27 +996,27 @@
zero monotonically increasing integer value, incremented for each
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 PRNG seed, value 0 is prohibited). This repair key is communicated
to the coefficient generation function (Section Section 3.5) in order
to generate ew_size coding coefficients. Finally, the FECFRAME
sender computes the repair symbol as a linear combination of the
ew_size source symbols using the ew_size coding coefficients. When E
is small and when there is an incentive to pack several repair
symbols within the same FEC Repair Packet, the appropriate number of
- repair symbols are computed. The only constraint is to increment by
- 1 the repair key for each of them, keeping the same ew_size source
+ repair symbols are computed. In that case the repair key for each of
+ them MUST be incremented by 1, keeping the same ew_size source
symbols, since only the first repair key will be carried in the
- Repair FEC Payload ID. The FEC Repair Packet can then be sent. The
- source versus repair FEC packet transmission order is out of scope of
- this document and several approaches exist that are implementation
- specific.
+ Repair FEC Payload ID. The FEC Repair Packet can then be passed to
+ the transport layer for transmission. The source versus repair FEC
+ packet transmission order is out of scope of this document and
+ several approaches exist that are implementation specific.
Other solutions are possible to select a repair key value when a new
FEC Repair Packet is needed, for instance by choosing a random
integer between 1 and 65535. However, selecting the same repair key
as before (which may happen in case of a random process) is only
meaningful if the encoding window has changed, otherwise the same FEC
Repair Packet will be generated.
6.2. Decoding Side
@@ -892,32 +1034,37 @@
ew_size coding coefficients that are computed by the same coefficient
generation function (Section Section 3.5), using the repair key and
encoding window descriptions carried in the Repair FEC Payload ID.
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
recover lost source symbols. Each time an ADUI can be totally
recovered, padding is removed (thanks to the Length field, L, of the
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
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
application. This document does not mandate any approach as this is
an operational and management decision.
With real-time flows, a lost ADU that is decoded after the maximum
- latency or an ADU received after this delay should not be passed to
- the application. Instead the associated source symbols should be
- removed from the linear system maintained by the receiver(s).
- Appendix A discusses a backward compatible optimization whereby those
- late source symbols may still be used in order to improve the global
- robustness.
+ latency or an ADU received after this delay has no value to the
+ application. This raises the question of deciding whether or not an
+ ADU is late. This decision MAY be taken within the FECFRAME receiver
+ (e.g., using the decoding window, see Section 3.1) or within the
+ application (e.g., using RTP timestamps within the ADU). Deciding
+ 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
Editor's notes: RFC Editor, please remove this section motivated by
RFC 6982 before publishing the RFC. Thanks.
An implementation of the Sliding Window RLC FEC Scheme for FECFRAME
exists:
o Organisation: Inria
@@ -1090,20 +1237,29 @@
Forward Error Correction (FEC) Framework", RFC 6364,
DOI 10.17487/RFC6364, October 2011,
```.
12.2. Informative References
[CA90] Carta, D., "Two Fast Implementations of the Minimal
Standard Random Number Generator", Communications of the
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,
+ .
+
[PM88] Park, S. and K. Miller, "Random Number Generators: Good
Ones are Hard to Find", Communications of the ACM, Vol.
31, No. 10, pp.1192-1201, 1988.
[PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
"Numerical Recipies in C; Second Edition", Cambridge
University Press, ISBN: 0-521-43108-5, 1992.
[rand31pmc]
Whittle, R., "31 bit pseudo-random number generator",
@@ -1155,53 +1311,66 @@
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:
+ of old source symbols.
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).
+ 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
/---------------------------------^-------------------------------\
late source symbols
(pot. decoded but not delivered) dw_max_size
/--------------^-----------------\ /--------------^---------------\
src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12
Figure 8: Relationship between parameters to decode beyond maximum
latency.
It means that source symbols, and therefore ADUs, may be decoded even
if the added latency exceeds the maximum value permitted by the
- application. It follows that the corresponding ADUs SHOULD NOT be
- delivered to the application and SHOULD be dropped once they are no
- longer needed. However, decoding these "late symbols" significantly
- improves the global robustness in bad reception 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
+ application. It follows that the corresponding ADUs will not be
+ useful to the application. However, decoding these "late symbols"
+ significantly improves the global robustness in bad reception
+ 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
France
EMail: vincent.roca@inria.fr
Belkacem Teibi
INRIA
Grenoble