Random early detection (RED), also known as random early discard or random early drop is a
queuing discipline
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
for a
network scheduler
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
suited for
congestion avoidance
Network congestion in data networking and queueing theory is the reduced quality of service that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay, packet loss or the blocking of ...
.
In the conventional
tail drop
Tail drop is a simple queue management algorithm used by network schedulers in network equipment to decide when to drop packets. With tail drop, when the queue is filled to its maximum capacity, the newly arriving packets are dropped until the qu ...
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
TCP global synchronization in computer networks can happen to
TCP/ IP flows during periods of congestion because each sender will reduce their transmission rate at the same time when packet loss occurs.
Routers on the Internet normally have packe ...
as all
TCP connections "hold back" simultaneously, and then step forward simultaneously. Networks become under-utilized and flooded—alternately, in waves.
RED addresses these issues by pre-emptively dropping packets before the buffer becomes completely full. It uses predictive models to decide which packets to drop. It was invented in the early 1990s by
Sally Floyd
Sally Jean Floyd (May 20, 1950 – August 25, 2019) was an American computer scientist known for her work on computer networking. Formerly associated with the International Computer Science Institute in Berkeley, California, she retired in 2009 a ...
and
Van Jacobson
Van Jacobson (born 1950) is an American computer scientist, renowned for his work on TCP/IP network performance and scaling. .
Operation
RED monitors the average queue size and drops (or marks when used in conjunction with
ECN) packets based on statistical
probabilities. If the buffer is almost empty, then 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 Jacobson, "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. There has been some work in trying to finish off the research and fix the bugs.
Pure RED does not accommodate
quality of service
Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
(QoS) differentiation.
Weighted RED (WRED) and RED with In and Out (RIO) provide early detection with QoS considerations.
Other variants
WRED
In weighted RED you can have different probabilities for different priorities (
IP precedence,
DSCP) and/or queues.
ARED
The adaptive RED or 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 aggressively it senses it has been discarding traffic.
See Srikant
for an in-depth account on these techniques and their analysis.
RRED
Robust random early detection (RRED) algorithm was proposed to improve the TCP throughput against Denial-of-Service (DoS) attacks, particularl
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.
See also
*
Blue (queue management algorithm) Blue is a scheduling discipline for the network scheduler developed by graduate student Wu-chang Feng for Professor Kang G. Shin at the University of Michigan and others at the Thomas J. Watson Research Center of IBM in 1999.
Functioning
Like r ...
*
Active queue management
In Router (computing), routers and network switch, switches, active queue management (AQM) is the policy of dropping packets inside a buffer associated with a network interface controller (NIC) before that buffer becomes full, often with the goal ...
References
External links
RED (Random Early Detection) Queue Management Author: Sally Floyd
Guduz– A Simple Random Early Detection (RED) Simulator
Author: Hei Xiao Jun
Recent Publications in Random Early Detection (RED) schemes
{{DEFAULTSORT:Random Early Detection
Network performance
Network scheduling algorithms
da:Undgåelse af datanet-trafikforstoppelse#RED og WRED