tfrc_equation.c

linux 内核源代码

	{  26187127, 161810 },
	{  26517388, 162250 },
	{  26850728, 162690 },
	{  27187165, 163130 },
	{  27526716, 163569 },
	{  27869400, 164009 },
	{  28215234, 164449 },
	{  28564236, 164889 },
	{  28916423, 165328 },
	{  29271815, 165768 },
	{  29630428, 166208 },
	{  29992281, 166647 },
	{  30357392, 167087 },
	{  30725779, 167526 },
	{  31097459, 167965 },
	{  31472452, 168405 },
	{  31850774, 168844 },
	{  32232445, 169283 },
	{  32617482, 169723 },
	{  33005904, 170162 },
	{  33397730, 170601 },
	{  33792976, 171041 },
	{  34191663, 171480 },
	{  34593807, 171919 },
	{  34999428, 172358 },
	{  35408544, 172797 },
	{  35821174, 173237 },
	{  36237335, 173676 },
	{  36657047, 174115 },
	{  37080329, 174554 },
	{  37507197, 174993 },
	{  37937673, 175433 },
	{  38371773, 175872 },
	{  38809517, 176311 },
	{  39250924, 176750 },
	{  39696012, 177190 },
	{  40144800, 177629 },
	{  40597308, 178068 },
	{  41053553, 178507 },
	{  41513554, 178947 },
	{  41977332, 179386 },
	{  42444904, 179825 },
	{  42916290, 180265 },
	{  43391509, 180704 },
	{  43870579, 181144 },
	{  44353520, 181583 },
	{  44840352, 182023 },
	{  45331092, 182462 },
	{  45825761, 182902 },
	{  46324378, 183342 },
	{  46826961, 183781 },
	{  47333531, 184221 },
	{  47844106, 184661 },
	{  48358706, 185101 },
	{  48877350, 185541 },
	{  49400058, 185981 },
	{  49926849, 186421 },
	{  50457743, 186861 },
	{  50992759, 187301 },
	{  51531916, 187741 },
	{  52075235, 188181 },
	{  52622735, 188622 },
	{  53174435, 189062 },
	{  53730355, 189502 },
	{  54290515, 189943 },
	{  54854935, 190383 },
	{  55423634, 190824 },
	{  55996633, 191265 },
	{  56573950, 191706 },
	{  57155606, 192146 },
	{  57741621, 192587 },
	{  58332014, 193028 },
	{  58926806, 193470 },
	{  59526017, 193911 },
	{  60129666, 194352 },
	{  60737774, 194793 },
	{  61350361, 195235 },
	{  61967446, 195677 },
	{  62589050, 196118 },
	{  63215194, 196560 },
	{  63845897, 197002 },
	{  64481179, 197444 },
	{  65121061, 197886 },
	{  65765563, 198328 },
	{  66414705, 198770 },
	{  67068508, 199213 },
	{  67726992, 199655 },
	{  68390177, 200098 },
	{  69058085, 200540 },
	{  69730735, 200983 },
	{  70408147, 201426 },
	{  71090343, 201869 },
	{  71777343, 202312 },
	{  72469168, 202755 },
	{  73165837, 203199 },
	{  73867373, 203642 },
	{  74573795, 204086 },
	{  75285124, 204529 },
	{  76001380, 204973 },
	{  76722586, 205417 },
	{  77448761, 205861 },
	{  78179926, 206306 },
	{  78916102, 206750 },
	{  79657310, 207194 },
	{  80403571, 207639 },
	{  81154906, 208084 },
	{  81911335, 208529 },
	{  82672880, 208974 },
	{  83439562, 209419 },
	{  84211402, 209864 },
	{  84988421, 210309 },
	{  85770640, 210755 },
	{  86558080, 211201 },
	{  87350762, 211647 },
	{  88148708, 212093 },
	{  88951938, 212539 },
	{  89760475, 212985 },
	{  90574339, 213432 },
	{  91393551, 213878 },
	{  92218133, 214325 },
	{  93048107, 214772 },
	{  93883493, 215219 },
	{  94724314, 215666 },
	{  95570590, 216114 },
	{  96422343, 216561 },
	{  97279594, 217009 },
	{  98142366, 217457 },
	{  99010679, 217905 },
	{  99884556, 218353 },
	{ 100764018, 218801 },
	{ 101649086, 219250 },
	{ 102539782, 219698 },
	{ 103436128, 220147 },
	{ 104338146, 220596 },
	{ 105245857, 221046 },
	{ 106159284, 221495 },
	{ 107078448, 221945 },
	{ 108003370, 222394 },
	{ 108934074, 222844 },
	{ 109870580, 223294 },
	{ 110812910, 223745 },
	{ 111761087, 224195 },
	{ 112715133, 224646 },
	{ 113675069, 225097 },
	{ 114640918, 225548 },
	{ 115612702, 225999 },
	{ 116590442, 226450 },
	{ 117574162, 226902 },
	{ 118563882, 227353 },
	{ 119559626, 227805 },
	{ 120561415, 228258 },
	{ 121569272, 228710 },
	{ 122583219, 229162 },
	{ 123603278, 229615 },
	{ 124629471, 230068 },
	{ 125661822, 230521 },
	{ 126700352, 230974 },
	{ 127745083, 231428 },
	{ 128796039, 231882 },
	{ 129853241, 232336 },
	{ 130916713, 232790 },
	{ 131986475, 233244 },
	{ 133062553, 233699 },
	{ 134144966, 234153 },
	{ 135233739, 234608 },
	{ 136328894, 235064 },
	{ 137430453, 235519 },
	{ 138538440, 235975 },
	{ 139652876, 236430 },
	{ 140773786, 236886 },
	{ 141901190, 237343 },
	{ 143035113, 237799 },
	{ 144175576, 238256 },
	{ 145322604, 238713 },
	{ 146476218, 239170 },
	{ 147636442, 239627 },
	{ 148803298, 240085 },
	{ 149976809, 240542 },
	{ 151156999, 241000 },
	{ 152343890, 241459 },
	{ 153537506, 241917 },
	{ 154737869, 242376 },
	{ 155945002, 242835 },
	{ 157158929, 243294 },
	{ 158379673, 243753 },
	{ 159607257, 244213 },
	{ 160841704, 244673 },
	{ 162083037, 245133 },
	{ 163331279, 245593 },
	{ 164586455, 246054 },
	{ 165848586, 246514 },
	{ 167117696, 246975 },
	{ 168393810, 247437 },
	{ 169676949, 247898 },
	{ 170967138, 248360 },
	{ 172264399, 248822 },
	{ 173568757, 249284 },
	{ 174880235, 249747 },
	{ 176198856, 250209 },
	{ 177524643, 250672 },
	{ 178857621, 251136 },
	{ 180197813, 251599 },
	{ 181545242, 252063 },
	{ 182899933, 252527 },
	{ 184261908, 252991 },
	{ 185631191, 253456 },
	{ 187007807, 253920 },
	{ 188391778, 254385 },
	{ 189783129, 254851 },
	{ 191181884, 255316 },
	{ 192588065, 255782 },
	{ 194001698, 256248 },
	{ 195422805, 256714 },
	{ 196851411, 257181 },
	{ 198287540, 257648 },
	{ 199731215, 258115 },
	{ 201182461, 258582 },
	{ 202641302, 259050 },
	{ 204107760, 259518 },
	{ 205581862, 259986 },
	{ 207063630, 260454 },
	{ 208553088, 260923 },
	{ 210050262, 261392 },
	{ 211555174, 261861 },
	{ 213067849, 262331 },
	{ 214588312, 262800 },
	{ 216116586, 263270 },
	{ 217652696, 263741 },
	{ 219196666, 264211 },
	{ 220748520, 264682 },
	{ 222308282, 265153 },
	{ 223875978, 265625 },
	{ 225451630, 266097 },
	{ 227035265, 266569 },
	{ 228626905, 267041 },
	{ 230226576, 267514 },
	{ 231834302, 267986 },
	{ 233450107, 268460 },
	{ 235074016, 268933 },
	{ 236706054, 269407 },
	{ 238346244, 269881 },
	{ 239994613, 270355 },
	{ 241651183, 270830 },
	{ 243315981, 271305 }
};

