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 <syslog.h>
  17 #include <fcntl.h>
  18 #include <math.h>
  19 #include <sys/socket.h>
  20 #include <netinet/in.h>
  21 #include <arpa/inet.h>
  22 #include <string.h>
  23
  24 #include "tc_core.h"
  25 #include "tc_red.h"
  26
  27 /*
  28    Plog = log(prob/(qmax - qmin))
  29  */
  30 int tc_red_eval_P(unsigned qmin, unsigned qmax, double prob)
  31 {
  32         int i = qmax - qmin;
  33
  34         if (i <= 0)
  35                 return -1;
  36
  37         prob /= i;
  38
  39         for (i=0; i<32; i++) {
  40                 if (prob > 1.0)
  41                         break;
  42                 prob *= 2;
  43         }
  44         if (i>=32)
  45                 return -1;
  46         return i;
  47 }
  48
  49 /*
  50    burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
  51  */
  52
  53 int tc_red_eval_ewma(unsigned qmin, unsigned burst, unsigned avpkt)
  54 {
  55         int wlog = 1;
  56         double W = 0.5;
  57         double a = (double)burst + 1 - (double)qmin/avpkt;
  58
  59         if (a < 1.0)
  60                 return -1;
  61         for (wlog=1; wlog<32; wlog++, W /= 2) {
  62                 if (a <= (1 - pow(1-W, burst))/W)
  63                         return wlog;
  64         }
  65         return -1;
  66 }
  67
  68 /*
  69    Stab[t>>Scell_log] = -log(1-W) * t/xmit_time
  70  */
  71
  72 int tc_red_eval_idle_damping(int Wlog, unsigned avpkt, unsigned bps, __u8 *sbuf)
  73 {
  74         double xmit_time = tc_core_usec2tick(1000000*(double)avpkt/bps);
  75         double lW = -log(1.0 - 1.0/(1<<Wlog))/xmit_time;
  76         double maxtime = 31/lW;
  77         int clog;
  78         int i;
  79         double tmp;
  80
  81         tmp = maxtime;
  82         for (clog=0; clog<32; clog++) {
  83                 if (maxtime/(1<<clog) < 512)
  84                         break;
  85         }
  86         if (clog >= 32)
  87                 return -1;
  88
  89         sbuf[0] = 0;
  90         for (i=1; i<255; i++) {
  91                 sbuf[i] = (i<<clog)*lW;
  92                 if (sbuf[i] > 31)
  93                         sbuf[i] = 31;
  94         }
  95         sbuf[255] = 31;
  96         return clog;
  97 }