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

[Igor Slepchin <[e-mail]>]

Vincent,

My apologies for a really late response and thanks for the detailed 
analysis.

I largely agree with your conclusions and the current n-algorithm is 
indeed operational. However, I still feel that it unnecessarily limits 
how the server can choose n, however lightly, and, since it's not really 
required for interop between the server and the client, I think it'd be 
nice to change the use of n-algorithm for Reed-Solomon to RECOMMENDED 
instead of the implied MUST. That is, the first paragraph in section 6.2 
could be rephrased to something like the following:

"The following algorithm, also called "n-algorithm", explains how to 
determine the actual number of encoding symbols for a given block. It is 
RECOMMENDED that the algorithm be used by the server to determine n and 
max_n; it MAY be used by the client to get an estimate of n. If the 
client uses the n-algorithm, it MUST be prepared to handle symbols with 
ESNs higher than the computed n, e.g. it can choose to simply drop them."

I guess the last sentence is not really necessary, it's what any robust 
implementation will do regardless of the algorithm used.

Also, it'd be nice to mention more explicitly that the use of the block 
partitioning algorithm is a MUST for FEC Encoding IDs 2 and 5 (it's 
already stated as a MAY for 129) rather than implying this within 
n-algorithm description.

Thank you,
Igor Slepchin



Vincent Roca wrote:
> 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.
> 
> 
> ------------------------------------------------------------------------
> 
> /**
> */
> 
> #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);
> 
> }
> 


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.


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