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

From: The IESG <[email-masked]>
Date: Thu, 20 Sep 2007 11:22:28 -0400

The IESG has received a request from the Reliable Multicast Transport WG
(rmt) to consider the following document:

- 'Reed-Solomon Forward Error Correction (FEC) Schemes '
   <draft-ietf-rmt-bb-fec-rs-03.txt> as an Experimental RFC

The IESG plans to make a decision in the next few weeks, and solicits
final comments on this action.  Please send substantive comments to the
[email-masked] mailing lists by 2007-10-04. Exceptionally, 
comments may be sent to [email-masked] instead. In either case, please 
retain the beginning of the Subject line to allow automated sorting.

The file can be obtained via
http://www.ietf.org/internet-drafts/draft-ietf-rmt-bb-fec-rs-03.txt

IESG discussion can be tracked via
https://datatracker.ietf.org/public/pidtracker.cgi?command=view_id&dTag=14454&rfc_flag=0

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

---

From: Igor Slepchin <[email-masked]>
Date: Fri, 21 Sep 2007 16:18:38 -0400

I realize Last Call is not the best time to bring up issues with a draft 
but here it goes...

As far as I can tell, the n-algorithm described in section 6.2 of 
draft-ietf-rmt-bb-fec-rs-03 is badly broken. Let's go through the steps:

1. Maximum source block length is computed as

B = min(max1_B, max2_B) where max1_B = 2^^m - 1 and max2_B is an 
additional limitation imposed by the codec that may or may not be there. 
Let's assume it's not there so B = 2^^m - 1.

2. Maximum number of encoding symbols for any block is defined by 
n-algorithm as

max_n = floor(B / rate). Given that rate is defined as k/n, its value is 
<= 1. Hence, max_n is >= B, i.e., max_n >= 2^^m - 1

3. Now, the next step of n-algorithm is:

if (max_n > 2^^m - 1) then return an error ("invalid code rate");

So n-algorithm will pretty much _always_ returns an error for 
non-trivial code rates in this scenario, even if the block partitioning 
algorithm produced source blocks of the length that allows generating 
the required number of repair symbols.

One way to fix step 3 is to redefine B as the maximum length of all 
source blocks _produced by the block partitioning algorithm_, i.e., as 
A_large. But even then the resulting number of repair symbols may be 
less than required by the input code rate due to the two "floor" 
operations. Am I missing anything?

That said, I don't think I understand the point of getting floor(B / 
rate) and then floor(k * max_n / B) in the first place. Why not just say 
that n = ceil(k/rate) and return an error if n turns out to be larger 
than 2^^m-1 for any of the source blocks? As mentioned in the draft 
itself, client does not need to know n so the value of max_n is 
irrelevant for the decoding operation. If we really want to give the 
client some rough idea of n, one could set max_n to ceil(A_large/rate).

Thank you,
Igor Slepchin

The IESG wrote:
> <...>

CONFIDENTIALITY NOTICE:  This email message and any attachments contain proprietary and privileged information of Roundbox, Inc., which are provided for the sole and confidential use of the intended recipients.  Any review, use, disclosure or distribution of this information is restricted and must comply with the nondisclosure agreement between Roundbox, Inc. and you (or your company).  All other uses are prohibited.  If you are not an intended recipient, please contact the sender by reply email and promptly delete and otherwise destroy all copies of the message and its attachments.

---

From: Vincent Roca <[email-masked]>
Date: Tue, 25 Sep 2007 10:36:56 +0200

Dear Igor,

Thanks a lot for the issue you noticed!

There's indeed an error in section 6.1, since room must of course be reserved
for the future parity symbols when defining the maximum source block length, B.
So we suggest to replace current section 6.1. Here is the new text (where the
only change is the definition of max1_B):

---------
6.1.  Determining the Maximum Source Block Length (B)

   The finite field size parameter, m, defines the number of non zero
   elements in this field which is equal to: q - 1 = 2^^m - 1.  Note
   that q - 1 is also the theoretical maximum number of encoding symbols
   that can be produced for a source block.  For instance, when m = 8
