1aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/* 2aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * tc_red.c RED maintanance routines. 3aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * 4aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * This program is free software; you can redistribute it and/or 5aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * modify it under the terms of the GNU General Public License 6aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * as published by the Free Software Foundation; either version 7aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * 2 of the License, or (at your option) any later version. 8aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * 9aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 10aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger * 11aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger */ 12aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 13aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <stdio.h> 14aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <stdlib.h> 15aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <unistd.h> 16aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <syslog.h> 17aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <fcntl.h> 18aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <math.h> 19aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <sys/socket.h> 20aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <netinet/in.h> 21aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <arpa/inet.h> 22aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include <string.h> 23aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 24aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "tc_core.h" 25aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "tc_red.h" 26aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 27aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/* 28aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Plog = log(prob/(qmax - qmin)) 29aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger */ 30aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerint tc_red_eval_P(unsigned qmin, unsigned qmax, double prob) 31aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger{ 32aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int i = qmax - qmin; 33aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 34aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (i <= 0) 35aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return -1; 36aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 37aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger prob /= i; 38aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 39aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (i=0; i<32; i++) { 40aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (prob > 1.0) 41aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger break; 42aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger prob *= 2; 43aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 44aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (i>=32) 45aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return -1; 46aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return i; 47aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 48aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 49aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/* 50aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W 51aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger */ 52aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 53aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerint tc_red_eval_ewma(unsigned qmin, unsigned burst, unsigned avpkt) 54aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger{ 55aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int wlog = 1; 56aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger double W = 0.5; 57aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger double a = (double)burst + 1 - (double)qmin/avpkt; 58aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 590cf67ead7bdc95700958b9cfd341b75b4432bb88Eric Dumazet if (a < 1.0) { 600cf67ead7bdc95700958b9cfd341b75b4432bb88Eric Dumazet fprintf(stderr, "tc_red_eval_ewma() burst %u is too small ?" 610cf67ead7bdc95700958b9cfd341b75b4432bb88Eric Dumazet " Try burst %u\n", burst, 1 + qmin/avpkt); 62aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return -1; 630cf67ead7bdc95700958b9cfd341b75b4432bb88Eric Dumazet } 64aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (wlog=1; wlog<32; wlog++, W /= 2) { 65aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (a <= (1 - pow(1-W, burst))/W) 66aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return wlog; 67aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 68aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return -1; 69aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 70aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 71aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/* 72aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Stab[t>>Scell_log] = -log(1-W) * t/xmit_time 73aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger */ 74aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 75aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerint tc_red_eval_idle_damping(int Wlog, unsigned avpkt, unsigned bps, __u8 *sbuf) 76aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger{ 77476daa7278aaf324f6cef27981f81187afce8836Patrick McHardy double xmit_time = tc_calc_xmittime(bps, avpkt); 78aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger double lW = -log(1.0 - 1.0/(1<<Wlog))/xmit_time; 79aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger double maxtime = 31/lW; 80aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int clog; 81aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int i; 82aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 83aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (clog=0; clog<32; clog++) { 84aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (maxtime/(1<<clog) < 512) 85aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger break; 86aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 87aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (clog >= 32) 88aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return -1; 89aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 90aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger sbuf[0] = 0; 91aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (i=1; i<255; i++) { 92aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger sbuf[i] = (i<<clog)*lW; 93aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (sbuf[i] > 31) 94aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger sbuf[i] = 31; 95aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 96aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger sbuf[255] = 31; 97aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return clog; 98aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 99