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