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 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 
     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 
     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