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