Skip to main content

Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Schemes for FECFRAME
draft-ietf-tsvwg-rlc-fec-scheme-16

Discuss


Yes

(Magnus Westerlund)

No Objection

Éric Vyncke
(Alvaro Retana)
(Deborah Brungard)
(Martin Vigoureux)
(Suresh Krishnan)

Note: This ballot was opened for revision 09 and is now closed.

Roman Danyliw
(was Discuss) No Objection
Comment (2019-06-18 for -15) Sent for earlier
Thank you for addressing my DISCUSSes and COMMENTs.
Éric Vyncke
No Objection
Eric Rescorla Former IESG member
Discuss
Discuss [Treat as non-blocking comment] (2018-10-09 for -09) Sent
Rich version of this review at:
https://mozphab-ietf.devsvcdev.mozaws.net/D3423


I do not believe that this specification is sufficiently precise to be
interoperably implemented.

DETAIL
S 3.4.
>      value, in addition to the maximum FEC-related latency budget
>      (Section 3.1).
>   
>   3.4.  Pseudo-Random Number Generator (PRNG)
>   
>      The RLC FEC Schemes defined in this document rely on the TinyMT32

What is the normative reference here? We can't really plausibly
normatively reference a github link without even a version hash. Is
the code in the appendix the normative description of the algorithm.


S 3.5.
>      These considerations apply both the RLC over GF(2) and RLC over
>      GF(2^^8), the only difference being the value of the m parameter.
>      With the RLC over GF(2) FEC Scheme (Section 5), m MUST be equal to 1.
>      With RLC over GF(2^^8) FEC Scheme (Section 4), m MUST be equal to 8.
>   
>      <CODE BEGINS>

Again, is the normative reference here the code? I note that this code
contains references to constants which are not defined here and
therefore will not compile


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

You should provide an algorithm for solving this system or at least a
pointer to a description of how to do so


S 12.2.
>    #define TINYMT32_MEXP 127
>    #define TINYMT32_SH0 1
>    #define TINYMT32_SH1 10
>    #define TINYMT32_SH8 8
>    #define TINYMT32_MASK UINT32_C(0x7fffffff)
>    #define TINYMT32_MUL (1.0f / 16777216.0f)

ANSI C doesn't specify any particular method of computing floating
point arithmetic, so I don't believe that any of this code is portably
deterministic.


S 12.2.
>        s->status[0] = s->status[1];
>        s->status[1] = s->status[2];
>        s->status[2] = x ^ (y << TINYMT32_SH1);
>        s->status[3] = y;
>        s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
>        s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;

You also can't assume that negative numbers have any particular
representation (e.g., twos complement) so this XOR is not
deterministic.
Magnus Westerlund Former IESG member
Yes
Yes (for -13) Not sent

                            
Spencer Dawkins Former IESG member
Yes
Yes (2018-10-01 for -09) Unknown
There's an extra "n" in "reasonnable bounds".
Adam Roach Former IESG member
No Objection
No Objection (2018-10-09 for -09) Sent
I support Eric Rescorla's DISCUSS, in particular the portion dealing with
being clear about which instance of the TinyMT32 PNRG is normative.

---------------------------------------------------------------------------

§1.2:

>  The RLC codes belong to the broad class of sliding window AL-FEC

Nit: "...sliding-window..."

---------------------------------------------------------------------------

§3.1.1:

>  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
...
>  A receiver can then
>  easily compute dw_max_size:
>
>     dw_max_size = max_NSS_observed / 0.75

Since the computation of ew_max_size is only "SHOULD" rather than "MUST," it
seems that the sender and receiver can end up with different notions of
ew_max_size. This raises two questions: (1) is such a situation harmful? and (2)
are there valid reasons a sender would compute ew_max_size differently than the
formula above?

If the answer to (1) is "yes" or the answer to (2) is "no", then I think the
"SHOULD" quoted above needs to be a "MUST."

---------------------------------------------------------------------------

§3.3:

>  new ADU arrives, once the ADU to source symbols mapping has been

"...ADU-to-source-symbols..."

---------------------------------------------------------------------------

§3.5:

>  When DT is between 0 (minimum
>  value) and strictly inferior to 15, the average probability of having
>  a non zero coefficient equals (DT +1) / 16.

This language ("strictly inferior to 15") seems odd, as the statement holds
true for DT=15 as well.

