MERED

mered − Mice and Elephant Random Early Detection

tc qdisc ... mered

qMaxPkts npackets bps bits mtu bytes [ th1 npackets ] [ th2 npackets ] [ th3 npackets ] [ wq val ] [ maxCount npackets ] [ aredIval nseconds ] [ elepDsize BYTES ] [ elepQsize BYTES ] [ mFlows NRECS ] [ flowActivSecs SECONDS ]

A Mice and Elephants queueing discipline is one which favours short flows over long flows. Flows are classified according to how many bytes have passed in that flow. Flows longer than a given threshold are referred to as elephants. Flows that up until now have not reached that threshold are referred to as mice. Mice and Elephants is a concept that is analagous to shortest job first in scheduling. The short flows gain, and the long flows are no worse off. The Mice are advantaged in two ways. The first is a dropping advantage and the second is a queuing advantage.

The way the dropping advantage works, is that mice packets are given immunity to dropping. This Mice and Elephants queueing discipline is based on ARED, except that the mice are excempt from being dropped. As in the ARED queueing discipline the random dropping uses "Uniform random variables" as opposed to "geometric random variables" as proposed by Floyd. When ARED is decides that a packet should be dropped, the dropping advice is delayed until an elephant packet arrives which can be dropped.

The second way that mice packets are advantaged is that the mice get their own queue which has absolute priority over the queue which contains queued elephant packets.

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.

elepDsize

An optional integer parameter - Once a flow has passed more than this size in bytes, it is regarded as an elephant for the purposes of dropping. If unspecified, this defaults to 10000 bytes.

elepQsize

An optional integer parameter - Once a flow has passed more than this size in bytes, it is regarded as an elephant for the purposes of queuing. If unspecified, this defaults to 6000 bytes.

mFlows

An optional integer parameter - The maximum number of flows that this queueing discipline can keep track of. Packets coming from a new flow after this threshold is reached will not have their flow recognised and will be treated as mice flows. If unspecified, this defaults to qMaxPkts flow records.

flowActivSecs

Flows with no activity are forgotten after this many seconds. If not specified this defaults to 10.

tc(8)

o

Guo and Matta, The War Between Mice and Elephants http://www.cs.bu.edu/techreports/pdf/2001-005-war-tcp-rio.pdf

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