tc/tc_red.c

   1 /*
   2  * tc_red.c             RED maintanance routines.
   3  *
   4  *              This program is free software; you can redistribute it and/or
   5  *              modify it under the terms of the GNU General Public License
   6  *              as published by the Free Software Foundation; either version
   7  *              2 of the License, or (at your option) any later version.
   8  *
   9  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  10  *
  11  */
  12
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <unistd.h>
  16 #include <fcntl.h>
  17 #include <math.h>
  18 #include <sys/socket.h>
  19 #include <netinet/in.h>
  20 #include <arpa/inet.h>
  21 #include <string.h>
  22
  23 #include "tc_core.h"
  24 #include "tc_red.h"
  25
  26 /*
  27    Plog = log(prob/(qmax - qmin))
  28  */
  29 int tc_red_eval_P(unsigned int qmin, unsigned int qmax, double prob)
  30 {
  31         int i = qmax - qmin;
  32
  33         if (!i)
  34                 return 0;
  35         if (i < 0)
  36                 return -1;
  37
  38         prob /= i;
  39
  40         for (i = 0; i < 32; i++) {
  41                 if (prob > 1.0)
  42                         break;
  43                 prob *= 2;
  44         }
  45         if (i >= 32)
  46                 return -1;
  47         return i;
  48 }
  49
  50 /*
  51    burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
  52  */
  53
  54 int tc_red_eval_ewma(unsigned int qmin, unsigned int burst, unsigned int avpkt)
  55 {
  56         int wlog = 1;
  57         double W = 0.5;
  58         double a = (double)burst + 1 - (double)qmin/avpkt;
  59
  60         if (a < 1.0) {
  61                 fprintf(stderr, "tc_red_eval_ewma() burst %u is too small ? Try burst %u\n",
  62                                 burst, 1 + qmin/avpkt);
  63                 return -1;
  64         }
  65         for (wlog = 1; wlog < 32; wlog++, W /= 2) {
  66                 if (a <= (1 - pow(1-W, burst))/W)
  67                         return wlog;
  68         }
  69         return -1;
  70 }
  71
  72 /*
  73    Stab[t>>Scell_log] = -log(1-W) * t/xmit_time
  74  */
  75
  76 int tc_red_eval_idle_damping(int Wlog, unsigned int avpkt, unsigned int bps, __u8 *sbuf)
  77 {
  78         double xmit_time = tc_calc_xmittime(bps, avpkt);
  79         double lW = -log(1.0 - 1.0/(1<<Wlog))/xmit_time;
  80         double maxtime = 31/lW;
  81         int clog;
  82         int i;
  83
  84         for (clog = 0; clog < 32; clog++) {
  85                 if (maxtime/(1<<clog) < 512)
  86                         break;
  87         }
  88         if (clog >= 32)
  89                 return -1;
  90
  91         sbuf[0] = 0;
  92         for (i = 1; i < 255; i++) {
  93                 sbuf[i] = (i<<clog)*lW;
  94                 if (sbuf[i] > 31)
  95                         sbuf[i] = 31;
  96         }
  97         sbuf[255] = 31;
  98         return clog;
  99 }