2 * net/dccp/ccids/lib/tfrc_equation.c
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz>
6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
7 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
15 #include <linux/module.h>
16 #include <asm/div64.h>
17 #include "../../dccp.h"
20 #define TFRC_CALC_X_ARRSIZE 500
22 #define TFRC_CALC_X_SPLIT 50000
23 /* equivalent to 0.05 */
25 static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
214 { 10018296, 131561 },
215 { 10178755, 132014 },
216 { 10341174, 132466 },
217 { 10505569, 132917 },
218 { 10671954, 133369 },
219 { 10840345, 133820 },
220 { 11010757, 134271 },
221 { 11183206, 134721 },
222 { 11357706, 135171 },
223 { 11534274, 135621 },
224 { 11712924, 136071 },
225 { 11893673, 136520 },
226 { 12076536, 136969 },
227 { 12261527, 137418 },
228 { 12448664, 137867 },
229 { 12637961, 138315 },
230 { 12829435, 138763 },
231 { 13023101, 139211 },
232 { 13218974, 139658 },
233 { 13417071, 140106 },
234 { 13617407, 140553 },
235 { 13819999, 140999 },
236 { 14024862, 141446 },
237 { 14232012, 141892 },
238 { 14441465, 142339 },
239 { 14653238, 142785 },
240 { 14867346, 143230 },
241 { 15083805, 143676 },
242 { 15302632, 144121 },
243 { 15523842, 144566 },
244 { 15747453, 145011 },
245 { 15973479, 145456 },
246 { 16201939, 145900 },
247 { 16432847, 146345 },
248 { 16666221, 146789 },
249 { 16902076, 147233 },
250 { 17140429, 147677 },
251 { 17381297, 148121 },
252 { 17624696, 148564 },
253 { 17870643, 149007 },
254 { 18119154, 149451 },
255 { 18370247, 149894 },
256 { 18623936, 150336 },
257 { 18880241, 150779 },
258 { 19139176, 151222 },
259 { 19400759, 151664 },
260 { 19665007, 152107 },
261 { 19931936, 152549 },
262 { 20201564, 152991 },
263 { 20473907, 153433 },
264 { 20748982, 153875 },
265 { 21026807, 154316 },
266 { 21307399, 154758 },
267 { 21590773, 155199 },
268 { 21876949, 155641 },
269 { 22165941, 156082 },
270 { 22457769, 156523 },
271 { 22752449, 156964 },
272 { 23049999, 157405 },
273 { 23350435, 157846 },
274 { 23653774, 158287 },
275 { 23960036, 158727 },
276 { 24269236, 159168 },
277 { 24581392, 159608 },
278 { 24896521, 160049 },
279 { 25214642, 160489 },
280 { 25535772, 160929 },
281 { 25859927, 161370 },
282 { 26187127, 161810 },
283 { 26517388, 162250 },
284 { 26850728, 162690 },
285 { 27187165, 163130 },
286 { 27526716, 163569 },
287 { 27869400, 164009 },
288 { 28215234, 164449 },
289 { 28564236, 164889 },
290 { 28916423, 165328 },
291 { 29271815, 165768 },
292 { 29630428, 166208 },
293 { 29992281, 166647 },
294 { 30357392, 167087 },
295 { 30725779, 167526 },
296 { 31097459, 167965 },
297 { 31472452, 168405 },
298 { 31850774, 168844 },
299 { 32232445, 169283 },
300 { 32617482, 169723 },
301 { 33005904, 170162 },
302 { 33397730, 170601 },
303 { 33792976, 171041 },
304 { 34191663, 171480 },
305 { 34593807, 171919 },
306 { 34999428, 172358 },
307 { 35408544, 172797 },
308 { 35821174, 173237 },
309 { 36237335, 173676 },
310 { 36657047, 174115 },
311 { 37080329, 174554 },
312 { 37507197, 174993 },
313 { 37937673, 175433 },
314 { 38371773, 175872 },
315 { 38809517, 176311 },
316 { 39250924, 176750 },
317 { 39696012, 177190 },
318 { 40144800, 177629 },
319 { 40597308, 178068 },
320 { 41053553, 178507 },
321 { 41513554, 178947 },
322 { 41977332, 179386 },
323 { 42444904, 179825 },
324 { 42916290, 180265 },
325 { 43391509, 180704 },
326 { 43870579, 181144 },
327 { 44353520, 181583 },
328 { 44840352, 182023 },
329 { 45331092, 182462 },
330 { 45825761, 182902 },
331 { 46324378, 183342 },
332 { 46826961, 183781 },
333 { 47333531, 184221 },
334 { 47844106, 184661 },
335 { 48358706, 185101 },
336 { 48877350, 185541 },
337 { 49400058, 185981 },
338 { 49926849, 186421 },
339 { 50457743, 186861 },
340 { 50992759, 187301 },
341 { 51531916, 187741 },
342 { 52075235, 188181 },
343 { 52622735, 188622 },
344 { 53174435, 189062 },
345 { 53730355, 189502 },
346 { 54290515, 189943 },
347 { 54854935, 190383 },
348 { 55423634, 190824 },
349 { 55996633, 191265 },
350 { 56573950, 191706 },
351 { 57155606, 192146 },
352 { 57741621, 192587 },
353 { 58332014, 193028 },
354 { 58926806, 193470 },
355 { 59526017, 193911 },
356 { 60129666, 194352 },
357 { 60737774, 194793 },
358 { 61350361, 195235 },
359 { 61967446, 195677 },
360 { 62589050, 196118 },
361 { 63215194, 196560 },
362 { 63845897, 197002 },
363 { 64481179, 197444 },
364 { 65121061, 197886 },
365 { 65765563, 198328 },
366 { 66414705, 198770 },
367 { 67068508, 199213 },
368 { 67726992, 199655 },
369 { 68390177, 200098 },
370 { 69058085, 200540 },
371 { 69730735, 200983 },
372 { 70408147, 201426 },
373 { 71090343, 201869 },
374 { 71777343, 202312 },
375 { 72469168, 202755 },
376 { 73165837, 203199 },
377 { 73867373, 203642 },
378 { 74573795, 204086 },
379 { 75285124, 204529 },
380 { 76001380, 204973 },
381 { 76722586, 205417 },
382 { 77448761, 205861 },
383 { 78179926, 206306 },
384 { 78916102, 206750 },
385 { 79657310, 207194 },
386 { 80403571, 207639 },
387 { 81154906, 208084 },
388 { 81911335, 208529 },
389 { 82672880, 208974 },
390 { 83439562, 209419 },
391 { 84211402, 209864 },
392 { 84988421, 210309 },
393 { 85770640, 210755 },
394 { 86558080, 211201 },
395 { 87350762, 211647 },
396 { 88148708, 212093 },
397 { 88951938, 212539 },
398 { 89760475, 212985 },
399 { 90574339, 213432 },
400 { 91393551, 213878 },
401 { 92218133, 214325 },
402 { 93048107, 214772 },
403 { 93883493, 215219 },
404 { 94724314, 215666 },
405 { 95570590, 216114 },
406 { 96422343, 216561 },
407 { 97279594, 217009 },
408 { 98142366, 217457 },
409 { 99010679, 217905 },
410 { 99884556, 218353 },
411 { 100764018, 218801 },
412 { 101649086, 219250 },
413 { 102539782, 219698 },
414 { 103436128, 220147 },
415 { 104338146, 220596 },
416 { 105245857, 221046 },
417 { 106159284, 221495 },
418 { 107078448, 221945 },
419 { 108003370, 222394 },
420 { 108934074, 222844 },
421 { 109870580, 223294 },
422 { 110812910, 223745 },
423 { 111761087, 224195 },
424 { 112715133, 224646 },
425 { 113675069, 225097 },
426 { 114640918, 225548 },
427 { 115612702, 225999 },
428 { 116590442, 226450 },
429 { 117574162, 226902 },
430 { 118563882, 227353 },
431 { 119559626, 227805 },
432 { 120561415, 228258 },
433 { 121569272, 228710 },
434 { 122583219, 229162 },
435 { 123603278, 229615 },
436 { 124629471, 230068 },
437 { 125661822, 230521 },
438 { 126700352, 230974 },
439 { 127745083, 231428 },
440 { 128796039, 231882 },
441 { 129853241, 232336 },
442 { 130916713, 232790 },
443 { 131986475, 233244 },
444 { 133062553, 233699 },
445 { 134144966, 234153 },
446 { 135233739, 234608 },
447 { 136328894, 235064 },
448 { 137430453, 235519 },
449 { 138538440, 235975 },
450 { 139652876, 236430 },
451 { 140773786, 236886 },
452 { 141901190, 237343 },
453 { 143035113, 237799 },
454 { 144175576, 238256 },
455 { 145322604, 238713 },
456 { 146476218, 239170 },
457 { 147636442, 239627 },
458 { 148803298, 240085 },
459 { 149976809, 240542 },
460 { 151156999, 241000 },
461 { 152343890, 241459 },
462 { 153537506, 241917 },
463 { 154737869, 242376 },
464 { 155945002, 242835 },
465 { 157158929, 243294 },
466 { 158379673, 243753 },
467 { 159607257, 244213 },
468 { 160841704, 244673 },
469 { 162083037, 245133 },
470 { 163331279, 245593 },
471 { 164586455, 246054 },
472 { 165848586, 246514 },
473 { 167117696, 246975 },
474 { 168393810, 247437 },
475 { 169676949, 247898 },
476 { 170967138, 248360 },
477 { 172264399, 248822 },
478 { 173568757, 249284 },
479 { 174880235, 249747 },
480 { 176198856, 250209 },
481 { 177524643, 250672 },
482 { 178857621, 251136 },
483 { 180197813, 251599 },
484 { 181545242, 252063 },
485 { 182899933, 252527 },
486 { 184261908, 252991 },
487 { 185631191, 253456 },
488 { 187007807, 253920 },
489 { 188391778, 254385 },
490 { 189783129, 254851 },
491 { 191181884, 255316 },
492 { 192588065, 255782 },
493 { 194001698, 256248 },
494 { 195422805, 256714 },
495 { 196851411, 257181 },
496 { 198287540, 257648 },
497 { 199731215, 258115 },
498 { 201182461, 258582 },
499 { 202641302, 259050 },
500 { 204107760, 259518 },
501 { 205581862, 259986 },
502 { 207063630, 260454 },
503 { 208553088, 260923 },
504 { 210050262, 261392 },
505 { 211555174, 261861 },
506 { 213067849, 262331 },
507 { 214588312, 262800 },
508 { 216116586, 263270 },
509 { 217652696, 263741 },
510 { 219196666, 264211 },
511 { 220748520, 264682 },
512 { 222308282, 265153 },
513 { 223875978, 265625 },
514 { 225451630, 266097 },
515 { 227035265, 266569 },
516 { 228626905, 267041 },
517 { 230226576, 267514 },
518 { 231834302, 267986 },
519 { 233450107, 268460 },
520 { 235074016, 268933 },
521 { 236706054, 269407 },
522 { 238346244, 269881 },
523 { 239994613, 270355 },
524 { 241651183, 270830 },
525 { 243315981, 271305 }
528 /* Calculate the send rate as per section 3.1 of RFC3448
530 Returns send rate in bytes per second
532 Integer maths and lookups are used as not allowed floating point in kernel
534 The function for Xcalc as per section 3.1 of RFC3448 is:
537 -------------------------------------------------------------
538 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
541 X is the trasmit rate in bytes/second
542 s is the packet size in bytes
543 R is the round trip time in seconds
544 p 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
546 t_RTO is the TCP retransmission timeout value in seconds
547 b is the number of packets acknowledged by a single TCP acknowledgement
549 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
552 -----------------------------------------------------------------------
553 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
556 which we can break down into:
562 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
567 p - loss rate (decimal fraction multiplied by 1,000,000)
569 Returns Xcalc in bytes per second
571 DON'T alter this code unless you run test cases against it as the code
572 has been manipulated to stop underflow/overlow.
575 u32 tfrc_calc_x(u16 s, u32 R, u32 p)
581 if (p < TFRC_CALC_X_SPLIT)
582 index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
584 index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
587 /* p should be 0 unless there is a bug in my code */
591 DCCP_WARN("RTT==0, setting to 1\n");
592 R = 1; /* RTT can't be zero or else divide by zero */
595 BUG_ON(index >= TFRC_CALC_X_ARRSIZE);
597 if (p >= TFRC_CALC_X_SPLIT)
598 f = tfrc_calc_x_lookup[index][0];
600 f = tfrc_calc_x_lookup[index][1];
602 tmp1 = ((u64)s * 100000000);
603 tmp2 = ((u64)R * (u64)f);
606 /* Don't alter above math unless you test due to overflow on 32 bit */
611 EXPORT_SYMBOL_GPL(tfrc_calc_x);
614 * args: fvalue - function value to match
615 * returns: p closest to that value
617 * both fvalue and p are multiplied by 1,000,000 to use ints
619 u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
624 if (fvalue < tfrc_calc_x_lookup[0][1])
627 if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
629 else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
634 while (fvalue > tfrc_calc_x_lookup[ctr][small])
638 return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE;
640 return 1000000 * ctr / TFRC_CALC_X_ARRSIZE;
643 EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);