>  These considerations apply both the RLC over GF(2) and RLC over

Nit: "...apply to both..."

>      Figure 2: Coding Coefficients Generation Function pseudo-code

It seems a bit odd to call this "pseudocode": except of a handful of missing
definitions (stdint.h, string.h, tinymt32_t, tinymt32_rand, tinymt32_init, and
the success/error return codes), it is syntactically valid C that compiles
just fine.

---------------------------------------------------------------------------

§3.6.2:

"...and + is an XOR operation."

This is confusing. I understand that this is being done in an attempt to
simulate the "⊕" symbol in a document that is limited to ASCII, but the use of
"+" in a mathematical context is so well established that its use to mean
something different than addition runs the risk of implementor confusion.
Since this document uses "^^" for exponentiation, it would appear that the
symbol "^" remains available for XOR. This is consistent with the use of C in
multiple places in the document.

Alternatively, for complete avoidance of doubt, the computation of the repair
buffer could be denoted with:

      repair[i] = cc_tab[0] * src_0[i] XOR cc_tab[1] * src_1[i]
        XOR ... XOR cc_tab[ew_size - 1] * src_ew_size_1[i]

---------------------------------------------------------------------------

§6.1:

>  and several approaches exist that are implementation specific.

Nit: "...implementation-specific."

---------------------------------------------------------------------------

§6.2:

I agree and reiterate Eric Rescorla's concerns regarding this section. While I
understand that it is somewhat beyond the remit of this document to provide
tutorial information about theories of solving high-order systems of linear
equations, references to related materials would seem to be in order, as such
information is normatively required to implement this specification. If an
exemplary algorithm can be provided for solving the specific systems described
in this document, that would be even better (I understand that might not be
practical).

---------------------------------------------------------------------------

Appendix A:

Presuming the code in this appendix is intended to be normative, it needs to
normatively cite the formal language it uses. In this case, that would be C99 or
newer, as prior to C99, initial declarations in for loops were not allowed. I
believe the citation you want is ISO/IEC 9899:1999 (or something newer, such as
ISO/IEC 9899:2011)

Additionally, if the code in this appendix could also be described in prose, it
would make it more accessible (e.g., for non-C implementations) and more
maintainable. One of the lessons learned from publishing normative code as
part of RFC 6716 is that it is clearer and more maintainable to publish
normative prose accompanied by a non-normative reference implementation. See,
e.g., the discussion thread at
https://mailarchive.ietf.org/arch/msg/video-codec/SSdqF3q96WaLsSuYcjmgzLg32S8

I will further note that this arrangement should address the portability issues
that Eric Rescorla has identified in his discuss, as normative prose will
presumably not be subject to portability concerns.
Alissa Cooper Former IESG member
No Objection
No Objection (2018-10-11 for -09) Sent
I support Mirja's DISCUSS. I don't believe the copyright line can be included as-is in the appendix without also naming the IETF Trust.
Alvaro Retana Former IESG member
No Objection
No Objection (for -09) Not sent

                            
Ben Campbell Former IESG member
No Objection
No Objection (2018-10-10 for -09) Sent
I support Mirja's discuss, and extend it to mention that the inclusion of license language other than that in the Trust Legal Provisions (see the copyright notice boilerplate) is generally not allowed in RFCs.

I agree with Ekr's discuss point and Adam's comments about the normative reference for the TinyMT32 PRNG. I hope the answer is not that the code in Appendix A is normative; as Adam mentioned we've learned from experience (RFC 6716) that normative code is sub-optimal for the IETF standards process as it stands today.
Benjamin Kaduk Former IESG member
(was Discuss) No Objection
No Objection (2019-05-28 for -14) Sent
Thank you for resolving my Discuss points!  Additionally,
I really like the reorganization of the document(s) -- it seems to do a
great job at putting the core protocol/algorithm elements in the
spotlight, while retaining the interesting discussion about use cases
and parameter derivation in a less-prominent location.  The introductory
material for Appendix C also does a great job to frame the subsequent
discussion.  Thank you!

I agree with Roman that the code snippets should be more clearly marked
as (a specific version of) C and in the case of
generate_coding_coefficeints() as a normative part of the protocol
specification.

Section 3.1

   Appendix C proposes non normative technics to derive those
   parameters, depending on the use-case specificities.

