Subject: [Rmt] Hopefully final resolution of FLUTE-03 to be submitted on Monday, October 27, 2003

From: "Michael Luby" <[email-masked]>
Date: Wed, 29 Oct 2003 17:38:39 -0800

RMTers interested in FLUTE:

In response to Brian's email (see bottom of this email):

The reason this came up in the first place is that it was found by
implementors that they needed to receive potentially two packets to
determine the encoding symbol length, because if they were using the payload
length of data packets to determine the encoding symbol length and if the
last source symbol (which could be an encoding symbol) of the last source
block could be shorter then this would require reception of two packets to
accurately determine the encoding symbol length.

However, after looking at the FLUTE spec more carefully, the Encoding Symbol
Length and the File Length are both part of the FEC Object Transmission
Information (FEC OTI), and the FLUTE specification says that the FEC OTI
MUST be delivered in-band either in an FDT or using the EXT_FTI header
extension.  Thus, the implementors should have used the FEC OTI contained in
either the FDT or the EXT_FTI to determine the Encoding Symbol Length, and
not determine this from the length of the payloads in the data packets.
Thus, it is really immaterial whether the last source symbol of the last
source block of the file is shorter than the rest, it can be and it
shouldn't introduce any additional complications for implementors.  Since
the FLUTE specification currently says that the last source symbol of the
last source block doesn't have to be transmitted, I suggest we leave it that
way and everyone can be happy.  We should say that logically it is padded
out with zeroes to the length of a normal source symbol when an encoding
symbol is computed based on this source symbol in order for the sender and
receiver to agree on the meaning of the encoding symbol to avoid decoding
the wrong thing based on received encoding symbols that are computed based
on this source symbol.  Thus, we can agree that the last source symbol of
the last block of the file can be truncated if it is transmitted, but that
it is logically padded out with zeroes if any other encoding symbols are
computed based on it.

More generally:

I also think that we have resolved the only other remaining issue of the
algorithm for computing the source block structure based on the File Length,
the Encoding Symbol Length and the Maximum Source Block Length (in units of
source symbols).   I've included this as written up by Rod Walsh below
(based on what I suggested previously), except I fleshed it out a bit more.

-------------beginning of new section 5.1.2.1----------------------------

5.1.2.1 FEC Encoding IDs 0, 128, and 130

   FEC Encoding ID 0 is 'Compact No-Code FEC' (Fully-Specified) [8].
   FEC Encoding ID 128 is 'Small Block, Large Block and Expandable FEC'
   (Under-Specified) [5].  FEC Encoding ID 130 is 'Compact FEC'
   (Under-Specified) [8].  For these FEC Encoding IDs, the FEC Encoding
   ID specific format of EXT_FTI is defined as follows.

    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
                                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      General EXT_FTI format       |    Encoding Symbol Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 Maximum Source Block Length                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Encoding Symbol Length, 16 bits:

   Length of encoding symbols in bytes.

   All encoding symbols of a file MUST be equal to this length, with
   the optional exception of the last source symbol of the last source
   block (so that redundant padding is not mandatory in this last
   symbol -- although this last source symbol MUST be logically padded out
with
   zeroes when any other encoding symbol is computed based on this source
symbol
   to ensure the same interpretation of this encoding symbol value by the
sender
   and receiver).

   Maximum Source Block Length, 32 bits:

   The maximum number of source symbols in a source block.  Recall that
length of
   a source symbol is generally the same as the Encoding Symbol Length
except for
   possibly the last source symbol of the last source block.

   This EXT_FTI specification requires that an algorithm is known
   to both sender and receivers for determining the size of all source
   blocks within the file identified by the TOI (or within the FDT
   Instance identified by the TOI and the FDT Instance ID). The
   algorithm SHOULD be the same for all files using the same FEC
   Encoding ID within a session.

   The following algorithm is RECOMMENDED for all files:

   This algorithm computes a source block structure so that
   all source blocks are as close to being equal length as possible. A first
   number of source blocks each contain the same larger number of source
