Re: [Rmt] Last Call: draft-ietf-rmt-bb-fec-rs (Reed-Solomon Forward Error Correction (FEC) Schemes) to Experimental RFC

[Vincent Roca <[e-mail]>]

Dear Igor,

> I don't think the proposed change completely solves the problem, it only
> lets us pass the sanity check.

The proposed change _does correct the big mistake_ that you identified
(thanks a lot!), i.e. the fact there was no room to produce parity symbols
when following the indications given in section 6.1, which was a little bit
annoying ;-)

> As I briefly mentioned in my previous email, taking the two floors in
> the n-algorithm will not produce the required number of repair symbols
> in some situations.

Let's analyze this point in detail:

1- It's perfectly normal that, because of rounding (be it with floor or ceil),
the number of repair symbols produced differ from the target one, or said
differently, that the actual code rate differ from the target one. We were
aware of that since the beginning.

2- Is the current n-algorithm the best one, i.e. the one that guaranties
the best match? We studied the question and the answer is NO. We can have
a better match by using:
	max_n = ceil(B / rate)		// proposed change
instead of:
	max_n = floor(B / rate)		// initial version
A detailed analysis is provided below.

The same remark applies to the LDPC I-D, section 5.4 too!


> [...] However, since knowing the rate is not required for
> decoding of Reed-Solomon codes, knowing the exact number of repair
> symbols is not really required for decoding either. I understand that
> having a reasonable estimate for that number may make memory management
> on some implementations easier, but I don't think that knowing the
> precise value is critical. For example, if the server sets max_n to
> the maximum number of encoding symbols generated for any of the source
> blocks, it gives the client a reasonable estimate for pre-allocating its
> memory structures. The estimate may be off (on the plus side) by up to 2
> encoding symbols for A_small source blocks, but that doesn't sound too
> bad for me.

You're right, with RS codes, knowing the exact n value of any source block
is not mandatory, and a reasonable over-estimate can be sufficient. But:

- knowing the actual "n" value at a receiver is rather simple;

- we don't say that the receiver MUST calculate it, it's optional. If he
  wants to reserve room for 255 symbols (if m==8), he can;

- the same algorithm can be used in other FEC codes where knowing "n" is
  mandatory (LDPC-staircase/triangle being one of them). A "cut-and-paste"
  of this section is easy (and that's what we did).


To summarize, we suggest:

- to update the n-algorithm section with the above change (i.e. ceil instead
  of floor in the max_n formula) in both the RS and LDPC I-Ds.

- as a result, the number of repair symbols produced will better match the
  target rate, with a different distribution (see the histograms below):

  * with ceil (new version): n is in ]k/rate -1; k/rate+1] and most of the
    time we produce fewer (up to 1, included) repair symbols than expected,
    sometimes more (but less than 1).

  * with floor (old version): n is in ]k/rate -2; k/rate] and we often produce
    fewer (up to almost 2) repair symbols.

  It does not seem to raise any issue (but we haven't yet updated our
  respective FLUTE/ALC tools).

Thanks for the comment that led us to give a thought to this point once
again.


  The authors



Why is ceil() better than floor() in max_n calculation?
-------------------------------------------------------

Here are some results, produced with the attached C program that
tests all the code rates in the range [0.00001; 1.0] (with a 0.00001
increment), and for each code rate, all the possible k values in [1; B].
It then computes k/rate - n, i.e. the difference between the target
number of repair symbols (floating point value) and the actual number
(integer). These values are then analyzed with a descriptive statistics
tool:
	http://planete.inrialpes.fr/people/roca/descr_stats/

We see that in all cases there is an interval of 2 symbols between
the number of parity symbols that should be produced (k/rate) and
the number actually produced (n-algo). In one case n is below the
target (if floor is used), in the other case, it straddles the
target (if ceil is used instead). In that latter case, most of the
time the n-algo produces fewer repair symbols, but sometimes it produces
more.

New version:
 ~/work/descr_stats/descr_stats 1 results_with_ceil.txt
        ------------------------------------------------------
        nb of samples = 12700127
        mean = 0.256850			<=== NB: important point here
        median = 0.260329
        variance = 0.129964
        standard deviation = 0.360505
        range = 1.995841         min = -1.000000  max = 0.995841
        confidence interval around mean 0.256850:
                90: ± 0.584438
                95: ± 0.665684
                99: ± 0.888069
        confidence interval around median 0.260329:
                90: ± 0.583622
                95: ± 0.665245
                99: ± 0.891548
        ------------------------------------------------------

Old version:
$ ~/work/descr_stats/descr_stats 1 results_with_floor.txt
        ------------------------------------------------------
        nb of samples = 12700127
        mean = 0.761280			<=== NB: important point here
        median = 0.757799
        variance = 0.139688
        standard deviation = 0.373748
        range = 1.991292         min = 0.000000  max = 1.991292
        confidence interval around mean 0.761280:
                90: ± 0.611945
                95: ± 0.694886
                99: ± 0.888559
        confidence interval around median 0.757799:
                90: ± 0.611284
                95: ± 0.694555
                99: ± 0.892040
        ------------------------------------------------------

The histograms (PDF) are available here:

New version:
http://planete.inrialpes.fr/~roca/doc/results_with_ceil_histogram.pdf

Old version:
http://planete.inrialpes.fr/~roca/doc/results_with_floor_histogram.pdf

Attached is the (quick and dirty) C program that has been used to produce them
if somebody wants to check by himself.

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