Abstracts for RED Gateway Papers
Last modified: October 1996
Proactive Packet Dropping Methods for IP Gateways.
Packet switching technology has seen a tremendous raise in
popularity with the rapid growth in the Internet. Like the freeways
built for traffic of the 1960's that now face gridlock with traffic
patterns of the 1990's, the Internet now faces congestion at the more
popular times of the day. Situations arise where there are simply too
many data packets. Sometimes discarding packets is necessary. This
paper compares two different proactive packet dropping methods using
several traffic scenarios. We test both Random Early Drop (RED) and a
proposed modification to it called Derivative Random Drop (DRD) with
steady state and dynamic traffic models. Our tests use an actual
implementation. By calculating the probability of packet discard for
each packet the computation cost of our efficient coding of RED
required between 200 to over 400 cycles per packet. Our method called
DRD, gives similar TCP performance, but only requiresbetween 50 to
200 cycles per packet. The code for DRD is simpler than RED and
requires no hardware/operating system dependent operations involving
timing how long the queue has been empty. DRD, like RED, is fair for
both greedy and constant low bandwidth TCP connections for our limited
tests. Both methods allow controlling of the average queue
length. DRD maintains a smoother average queue size with less than 1/2
the variance that RED gives. The memory requirements for our
efficient implementation of DRD are small and require only a few
variables and an optional array of random numbers.
Comments from Sally:
As far as I know, this paper contains the only publicly-available RED
implementation. The paper also proposes a modification to RED, called
DRD. While DRD is simplier than RED, it computes the packet-dropping
probability as a function of the instantaneous queue size instead of
the estimated average queue size. The dangers of this are discussed in
``Notes on Testing RED Implementations''.
Villamizar, C., and Song, C.,
High Performance TCP in ANSNET.
Computer Communications Review, V. 24 N. 5, October 1994, p. 45-60.
This report concentrates on specific requirements and goals of the
research networks supported by ANSNET, but applies to any TCP dominated
high speed WAN and in particular those striving to support high speed
end-to-end flows. Measurements have been made under conditions
intended to better understand performance barriers imposed by queueing
capacities and queue drop strategies. The IBM RS/6000 based routers
currently supporting ANSNET performed very well in these tests.
Measurements have been made with the current software and performance
enhanced software. Single TCP flows are able to achieve 40 Mb/s and
competing multiple TCP flows achieve over 41 Mb/s link utilization on
44.7 Mb/s DS3 links with delays comparable to US cross continent ANSNET
delays. Congestion collapse is demonstrated with intentionally reduced
queueing capacity and using window sizes much larger than optimal. A
variation of Floyd and Jacobson's random early detection (RED)
algorithm is tested. Performance improved with the use of RED for tests
involving multiple flows. With RED and queueing capacity at or above
the delay bandwidth product, congestion collapse is avoided, allowing
the window size to safely be set arbitrarily high. Queueing capacity
greater than or equal to the delay bandwidth product and RED are
recommended. RED provides performance improvement in all but the single
flow case, but cannot substitute for adequate queueing capacity,
particularly if high speed flows are to be supported.