• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 qmin,unsigned qmax,double prob)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 
tc_red_eval_ewma(unsigned qmin,unsigned burst,unsigned avpkt)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 		fprintf(stderr, "tc_red_eval_ewma() burst %u is too small ?"
61 				" Try burst %u\n", 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 avpkt,unsigned bps,__u8 * sbuf)75 int tc_red_eval_idle_damping(int Wlog, unsigned avpkt, unsigned 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