TCP congestion: Random Early Detection (RED)

With increasingly high-speed networks, it is increasingly important to have mechanisms that keep throughput high but average queue sizes low. Congestion avoidance scheme maintains the network in a region of low delay and high throughput.

Congestion Avoidance Overview

CA technics monitor the network traffic loads in an effort to anticipate and avoid congestion.  Congestion avoidance is achieved through packet dropping. Some CA mechanisms provided by Cisco IOS:

• Tail drop
• WRED (Cisco implementations of RED) WRED differs from other congestion avoidance techniques such as queueing strategies because it attempts to anticipate and avoid congestion rather than control congestion once it occurs.

Difference RED and Tail drop

In Tail drop traffic is not differentiated. When the queue is full, all arriving packets are dropped

Random Early Detection (RED)

RED was proposed by Floyd and Van Jacobson in the early 1990s to address network congestion in a responsive rather than reactive manner. It is a congestion avoidance mechanism. The main goal is to provide congestion avoidance by controlling the average queue size.  Other goals are the avoidance of global synchronization* and introduce fairness to reduce the bias against bursty traffic

• TCP global synchronization in computer networks can happen to TCP/IP flow during periods of congestion because each sender will reduce and then increase their transmission rate at the same time when packet loss occurs)

What Random and Early means?

Random: In order to avoid biases against bursty traffic and global synchronization, RED uses randomization in choosing which arriving packets to drop or mark.

Early: The “early” part of the RED acronym suggests that the router drops the packet earlier than it would have to, so as to notify the source that it should decrease its congestion window sooner than it would normally.

How it works

RED mechanism detects incipient congestion and decides which connections to notify of congestion at the gateway

RED algorithm process

RED aims to control the average queue size by informing the end host to slow down the transmission of packets. It monitors the average queue size and drops or marks packets based on statistical probabilities

The following process is performed:

1. We have an incoming packet
2. The average queue length is computed
3. If avr<min length threshold then the packet is placed in the queue
4. If min<avr<max qulen thres then check dropping probability (Pa)
   1. If high probability => packet is dropped
   2. If low probability => packed placed in the queue

5. If avr>max =>packet is dropped

The rate of packet drop increases linearly as the average queue size increases until the average queue size reaches the maximum threshold. The packet drop probability is based on the minimum threshold, maximum threshold, and mark probability denominator.

Packet Drop Probability

When the average queue depth is above the minimum threshold, RED starts dropping packets. The rate of packet drop increases linearly as the average queue size increases until the average queue size reaches the maximum threshold

The min thres should be high enough to maximize link usage. If the min thres is too low, then may packets be dropped unnecessarily.

Also, the difference between min and max thres should be enough in order to avoid global synchronization. If the difference is not enough, then senders will back-off almost at the same time. With RED we avoid TCP global synchronization. RED gateways avoid global synchronization by marking packets at as low a rate as possible

Variants of RED

• Weighted Random Early Detection
• RED with the Unresponsive Flow Identification
• Flow Random Early Detection
• Balanced Random Early Detection
• Stabilized Random Early Detection

WRED

Weighted RED (WRED) is the RED implementation for the cisco ios which generally drops packets selectively based on the IP precedence. It can selectively discard lower priority traffic when the interface begins to get congested and provide differentiated performance characteristics for different classes of service.

For interfaces configured to use the Resource Reservation Protocol (RSVP) feature, WRED chooses packets from other flows to drop rather than the RSVP flows. Also, IP Precedence governs which packets are dropped—traffic that is at lower precedence has a higher drop rate and therefore is more likely to be throttled back.