nit: I think "techniques" would be more conventional usage than
"technics" here.

Section 3.5

   Any implementation of this PRNG MUST fulfill three validation
   criteria: the one described in [tinymt32] (for the TinyMT32 32-bit
   unsigned integer generator), and the two others detailed in
   Appendix A (for the mapping to 4-bit and 8-bit intervals).  [...]

As I noted on the tinymt32 document, this phrasing is a bit odd, though
it feels less out of place here than in the tinymt32 document.

Section 3.6

    * (in/out) cc_tab[]  pointer to a table of the right size to store
    *                    coding coefficients. All coefficients are
    *                    stored as bytes, regardless of the m parameter,
    *                    upon return of this function.

Assuming this is C, it's perhaps a bit jarring to spell the function
parameter as "cc_tab[]" but describe it as a pointer.  (In either case,
the encoding for the function call will be that of a pointer, of course,
so the array syntax seems needlessly confusing.)

Section 3.7.1

   The two RLC FEC Schemes specified in this document reuse the Finite
   Fields defined in [RFC5510], section 8.1.  More specifically, the
   [...]
   The following irreducible polynomial MUST be used for GF(2^^8):

      x^^8 + x^^4 + x^^3 + x^^2 + 1

Given the former chunk, the normative "MUST" in the second chunk is
redundant, since the authoritative source for this polynomial is the
cited portion of RFC 5510.

Section 3.7.2

             For each byte of position i in each source and the repair
   symbol, where i belongs to {0; E-1}, compute:

nit: do we expect the usage of the curly braces {} to indicate a closed
interval to be well-understood by the readership (as opposed to square
brackets [])?

                                      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}.  [...]

(ditto)

Section 6.1

I might add a note that the scheme for chosing the repair key is
entirely at the discretion of the sender, since it is communicated in
the wire format to the receiver(s), and that the sequential counter is
presented as the simplest method that ensures new coefficients for each
repair packet.  As already mentioned, other schemes are possible, and we
definitely don't want any receivers hardcoding the assumption of
sequentially incrementing counter.

Section 9.1

                                              In case of small encoding
   windows, the associated processing overhead is not an issue (e.g., we
   measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM
   Cortex-A15 embedded board in [Roca17] for an encoding window of size
   18 or 23 symbols).  [...]

Just to double-check: does the 2.8 Gbps correspond to the window of 18
symbols or 23?

Appendix A

Please note whether the numbers should be read out column-first or
row-first.

I refer again to my comment on the tinymt32 document regarding the
normative "MUST" language here vs. stating that these are test vectors.

Appendix B

side note: I don't propose to have you redo the analysis, but looking at
the small sequences generated using seed values from 0 to 1,000,000 - 1
is not terribly representative of the FEC usage, since the seed values
there are limited to the range from 0 to 16k.  Comprehensive statistics
on the 16k possible sequences (corresponding to the 16k possible repair
keys) of 20 pseudo-random numbers would be more compelling.

Also, for the scenario presented in Figure 12, I'm not sure I agree with
the claim that "although the distribution is not perfect, there is no
major bias".  Not in that I think there is bias, but in that I think
that we should not expect the average occurrences column to be a
constant -- the numbers here seem largely within the expected sort of
variances for this type of sampling.

Appendix D

   Finally, it is worth noting that a receiver that benefits from an FEC
   protection significantly higher than what is required to recover from
   packet losses, can choose to reduce the ls_max_size.  In that case
   lost ADUs will be recovered without relying on this optimization.

nit(?): It's not entirely clear to me that this statement is well-placed
in its current location.
Deborah Brungard Former IESG member
No Objection
No Objection (for -09) Not sent

                            
Ignas Bagdonas Former IESG member
No Objection
No Objection (2018-10-11 for -09) Sent
What is the status of interoperable implementations for this specification, and is there any operational experience? Implementation Status section shows one prototype implementation - is there any other running code, has any interoperability validation been done?
Martin Vigoureux Former IESG member
No Objection
No Objection (for -14) Not sent

                            
Mirja Kühlewind Former IESG member
(was Discuss) No Objection
No Objection (2019-05-20 for -13) Sent
Thanks for resolving the copyright issue.

I would prefer to see the Coding Coefficients Generation Function specified normatively in text and not only as code.
Suresh Krishnan Former IESG member
No Objection
No Objection (for -09) Not sent