Re: [Rmt] RE: Comments to draft-ietf-rmt-fec-bb-revised-00.txt

[Vincent Roca <[e-mail]>]

Hello Mike/Mark,


Two parts in this answer:


1/  "** Section 6.1: What about classes of FEC codes?"
Let's discuss this aspect some more since it is directly related to our
LDPC FEC BB I-D.

You're right, the idea of "class of codes" is nebulous and should be used
with great care.

But the two LDPC codes we specified and many other codes, like
the regular LDPC codes introduced by Gallager in 1962, the LDPC codes
that have been standardized for DVB-S2, the 802.11n LDPC proposals
(TGnsync and WWISE), and other ways of building the parity check matrix
proposed here and there, share many similarities.

(NB: Of course, here I assume that the DVB-S2/802.11n proposals can be
applied to a packet erasure channel rather than on the physical channel,
their initial target, but this is usually not a problem.)

For instance:

 - these codes rely on a parity check matrix (or a cascade of such matrices),
   which can also be used as a generator matrix in some cases (e.g. LDGM-*)
   for encoding performance purposes;

 - this matrix is pre-defined and shared by both the encoder and decoder;

 - codes are not MDS (which requires an appropriate behavior at the decoder);

 - they are large block FEC codes (in the sense of RFC 3453);

 - they can use an iterative decoding algorithm (even if it's not
   mandatory);

(NB: this list must be carefully checked in order to find the
 most appropriate criteria...)

The LT/Raptor codes, being rateless, build the graph (which translates
to a parity check matrix) dynamically. That's a completely different
approach and it does not fit in the framework we want to setup (e.g.
the FEC OTI does not need any Max-Nb-of-Encoding-Symbols).

So I think we can nonetheless identify a class that is a subset of
the "large block FEC codes" (RFC 3453) and that excludes the "expandable
FEC codes". You're right, we need to clarify in the I-D what we mean
by LDPC in _this_ context. You're also right, there is a risk that by
over-restricting the common part for FEC Encoding ID 132, some LDPC codes
may not be able to use this FEC Encoding ID. Though, this risk is now
minimized by the scheme specific optional elements.

Finally, if our LDPC I-D restricts the applicability of the Under-Specified
FEC Encoding ID 132 to a "class of logically related codes", which is
not recommended in general, it does not mean that the same should be done
with other Under-Specified FEC Encoding IDs.

Note that the LDPC Staircase/Triangle codes cannot use FEC Encoding ID
128 since it lacks the "Max-Nb-of-Encoding-Symbols" element (same remark
for the seed, even if a default value could be hard-coded). So we need
something else in any case.



2/ Actual use of Under-specified FEC Encoding ID 128

128 is in theory for "small/large block, expandable" schemes, but:
(1) we've seen it's inappropriate for LDPC,
(2) Raptor is fully specified, and
(3) Reed-Solomon (RS) is better supported with 129, as we explained
last year in: draft-peltotalo-rmt-bb-fec-supp-xor-pcm-rs-00.txt.
And from discussion in December 2004, two people were in favor
of having RS be fully specified...

Will 128 be used one day (i.e. Instance IDs be specified) ? It's not
obvious. Don't know for 129/130...


Regards,


    Vincent/Christoph.


