MEREDT

meredt − Table driven Mice and Elephant Random Early Detection

tc qdisc ... meredt

qMaxPkts npackets bps bits mtu bytes [ th1 npackets ] [ th2 npackets ] [ th3 npackets ] [ wq val ] [ maxCount npackets ] [ aredIval nseconds ] [ flr val ] [ elepQsize BYTES ] [ mFlows NRECS ] [ flowActivSecs SECONDS ] [ IPIPP ] [ ED ] [ fairQfact VAL ] [ fltbl flow table ]

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 some immunity to dropping. The flow length in bytes of each active flow is maintained. This flow length is converted to a flow value by means of a piecewise linear function, which can be specified in table form by the user. As each packet is processed, the flow value of its corresponding flow record contributes to a running average flow value. The dropping probability for the packet given by ARED is multiplied by the flow value for the flow and divided by the average flow value to give the actual dropping probability used. This scheme allows configuration that has a simple mice/elephants cutoff point, or can permit a flow to gradually become an elephant and have some elephants larger than others.

This Mice and Elephants queueing discipline is based on ARED, but unlike mered, this does not use Floyd’s "uniform random variables". Instead, it uses "geometric random variables" as proposed by Floyd, thus permitting the above table driven scheme.

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.

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.

flr

An optional floating point parameter - Used for determining how fast the average flow value is influenced by the flow value of the flow corresponding to each packet as it arrives. As each packet arrives, the current flow value is multiplied by flr and the flow value corresponding to the current packet times (1-flr) is added. If not specified, then this will be set to (1-wq).

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

An optional integer parameter - Flows with no activity are forgotten after this many seconds. If not specified this defaults to 10. As mentioned below, there meredt’s idea of a flow length will be truncated so as not to excees the highest flow length of the flow table.

fltbl

An optional table - The flow table consists of 14 integers separated by spaces. This is treated as 7 X,Y pairs, where X corresponds to the actual flow length in bytes, and Y corresponds to the flow length weighting used to determine packet dropping probabilities. The X values must be in non decreasing order. The Y values must be in strictly increasing order. This queueing disciplines idea of individual flow length will not be permitted to exceed the highest X value, but will be truncated to that whenever it grows larger. The Y values must be in strictly increasing order. If not specified, then flow values are zero until a flow reaches 6000 bytes, and linearly increases to 100 at the point where a flow reaches 30000 bytes.

fairQfact

The fairQfact optional floating point parameter provides a mechanism to alter the behaviour of this filter so that it can be a pure mice and elephants filter or a fair queueing filter, or something in between. It works by reducing the size of this filter’s idea of individual flow lengths in bytes by a value derived by multiplying the total flow target by the the fairQfact and dividing by the number of flows. If fairQfact is set to 0.0 (the default), then this is a pure mice and elephants filter. If it is 1.0 (or a bit above that) and the mice and elephants threshold is low, then this is a fair queuing filter. A compromise is possible by setting in the vicinity of 1.0 and having the mice and elephants threshold not so low. As mentioned above, meredt’s idea of a flow length will be truncated so as not to excees the highest flow length of the flow table.

IPIPP

IPIPP specifies the definition of a flow. The letters of IPIPP must be in order and correspond to destination (I)p number, destination (P)ort number, source (I)p number, source (P)ort number and (P)rotocol in that order. A capitalised letter indicates that the attribute will be used as part of the flow definition. Lowercase indicates that it will not. "ipipp" is illegal, because that would mean there would be no attributes to differentiate between flows.

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

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