ARED

ared − Adaptive Random Early Detection

tc qdisc ... ared

qMaxPkts npackets bps bits mtu bytes [ th1 npackets ] [ th2 npackets ] [ th3 npackets ] [ wq val ] [ maxCount npackets ] [ aredIval nseconds ] [ ED ]

Random Early Detection (RED) is a classless qdisc which manages its queue size smartly. Regular queues simply drop packets from the tail when they are full, which may not be the optimal behaviour. RED also performs tail drop, but does so in a more gradual way.

Once the queue hits a certain average length, packets enqueued have a configurable chance of being marked (which may mean dropped). This chance increases linearly up to a point called the th2 average queue length, although the queue might get bigger.

This has a host of benefits over simple taildrop, while not being processor intensive. It prevents synchronous retransmits after a burst in traffic, which cause further retransmits, etc.

The goal is the have a small queue size, which is good for interactivity while not disturbing TCP/IP traffic with too many sudden drops after a burst of traffic.

The average queue size is used for determining the marking probability. This is calculated using an Exponential Weighted Moving Average, which can be more or less sensitive to bursts.

When the average queue size is below th1 packets, no packet will ever be marked. When it exceeds th1, the probability of doing so climbs linearly up to maxp, until the average queue size hits th2 packets. Because probability is normally not set to 100%, the queue size might conceivably rise above th2 bytes, so the qMaxPkts parameter is provided to set a hard maximum for the size of the queue.

This uses the "gentle" variety of RED as suggested by Sally Floyd where the dropping probablity does not go immediately to 1 after the queue size hits th2. Instead, the dropping probability climbs linearly up to 1 as the queue size hits th3.

RED does not work well unless it is properly configured for the traffic. This is not so easy to do. One feature of an ill configured is oscillations in the size of the queue. Sadly, the volume of traffic can change, and if RED was properly configured, then it will no longer be properly configured after the chante.

Adaptive RED ARED, like RED, may be attributed to Sally Floyd et al. It automatically adusts the key parameter (maxp) to keep the RED properly configured. There is a target queue size (which will be 1/6 of the actual queue size. A second, slower estimate of average queue size is kept, and if this is larger than the target queue size, then maxp is increased. Otherwise, maxp is decreased.

You can configure all of the parameters to ARED directly. Or, you can choose to provide only the mandatory parameters, and ARED will attempt to make sensible assumptions and choose sutiable values for the optional parameters. This latter strategy is recommended.

qMaxPkts

A mandatory integer parameter - the total number of packets that the queue will hold. In order to set this, you should take into account the queuing delay of a queue at the target queue size (normally 1/3 of the total number of packets) and also the memory usage. (You might use the MTU times the half queue size.) If you have no clues, then try 200.

bps

A mandatory integer parameter - the bits per second rate of your interface in the direction of the packet. If you are using SDSL this could be anything from 250000 to 1500000. If your are configuring an upstream ADSL, this could be anything from 56000 to 250000.

mtu

A mandatory integer parameter - the Maximum Transmission Unit (MTU). You can find this out using the ifconfig command.

th1

An optional integer parameter - This is the number of packets below which the dropping probability is set to zero. This will be set to qMaxPkts/6 if not specified.

th2

An optional integer parameter - Knee of the packet dropping probability curve, after which the probability of marking slopes to 1. If not specified, this will be set to qMaxPkts/2.

th3

An optional integer parameter - Queue size in packets after which dropping probablity becomes 1. If not specified, this will be set to th2 * 2, which would normally be qMaxPkts. If you do not wish the gentle variety of RED, you could set this to be th2+1.

wq

An optional floating point parameter - Used for determining how fast the average queue size is influenced by the real queue size. As each packet arrives, the current queue size is multiplied by (1-wq) and the current queue size times wq is added. If not specified, then this will be set according to the following formula :- "ps = bps / (80 * mtu)" "wq = 1 - exp(ln(0.37)/ps)".

maxcount

An optional integer parameter - As proposed by Floyd et al, this version of ARED uses "Uniform random variables" as opposed to "geometric random variables". If the dropping probability is low, then the number of packets we allow without checking for dropping is potentially high. The queue may be in a different state by that time, so this version of ARED imposes a limit (maxcount) on how many packets enter before we check again. If not specified, this is set to th1/4.

aredIval

An optional floating point parameter - This is "ARED interval" the number of seconds between each adjustment of maxp. If not specified, this is set to half a second.

ED

ED specifies the action for flow notification. The letters of ED must be in order and correspond to (E)xplicit congestion notification and (D)ropping. A capitalised letter selects that feature. Lowercase deselects. "ed" is illegal, because that would mean that targeted packets would be neither dropped or marked. "Ed" indicates that there is to be no dropping. Packets are marked if ECN is supported. "ED" indicates that ECN will be used where it is supported and dropping otherwise. "eD" indicates that targeted packets are to be dropped.

tc(8)

o

Floyd and Jacobson, Random Early Detection gateways for Congestion Avoidance. http://www.aciri.org/floyd/papers/red/red.html

o

Floyd, Gummadi and Shenker, An Algorithm for increasing the robustness of RED’s Active Queue Management. http://www.icir.org/floyd/papers/adaptiveRed.pdf

Stephen Braithwaite Some code originates from the RED queueing discipline and the SFQ discipline which was written by Alexey N. Kuznetsov, <kuznet@ms2.inr.ac.ru>, Alexey Makarenko <makar@phoenix.kharkov.ua>, J Hadi Salim <hadi@nortelnetworks.com>. Manpages maintained by bert hubert <ahu@ds9a.nl>