symbols,
   and the remaining second number of source blocks each contain the same
   smaller number of source symbols. The total number of source blocks (N),
   the first number of source blocks (I), the second number of source blocks
   (N-I), the larger number of source symbols (A_large) and the smaller
number
   of source symbols (A_small) are calculated thus,

      Inputs:
         B -- Maximum Source Block length, i.e., the maximum number of
source symbols in a source block.
         F -- File length in bytes
         E -- Encoding Symbol Length in bytes
      Output:
         N -- The number of source blocks the file is partitioned into
         The number and lengths of source symbols in each of the N source
blocks

      Algorithm:
      (a) The number of source symbols in the file is computed as T = F/E
rounded up to the nearest integer.
      (b) Each file is partitioned into N source blocks, where N=T/B
         rounded up to the nearest integer
      (c) The average length of a source block, A = T/N
         (this may be non-integer)
      (d) A_large = A rounded up to the nearest integer
         (it will always be the case that the value of A_large is at most B)
      (e) A_small = A rounded down to the nearest integer
         (if A is an integer A_small = A_large,
         and otherwise A_small = A_large - 1)
      (f) The fractional part of A, A_fraction = A - A_small
      (g) I = A_fraction * N
         (I is an integer between 0 and N-1)
      (h) Each of the first I source blocks consists of A_large source
symbols, each source symbol is E bytes in length.
          Each of the remaining N-I source blocks consist of A_small source
symbols,
            each source symbol is E bytes in length except
            that the last source symbol of the last source block
            is F-(((F-1)/E) rounded down to the nearest integer)*E bytes in
length.

----------------end of new section 5.1.2.1-------------

Probably the same changes need to be made to section 5.1.2.2, i.e., the
algorithm needs to be specified so that the receiver can determine the block
structure as soon as it knows the file length, the encoding symbol length
and the maximum number of source symbols per source block.  Since the source
block length also appears as part of the FEC Payload ID for FEC Encoding ID
129, it should also be stated that the source block length used for each
source block MUST adhere to the source block lengths computed by the
algorithm.

I've also attached a marked up version of FLUTE that shows a few places
where
"data symbols" should be changed to "source symbols" or "encoding symbols"
as appropriate, and "Source-Block-Length" changed to
"Maximum-Source-Block-Length", etc.

I think once the above is incorpated that FLUTE is good to go.
Mike

> -----Original Message-----
> From: Brian Adamson [mailto:[email-masked]]
> Sent: Wednesday, October 29, 2003 2:17 PM
> To: Michael Luby; [email-masked]; [email-masked]
> Cc: [email-masked]; [email-masked];
> [email-masked]; [email-masked];
> [email-masked]; [email-masked];
> [email-masked]; [email-masked]; Michael Luby
> Subject: RE: FLUTE-03 to be submitted on Monday, October 27, 2003
>
>
> I would assume that the "padding" being discussed does not have to be
> literal? ... For example, if the sender and receiver both assume
> virtual "ZERO" value padding for truncated source blocks or symbols,
> the actual padding need not be sent ...
>
> I have been following this exchange, trying to figure out what the
> conflict is ... I thought the FEC building block was left in general
> enough form and that instantiations could fill in the details as
> needed.  The FLUTE EXT_FTI provides the maximum symbol length value
> (i.e. corresponds to the maximum length of source symbols and the
> actual length of encoding symbols).
>
> So I don't understand why the padding is necessary if the EXT_FTI
> information is provided one way or another.  Agreeing on the
> segmentation algorithm given this information is necessary and I do
> understand for ALC that avoiding short block sizes (i.e the tail of a
> file) helps statistically ... but again,I don't see why the actual
> padding needs to be transmitted, particularly if only encoding
> symbols are transmitted ...
>
>
>
> --
> Brian
> __________________________________
> Brian Adamson
> <http://manimac.itd.nrl.navy.mil>
> <mailto:[email-masked]>
>