Home | History | Annotate | Download | only in tc 
      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 (at) 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_calc_xmittime(bps, avpkt);
     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 }
     98