With the help of some test and verification programs, I have reverse-engineered how the TFRC lookup table is generated. The results of this were added as detailed documentation to the tfrc_equation.c file. The work also has made possible a few improvements which are included in this patch set. A detailed analysis plus the test programs are online on http://www.erg.abdn.ac.uk/users/gerrit/dccp/tfrc_documentation/ Patch 1: This adds the documentation to tfrc_equation.c and * fixes a small bug in the reverse-lookup code which incurred an average error of 1.12% (the bug was due to a missing '+ 1' in inverting the indices; this was confirmed using one of the online test programs) * simplifies BUG conditions - if RTT = 0, the maximum = ~0U is now returned * adds warnings in both functions when p goes below the resolution of the table (the smallest possible value is 0.0001) Patch 2: Avoid masking resolution errors in table lookup The lookup table can not resolve values of p smaller than 0.0001. I have checked the error that results by substituting other values and it is not a good idea. Attached is the calculation of the error when substituting f(0.0001) for values of p smaller than 0.0001. Both axes are logarithmic - the increase in error is thus exponential. Warning messages to avoid `resolution underflow' have already been introduced in the first patch; this patch continues this work by making all error handling local to the TFRC library. If the warning messages accumulate, it is an indication that the lookup table does not have suitable proportions and a larger one should be generated. Patch 3: Use binary search in reverse lookup This speeds up reverse lookups, exploiting the following feature: The lookup table is sorted (since i < j => f(i) < f(j)). Currently, if every interval is equally likely, the average number of iterations to reverse-lookup is 250. With bin search this goes down to 8 or 9 (log2(500)), which is almost 30 times faster. I have verified this also using tests. Gerrit
Attachment:
tfrc_resolution-error_for_smallest_p.png
Description: PNG image
