Random early detection

from Wikipedia, the free encyclopedia
Random Early Detection algorithm en.svg

Random early detection ( RED ), also known as random early discard or random early drop, is an algorithm for a network scheduler to avoid congestion (see congestion avoidancealgorithm).

In the conventional Taildrop algorithm, a router or other network component buffers as many packets as possible and discards those that no longer fit in the queue. When the queue is full, the network is called congested . The Taildrop algorithm does not distribute the queue space fairly between the streams of network participants. Taildrop can also lead to TCP Global Synchronization , whereby all TCP connections wait at the same time and start sending again at the same time after their timeouts have expired . As a result, the networks are either not being used optimally or are overloaded.

This is where RED comes in. It observes the mean queue length and discards (or marks if used in conjunction with ECN ) packets based on statistical probabilities . When the queue is almost empty, all incoming packets are accepted. As the queue grows, so does the likelihood of discarding incoming packets. If it is full (approximately - see maximum upper limit), the probability of discarding is 1 and accordingly all packets are discarded.

RED offers greater fairness than the Taildrop algorithm. The more a host communicates, the more likely it is that its packets will be dropped. Early detection helps avoid TCP global synchronization .

RED takes no account of traffic classes in Quality of Service (QoS). Weighted RED (WRED) and Red In / Out (RIO) provide early detection with regard to QoS.

RED is a way of avoiding network overload. RED-capable network components use a port queue. If several of these buffers are available per port, WRED ( Weighted Random Early Detection ) can be used. RED only informs sender and recipient indirectly about the traffic jam by deleting a few randomly selected packets (usually 1–2%) from the queue when the queue has reached a certain level (e.g. 50%). As the length of the buffer increases, exponentially more packets are deleted the closer the average queue length approaches the 100% mark. The average level is usually calculated over a period of one second. The randomly controlled procedure of RED automatically results in a fair allocation of the bandwidth.

Other variants

Weighted RED (WRED) can assign different probabilities for different priorities and queues.

Adaptive / Active RED (ARED) looks at the average queue length and then decides how aggressively RED should proceed. If the average queue length varies around the lower limit, then the early detection method is too aggressive. If the average queue length varies around the upper limit, then early detection is too conservative. The algorithm alters the likelihood by referring to its ability to "sense" the aggressiveness of discarding traffic.

Web links