Randomly Early Detection Gateways for congestion Avoidance

Different congestion control mechanism has been suggested and implemented to overcome the performance degradation with increasing the use and size of computer network and to keep the network in a region of low delay and high throughput. The congestion detection can occur either TCP at the source or in the gateway which is the most effective detection since the gateway can distinguish between propagation delay and persistence queueing delay.

The paper points out some Congestion avoidance method at the gateway before the description of the own method RED gateway like:

• Random Drop: when new packet arrives to the gateway with full queue, the gateway randomly chooses a packet from the gateway queue to drop.


• Drop Tail: when the queue overflows the gateway drops packet from several connections that result in global synchronization in the network where many connections reduce their window at the same time.


• Early Random Drop: when queue length is more than a certain level, the gateway drops each arrived packet with fixed drop probability. However it can't control on misbehaving sources


• Source Quench message: the gateway sends a Source Quench message to the sources when the queue size reaches to a defined threshold and also the gateway can drop the arriving packets when the queue size approaches the maximum level


• DECbit; a binary feedback in arriving packet header is used to indicate the congestion in the network if the calculated average queue length over a certain time exceed one. At the source, if half the packets over two round trip time had the indicated congestion bit set, then the window is decreased exponentially. Otherwise, the window is linearly increased

Then, the authors focused on three design goal for RED gateway

• CA by controlling on average queue size. it should be kept low while the fluctuation in its actual size must be allowed to avoid transient congestion.


• Avoidance of global synchronization and avoidance of a bias against bursty traffic by using distinict algorithm for congestion detection and for deciding which connectons should be notified of the congestion.


• Effective even in the absence of cooperation from transport layer protocol at the source, such that the gateway drops packets if the average queue size exceed the maximum threshold level rather than setting bit as a feedback.

RED gateway at first calculates the average queue size and compares it with min. and max. thresholds. If the average queue size is lower the min. threshold no action will be taken while if the size is over the max. threshold then the gateway marks every arriving packet even by setting a bit in the packet header or dropping the packet in case of uncooperative sources. When the average queue size is between the min and max threshold, the gateway mark each arriving packet with probability that is roughly proportional to that connection's share of the bandwidth at the gateway
The simulation proved the success of RED gateway to meet the above goal. Moreover, it maximizes global power (ratio of throughput to the delay), and fairness since RED gateway does not discriminate against particular connection and the fraction of marked packets for each connection is roughly proportional to the connection share's of bandwidth.