tfrc_equation.c

linux 内核源代码

/*
 *  net/dccp/ccids/lib/tfrc_equation.c
 *
 *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
 *  Copyright (c) 2005 Ian McDonald <[e-mail]>
 *  Copyright (c) 2005 Arnaldo Carvalho de Melo <[e-mail]>
 *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 */

#include <linux/module.h>
#include "../../dccp.h"
#include "tfrc.h"

#define TFRC_CALC_X_ARRSIZE 500
#define TFRC_CALC_X_SPLIT   50000	/* 0.05 * 1000000, details below */
#define TFRC_SMALLEST_P	    (TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE)

/*
  TFRC TCP Reno Throughput Equation Lookup Table for f(p)

  The following two-column lookup table implements a part of the TCP throughput
  equation from [RFC 3448, sec. 3.1]:

				     s
  X_calc  =  --------------------------------------------------------------
	     R * sqrt(2*b*p/3) + (3 * t_RTO * sqrt(3*b*p/8) * (p + 32*p^3))

  Where:
	X      is the transmit rate in bytes/second
	s      is the packet size in bytes
	R      is the round trip time in seconds
	p      is the loss event rate, between 0 and 1.0, of the number of loss
		      events as a fraction of the number of packets transmitted
	t_RTO  is the TCP retransmission timeout value in seconds
	b      is the number of packets acknowledged by a single TCP ACK

  We can assume that b = 1 and t_RTO is 4 * R. The equation now becomes:

				     s
  X_calc  =  -------------------------------------------------------
	     R * sqrt(p*2/3) + (12 * R * sqrt(p*3/8) * (p + 32*p^3))

  which we can break down into:

		      s
	X_calc  =  ---------
		    R * f(p)

  where f(p) is given for 0 < p <= 1 by:

	f(p)  =  sqrt(2*p/3) + 12 * sqrt(3*p/8) *  (p + 32*p^3)

  Since this is kernel code, floating-point arithmetic is avoided in favour of
  integer arithmetic. This means that nearly all fractional parameters are
  scaled by 1000000:
    * the parameters p and R
    * the return result f(p)
  The lookup table therefore actually tabulates the following function g(q):

	g(q)  =  1000000 * f(q/1000000)

  Hence, when p <= 1, q must be less than or equal to 1000000. To achieve finer
  granularity for the practically more relevant case of small values of p (up to
  5%), the second column is used; the first one ranges up to 100%.  This split
  corresponds to the value of q = TFRC_CALC_X_SPLIT. At the same time this also
  determines the smallest resolution possible with this lookup table:

    TFRC_SMALLEST_P   =  TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE

  The entire table is generated by:
    for(i=0; i < TFRC_CALC_X_ARRSIZE; i++) {
	lookup[i][0]  =  g((i+1) * 1000000/TFRC_CALC_X_ARRSIZE);
	lookup[i][1]  =  g((i+1) * TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE);
    }

  With the given configuration, we have, with M = TFRC_CALC_X_ARRSIZE-1,
    lookup[0][0]  =  g(1000000/(M+1)) 		 =  1000000 * f(0.2%)
    lookup[M][0]  =  g(1000000)			 =  1000000 * f(100%)
    lookup[0][1]  =  g(TFRC_SMALLEST_P)		  = 1000000 * f(0.01%)
    lookup[M][1]  =  g(TFRC_CALC_X_SPLIT)	 =  1000000 * f(5%)

  In summary, the two columns represent f(p) for the following ranges:
    * The first column is for   0.002  <= p <= 1.0
    * The second column is for  0.0001 <= p <= 0.05
  Where the columns overlap, the second (finer-grained) is given preference,
  i.e. the first column is used only for p >= 0.05.
 */
