Random Early Discard (RED) Queue Evaluation for Congestion Control

Literature Review

Active queue management has been recommended by the Internet Engineering Task force (IETF) as a way of mitigating the above stated performance limitations of TCP over drop tail networks. Random Early Detection (RED) is the first active queue management algorithm proposed for deployment in TCP/IP networks (Floyd, Jacobson, 1999). The basic idea behind an active queue management algorithm is to convey congestion notification early to the TCP endpoints so that they can reduce their transmission rates before queue overflow and sustained packet loss occur. It is now widely accepted that RED controlled queue performs better than a drop-tail queue. However, RED has some parameter tuning issues that need to be carefully addressed for it to give good performance under different network scenarios. Random early detection (RED), also known as Random Early Discard or Random Early Drop is an active queue management algorithm (Floyd, Jacobson, 1993). It is also a congestion avoidance algorithm. In the traditional 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 underutilized and flooded by turns. RED addresses these issues. It 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, all incoming packets reaccepted. 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 bursts 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. Early detection helps avoid global synchronization. The most common technique of queue management is a tail drop. In this method packets are accepted as long as there is space in the buffer. When it becomes full, incoming packets are dropped. This kind of approach results in dropping large number of packets in the time of congestion. This can result in lower throughput and TCP synchronization (Floyd, 1997).