<NEW TEXT>
   (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols.

   Given the target FEC code rate (e.g. provided by the user when
   starting a FLUTE sending application), the sender calculates:

      max1_B = floor((2^^m - 1) * rate)

   This max1_B value leaves enough room for the sender to produce the
   desired number of parity symbols.
</NEW TEXT>

   Additionally, a codec MAY impose other limitations on the maximum
   block size.  Yet it is not expected that such limits exist when using
   the default m = 8 value.  This decision MUST be clarified at
   implementation time, when the target use case is known.  This results
   in a max2_B limitation.

   Then, B is given by:

      B = min(max1_B, max2_B)

   Note that this calculation is only required at the coder, since the B
   parameter is communicated to the decoder through the FEC OTI.
----------

Nothing else needs to be changed. The following check, in section 6.2:
        if (max_n > 2^^m - 1) then return an error ("invalid code rate");
is a sanity check that should never raise any problem if max1_B is initialized
as recommended.

Concerning the need to calculate max_n first and then n, instead of calculating
just n = ceil(k/rate) (what you suggested), the motivation is that the _target_
rate parameter (a floating point value) is not communicated to the receiver.
Instead the receiver knows B and max_n, i.e. a _rounded_ rate: B/max_n. That's
enough.

Best regards,

   The authors

Igor Slepchin wrote:
> CONFIDENTIALITY NOTICE:  This email message and any attachments contain
> proprietary and privileged information of Roundbox, Inc., which are
> provided for the sole and confidential use of the intended recipients. 
> Any review, use, disclosure or distribution of this information is
> restricted and must comply with the nondisclosure agreement between
> Roundbox, Inc. and you (or your company).  All other uses are
> prohibited.  If you are not an intended recipient, please contact the
> sender by reply email and promptly delete and otherwise destroy all
> copies of the message and its attachments.
> 
>

---

From: Igor Slepchin <[email-masked]>
Date: Tue, 25 Sep 2007 23:06:37 -0400

Vincent,

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

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. For example, let's say the code rate is 0.9, m=8,
and B=229 (e.g., max1_B=floor(255*0.9)=229, or max2_B=229 for whatever
reason). Let's assume that the block partitioning algorithm produced a
source block of 180 symbols, i.e., k=180. Then we have:

max_n=floor(B/rate)=floor(229/0.9)=254.
n=floor(k * max_n / B)=floor(180*254/229)=199.

Thus, the n-algorithm generated 199-180=19 repair symbols. However, the
requested code rate requires 180/0.9=200 encoding symbols, i.e., 20
repair symbols. So the n-algorithm causes us to generate fewer repair
symbols than requested by the code rate.

More comments below.

> Instead the receiver knows B and max_n, i.e. a _rounded_ rate: B/max_n. That's

Right, I understand that we cannot communicate the floating point code
rate to the client. 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.

That said, I've nothing against determining the exact number of encoding
symbols for each source block on the client based on just max_n and B, I
just could not come up with a way to do that without running into the
issue I described above.

Thank you,
Igor Slepchin

---

From: Vincent Roca <[email-masked]>
Date: Thu, 27 Sep 2007 15:16:30 +0200

Dear Igor,

> 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 ;-)

> 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

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.
/**
*/

#include <stdio.h>
#include <math.h>

#define min(a,b)  ((a) <= (b) ? (a) : (b))

int main ()
{
	int	m = 8;		/* INPUT */
	int	max1_B;
	int	max2_B;		/* INPUT */
	int	B;
	int	k;
	int	n;
	double	rate;		/* INPUT */
	int	max_n;
	double	diff_val;
	double	diff_thresh = 0.99;	/* theshold above which we print a warning */
	bool	verbose = false;	/* false: no warning, true: all warnings */
	bool	output_to_file = true;
	FILE	*ofp;

	max2_B = ((int)pow(2, m) - 1);	/* no further restriction */
#if 0
	max2_B = 50;			/* stricly restricted */
#endif

	if (output_to_file && (ofp = fopen("results_with_floor.txt", "w")) < 0) {
		perror("open");
		return(-1);
	}

	for (rate = 0.00001; rate <= 1.0; rate += 0.00001){
		max1_B = (int)floor((pow(2, m) - 1) * rate);
		B = min(max1_B, max2_B);
		for (k = 1; k <= B; k++) {
			/* use floor ! */
			max_n = (int)floor(B / rate);
			if (max_n > (int)pow(2, m) - 1) {
				printf("ERROR: invalid code rate");
				return(-1);
			}
			n = (int)floor(k * max_n / B);
			if (n > (int)pow(2, m) - 1) {
				printf("ERROR: invalid code rate");
				return(-1);
			}
			/* how far are the actual nb of parity symbols value from the target? */
			diff_val = (double)k / (double)rate - (double)n;
			if (verbose) {
				if (fabs(diff_val) >= diff_thresh) {
					printf("WARNING: B=%d, k=%d, rate=%lf, actual_rate=%lf, n=%d, k/rate-n=%lf\n",
						B, k, rate, (double)k/(double)n, n, diff_val);
				}
			}
			if (output_to_file) {
				fprintf(ofp, "%lf\n", diff_val);
			}
		}
	}
	if (output_to_file) {
		fclose(ofp);
	}

	if (output_to_file && (ofp = fopen("results_with_ceil.txt", "w")) < 0) {
		perror("open");
		return(-1);
	}

	for (rate = 0.00001; rate <= 1.0; rate += 0.00001){
		max1_B = (int)floor((pow(2, m) - 1) * rate);
		B = min(max1_B, max2_B);
		for (k = 1; k <= B; k++) {
			/* use ceil ! */
			max_n = (int)ceil(B / rate);
			if (max_n > (int)pow(2, m) - 1) {
				printf("ERROR: invalid code rate");
				return(-1);
			}
			n = (int)floor(k * max_n / B);
			if (n > (int)pow(2, m) - 1) {
				printf("ERROR: invalid code rate");
				return(-1);
			}
			/* how far are the actual nb of parity symbols value from the target? */
			diff_val = (double)k / (double)rate - (double)n;
			if (verbose) {
				if (fabs(diff_val) >= diff_thresh) {
					printf("WARNING: B=%d, k=%d, rate=%lf, actual_rate=%lf, n=%d, k/rate-n=%lf\n",
						B, k, rate, (double)k/(double)n, n, diff_val);
				}
			}
			if (output_to_file) {
				fprintf(ofp, "%lf\n", diff_val);
			}
		}
	}
	if (output_to_file) {
		fclose(ofp);
	}
	return(0);

}