This commit was manufactured by cvs2svn to create branch
[iproute2.git] / 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 }