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 <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
   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);