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