4fd2ebebf5a0d7a1eb2a4c46c9a4a33c62f0d2cf
[linux-2.6.git] / net / dccp / ccids / lib / tfrc_equation.c
1 /*
2  *  net/dccp/ccids/lib/tfrc_equation.c
3  *
4  *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5  *  Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
6  *  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
15 #include <linux/module.h>
16
17 #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
26 static 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  
531 Returns send rate in bytes per second
532
533 Integer maths and lookups are used as not allowed floating point in kernel
534
535 The function for Xcalc as per section 3.1 of RFC3448 is:
536
537 X =                            s
538      -------------------------------------------------------------
539      R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
540
541 where 
542 X is the trasmit rate in bytes/second
543 s is the packet size in bytes
544 R is the round trip time in seconds
545 p 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
547 t_RTO is the TCP retransmission timeout value in seconds
548 b is the number of packets acknowledged by a single TCP acknowledgement
549
550 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
551
552 X =                            s
553      -----------------------------------------------------------------------
554      R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
555
556
557 which we can break down into:
558
559 X =     s
560      --------
561      R * f(p)
562
563 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
564
565 Function parameters:
566 s - bytes
567 R - RTT in usecs
568 p - loss rate (decimal fraction multiplied by 1,000,000)
569
570 Returns Xcalc in bytes per second
571
572 DON'T alter this code unless you run test cases against it as the code
573 has been manipulated to stop underflow/overlow.
574
575 */
576 u32 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
610 EXPORT_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  */
618 u32 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
642 EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);