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
tfrc_resolution-error_for_smallest_p.png
Description: PNG image
