Congestion Avoidance – WRED

Tail Drop

What happens when there are more packets than the queue length? By default, all these packets are dropped, a process that is called “Tail Drop”. Unfortunately, we will never know what we dropped, maybe packets of an important flow.

Random Early Detection (RED)

Random Early Detection is a fancy word for randomly dropping packets in a queue so we can avoid congestions and not perform Tail Drop. RED takes advantage of the congestion mechanism of TCP, therefor it is only suitable for this kind of traffic. When RED drops a packet, the source will not receive a confirmation for it and will reduce the window size, therefore slowing down the transmission rate. Another advantage of RED is that it avoids Global Synchronization. If all traffic that is over the limit is dropped, then all sources slow down, and then they all begin to send, overwhelming again the link. By randomly dropping traffic, not all sources are affected of a drop at the same time.

Since RED drops the packets randomly, the sources that send more packets are more likely to be affected by those that send fewer packets

RED drops packets based on the Drop Probability. When the average Queue Depth is above the minimum threshold (MIN-TH), RED starts dropping packets. The rate of the packet drop increases linearly as the average queue size increases until it reaches maximum threshold (MAX-TH). At this point, the drop probability is limited to the value known as Mark Probability Denominator. If the average queue size continues to grow until it reaches the Queue Limit, then all the packets are dropped. If the Mark Probability Denominator = X, then 1 out of every X packets is dropped.

To calculate the average Queue Depth, the router uses the following formula:

Average=Averageold(112n)+QueueSizecurrent12nAverage = Average_{old}*(1-\frac{1}{2^n}) + QueueSize_{current}*\frac{1}{2^n}

n is a called the exponential weight factor, and can be configured:

R(config-if)# random-detect exponential-weighting-constant EXPONENT
! EXPONENT = n. Default: 9

Interface level WRED

WRED can selectively discard lower priority traffic when the interface begins to be congested. To enable WRED on an interface, use:

R(config-if)# random-detect

You can’t configure interface-level WRED when CBWFQ is used on the same interface. By default, WRED uses IP Precedence values but it can be configured to use the DSCP values

!Based on IP Precedence
R(config-if)# random-detect prec-based
R(config-if)# random-detect precedence PRECEDENCE MIN-TH MAX-TH MARK-PROB-DENOMINATOR
!Based on DSCP
R(config-if)# random-detect dscp-based
R(config-if)# random-detect dscp DSCP MIN-TH MAX-TH MARK-PROB-DENOMINATOR

To verify WRED configuration, use:

R#show queueing random-detect
!Output for IP Precedence based WRED.
Current random-detect configuration:
    Queueing strategy: random early detection (WRED)
    Random-detect not active on the dialer
    Exp-weight-constant: 9 (1/512)
    Mean queue depth: 0

  class          Random drop      Tail drop    Minimum Maximum  Mark
                  pkts/bytes       pkts/bytes    thresh  thresh  prob
      0      0/0              0/0           20      40  1/10
      1      0/0              0/0           22      40  1/10
      2      0/0              0/0           24      40  1/10
      3      0/0              0/0           26      40  1/10
      4      0/0              0/0           28      40  1/10
      5      0/0              0/0           31      40  1/10
      6      0/0              0/0           33      40  1/10
      7      0/0              0/0           35      40  1/10
   rsvp      0/0              0/0           37      40  1/10

Flow-Based WRED

Flow-Based WRED maintains a count of the number of active flows that exist on an output interface and calculates a number of buffers available for each flow. An Average Queue Size is calculated as:

AverageQueueSize=QueueLimitFlowCountScaleAverage_{QueueSize} =\frac {QueueLimit} {FlowCount}Scale

Flows with a Queue Size that is less than the Average Queue Size will not experience Drops. Flows with a Queue Size greater than the Average Queue Size will start to experience Drops and the MAX-TH is recalculated as

maxTH=minTH+maxTHminTH2\max_{TH} =\min_{TH} + \frac{\max_{TH}-\min_{TH}}2

This will actually bring the MAX-TH closer to the MIN-TH making the Drop Probability to increase quicker.

To enable Flow-Based RED, use:

R(config-if)# random-detect flow

You can set the number of flows to use and a scaling-factor that is used to calculate if the flow is adaptive or not.

R(config-if)# random-detect flow average-depth-factor SCALE
! Sets the scaling factor. Default: 4
R(config-if)# random-detect flow count NUMBER
! Sets the max number of flows

Class Based WRED

WRED can also be set using the MQC, inside the class of a policy, but with similar configuration commands: To enable WRED for a class, use:

R(config-pmap-c)# random-detect

It will enable IP-Precedence based WRED which can be configured with:

R(config-pmap-c)# random-detect prec-based
R(config-pmap-c)# random-detect precedence PRECEDENCE MIN-TH MAX-TH MARK-PROB-DENOMINATOR

You can switch to a DSCP based WRED with:

R(config-pmap-c)# random-detect dscp-based
R(config-pmap-c)# random-detect dscp DSCP MIN-TH MAX-TH MARK-PROB-DENOMINATOR

The Exponential Weight Factor can be configured with

R(config-pmap-c)# random-detect exponential-weighting-constant EXPONENT
! Default:9

You can verify the configuration using the command:

R#show policy-map interface INTERFACE

WRED Explicit Congestion Notification (ECN)

Instead of dropping the packets, ECN marks them in a way similar to the Discard Eligible bit for Frame Relay. The difference is that this marking is done at Layer 3, inside the ToS Byte.

In the IP ToS byte, the first 6 bits are used for DSCP, and the last 2 bits are used for Explicit Congestion Notification. The first bit is called ECT (ECN-capable Transport) and the second bit is called CE (Congestion Experienced). ECN bits are set by the sender to indicate to the router if the endpoints of the connection (sender and receiver) are ECN capable




The endpoints are not ECN capable



The endpoints are ECN capable but no congestion is experienced






The endpoints are ECN capable and congestion is being experienced

If the number of packets in the queue is below the minimum threshold, then packets are transmitted, just like in normal WRED. If the number of packets in the queue exceeds the maximum threshold, then packets are dropped, again, just like in normal WRED.

The difference appears when the number of packets is between the minimum and the maximum threshold. If the endpoints are not ECN-capable (00), the traffic will be dropped according to the probability, just like in normal WRED. If the endpoints are ECN-capable but no congestion is experienced (10 or 01), then if the packet should be dropped based on the probability, it will be marked with (11) and will be transmitted instead. If a congestion is being experienced (11), then the packet is transmitted because it is already marked as such.

The packets that are marked can be dropped at another point in the network if congestion also happens there, or may be forwarded to the next hop.

To enable ECN, use this command when configuring the class inside a policy:

R(config-pmap-c)# random-detect ecn

Last updated