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 */
30int 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
53int 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
75int 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