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 */
tc_red_eval_P(unsigned int qmin,unsigned int qmax,double prob)30 int tc_red_eval_P(unsigned int qmin, unsigned int 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
tc_red_eval_ewma(unsigned int qmin,unsigned int burst,unsigned int avpkt)53 int tc_red_eval_ewma(unsigned int qmin, unsigned int burst, unsigned int 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 fprintf(stderr, "tc_red_eval_ewma() burst %u is too small ? Try burst %u\n",
61 burst, 1 + qmin/avpkt);
62 return -1;
63 }
64 for (wlog = 1; wlog < 32; wlog++, W /= 2) {
65 if (a <= (1 - pow(1-W, burst))/W)
66 return wlog;
67 }
68 return -1;
69 }
70
71 /*
72 Stab[t>>Scell_log] = -log(1-W) * t/xmit_time
73 */
74
tc_red_eval_idle_damping(int Wlog,unsigned int avpkt,unsigned int bps,__u8 * sbuf)75 int tc_red_eval_idle_damping(int Wlog, unsigned int avpkt, unsigned int bps, __u8 *sbuf)
76 {
77 double xmit_time = tc_calc_xmittime(bps, avpkt);
78 double lW = -log(1.0 - 1.0/(1<<Wlog))/xmit_time;
79 double maxtime = 31/lW;
80 int clog;
81 int i;
82
83 for (clog = 0; clog < 32; clog++) {
84 if (maxtime/(1<<clog) < 512)
85 break;
86 }
87 if (clog >= 32)
88 return -1;
89
90 sbuf[0] = 0;
91 for (i = 1; i < 255; i++) {
92 sbuf[i] = (i<<clog)*lW;
93 if (sbuf[i] > 31)
94 sbuf[i] = 31;
95 }
96 sbuf[255] = 31;
97 return clog;
98 }
99