Random Early Discard (RED) Queue Evaluation for Congestion Control

Random Early Discard (RED) Queue Evaluation for Congestion Control

Md. Shohidul Islam (Dhaka University of Engineering & Technology, Bangladesh), Md. Niaz Morshed (Dhaka University of Engineering & Technology, Bangladesh), Sk. Shariful Islam (Dhaka University of Engineering & Technology, Bangladesh) and Md. Mejbahul Azam (Dhaka University of Engineering & Technology, Bangladesh)
DOI: 10.4018/978-1-4666-0203-8.ch012
OnDemand PDF Download:
List Price: $37.50


Congestion is an un-avoiding issue of networking, and many attempts and mechanisms have been devised to avoid and control congestion in diverse ways. Random Early Discard (RED) is one of such type of algorithm that applies the techniques of Active Queue Management (AQM) to prevent and control congestion and to provide a range of Internet performance facilities. In this chapter, performance of RED algorithm has been measured from different point of views. RED works with Transmission Control Protocol (TCP), and since TCP has several variants, the authors investigated which versions of TCP behave well with RED in terms of few network parameters. Also, performance of RED has been compared with its counterpart Drop Tail algorithm. These statistics are immensely necessary to select the best protocol for Internet performance optimization.
Chapter Preview

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).

Complete Chapter List

Search this Book: