blob: 44076e0c65918eda8620b0f9bae6aad57fb9e0e5 [file] [log] [blame]
Arnaldo Carvalho de Melo36729c12005-08-28 00:47:15 -03001/*
2 * net/dccp/ccids/lib/tfrc_equation.c
3 *
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
Ian McDonalde6bccd352006-08-26 19:01:30 -07005 * Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz>
Arnaldo Carvalho de Melo36729c12005-08-28 00:47:15 -03006 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
7 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
8 *
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.
13 */
14
Arnaldo Carvalho de Melo36729c12005-08-28 00:47:15 -030015#include <linux/module.h>
16
Arnaldo Carvalho de Melo36729c12005-08-28 00:47:15 -030017#include <asm/div64.h>
18
19#include "tfrc.h"
20
21#define TFRC_CALC_X_ARRSIZE 500
22
23#define TFRC_CALC_X_SPLIT 50000
24/* equivalent to 0.05 */
25
26static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
27 { 37172, 8172 },
28 { 53499, 11567 },
29 { 66664, 14180 },
30 { 78298, 16388 },
31 { 89021, 18339 },
32 { 99147, 20108 },
33 { 108858, 21738 },
34 { 118273, 23260 },
35 { 127474, 24693 },
36 { 136520, 26052 },
37 { 145456, 27348 },
38 { 154316, 28589 },
39 { 163130, 29783 },
40 { 171919, 30935 },
41 { 180704, 32049 },
42 { 189502, 33130 },
43 { 198328, 34180 },
44 { 207194, 35202 },
45 { 216114, 36198 },
46 { 225097, 37172 },
47 { 234153, 38123 },
48 { 243294, 39055 },
49 { 252527, 39968 },
50 { 261861, 40864 },
51 { 271305, 41743 },
52 { 280866, 42607 },
53 { 290553, 43457 },
54 { 300372, 44293 },
55 { 310333, 45117 },
56 { 320441, 45929 },
57 { 330705, 46729 },
58 { 341131, 47518 },
59 { 351728, 48297 },
60 { 362501, 49066 },
61 { 373460, 49826 },
62 { 384609, 50577 },
63 { 395958, 51320 },
64 { 407513, 52054 },
65 { 419281, 52780 },
66 { 431270, 53499 },
67 { 443487, 54211 },
68 { 455940, 54916 },
69 { 468635, 55614 },
70 { 481581, 56306 },
71 { 494785, 56991 },
72 { 508254, 57671 },
73 { 521996, 58345 },
74 { 536019, 59014 },
75 { 550331, 59677 },
76 { 564939, 60335 },
77 { 579851, 60988 },
78 { 595075, 61636 },
79 { 610619, 62279 },
80 { 626491, 62918 },
81 { 642700, 63553 },
82 { 659253, 64183 },
83 { 676158, 64809 },
84 { 693424, 65431 },
85 { 711060, 66050 },
86 { 729073, 66664 },
87 { 747472, 67275 },
88 { 766266, 67882 },
89 { 785464, 68486 },
90 { 805073, 69087 },
91 { 825103, 69684 },
92 { 845562, 70278 },
93 { 866460, 70868 },
94 { 887805, 71456 },
95 { 909606, 72041 },
96 { 931873, 72623 },
97 { 954614, 73202 },
98 { 977839, 73778 },
99 { 1001557, 74352 },
100 { 1025777, 74923 },
101 { 1050508, 75492 },
102 { 1075761, 76058 },
103 { 1101544, 76621 },
104 { 1127867, 77183 },
105 { 1154739, 77741 },
106 { 1182172, 78298 },
107 { 1210173, 78852 },
108 { 1238753, 79405 },
109 { 1267922, 79955 },
110 { 1297689, 80503 },
111 { 1328066, 81049 },
112 { 1359060, 81593 },
113 { 1390684, 82135 },
114 { 1422947, 82675 },
115 { 1455859, 83213 },
116 { 1489430, 83750 },
117 { 1523671, 84284 },
118 { 1558593, 84817 },
119 { 1594205, 85348 },
120 { 1630518, 85878 },
121 { 1667543, 86406 },
122 { 1705290, 86932 },
123 { 1743770, 87457 },
124 { 1782994, 87980 },
125 { 1822973, 88501 },
126 { 1863717, 89021 },
127 { 1905237, 89540 },
128 { 1947545, 90057 },
129 { 1990650, 90573 },
130 { 2034566, 91087 },
131 { 2079301, 91600 },
132 { 2124869, 92111 },
133 { 2171279, 92622 },
134 { 2218543, 93131 },
135 { 2266673, 93639 },
136 { 2315680, 94145 },
137 { 2365575, 94650 },
138 { 2416371, 95154 },
139 { 2468077, 95657 },
140 { 2520707, 96159 },
141 { 2574271, 96660 },
142 { 2628782, 97159 },
143 { 2684250, 97658 },
144 { 2740689, 98155 },
145 { 2798110, 98651 },
146 { 2856524, 99147 },
147 { 2915944, 99641 },
148 { 2976382, 100134 },
149 { 3037850, 100626 },
150 { 3100360, 101117 },
151 { 3163924, 101608 },
152 { 3228554, 102097 },
153 { 3294263, 102586 },
154 { 3361063, 103073 },
155 { 3428966, 103560 },
156 { 3497984, 104045 },
157 { 3568131, 104530 },
158 { 3639419, 105014 },
159 { 3711860, 105498 },
160 { 3785467, 105980 },
161 { 3860253, 106462 },
162 { 3936229, 106942 },
163 { 4013410, 107422 },
164 { 4091808, 107902 },
165 { 4171435, 108380 },
166 { 4252306, 108858 },
167 { 4334431, 109335 },
168 { 4417825, 109811 },
169 { 4502501, 110287 },
170 { 4588472, 110762 },
171 { 4675750, 111236 },
172 { 4764349, 111709 },
173 { 4854283, 112182 },
174 { 4945564, 112654 },
175 { 5038206, 113126 },
176 { 5132223, 113597 },
177 { 5227627, 114067 },
178 { 5324432, 114537 },
179 { 5422652, 115006 },
180 { 5522299, 115474 },
181 { 5623389, 115942 },
182 { 5725934, 116409 },
183 { 5829948, 116876 },
184 { 5935446, 117342 },
185 { 6042439, 117808 },
186 { 6150943, 118273 },
187 { 6260972, 118738 },
188 { 6372538, 119202 },
189 { 6485657, 119665 },
190 { 6600342, 120128 },
191 { 6716607, 120591 },
192 { 6834467, 121053 },
193 { 6953935, 121514 },
194 { 7075025, 121976 },
195 { 7197752, 122436 },
196 { 7322131, 122896 },
197 { 7448175, 123356 },
198 { 7575898, 123815 },
199 { 7705316, 124274 },
200 { 7836442, 124733 },
201 { 7969291, 125191 },
202 { 8103877, 125648 },
203 { 8240216, 126105 },
204 { 8378321, 126562 },
205 { 8518208, 127018 },
206 { 8659890, 127474 },
207 { 8803384, 127930 },
208 { 8948702, 128385 },
209 { 9095861, 128840 },
210 { 9244875, 129294 },
211 { 9395760, 129748 },
212 { 9548529, 130202 },
213 { 9703198, 130655 },
214 { 9859782, 131108 },
215 { 10018296, 131561 },
216 { 10178755, 132014 },
217 { 10341174, 132466 },
218 { 10505569, 132917 },
219 { 10671954, 133369 },
220 { 10840345, 133820 },
221 { 11010757, 134271 },
222 { 11183206, 134721 },
223 { 11357706, 135171 },
224 { 11534274, 135621 },
225 { 11712924, 136071 },
226 { 11893673, 136520 },
227 { 12076536, 136969 },
228 { 12261527, 137418 },
229 { 12448664, 137867 },
230 { 12637961, 138315 },
231 { 12829435, 138763 },
232 { 13023101, 139211 },
233 { 13218974, 139658 },
234 { 13417071, 140106 },
235 { 13617407, 140553 },
236 { 13819999, 140999 },
237 { 14024862, 141446 },
238 { 14232012, 141892 },
239 { 14441465, 142339 },
240 { 14653238, 142785 },
241 { 14867346, 143230 },
242 { 15083805, 143676 },
243 { 15302632, 144121 },
244 { 15523842, 144566 },
245 { 15747453, 145011 },
246 { 15973479, 145456 },
247 { 16201939, 145900 },
248 { 16432847, 146345 },
249 { 16666221, 146789 },
250 { 16902076, 147233 },
251 { 17140429, 147677 },
252 { 17381297, 148121 },
253 { 17624696, 148564 },
254 { 17870643, 149007 },
255 { 18119154, 149451 },
256 { 18370247, 149894 },
257 { 18623936, 150336 },
258 { 18880241, 150779 },
259 { 19139176, 151222 },
260 { 19400759, 151664 },
261 { 19665007, 152107 },
262 { 19931936, 152549 },
263 { 20201564, 152991 },
264 { 20473907, 153433 },
265 { 20748982, 153875 },
266 { 21026807, 154316 },
267 { 21307399, 154758 },
268 { 21590773, 155199 },
269 { 21876949, 155641 },
270 { 22165941, 156082 },
271 { 22457769, 156523 },
272 { 22752449, 156964 },
273 { 23049999, 157405 },
274 { 23350435, 157846 },
275 { 23653774, 158287 },
276 { 23960036, 158727 },
277 { 24269236, 159168 },
278 { 24581392, 159608 },
279 { 24896521, 160049 },
280 { 25214642, 160489 },
281 { 25535772, 160929 },
282 { 25859927, 161370 },
283 { 26187127, 161810 },
284 { 26517388, 162250 },
285 { 26850728, 162690 },
286 { 27187165, 163130 },
287 { 27526716, 163569 },
288 { 27869400, 164009 },
289 { 28215234, 164449 },
290 { 28564236, 164889 },
291 { 28916423, 165328 },
292 { 29271815, 165768 },
293 { 29630428, 166208 },
294 { 29992281, 166647 },
295 { 30357392, 167087 },
296 { 30725779, 167526 },
297 { 31097459, 167965 },
298 { 31472452, 168405 },
299 { 31850774, 168844 },
300 { 32232445, 169283 },
301 { 32617482, 169723 },
302 { 33005904, 170162 },
303 { 33397730, 170601 },
304 { 33792976, 171041 },
305 { 34191663, 171480 },
306 { 34593807, 171919 },
307 { 34999428, 172358 },
308 { 35408544, 172797 },
309 { 35821174, 173237 },
310 { 36237335, 173676 },
311 { 36657047, 174115 },
312 { 37080329, 174554 },
313 { 37507197, 174993 },
314 { 37937673, 175433 },
315 { 38371773, 175872 },
316 { 38809517, 176311 },
317 { 39250924, 176750 },
318 { 39696012, 177190 },
319 { 40144800, 177629 },
320 { 40597308, 178068 },
321 { 41053553, 178507 },
322 { 41513554, 178947 },
323 { 41977332, 179386 },
324 { 42444904, 179825 },
325 { 42916290, 180265 },
326 { 43391509, 180704 },
327 { 43870579, 181144 },
328 { 44353520, 181583 },
329 { 44840352, 182023 },
330 { 45331092, 182462 },
331 { 45825761, 182902 },
332 { 46324378, 183342 },
333 { 46826961, 183781 },
334 { 47333531, 184221 },
335 { 47844106, 184661 },
336 { 48358706, 185101 },
337 { 48877350, 185541 },
338 { 49400058, 185981 },
339 { 49926849, 186421 },
340 { 50457743, 186861 },
341 { 50992759, 187301 },
342 { 51531916, 187741 },
343 { 52075235, 188181 },
344 { 52622735, 188622 },
345 { 53174435, 189062 },
346 { 53730355, 189502 },
347 { 54290515, 189943 },
348 { 54854935, 190383 },
349 { 55423634, 190824 },
350 { 55996633, 191265 },
351 { 56573950, 191706 },
352 { 57155606, 192146 },
353 { 57741621, 192587 },
354 { 58332014, 193028 },
355 { 58926806, 193470 },
356 { 59526017, 193911 },
357 { 60129666, 194352 },
358 { 60737774, 194793 },
359 { 61350361, 195235 },
360 { 61967446, 195677 },
361 { 62589050, 196118 },
362 { 63215194, 196560 },
363 { 63845897, 197002 },
364 { 64481179, 197444 },
365 { 65121061, 197886 },
366 { 65765563, 198328 },
367 { 66414705, 198770 },
368 { 67068508, 199213 },
369 { 67726992, 199655 },
370 { 68390177, 200098 },
371 { 69058085, 200540 },
372 { 69730735, 200983 },
373 { 70408147, 201426 },
374 { 71090343, 201869 },
375 { 71777343, 202312 },
376 { 72469168, 202755 },
377 { 73165837, 203199 },
378 { 73867373, 203642 },
379 { 74573795, 204086 },
380 { 75285124, 204529 },
381 { 76001380, 204973 },
382 { 76722586, 205417 },
383 { 77448761, 205861 },
384 { 78179926, 206306 },
385 { 78916102, 206750 },
386 { 79657310, 207194 },
387 { 80403571, 207639 },
388 { 81154906, 208084 },
389 { 81911335, 208529 },
390 { 82672880, 208974 },
391 { 83439562, 209419 },
392 { 84211402, 209864 },
393 { 84988421, 210309 },
394 { 85770640, 210755 },
395 { 86558080, 211201 },
396 { 87350762, 211647 },
397 { 88148708, 212093 },
398 { 88951938, 212539 },
399 { 89760475, 212985 },
400 { 90574339, 213432 },
401 { 91393551, 213878 },
402 { 92218133, 214325 },
403 { 93048107, 214772 },
404 { 93883493, 215219 },
405 { 94724314, 215666 },
406 { 95570590, 216114 },
407 { 96422343, 216561 },
408 { 97279594, 217009 },
409 { 98142366, 217457 },
410 { 99010679, 217905 },
411 { 99884556, 218353 },
412 { 100764018, 218801 },
413 { 101649086, 219250 },
414 { 102539782, 219698 },
415 { 103436128, 220147 },
416 { 104338146, 220596 },
417 { 105245857, 221046 },
418 { 106159284, 221495 },
419 { 107078448, 221945 },
420 { 108003370, 222394 },
421 { 108934074, 222844 },
422 { 109870580, 223294 },
423 { 110812910, 223745 },
424 { 111761087, 224195 },
425 { 112715133, 224646 },
426 { 113675069, 225097 },
427 { 114640918, 225548 },
428 { 115612702, 225999 },
429 { 116590442, 226450 },
430 { 117574162, 226902 },
431 { 118563882, 227353 },
432 { 119559626, 227805 },
433 { 120561415, 228258 },
434 { 121569272, 228710 },
435 { 122583219, 229162 },
436 { 123603278, 229615 },
437 { 124629471, 230068 },
438 { 125661822, 230521 },
439 { 126700352, 230974 },
440 { 127745083, 231428 },
441 { 128796039, 231882 },
442 { 129853241, 232336 },
443 { 130916713, 232790 },
444 { 131986475, 233244 },
445 { 133062553, 233699 },
446 { 134144966, 234153 },
447 { 135233739, 234608 },
448 { 136328894, 235064 },
449 { 137430453, 235519 },
450 { 138538440, 235975 },
451 { 139652876, 236430 },
452 { 140773786, 236886 },
453 { 141901190, 237343 },
454 { 143035113, 237799 },
455 { 144175576, 238256 },
456 { 145322604, 238713 },
457 { 146476218, 239170 },
458 { 147636442, 239627 },
459 { 148803298, 240085 },
460 { 149976809, 240542 },
461 { 151156999, 241000 },
462 { 152343890, 241459 },
463 { 153537506, 241917 },
464 { 154737869, 242376 },
465 { 155945002, 242835 },
466 { 157158929, 243294 },
467 { 158379673, 243753 },
468 { 159607257, 244213 },
469 { 160841704, 244673 },
470 { 162083037, 245133 },
471 { 163331279, 245593 },
472 { 164586455, 246054 },
473 { 165848586, 246514 },
474 { 167117696, 246975 },
475 { 168393810, 247437 },
476 { 169676949, 247898 },
477 { 170967138, 248360 },
478 { 172264399, 248822 },
479 { 173568757, 249284 },
480 { 174880235, 249747 },
481 { 176198856, 250209 },
482 { 177524643, 250672 },
483 { 178857621, 251136 },
484 { 180197813, 251599 },
485 { 181545242, 252063 },
486 { 182899933, 252527 },
487 { 184261908, 252991 },
488 { 185631191, 253456 },
489 { 187007807, 253920 },
490 { 188391778, 254385 },
491 { 189783129, 254851 },
492 { 191181884, 255316 },
493 { 192588065, 255782 },
494 { 194001698, 256248 },
495 { 195422805, 256714 },
496 { 196851411, 257181 },
497 { 198287540, 257648 },
498 { 199731215, 258115 },
499 { 201182461, 258582 },
500 { 202641302, 259050 },
501 { 204107760, 259518 },
502 { 205581862, 259986 },
503 { 207063630, 260454 },
504 { 208553088, 260923 },
505 { 210050262, 261392 },
506 { 211555174, 261861 },
507 { 213067849, 262331 },
508 { 214588312, 262800 },
509 { 216116586, 263270 },
510 { 217652696, 263741 },
511 { 219196666, 264211 },
512 { 220748520, 264682 },
513 { 222308282, 265153 },
514 { 223875978, 265625 },
515 { 225451630, 266097 },
516 { 227035265, 266569 },
517 { 228626905, 267041 },
518 { 230226576, 267514 },
519 { 231834302, 267986 },
520 { 233450107, 268460 },
521 { 235074016, 268933 },
522 { 236706054, 269407 },
523 { 238346244, 269881 },
524 { 239994613, 270355 },
525 { 241651183, 270830 },
526 { 243315981, 271305 }
527};
528
529/* Calculate the send rate as per section 3.1 of RFC3448
530
531Returns send rate in bytes per second
532
533Integer maths and lookups are used as not allowed floating point in kernel
534
535The function for Xcalc as per section 3.1 of RFC3448 is:
536
537X = s
538 -------------------------------------------------------------
539 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
540
541where
542X is the trasmit rate in bytes/second
543s is the packet size in bytes
544R is the round trip time in seconds
545p is the loss event rate, between 0 and 1.0, of the number of loss events
546 as a fraction of the number of packets transmitted
547t_RTO is the TCP retransmission timeout value in seconds
548b is the number of packets acknowledged by a single TCP acknowledgement
549
550we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
551
552X = s
553 -----------------------------------------------------------------------
554 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
555
556
557which we can break down into:
558
559X = s
560 --------
561 R * f(p)
562
563where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
564
565Function parameters:
566s - bytes
567R - RTT in usecs
568p - loss rate (decimal fraction multiplied by 1,000,000)
569
570Returns Xcalc in bytes per second
571
572DON'T alter this code unless you run test cases against it as the code
573has been manipulated to stop underflow/overlow.
574
575*/
576u32 tfrc_calc_x(u16 s, u32 R, u32 p)
577{
578 int index;
579 u32 f;
580 u64 tmp1, tmp2;
581
582 if (p < TFRC_CALC_X_SPLIT)
583 index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
584 else
585 index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
586
587 if (index < 0)
588 /* p should be 0 unless there is a bug in my code */
589 index = 0;
590
591 if (R == 0)
592 R = 1; /* RTT can't be zero or else divide by zero */
593
594 BUG_ON(index >= TFRC_CALC_X_ARRSIZE);
595
596 if (p >= TFRC_CALC_X_SPLIT)
597 f = tfrc_calc_x_lookup[index][0];
598 else
599 f = tfrc_calc_x_lookup[index][1];
600
601 tmp1 = ((u64)s * 100000000);
602 tmp2 = ((u64)R * (u64)f);
603 do_div(tmp2, 10000);
604 do_div(tmp1, tmp2);
605 /* Don't alter above math unless you test due to overflow on 32 bit */
606
607 return (u32)tmp1;
608}
609
610EXPORT_SYMBOL_GPL(tfrc_calc_x);
611
612/*
613 * args: fvalue - function value to match
614 * returns: p closest to that value
615 *
616 * both fvalue and p are multiplied by 1,000,000 to use ints
617 */
618u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
619{
620 int ctr = 0;
621 int small;
622
623 if (fvalue < tfrc_calc_x_lookup[0][1])
624 return 0;
625
626 if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
627 small = 1;
628 else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
629 return 1000000;
630 else
631 small = 0;
632
633 while (fvalue > tfrc_calc_x_lookup[ctr][small])
634 ctr++;
635
636 if (small)
637 return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE;
638 else
639 return 1000000 * ctr / TFRC_CALC_X_ARRSIZE;
640}
641
642EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);