Michael Luby wrote:
> All,
> Below are responses (start with ***) to Vincent/Christoph comments on the
> revised FEC building block.  Vincent's original comments are included for
> context.
> Mike Luby and Mark Watson
> 
> From: Vincent Roca [[e-mail]]
> Sent: Friday, July 01, 2005 5:47 AM
> To: [e-mail]; Michael Luby; [e-mail]; Lorenzo
> Vicisano
> Cc: Vincent Roca; Christoph Neumann
> Subject: Comments to draft-ietf-rmt-fec-bb-revised-00.txt
> 
> Dear all,
> 
> Here are a few comments for the FEC BB revised I-D.
> 
> 
> ** Section 2, definitions:
> --------------------------
> 
> What is a FEC scheme? This is not defined here.
> There is no ambiguity with Fully-Specified Schemes (it's an instance of
> FEC codes), but with Under-Specified schemes, there can be several
> FEC Scheme instances per FEC Scheme, and it begins to be confusing...
> For instance, to follow the guidelines of section 6.1 regarding the
> share of existing Under-Specified schemes, if FEC codes A and FEC codes B
> can both use the FPI and FEC OTI of FEC Encoding ID 128, then they will
> be part of the same FEC Scheme, even if they need completely different
> codecs?
> 
> *** Yes, this last sentence is the interpretation that is intended.  The
> intention of the FEC Encoding ID
> is to define the structural format of the protocol, including the particular
> parameters and their lengths
> and their generic usage, but not at all to define the FEC code.  In
> particular, the FEC Payload ID and
> the FEC OTI parameters and their lengths and formats are both defined by the
> FEC Encoding ID for an Under-Specified Scheme, and then once the FEC code is
> specified (as specified by the FEC Instance ID, where the FEC Instance ID
> specifies the particular FEC code) then it is a Fully-Specified FEC Scheme.
> 
> As a consequence, the definition of "Encoder" and "Decoder" are
> ambiguous. From the I-D, and encoder defines the "FEC scheme specific
> functions". But with FEC Encoding ID 128 (for instance), there will
> be several different __codecs__, one per FEC code instance... What the
> I-D defines as Encoder and Decoder is not in line with the traditional
> acceptation of these words. I suggest:
> Encoder: The FEC Scheme __instance__ specific functions...
> Decoder: idem
> 
> In other words, Encoder+Decoder == FEC codec
> 
> *** Yes, that was the intention. The FEC Encoding ID identifies the FEC
> Scheme, which defines the FPI and OTI and their encodings and the FEC
> Instance ID identifies the specific FEC codec.
> 
> 
> ** Section 6.1:
> ---------------
> 
> It is said:
>         "The FEC Encoding ID allows receivers to select the appropriate
>         FEC decoder".
> This is only true with Fully Specified schemes, not with Under-Specified
> schemes. Since this sentence appears just after the definition of
> Under-Specified Schemes, this is rather misleading.
> I'd say instead:
>         "The FEC Encoding ID allows receivers to select the appropriate
>         FEC Scheme, and in case of Fully-Specified  FEC Schemes, to select
>         the appropriate decoder."
> 
> *** True.  What you say above is ok in terms of a fuller explanation.  Might
> even want to add that for Under-Specified FEC Schemes the FEC Instance ID
> determines the particular FEC code that is to be used.
> 
> 
> ** Section 6.1: What about classes of FEC codes?
> ------------------------------------------------
> 
> Just like RFC3452, this I-D does not introduce the possibility of defining
> broad classes of FEC codes, that would share the same FEC Encoding ID!
> LDPC codes are typically a broad class of FEC codes, that usually share
> share the same FPI/FEC OTI, and therefore the same FEC Scheme. This is
> what we suggested for LDPC (draft-roca-rmt-ldpc-00.txt).
> In that case:
>   FEC Encoding ID 132 ==> LDPC codes
>   As such this is Under-Specified.
>   FEC Encoding ID 132 + FEC Instance ID 0 ==> flavor 1 of LDPC codes
>   This time 132/0 is "Completely Specified", i.e. its definition is non
>   ambiguous and enables independant implementers to define interoperable
>   implementations, just like Fully-Specified FEC Schemes.
> 
> *** It is difficult/pretty much impossible to identify FEC codes by
> "classes".  Yes, in coding communities this is done on an informal basis,
> but to put this into a RFC is pretty tricky and has lots of pitfalls.  That
> is why the idea instead in the FEC building block was to classify FEC
> schemes based on similarities in terms of protocol behavior and parameter
> definitions (same FEC Payload ID parameters and formats, same FEC OTI
> parameters and formats, same application behavior) which are easy to specify
> in an RFC rather than vague concepts like FEC code classes.  For example,
> the "LDPC class" is fairly nebulous in its definition, as it may contain
> codes such as LDGM triangle (which is really not an LDPC formally at all,
> since it doesn't have any parity-checks), LT codes, Raptor codes, and a
> bunch of other codes that have quite different properties.  No complaints
> against specifying another FEC Encoding ID 132, but to say that it is only
> for use by LDPC codes doesn't seem good.  There are other codes that would
> be hard to classify as LDPC codes that might want to use this same FEC
> Encoding ID, and other codes that could be classified as LDPC codes that
> probably would not use this FEC Encoding ID.  What is in the intention of
> the FEC building block for an Under-Specified FEC Scheme is for the FEC
> Encoding ID to define FEC Payload ID and FEC OTI parameters with their
> formats and a description of how these parameters would be used by the
> application.  The FEC Instance ID specifies the particular FEC code to be
> used, and whether or not a particular FEC code is suitable for that FEC
> Encoding ID depends on the parameter definitions and formats and the
> intended behavior.  Note that among the original FEC Encoding IDs, i.e.,
> 128, 129 and 130, there is no attempt to restrict the FEC Encoding ID to a
> particular class of codes, although for example it is clear that FEC
> Encoding ID 128 might be most suitable for LDPC-like codes, whereas FEC
> Encoding ID 129 is probably more suitable for Reed-Solomon-like codes,
> although there is no attempt to say that this is mandated.
> 
> 
> To enable that, we only need to change the over-restricting (IMHO) sentence:
>         "It is possible that an FEC scheme may not be a Fully-Specified FEC
>         Scheme, because either a specification is simply not available or a
>         party exists that owns the encoding scheme and is not willing to
>         disclose the algorithm and specification."
> We can add for instance:
>         ... or it gathers a set logically related FEC codes which may
>         be extended in the future as new FEC codes are discovered.
> 
> *** It probably makes sense to add this sentence, but without the words
> "logically related". Not to say that instances of a Scheme are not related -
> since they share the same FEC Payload ID and OTI they are related in that
> sense. But there should not be an implication that some other relationship
> is a necessary condition for a code to be defined as an instance of a
> particular FEC Scheme.
> 
> The assets:
> - it saves a large number of FEC Encoding IDs <= 127 since all sub-codes
>   will share the same FEC Encoding ID >= 128. I remember that
>   Mike already pointed out this as a potential issue in a previous meeting.
> 
> *** True enough Mike Luby said something like this, although we have
> resolved this for the time being with the strategy that we will not do
> anything about what is probably not really an issue for the forseeable
> future (too many FEC codes), and if we do see that we are running into an
> issue in the future then we can reserve a range of FEC Encoding IDs.  As
> Mark Watson pointed out, best not to reserve a range now because then people
> might feel that they can use that range immediately for private purposes
> without facing any consequences down the road since it is a reserved range.
> 
> - it does not contradict the Under-Specified definition, since as such, the
>   FEC scheme is not completely specified. Only the <FEC Enc ID, FEC Inst ID>
>   are __Completely Specified__ (to avoid using the "Fully-Specified" term).
> 
> - it saves the burden of defining a new introduction, FPI/FEC OTI, etc.
>   stuff since all instances will inherit it from their parent document.
> 
> 
> ** Section 6.2.1 and later: about the "encoding format"
> -------------------------------------------------------
> 
> In case the FEC Scheme specifies a binary encoding format (e.g. an
> EXT_FTI or similar format), this encoding format may include the FEC
> Instance ID (this is the case with an EXT_FTI encoding), which in fact
> MUST be defined by the CDP. Contradiction here.
> With an XML encoding format specification, this is not an issue since
> elements will be listed sequentially, instead of being packed together.
> 
> 
> Additional minor remarks:
> -------------------------
> 
> ** Section 2:
>         "Decoder: ...to transform received FEC encoded data into..."
>         Bad wording, not compliant with rules. Should say instead:
>         "...to transform received encoding symbols into..."
> 
> ** Section 6.2.1 introduces for the 1st time the "encoding format".
>         Maybe this term should be defined in section 2?
> 
> 
> Cheers,
> 
>    Vincent/Christoph
> 
> 
> _______________________________________________
> Rmt mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/rmt
> 
> 


-- 
---------------------- http://www.inrialpes.fr/planete/people/roca/
  INRIA Rhone-Alpes - projet planete      [e-mail]
  Zirst; 655 av. de l'Europe; Montbonnot  phone [phone]
  38334 ST ISMIER cedex - France          fax   [phone]

_______________________________________________
Rmt mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/rmt