Abstracts for RED Gateway Papers

• Gaynor, M. Proactive Packet Dropping Methods for IP Gateways. October 1996.
  
  Abstract: 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.
  
  Abstract: 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.