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

From: "Michael Luby" <[email-masked]>
Date: Tue, 19 Jul 2005 19:56:44 -0700

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 [[email-masked]]
Sent: Friday, July 01, 2005 5:47 AM
To: [email-masked]; Michael Luby; [email-masked]; 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
[email-masked]
https://www1.ietf.org/mailman/listinfo/rmt

---

From: Vincent Roca <[email-masked]>
Date: Fri, 29 Jul 2005 14:09:36 +0200

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.

-- 
---------------------- http://www.inrialpes.fr/planete/people/roca/
  INRIA Rhone-Alpes - projet planete      [email-masked]
  Zirst; 655 av. de l'Europe; Montbonnot  phone (+33) 4.76.61.52.16
  38334 ST ISMIER cedex - France          fax   (+33) 4.76.61.52.52

---

From: "Michael Luby" <[email-masked]>
Date: Fri, 29 Jul 2005 13:05:04 -0700

Just so you don't get me wrong, I'm not at all against introducing a new
Under-Specified FEC Encoding ID, I just don't think it is appropriate to say
that it is restricted in any way to a particular class of FEC codes, e.g.,
LDPC codes.  What I'm suggesting instead is to define the FEC OTI (common
parts) and the formats of the FEC Payload ID(s) and the expected common
parts of the algorithms (for example, forming source blocks from a file),
etc. in the normal way for a new FEC Encoding ID without specifying what
specific class of FEC codes is the target.  Informationally, it is fine to
say that the design of the FEC Encoding ID is targeted for example for large
file delivery and LDPC codes, but to specify this does not seem correct.
Then, whether or not an FEC code can use this FEC Encoding ID is not defined
by the design philosophy behind the FEC code design, but instead by whether
or not the FEC code is practical to use with the defined FEC Encoding ID.
No reason to rule out using RS, LT, Raptor, regular LDPC, irregular LDPC,
Turbo, some new codes from being a particular instance of ANY
Under-Specified FEC Encoding ID.

> -----Original Message-----
> From: Vincent Roca [mailto:[email-masked]]
> Sent: Friday, July 29, 2005 5:10 AM
> To: Michael Luby
> Cc: Rmt@ietf. org
> Subject: Re: [Rmt] RE: Comments to draft-ietf-rmt-fec-bb-revised-00.txt
>
>
> Hello Mike/Mark,
>
>