/* return largest index i such that fval <= lookup[i][small] */
static inline u32 tfrc_binsearch(u32 fval, u8 small)
{
	u32 try, low = 0, high = TFRC_CALC_X_ARRSIZE - 1;

	while (low < high) {
		try = (low + high) / 2;
		if (fval <= tfrc_calc_x_lookup[try][small])
			high = try;
		else
			low  = try + 1;
	}
	return high;
}

/**
 * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448
 *
 *  @s: packet size          in bytes
 *  @R: RTT                  scaled by 1000000   (i.e., microseconds)
 *  @p: loss ratio estimate  scaled by 1000000
 *  Returns X_calc           in bytes per second (not scaled).
 */
u32 tfrc_calc_x(u16 s, u32 R, u32 p)
{
	u16 index;
	u32 f;
	u64 result;

	/* check against invalid parameters and divide-by-zero   */
	BUG_ON(p >  1000000);		/* p must not exceed 100%   */
	BUG_ON(p == 0);			/* f(0) = 0, divide by zero */
	if (R == 0) {			/* possible  divide by zero */
		DCCP_CRIT("WARNING: RTT is 0, returning maximum X_calc.");
		return ~0U;
	}

	if (p <= TFRC_CALC_X_SPLIT) 		{     /* 0.0000 < p <= 0.05   */
		if (p < TFRC_SMALLEST_P) {	      /* 0.0000 < p <  0.0001 */
			DCCP_WARN("Value of p (%d) below resolution. "
				  "Substituting %d\n", p, TFRC_SMALLEST_P);
			index = 0;
		} else 				      /* 0.0001 <= p <= 0.05  */
			index =  p/TFRC_SMALLEST_P - 1;

		f = tfrc_calc_x_lookup[index][1];

	} else {	 			      /* 0.05   <  p <= 1.00  */
		index = p/(1000000/TFRC_CALC_X_ARRSIZE) - 1;

		f = tfrc_calc_x_lookup[index][0];
	}

	/*
	 * Compute X = s/(R*f(p)) in bytes per second.
	 * Since f(p) and R are both scaled by 1000000, we need to multiply by
	 * 1000000^2. To avoid overflow, the result is computed in two stages.
	 * This works under almost all reasonable operational conditions, for a
	 * wide range of parameters. Yet, should some strange combination of
	 * parameters result in overflow, the use of scaled_div32 will catch
	 * this and return UINT_MAX - which is a logically adequate consequence.
	 */
	result = scaled_div(s, R);
	return scaled_div32(result, f);
}

EXPORT_SYMBOL_GPL(tfrc_calc_x);

/*
 *  tfrc_calc_x_reverse_lookup  -  try to find p given f(p)
 *
 *  @fvalue: function value to match, scaled by 1000000
 *  Returns closest match for p, also scaled by 1000000
 */
u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
{
	int index;

	if (fvalue == 0)	/* f(p) = 0  whenever  p = 0 */
		return 0;

	/* Error cases. */
	if (fvalue < tfrc_calc_x_lookup[0][1]) {
		DCCP_WARN("fvalue %d smaller than resolution\n", fvalue);
		return tfrc_calc_x_lookup[0][1];
	}
	if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0]) {
		DCCP_WARN("fvalue %d exceeds bounds!\n", fvalue);
		return 1000000;
	}

	if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) {
		index = tfrc_binsearch(fvalue, 1);
		return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE;
	}

	/* else ... it must be in the coarse-grained column */
	index = tfrc_binsearch(fvalue, 0);
	return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE;
}

EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);