Random early detection
Encyclopedia
Random early detection also known as random early discard or random early drop is an active queue management
algorithm. It is also a congestion avoidance algorithm.
In the conventional tail drop
algorithm, a router or other network component
buffers as many packets as it can, and simply drops the ones it cannot buffer. If buffers are constantly full, the network is congested
. Tail drop distributes buffer space unfairly among traffic flows. Tail drop can also lead to TCP global synchronization
as all TCP
connections "hold back" simultaneously, and then step forward simultaneously. Networks become under-utilized and flooded by turns. RED addresses these issues.
) packets based on statistical probabilities
. If the buffer is almost empty, all incoming packets are accepted. As the queue grows, the probability for dropping an incoming packet grows too. When the buffer is full, the probability has reached 1 and all incoming packets are dropped.
RED is more fair than tail drop, in the sense that it does not possess a bias against bursty traffic that uses only a small portion of the bandwidth. The more a host transmits, the more likely it is that its packets are dropped as the probability of a host's packet being dropped is proportional to the amount of data it has in a queue. Early detection helps avoid TCP global synchronization.
, "there are not one, but two bugs in classic RED." Improvements to the algorithm were developed, and a draft paper was prepared, but the paper was never published, and the improvements were not widely disseminated or implemented.
Pure RED does not accommodate quality of service
(QoS) differentiation. weighted RED
(WRED) and RED with In and Out (RIO) provide early detection with QoS considerations.
, DSCP) and/or queues.
The Adaptive / Active RED (ARED) algorithm infers whether to make RED more or less aggressive based on the observation of the average queue length. If the average queue length oscillates around min threshold then early detection is too aggressive. On the other hand if the average queue length oscillates around max threshold then early detection is being too conservative. The algorithm changes the probability according to how aggressive it senses it has been discarding traffic.
See Srikant for an in-depth account on these techniques and their analysis.
Active Queue Management
In Internet routers, active queue management is a technique that consists in dropping or ECN-marking packets before a router's queue is full.-Queue management:...
algorithm. It is also a congestion avoidance algorithm.
In the conventional tail drop
Tail drop
Tail Drop, or Drop Tail, is a simple queue management algorithm used by Internet routers to decide when to drop packets. In contrast to the more complex algorithms like RED and WRED, in Tail Drop all the traffic is not differentiated. Each packet is treated identically...
algorithm, a router or other network component
Computer networking device
'Computer networking devices are units that mediate data in a computer network. Computer networking devices are also called network equipment, Intermediate Systems or InterWorking Unit...
buffers as many packets as it can, and simply drops the ones it cannot buffer. If buffers are constantly full, the network is congested
Network congestion
In data networking and queueing theory, network congestion occurs when a link or node is carrying so much data that its quality of service deteriorates. Typical effects include queueing delay, packet loss or the blocking of new connections...
. Tail drop distributes buffer space unfairly among traffic flows. Tail drop can also lead to TCP global synchronization
TCP global synchronization
TCP global synchronization in Computer networks can happen toTCP/IP flows during periodsof congestion because each sender will reduce their transmission rate at the sametime when packet loss occurs....
as all TCP
Transmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
connections "hold back" simultaneously, and then step forward simultaneously. Networks become under-utilized and flooded by turns. RED addresses these issues.
Operation
RED monitors the average queue size and drops (or marks when used in conjunction with ECNExplicit Congestion Notification
Explicit Congestion Notification is an extension to the Internet Protocol and to the Transmission Control Protocol and is defined in RFC 3168 . ECN allows end-to-end notification of network congestion without dropping packets. ECN is an optional feature that is only used when both endpoints...
) packets based on statistical probabilities
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
. If the buffer is almost empty, all incoming packets are accepted. As the queue grows, the probability for dropping an incoming packet grows too. When the buffer is full, the probability has reached 1 and all incoming packets are dropped.
RED is more fair than tail drop, in the sense that it does not possess a bias against bursty traffic that uses only a small portion of the bandwidth. The more a host transmits, the more likely it is that its packets are dropped as the probability of a host's packet being dropped is proportional to the amount of data it has in a queue. Early detection helps avoid TCP global synchronization.
Problems with Classic RED
According to Van JacobsonVan Jacobson
Van Jacobson is one of the primary contributors to the TCP/IP protocol stack which is the technological foundation of today’s Internet. He is renowned for his pioneering achievements in network performance and scaling....
, "there are not one, but two bugs in classic RED." Improvements to the algorithm were developed, and a draft paper was prepared, but the paper was never published, and the improvements were not widely disseminated or implemented.
Pure RED does not accommodate quality of service
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...
(QoS) differentiation. weighted RED
Weighted random early detection
Weighted random early detection is a queue management algorithm with congestion avoidance capabilities. It is an extension to random early detection where a single queue may have several different queue thresholds. Each queue threshold is associated to a particular traffic class.For example, a...
(WRED) and RED with In and Out (RIO) provide early detection with QoS considerations.
Other variants
In Weighted RED you can have different probabilities for different priorities (IP precedenceType of Service
The type of service field in the IPv4 header has had various purposes over the years, and has been defined in different ways by five RFCs...
, DSCP) and/or queues.
The Adaptive / Active RED (ARED) algorithm infers whether to make RED more or less aggressive based on the observation of the average queue length. If the average queue length oscillates around min threshold then early detection is too aggressive. On the other hand if the average queue length oscillates around max threshold then early detection is being too conservative. The algorithm changes the probability according to how aggressive it senses it has been discarding traffic.
See Srikant for an in-depth account on these techniques and their analysis.
RRED: Robust RED
Robust Random Early Detection (RRED) algorithm was proposed to improve the TCP throughput against Denial-of-Service (DoS) attacks, particularly Low-rate Denial-of-Service (LDoS) attacks. Experiments have confirmed that the existing RED-like algorithms are notably vulnerable under Low-rate Denial-of-Service (LDoS) attacks due to the oscillating TCP queue size caused by the attacks. RRED algorithm can significantly improve the performance of TCP under Low-rate Denial-of-Service attacks.External links
- RED (Random Early Detection) Queue Management. Author: Sally Floyd
- Guduz – A Simple Random Early Detection (RED) Simulator
- Variants of RED. Author: Hei Xiao Jun
- Recent Publications in Random Early Detection (RED) schemes