Skip to content

: TFRC documentation and updates

Gerrit Renker dccp 1 version New

Get series with b4
b4 am 200611271849.44310@strip-the-willow

Versions newest first

  1. v1 Latest3 patches 0 repliesNew

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/3: Document boundaries and limits of TFRC lookup tablenet/dccp/ccids/lib/tfrc_equation.c+100 -720 replies
2/3: Avoid masking of low-resolution errorsnet/dccp/ccids/ccid3.c net/dccp/ccids/ccid3.h+4 -160 replies
3/3: Binary search for reverse TFRC lookupnet/dccp/ccids/lib/tfrc_equation.c+22 -140 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 0/3]: TFRC documentation and updates

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