08-16-2017, 10:05 PM
This paper presents Random Early Detection (RED) gateways
for congestion avoidance in packet-switched networks.
The gateway detects incipient congestion by computing
the average queue size. The gateway could notify
connections of congestion either by dropping packets arriving
at the gateway or by setting a bit in packet headers.
When the average queue size exceeds a preset threshold,
the gateway drops or marks each arriving packet with a
certain probability, where the exact probability is a function
of the average queue size.
RED gateways keep the average queue size low while
allowing occasional bursts of packetsin the queue. During
congestion, the probability that the gateway notifies a particular
connection to reduce its window is roughly proportional
to that connection s share of the bandwidth through
the gateway. RED gateways are designed to accompany a
transport-layer congestion control protocol such as TCP.
The RED gateway has no bias against bursty traffic and
avoids the global synchronization of many connections
decreasing their window at the same time. Simulations of
a TCP/IP network are used to illustrate the performance
of RED gateways.
Random early detection (RED), also known as random early discard or random early drop is a queueing discipline for a network scheduler suited for congestion avoidance.[1]
In the conventional 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 under-utilized and flooded by turns. RED addresses these issues.