LXR iproute2/tc/tc

   1/*
   2 * tc_red.c             RED maintenance 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 <fcntl.h>
  17#include <math.h>
  18#include <sys/socket.h>
  19#include <netinet/in.h>
  20#include <arpa/inet.h>
  21#include <string.h>
  22
  23#include "utils.h"
  24#include "tc_core.h"
  25#include "tc_util.h"
  26#include "tc_red.h"
  27
  28/*
  29   Plog = log(prob/(qmax - qmin))
  30 */
  31int tc_red_eval_P(unsigned int qmin, unsigned int qmax, double prob)
  32{
  33        int i = qmax - qmin;
  34
  35        if (!i)
  36                return 0;
  37        if (i < 0)
  38                return -1;
  39
  40        prob /= i;
  41
  42        for (i = 0; i < 32; i++) {
  43                if (prob > 1.0)
  44                        break;
  45                prob *= 2;
  46        }
  47        if (i >= 32)
  48                return -1;
  49        return i;
  50}
  51
  52/*
  53   burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
  54 */
  55
  56int tc_red_eval_ewma(unsigned int qmin, unsigned int burst, unsigned int avpkt)
  57{
  58        int wlog = 1;
  59        double W = 0.5;
  60        double a = (double)burst + 1 - (double)qmin/avpkt;
  61
  62        if (a < 1.0) {
  63                fprintf(stderr, "tc_red_eval_ewma() burst %u is too small ? Try burst %u\n",
  64                                burst, 1 + qmin/avpkt);
  65                return -1;
  66        }
  67        for (wlog = 1; wlog < 32; wlog++, W /= 2) {
  68                if (a <= (1 - pow(1-W, burst))/W)
  69                        return wlog;
  70        }
  71        return -1;
  72}
  73
  74/*
  75   Stab[t>>Scell_log] = -log(1-W) * t/xmit_time
  76 */
  77
  78int tc_red_eval_idle_damping(int Wlog, unsigned int avpkt, unsigned int bps, __u8 *sbuf)
  79{
  80        double xmit_time = tc_calc_xmittime(bps, avpkt);
  81        double lW = -log(1.0 - 1.0/(1<<Wlog))/xmit_time;
  82        double maxtime = 31/lW;
  83        int clog;
  84        int i;
  85
  86        for (clog = 0; clog < 32; clog++) {
  87                if (maxtime/(1<<clog) < 512)
  88                        break;
  89        }
  90        if (clog >= 32)
  91                return -1;
  92
  93        sbuf[0] = 0;
  94        for (i = 1; i < 255; i++) {
  95                sbuf[i] = (i<<clog)*lW;
  96                if (sbuf[i] > 31)
  97                        sbuf[i] = 31;
  98        }
  99        sbuf[255] = 31;
 100        return clog;
 101}
 102
 103void tc_red_print_flags(__u32 flags)
 104{
 105        if (flags & TC_RED_ECN)
 106                print_bool(PRINT_ANY, "ecn", "ecn ", true);
 107        else
 108                print_bool(PRINT_ANY, "ecn", NULL, false);
 109
 110        if (flags & TC_RED_HARDDROP)
 111                print_bool(PRINT_ANY, "harddrop", "harddrop ", true);
 112        else
 113                print_bool(PRINT_ANY, "harddrop", NULL, false);
 114
 115        if (flags & TC_RED_ADAPTATIVE)
 116                print_bool(PRINT_ANY, "adaptive", "adaptive ", true);
 117        else
 118                print_bool(PRINT_ANY, "adaptive", NULL, false);
 119
 120        if (flags & TC_RED_NODROP)
 121                print_bool(PRINT_ANY, "nodrop", "nodrop ", true);
 122        else
 123                print_bool(PRINT_ANY, "nodrop", NULL, false);
 124}
 125