Summary: RED Gateways

The paper presents a Random Early Detection(RED) gateways for congestion
avoidance in computer networks. The paper is motivated by the need to
provide mechanisms in high speed networks that keep throughput high but
average queue sizes low. The paper inherently assumes that gateway is the
most effective detector of congestion because it monitors the size of
queue over time and can reliably distinguish between prorogation delay and
persistent queuing delay.

In the early sections, the paper discusses the previous related work such
as Random Drop, Drop Tail and Early Random Drop gateways and summarizes
how they fail to make as effective congestion avoidance mechanism. Then,
it discusses the design goals of the RED gateways:
1)provide congestion avoidance by controlling average queue size (detect
incipient congestion that has persisted for a long time)
2)avoidance of global synchronization
3)bias against busty traffic
4)Ability to maintain upper bound on queue size even in the absence of
cooperating transport protocols

The rest of the paper delves into algorithmic details on how these goals
can be achieved by RED gateways and provides simulation results on
varieties of networks to support their arguments. RED gateway uses two
separate algorithms: algorithm to computer average queue size and
algorithm for calculating packet marking probability. Average queue size
is compared with two thresholds, minimum and maximum threshold. If the
average queue size is between these threshold, each arriving packet is
marked with probability P, a function of average queue size. If avg queue
size is less than minimum threshold, no packets are marked. If it exceeds
maximum threshold, every incoming packet is marked. A packet that is
marked can be dropped OR can also be used to set a congestion bit
depending on the support from underlying network. While algorithm for
computing average queue size determines the degree of burstiness, packet
marking probability algorithm determines how frequently gateway marks
packets.

Later parts of this paper provide show how the goals such as congestion
avoidance, global synchronization and fairness is achieved by extensive
simulations under varieties of networks. Finally, paper discusses behavior
of RED gateways vs drop trail gateways under busty traffic loads, and also
how RED gateways can be used to detect misbehaving hosts.
Received on Thu Sep 28 2006 - 11:07:46 EDT