Random early detection

Random early detection, also called random early discard or random early drop and abbreviated RED, is a queuing discipline for a network scheduler suited to congestion avoidance. Under conventional tail drop a router buffers as many packets as it can and drops the rest, which shares buffer space unfairly among traffic flows and can cause TCP global synchronization, where all connections hold back and then speed up together and the network alternates between under-use and flooding. RED instead drops packets pre-emptively before the buffer fills. It monitors the average queue size and drops, or marks when used with explicit congestion notification, packets with a probability that rises as the queue grows, reaching 1 when the buffer is full. It was invented in the early 1990s by Sally Floyd and Van Jacobson. Classic RED has known problems and no quality-of-service differentiation, which led to variants such as weighted RED, RED with In and Out, and adaptive RED.