~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/dccp/ccids/lib/tfrc_equation.c

Version: ~ [ linux-5.8 ] ~ [ linux-5.7.14 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.57 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.138 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.193 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.232 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.232 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp