aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorGerrit Renker <gerrit@erg.abdn.ac.uk>2006-12-03 11:51:29 -0500
committerArnaldo Carvalho de Melo <acme@mandriva.com>2006-12-03 11:51:29 -0500
commit50ab46c790a3408c441ba4c2faa9555cacc20028 (patch)
treec1d1a93375908ad66fb6599532351bfcb3785269 /net
parent26af3072b035daadf34a99d02510f0ff98f41f90 (diff)
[DCCP] tfrc: Document boundaries and limits of the TFRC lookup table
This adds documentation for the TCP Reno throughput equation which is at the heart of the TFRC sending rate / loss rate calculations. It spells out precisely how the values were determined and what they mean. The equations were derived through reverse engineering and found to be fully accurate (verified using test programs). This patch does not change any code. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz> Signed-off-by: Arnaldo Carvalho de Melo <acme@mandriva.com>
Diffstat (limited to 'net')
-rw-r--r--net/dccp/ccids/lib/tfrc_equation.c144
1 files changed, 88 insertions, 56 deletions
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
index 2601012383fb..57665e979308 100644
--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -18,10 +18,76 @@
18#include "tfrc.h" 18#include "tfrc.h"
19 19
20#define TFRC_CALC_X_ARRSIZE 500 20#define TFRC_CALC_X_ARRSIZE 500
21#define TFRC_CALC_X_SPLIT 50000 /* 0.05 * 1000000, details below */
21 22
22#define TFRC_CALC_X_SPLIT 50000 23/*
23/* equivalent to 0.05 */ 24 TFRC TCP Reno Throughput Equation Lookup Table for f(p)
24 25
26 The following two-column lookup table implements a part of the TCP throughput
27 equation from [RFC 3448, sec. 3.1]:
28
29 s
30 X_calc = --------------------------------------------------------------
31 R * sqrt(2*b*p/3) + (3 * t_RTO * sqrt(3*b*p/8) * (p + 32*p^3))
32
33 Where:
34 X is the transmit rate in bytes/second
35 s is the packet size in bytes
36 R is the round trip time in seconds
37 p is the loss event rate, between 0 and 1.0, of the number of loss
38 events as a fraction of the number of packets transmitted
39 t_RTO is the TCP retransmission timeout value in seconds
40 b is the number of packets acknowledged by a single TCP ACK
41
42 We can assume that b = 1 and t_RTO is 4 * R. The equation now becomes:
43
44 s
45 X_calc = -------------------------------------------------------
46 R * sqrt(p*2/3) + (12 * R * sqrt(p*3/8) * (p + 32*p^3))
47
48 which we can break down into:
49
50 s
51 X_calc = ---------
52 R * f(p)
53
54 where f(p) is given for 0 < p <= 1 by:
55
56 f(p) = sqrt(2*p/3) + 12 * sqrt(3*p/8) * (p + 32*p^3)
57
58 Since this is kernel code, floating-point arithmetic is avoided in favour of
59 integer arithmetic. This means that nearly all fractional parameters are
60 scaled by 1000000:
61 * the parameters p and R
62 * the return result f(p)
63 The lookup table therefore actually tabulates the following function g(q):
64
65 g(q) = 1000000 * f(q/1000000)
66
67 Hence, when p <= 1, q must be less than or equal to 1000000. To achieve finer
68 granularity for the practically more relevant case of small values of p (up to
69 5%), the second column is used; the first one ranges up to 100%. This split
70 corresponds to the value of q = TFRC_CALC_X_SPLIT. At the same time this also
71 determines the smallest resolution.
72
73 The entire table is generated by:
74 for(i=0; i < TFRC_CALC_X_ARRSIZE; i++) {
75 lookup[i][0] = g((i+1) * 1000000/TFRC_CALC_X_ARRSIZE);
76 lookup[i][1] = g((i+1) * TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE);
77 }
78
79 With the given configuration, we have, with M = TFRC_CALC_X_ARRSIZE-1,
80 lookup[0][0] = g(1000000/(M+1)) = 1000000 * f(0.2%)
81 lookup[M][0] = g(1000000) = 1000000 * f(100%)
82 lookup[0][1] = g(TFRC_CALC_X_SPLIT/(M+1)) = 1000000 * f(0.01%)
83 lookup[M][1] = g(TFRC_CALC_X_SPLIT) = 1000000 * f(5%)
84
85 In summary, the two columns represent f(p) for the following ranges:
86 * The first column is for 0.002 <= p <= 1.0
87 * The second column is for 0.0001 <= p <= 0.05
88 Where the columns overlap, the second (finer-grained) is given preference,
89 i.e. the first column is used only for p >= 0.05.
90 */
25static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = { 91static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
26 { 37172, 8172 }, 92 { 37172, 8172 },
27 { 53499, 11567 }, 93 { 53499, 11567 },
@@ -525,62 +591,26 @@ static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
525 { 243315981, 271305 } 591 { 243315981, 271305 }
526}; 592};
527 593
528/* Calculate the send rate as per section 3.1 of RFC3448 594/**
529 595 * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448
530Returns send rate in bytes per second 596 *
531 597 * @s: packet size in bytes
532Integer maths and lookups are used as not allowed floating point in kernel 598 * @R: RTT scaled by 1000000 (i.e., microseconds)
533 599 * @p: loss ratio estimate scaled by 1000000
534The function for Xcalc as per section 3.1 of RFC3448 is: 600 * Returns X_calc in bytes per second (not scaled).
535 601 *
536X = s 602 * Note: DO NOT alter this code unless you run test cases against it,
537 ------------------------------------------------------------- 603 * as the code has been optimized to stop underflow/overflow.
538 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2))) 604 */
539
540where
541X is the trasmit rate in bytes/second
542s is the packet size in bytes
543R is the round trip time in seconds
544p is the loss event rate, between 0 and 1.0, of the number of loss events
545 as a fraction of the number of packets transmitted
546t_RTO is the TCP retransmission timeout value in seconds
547b is the number of packets acknowledged by a single TCP acknowledgement
548
549we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
550
551X = s
552 -----------------------------------------------------------------------
553 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
554
555
556which we can break down into:
557
558X = s
559 --------
560 R * f(p)
561
562where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
563
564Function parameters:
565s - bytes
566R - RTT in usecs
567p - loss rate (decimal fraction multiplied by 1,000,000)
568
569Returns Xcalc in bytes per second
570
571DON'T alter this code unless you run test cases against it as the code
572has been manipulated to stop underflow/overlow.
573
574*/
575u32 tfrc_calc_x(u16 s, u32 R, u32 p) 605u32 tfrc_calc_x(u16 s, u32 R, u32 p)
576{ 606{
577 int index; 607 int index;
578 u32 f; 608 u32 f;
579 u64 tmp1, tmp2; 609 u64 tmp1, tmp2;
580 610
581 if (p < TFRC_CALC_X_SPLIT) 611 if (p < TFRC_CALC_X_SPLIT) /* 0 <= p < 0.05 */
582 index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1; 612 index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
583 else 613 else /* 0.05 <= p <= 1.00 */
584 index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1; 614 index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
585 615
586 if (index < 0) 616 if (index < 0)
@@ -599,11 +629,13 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
599 else 629 else
600 f = tfrc_calc_x_lookup[index][1]; 630 f = tfrc_calc_x_lookup[index][1];
601 631
632 /* The following computes X = s/(R*f(p)) in bytes per second. Since f(p)
633 * and R are both scaled by 1000000, we need to multiply by 1000000^2.
634 * ==> DO NOT alter this unless you test against overflow on 32 bit */
602 tmp1 = ((u64)s * 100000000); 635 tmp1 = ((u64)s * 100000000);
603 tmp2 = ((u64)R * (u64)f); 636 tmp2 = ((u64)R * (u64)f);
604 do_div(tmp2, 10000); 637 do_div(tmp2, 10000);
605 do_div(tmp1, tmp2); 638 do_div(tmp1, tmp2);
606 /* Don't alter above math unless you test due to overflow on 32 bit */
607 639
608 return (u32)tmp1; 640 return (u32)tmp1;
609} 641}
@@ -611,10 +643,10 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
611EXPORT_SYMBOL_GPL(tfrc_calc_x); 643EXPORT_SYMBOL_GPL(tfrc_calc_x);
612 644
613/* 645/*
614 * args: fvalue - function value to match 646 * tfrc_calc_x_reverse_lookup - try to find p given f(p)
615 * returns: p closest to that value
616 * 647 *
617 * both fvalue and p are multiplied by 1,000,000 to use ints 648 * @fvalue: function value to match, scaled by 1000000
649 * Returns closest match for p, also scaled by 1000000
618 */ 650 */
619u32 tfrc_calc_x_reverse_lookup(u32 fvalue) 651u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
620{ 652{