static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
	{     37172,   8172 },
	{     53499,  11567 },
	{     66664,  14180 },
	{     78298,  16388 },
	{     89021,  18339 },
	{     99147,  20108 },
	{    108858,  21738 },
	{    118273,  23260 },
	{    127474,  24693 },
	{    136520,  26052 },
	{    145456,  27348 },
	{    154316,  28589 },
	{    163130,  29783 },
	{    171919,  30935 },
	{    180704,  32049 },
	{    189502,  33130 },
	{    198328,  34180 },
	{    207194,  35202 },
	{    216114,  36198 },
	{    225097,  37172 },
	{    234153,  38123 },
	{    243294,  39055 },
	{    252527,  39968 },
	{    261861,  40864 },
	{    271305,  41743 },
	{    280866,  42607 },
	{    290553,  43457 },
	{    300372,  44293 },
	{    310333,  45117 },
	{    320441,  45929 },
	{    330705,  46729 },
	{    341131,  47518 },
	{    351728,  48297 },
	{    362501,  49066 },
	{    373460,  49826 },
	{    384609,  50577 },
	{    395958,  51320 },
	{    407513,  52054 },
	{    419281,  52780 },
	{    431270,  53499 },
	{    443487,  54211 },
	{    455940,  54916 },
	{    468635,  55614 },
	{    481581,  56306 },
	{    494785,  56991 },
	{    508254,  57671 },
	{    521996,  58345 },
	{    536019,  59014 },
	{    550331,  59677 },
	{    564939,  60335 },
	{    579851,  60988 },
	{    595075,  61636 },
	{    610619,  62279 },
	{    626491,  62918 },
	{    642700,  63553 },
	{    659253,  64183 },
	{    676158,  64809 },
	{    693424,  65431 },
	{    711060,  66050 },
	{    729073,  66664 },
	{    747472,  67275 },
	{    766266,  67882 },
	{    785464,  68486 },
	{    805073,  69087 },
	{    825103,  69684 },
	{    845562,  70278 },
	{    866460,  70868 },
	{    887805,  71456 },
	{    909606,  72041 },
	{    931873,  72623 },
	{    954614,  73202 },
	{    977839,  73778 },
	{   1001557,  74352 },
	{   1025777,  74923 },
	{   1050508,  75492 },
	{   1075761,  76058 },
	{   1101544,  76621 },
	{   1127867,  77183 },
	{   1154739,  77741 },
	{   1182172,  78298 },
	{   1210173,  78852 },
	{   1238753,  79405 },
	{   1267922,  79955 },
	{   1297689,  80503 },
	{   1328066,  81049 },
	{   1359060,  81593 },
	{   1390684,  82135 },
	{   1422947,  82675 },
	{   1455859,  83213 },
	{   1489430,  83750 },
	{   1523671,  84284 },
	{   1558593,  84817 },
	{   1594205,  85348 },
	{   1630518,  85878 },
	{   1667543,  86406 },
	{   1705290,  86932 },
	{   1743770,  87457 },
	{   1782994,  87980 },
	{   1822973,  88501 },
	{   1863717,  89021 },
	{   1905237,  89540 },
	{   1947545,  90057 },
	{   1990650,  90573 },
	{   2034566,  91087 },
	{   2079301,  91600 },
	{   2124869,  92111 },
	{   2171279,  92622 },
	{   2218543,  93131 },
	{   2266673,  93639 },
	{   2315680,  94145 },
	{   2365575,  94650 },
	{   2416371,  95154 },
	{   2468077,  95657 },
	{   2520707,  96159 },
	{   2574271,  96660 },
	{   2628782,  97159 },
	{   2684250,  97658 },
	{   2740689,  98155 },
	{   2798110,  98651 },
	{   2856524,  99147 },
	{   2915944,  99641 },
	{   2976382, 100134 },
	{   3037850, 100626 },
	{   3100360, 101117 },
	{   3163924, 101608 },
	{   3228554, 102097 },
	{   3294263, 102586 },
	{   3361063, 103073 },
	{   3428966, 103560 },
	{   3497984, 104045 },
	{   3568131, 104530 },
	{   3639419, 105014 },
	{   3711860, 105498 },
	{   3785467, 105980 },
	{   3860253, 106462 },
	{   3936229, 106942 },
	{   4013410, 107422 },
	{   4091808, 107902 },
	{   4171435, 108380 },
	{   4252306, 108858 },
	{   4334431, 109335 },
	{   4417825, 109811 },
	{   4502501, 110287 },
	{   4588472, 110762 },
	{   4675750, 111236 },
	{   4764349, 111709 },
	{   4854283, 112182 },
	{   4945564, 112654 },
	{   5038206, 113126 },
	{   5132223, 113597 },
	{   5227627, 114067 },
	{   5324432, 114537 },
	{   5422652, 115006 },
	{   5522299, 115474 },
	{   5623389, 115942 },
	{   5725934, 116409 },
	{   5829948, 116876 },
	{   5935446, 117342 },
	{   6042439, 117808 },
	{   6150943, 118273 },
	{   6260972, 118738 },
	{   6372538, 119202 },
	{   6485657, 119665 },
	{   6600342, 120128 },
	{   6716607, 120591 },
	{   6834467, 121053 },
	{   6953935, 121514 },
	{   7075025, 121976 },
	{   7197752, 122436 },
	{   7322131, 122896 },
	{   7448175, 123356 },
	{   7575898, 123815 },
	{   7705316, 124274 },
	{   7836442, 124733 },
	{   7969291, 125191 },
	{   8103877, 125648 },
	{   8240216, 126105 },
	{   8378321, 126562 },
	{   8518208, 127018 },
	{   8659890, 127474 },
	{   8803384, 127930 },
	{   8948702, 128385 },
	{   9095861, 128840 },
	{   9244875, 129294 },
	{   9395760, 129748 },
	{   9548529, 130202 },
	{   9703198, 130655 },
	{   9859782, 131108 },
	{  10018296, 131561 },
	{  10178755, 132014 },
	{  10341174, 132466 },
	{  10505569, 132917 },
	{  10671954, 133369 },
	{  10840345, 133820 },
	{  11010757, 134271 },
	{  11183206, 134721 },
	{  11357706, 135171 },
	{  11534274, 135621 },
	{  11712924, 136071 },
	{  11893673, 136520 },
	{  12076536, 136969 },
	{  12261527, 137418 },
	{  12448664, 137867 },
	{  12637961, 138315 },
	{  12829435, 138763 },
	{  13023101, 139211 },
	{  13218974, 139658 },
	{  13417071, 140106 },
	{  13617407, 140553 },
	{  13819999, 140999 },
	{  14024862, 141446 },
	{  14232012, 141892 },
	{  14441465, 142339 },
	{  14653238, 142785 },
	{  14867346, 143230 },
	{  15083805, 143676 },
	{  15302632, 144121 },
	{  15523842, 144566 },
	{  15747453, 145011 },
	{  15973479, 145456 },
	{  16201939, 145900 },
	{  16432847, 146345 },
	{  16666221, 146789 },
	{  16902076, 147233 },
	{  17140429, 147677 },
	{  17381297, 148121 },
	{  17624696, 148564 },
	{  17870643, 149007 },
	{  18119154, 149451 },
	{  18370247, 149894 },
	{  18623936, 150336 },
	{  18880241, 150779 },
	{  19139176, 151222 },
	{  19400759, 151664 },
	{  19665007, 152107 },
	{  19931936, 152549 },
	{  20201564, 152991 },
	{  20473907, 153433 },
	{  20748982, 153875 },
	{  21026807, 154316 },
	{  21307399, 154758 },
	{  21590773, 155199 },
	{  21876949, 155641 },
	{  22165941, 156082 },
	{  22457769, 156523 },
	{  22752449, 156964 },
	{  23049999, 157405 },
	{  23350435, 157846 },
	{  23653774, 158287 },
	{  23960036, 158727 },
	{  24269236, 159168 },
	{  24581392, 159608 },
	{  24896521, 160049 },
	{  25214642, 160489 },
	{  25535772, 160929 },
	{  25859927, 161370 },