Dear reader, I'm not updating these pages anymore. If you have tc or ip related questions, you can post them on the LARTC mailing list.



From help-file :
RED queue
CONFIG_NET_SCH_RED
  Say Y here if you want to use the Random Early Detection (RED)
  packet scheduling algorithm for some of your network devices (see
  the top of net/sched/sch_red.c for details and references about the
  algorithm).
 
  This code is also available as a module called sch_red.o ( = code
  which can be inserted in and removed from the running kernel
  whenever you want). If you want to compile it as a module, say M
  here and read Documentation/modules.txt

From source-files :
Random Early Detection (RED) algorithm.
=======================================

Source: Sally Floyd and Van Jacobson, "Random Early Detection Gateways
for Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking.

This file codes a "divisionless" version of RED algorithm
as written down in Fig.17 of the paper.
 
Short description.
------------------

When a new packet arrives we calculate the average queue length:

avg = (1-W)*avg + W*current_queue_len,

W is the filter time constant (choosen as 2^(-Wlog)), it controls
the inertia of the algorithm. To allow larger bursts, W should be
decreased.

if (avg > th_max) -> packet marked (dropped).
if (avg < th_min) -> packet passes.
if (th_min < avg < th_max) we calculate probability:

Pb = max_P * (avg - th_min)/(th_max-th_min)

and mark (drop) packet with this probability.
Pb changes from 0 (at avg==th_min) to max_P (avg==th_max).
max_P should be small (not 1), usually 0.01..0.02 is good value.

max_P is chosen as a number, so that max_P/(th_max-th_min)
is a negative power of two in order arithmetics to contain
only shifts.


Parameters, settable by user:
-----------------------------

limit       - bytes (must be > qth_max + burst)

Hard limit on queue length, should be chosen >qth_max
to allow packet bursts. This parameter does not
affect the algorithms behaviour and can be chosen
arbitrarily high (well, less than ram size)
Really, this limit will never be reached
if RED works correctly.

qth_min     - bytes (should be < qth_max/2)
qth_max     - bytes (should be at least 2*qth_min and less limit)
Wlog            - bits (<32) log(1/W).
Plog            - bits (<32)

Plog is related to max_P by formula:

max_P = (qth_max-qth_min)/2^Plog;

F.e. if qth_max=128K and qth_min=32K, then Plog=22
corresponds to max_P=0.02

Scell_log
Stab

Lookup table for log((1-W)^(t/t_ave).

NOTES:

Upper bound on W.
-----------------

If you want to allow bursts of L packets of size S,
you should choose W:

L + 1 - th_min/S < (1-(1-W)^L)/W

th_min/S = 32         th_min/S = 4

log(W)  L
-1  33
-2  35
-3  39
-4  46
-5  57
-6  75
-7  101
-8  135
-9  190
etc.