Ballot for draft-ietf-tsvwg-rlc-fec-scheme
Discuss
Yes
No Objection
Note: This ballot was opened for revision 09 and is now closed.
Thank you for addressing my DISCUSSes and COMMENTs.
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.
There's an extra "n" in "reasonnable bounds".
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.
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.
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.
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.
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?
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.