home *** CD-ROM | disk | FTP | other *** search
/ Internet Core Protocols / Oreilly-InternetCoreProtocols.iso / RFCs / rfc2309.txt < prev    next >
Encoding:
Text File  |  1999-10-14  |  38.1 KB  |  956 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                 B. Braden, USC/ISI
  8. Request for Comments: 2309                             D. Clark, MIT LCS
  9. Category: Informational                                J. Crowcroft, UCL
  10.                                                  B. Davie, Cisco Systems
  11.                                                S. Deering, Cisco Systems
  12.                                                           D. Estrin, USC
  13.                                                           S. Floyd, LBNL
  14.                                                        V. Jacobson, LBNL
  15.                                                   G. Minshall, Fiberlane
  16.                                                        C. Partridge, BBN
  17.                                       L. Peterson, University of Arizona
  18.                                       K. Ramakrishnan, ATT Labs Research
  19.                                                   S. Shenker, Xerox PARC
  20.                                                   J. Wroclawski, MIT LCS
  21.                                                           L. Zhang, UCLA
  22.                                                               April 1998
  23.  
  24.  
  25.  
  26.      Recommendations on Queue Management and Congestion Avoidance
  27.                             in the Internet
  28.  
  29.  
  30.  
  31. Status of Memo
  32.  
  33.       This memo provides information for the Internet community.  It
  34.       does not specify an Internet standard of any kind.  Distribution
  35.       of this memo is unlimited.
  36.  
  37. Copyright Notice
  38.  
  39.       Copyright (C) The Internet Society (1998).  All Rights Reserved.
  40.  
  41. Abstract
  42.  
  43.       This memo presents two recommendations to the Internet community
  44.       concerning measures to improve and preserve Internet performance.
  45.       It presents a strong recommendation for testing, standardization,
  46.       and widespread deployment of active queue management in routers,
  47.       to improve the performance of today's Internet.  It also urges a
  48.       concerted effort of research, measurement, and ultimate deployment
  49.       of router mechanisms to protect the Internet from flows that are
  50.       not sufficiently responsive to congestion notification.
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Braden, et. al.              Informational                      [Page 1]
  59.  
  60. RFC 2309          Internet Performance Recommendations        April 1998
  61.  
  62.  
  63. 1. INTRODUCTION
  64.  
  65.    The Internet protocol architecture is based on a connectionless end-
  66.    to-end packet service using the IP protocol.  The advantages of its
  67.    connectionless design, flexibility and robustness, have been amply
  68.    demonstrated.  However, these advantages are not without cost:
  69.    careful design is required to provide good service under heavy load.
  70.    In fact, lack of attention to the dynamics of packet forwarding can
  71.    result in severe service degradation or "Internet meltdown".  This
  72.    phenomenon was first observed during the early growth phase of the
  73.    Internet of the mid 1980s [Nagle84], and is technically called
  74.    "congestion collapse".
  75.  
  76.    The original fix for Internet meltdown was provided by Van Jacobson.
  77.    Beginning in 1986, Jacobson developed the congestion avoidance
  78.    mechanisms that are now required in TCP implementations [Jacobson88,
  79.    HostReq89].  These mechanisms operate in the hosts to cause TCP
  80.    connections to "back off" during congestion.  We say that TCP flows
  81.    are "responsive" to congestion signals (i.e., dropped packets) from
  82.    the network.  It is primarily these TCP congestion avoidance
  83.    algorithms that prevent the congestion collapse of today's Internet.
  84.  
  85.    However, that is not the end of the story.  Considerable research has
  86.    been done on Internet dynamics since 1988, and the Internet has
  87.    grown.  It has become clear that the TCP congestion avoidance
  88.    mechanisms [RFC2001], while necessary and powerful, are not
  89.    sufficient to provide good service in all circumstances.  Basically,
  90.    there is a limit to how much control can be accomplished from the
  91.    edges of the network.  Some mechanisms are needed in the routers to
  92.    complement the endpoint congestion avoidance mechanisms.
  93.  
  94.    It is useful to distinguish between two classes of router algorithms
  95.    related to congestion control: "queue management" versus "scheduling"
  96.    algorithms.  To a rough approximation, queue management algorithms
  97.    manage the length of packet queues by dropping packets when necessary
  98.    or appropriate, while scheduling algorithms determine which packet to
  99.    send next and are used primarily to manage the allocation of
  100.    bandwidth among flows.  While these two router mechanisms are closely
  101.    related, they address rather different performance issues.
  102.  
  103.    This memo highlights two router performance issues.  The first issue
  104.    is the need for an advanced form of router queue management that we
  105.    call "active queue management."  Section 2 summarizes the benefits
  106.    that active queue management can bring.  Section 3 describes a
  107.    recommended active queue management mechanism, called Random Early
  108.    Detection or "RED".  We expect that the RED algorithm can be used
  109.    with a wide variety of scheduling algorithms, can be implemented
  110.    relatively efficiently, and will provide significant Internet
  111.  
  112.  
  113.  
  114. Braden, et. al.              Informational                      [Page 2]
  115.  
  116. RFC 2309          Internet Performance Recommendations        April 1998
  117.  
  118.  
  119.    performance improvement.
  120.  
  121.    The second issue, discussed in Section 4 of this memo, is the
  122.    potential for future congestion collapse of the Internet due to flows
  123.    that are unresponsive, or not sufficiently responsive, to congestion
  124.    indications.  Unfortunately, there is no consensus solution to
  125.    controlling congestion caused by such aggressive flows; significant
  126.    research and engineering will be required before any solution will be
  127.    available.  It is imperative that this work be energetically pursued,
  128.    to ensure the future stability of the Internet.
  129.  
  130.    Section 5 concludes the memo with a set of recommendations to the
  131.    IETF concerning these topics.
  132.  
  133.    The discussion in this memo applies to "best-effort" traffic.  The
  134.    Internet integrated services architecture, which provides a mechanism
  135.    for protecting individual flows from congestion, introduces its own
  136.    queue management and scheduling algorithms [Shenker96, Wroclawski96].
  137.    Similarly, the discussion of queue management and congestion control
  138.    requirements for differential services is a separate issue.  However,
  139.    we do not expect the deployment of integrated services and
  140.    differential services to significantly diminish the importance of the
  141.    best-effort traffic issues discussed in this memo.
  142.  
  143.    Preparation of this memo resulted from past discussions of end-to-end
  144.    performance, Internet congestion, and RED in the End-to-End Research
  145.    Group of the Internet Research Task Force (IRTF).
  146.  
  147. 2. THE NEED FOR ACTIVE QUEUE MANAGEMENT
  148.  
  149.    The traditional technique for managing router queue lengths is to set
  150.    a maximum length (in terms of packets) for each queue, accept packets
  151.    for the queue until the maximum length is reached, then reject (drop)
  152.    subsequent incoming packets until the queue decreases because a
  153.    packet from the queue has been transmitted.  This technique is known
  154.    as "tail drop", since the packet that arrived most recently (i.e.,
  155.    the one on the tail of the queue) is dropped when the queue is full.
  156.    This method has served the Internet well for years, but it has two
  157.    important drawbacks.
  158.  
  159.    1.   Lock-Out
  160.  
  161.         In some situations tail drop allows a single connection or a few
  162.         flows to monopolize queue space, preventing other connections
  163.         from getting room in the queue.  This "lock-out" phenomenon is
  164.         often the result of synchronization or other timing effects.
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Braden, et. al.              Informational                      [Page 3]
  171.  
  172. RFC 2309          Internet Performance Recommendations        April 1998
  173.  
  174.  
  175.    2.   Full Queues
  176.  
  177.         The tail drop discipline allows queues to maintain a full (or,
  178.         almost full) status for long periods of time, since tail drop
  179.         signals congestion (via a packet drop) only when the queue has
  180.         become full.  It is important to reduce the steady-state queue
  181.         size, and this is perhaps queue management's most important
  182.         goal.
  183.  
  184.         The naive assumption might be that there is a simple tradeoff
  185.         between delay and throughput, and that the recommendation that
  186.         queues be maintained in a "non-full" state essentially
  187.         translates to a recommendation that low end-to-end delay is more
  188.         important than high throughput.  However, this does not take
  189.         into account the critical role that packet bursts play in
  190.         Internet performance.  Even though TCP constrains a flow's
  191.         window size, packets often arrive at routers in bursts
  192.         [Leland94].  If the queue is full or almost full, an arriving
  193.         burst will cause multiple packets to be dropped.  This can
  194.         result in a global synchronization of flows throttling back,
  195.         followed by a sustained period of lowered link utilization,
  196.         reducing overall throughput.
  197.  
  198.         The point of buffering in the network is to absorb data bursts
  199.         and to transmit them during the (hopefully) ensuing bursts of
  200.         silence.  This is essential to permit the transmission of bursty
  201.         data.  It should be clear why we would like to have normally-
  202.         small queues in routers: we want to have queue capacity to
  203.         absorb the bursts.  The counter-intuitive result is that
  204.         maintaining normally-small queues can result in higher
  205.         throughput as well as lower end-to-end delay.  In short, queue
  206.         limits should not reflect the steady state queues we want
  207.         maintained in the network; instead, they should reflect the size
  208.         of bursts we need to absorb.
  209.  
  210.    Besides tail drop, two alternative queue disciplines that can be
  211.    applied when the queue becomes full are "random drop on full" or
  212.    "drop front on full".  Under the random drop on full discipline, a
  213.    router drops a randomly selected packet from the queue (which can be
  214.    an expensive operation, since it naively requires an O(N) walk
  215.    through the packet queue) when the queue is full and a new packet
  216.    arrives.  Under the "drop front on full" discipline [Lakshman96], the
  217.    router drops the packet at the front of the queue when the queue is
  218.    full and a new packet arrives.  Both of these solve the lock-out
  219.    problem, but neither solves the full-queues problem described above.
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. Braden, et. al.              Informational                      [Page 4]
  227.  
  228. RFC 2309          Internet Performance Recommendations        April 1998
  229.  
  230.  
  231.    We know in general how to solve the full-queues problem for
  232.    "responsive" flows, i.e., those flows that throttle back in response
  233.    to congestion notification.  In the current Internet, dropped packets
  234.    serve as a critical mechanism of congestion notification to end
  235.    nodes.  The solution to the full-queues problem is for routers to
  236.    drop packets before a queue becomes full, so that end nodes can
  237.    respond to congestion before buffers overflow.  We call such a
  238.    proactive approach "active queue management".  By dropping packets
  239.    before buffers overflow, active queue management allows routers to
  240.    control when and how many packets to drop.  The next section
  241.    introduces RED, an active queue management mechanism that solves both
  242.    problems listed above (given responsive flows).
  243.  
  244.    In summary, an active queue management mechanism can provide the
  245.    following advantages for responsive flows.
  246.  
  247.    1.   Reduce number of packets dropped in routers
  248.  
  249.         Packet bursts are an unavoidable aspect of packet networks
  250.         [Willinger95].  If all the queue space in a router is already
  251.         committed to "steady state" traffic or if the buffer space is
  252.         inadequate, then the router will have no ability to buffer
  253.         bursts.  By keeping the average queue size small, active queue
  254.         management will provide greater capacity to absorb naturally-
  255.         occurring bursts without dropping packets.
  256.  
  257.         Furthermore, without active queue management, more packets will
  258.         be dropped when a queue does overflow.  This is undesirable for
  259.         several reasons.  First, with a shared queue and the tail drop
  260.         discipline, an unnecessary global synchronization of flows
  261.         cutting back can result in lowered average link utilization, and
  262.         hence lowered network throughput.  Second, TCP recovers with
  263.         more difficulty from a burst of packet drops than from a single
  264.         packet drop.  Third, unnecessary packet drops represent a
  265.         possible waste of bandwidth on the way to the drop point.
  266.  
  267.         We note that while RED can manage queue lengths and reduce end-
  268.         to-end latency even in the absence of end-to-end congestion
  269.         control, RED will be able to reduce packet dropping only in an
  270.         environment that continues to be dominated by end-to-end
  271.         congestion control.
  272.  
  273.    2.   Provide lower-delay interactive service
  274.  
  275.         By keeping the average queue size small, queue management will
  276.         reduce the delays seen by flows.  This is particularly important
  277.         for interactive applications such as short Web transfers, Telnet
  278.         traffic, or interactive audio-video sessions, whose subjective
  279.  
  280.  
  281.  
  282. Braden, et. al.              Informational                      [Page 5]
  283.  
  284. RFC 2309          Internet Performance Recommendations        April 1998
  285.  
  286.  
  287.         (and objective) performance is better when the end-to-end delay
  288.         is low.
  289.  
  290.    3.   Avoid lock-out behavior
  291.  
  292.         Active queue management can prevent lock-out behavior by
  293.         ensuring that there will almost always be a buffer available for
  294.         an incoming packet.  For the same reason, active queue
  295.         management can prevent a router bias against low bandwidth but
  296.         highly bursty flows.
  297.  
  298.         It is clear that lock-out is undesirable because it constitutes
  299.         a gross unfairness among groups of flows.  However, we stop
  300.         short of calling this benefit "increased fairness", because
  301.         general fairness among flows requires per-flow state, which is
  302.         not provided by queue management.  For example, in a router
  303.         using queue management but only FIFO scheduling, two TCP flows
  304.         may receive very different bandwidths simply because they have
  305.         different round-trip times [Floyd91], and a flow that does not
  306.         use congestion control may receive more bandwidth than a flow
  307.         that does.  Per-flow state to achieve general fairness might be
  308.         maintained by a per-flow scheduling algorithm such as Fair
  309.         Queueing (FQ) [Demers90], or a class-based scheduling algorithm
  310.         such as CBQ [Floyd95], for example.
  311.  
  312.         On the other hand, active queue management is needed even for
  313.         routers that use per-flow scheduling algorithms such as FQ or
  314.         class-based scheduling algorithms such as CBQ.  This is because
  315.         per-flow scheduling algorithms by themselves do nothing to
  316.         control the overall queue size or the size of individual queues.
  317.         Active queue management is needed to control the overall average
  318.         queue sizes, so that arriving bursts can be accommodated without
  319.         dropping packets.  In addition, active queue management should
  320.         be used to control the queue size for each individual flow or
  321.         class, so that they do not experience unnecessarily high delays.
  322.         Therefore, active queue management should be applied across the
  323.         classes or flows as well as within each class or flow.
  324.  
  325.         In short, scheduling algorithms and queue management should be
  326.         seen as complementary, not as replacements for each other.  In
  327.         particular, there have been implementations of queue management
  328.         added to FQ, and work is in progress to add RED queue management
  329.         to CBQ.
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Braden, et. al.              Informational                      [Page 6]
  339.  
  340. RFC 2309          Internet Performance Recommendations        April 1998
  341.  
  342.  
  343. 3. THE QUEUE MANAGEMENT ALGORITHM "RED"
  344.  
  345.    Random Early Detection, or RED, is an active queue management
  346.    algorithm for routers that will provide the Internet performance
  347.    advantages cited in the previous section [RED93].  In contrast to
  348.    traditional queue management algorithms, which drop packets only when
  349.    the buffer is full, the RED algorithm drops arriving packets
  350.    probabilistically.  The probability of drop increases as the
  351.    estimated average queue size grows.  Note that RED responds to a
  352.    time-averaged queue length, not an instantaneous one.  Thus, if the
  353.    queue has been mostly empty in the "recent past", RED won't tend to
  354.    drop packets (unless the queue overflows, of course!). On the other
  355.    hand, if the queue has recently been relatively full, indicating
  356.    persistent congestion, newly arriving packets are more likely to be
  357.    dropped.
  358.  
  359.    The RED algorithm itself consists of two main parts: estimation of
  360.    the average queue size and the decision of whether or not to drop an
  361.    incoming packet.
  362.  
  363.  
  364.    (a) Estimation of Average Queue Size
  365.  
  366.         RED estimates the average queue size, either in the forwarding
  367.         path using a simple exponentially weighted moving average (such
  368.         as presented in Appendix A of [Jacobson88]), or in the
  369.         background (i.e., not in the forwarding path) using a similar
  370.         mechanism.
  371.  
  372.            Note: The queue size can be measured either in units of
  373.            packets or of bytes.  This issue is discussed briefly in
  374.            [RED93] in the "Future Work" section.
  375.  
  376.            Note: when the average queue size is computed in the
  377.            forwarding path, there is a special case when a packet
  378.            arrives and the queue is empty.  In this case, the
  379.            computation of the average queue size must take into account
  380.            how much time has passed since the queue went empty.  This is
  381.            discussed further in [RED93].
  382.  
  383.  
  384.    (b) Packet Drop Decision
  385.  
  386.         In the second portion of the algorithm, RED decides whether or
  387.         not to drop an incoming packet.  It is RED's particular
  388.         algorithm for dropping that results in performance improvement
  389.         for responsive flows.  Two RED parameters, minth (minimum
  390.         threshold) and maxth (maximum threshold), figure prominently in
  391.  
  392.  
  393.  
  394. Braden, et. al.              Informational                      [Page 7]
  395.  
  396. RFC 2309          Internet Performance Recommendations        April 1998
  397.  
  398.  
  399.         this decision process.  Minth specifies the average queue size
  400.         *below which* no packets will be dropped, while maxth specifies
  401.         the average queue size *above which* all packets will be
  402.         dropped.  As the average queue size varies from minth to maxth,
  403.         packets will be dropped with a probability that varies linearly
  404.         from 0 to maxp.
  405.  
  406.            Note: a simplistic method of implementing this would be to
  407.            calculate a new random number at each packet arrival, then
  408.            compare that number with the above probability which varies
  409.            from 0 to maxp.  A more efficient implementation, described
  410.            in [RED93], computes a random number *once* for each dropped
  411.            packet.
  412.  
  413.            Note: the decision whether or not to drop an incoming packet
  414.            can be made in "packet mode", ignoring packet sizes, or in
  415.            "byte mode", taking into account the size of the incoming
  416.            packet.  The performance implications of the choice between
  417.            packet mode or byte mode is discussed further in [Floyd97].
  418.  
  419.    RED effectively controls the average queue size while still
  420.    accommodating bursts of packets without loss.  RED's use of
  421.    randomness breaks up synchronized processes that lead to lock-out
  422.    phenomena.
  423.  
  424.    There have been several implementations of RED in routers, and papers
  425.    have been published reporting on experience with these
  426.    implementations ([Villamizar94], [Gaynor96]).  Additional reports of
  427.    implementation experience would be welcome, and will be posted on the
  428.    RED web page [REDWWW].
  429.  
  430.    All available empirical evidence shows that the deployment of active
  431.    queue management mechanisms in the Internet would have substantial
  432.    performance benefits.  There are seemingly no disadvantages to using
  433.    the RED algorithm, and numerous advantages.  Consequently, we believe
  434.    that the RED active queue management algorithm should be widely
  435.    deployed.
  436.  
  437.    We should note that there are some extreme scenarios for which RED
  438.    will not be a cure, although it won't hurt and may still help.  An
  439.    example of such a scenario would be a very large number of flows,
  440.    each so tiny that its fair share would be less than a single packet
  441.    per RTT.
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Braden, et. al.              Informational                      [Page 8]
  451.  
  452. RFC 2309          Internet Performance Recommendations        April 1998
  453.  
  454.  
  455. 4. MANAGING AGGRESSIVE FLOWS
  456.  
  457.    One of the keys to the success of the Internet has been the
  458.    congestion avoidance mechanisms of TCP.  Because TCP "backs off"
  459.    during congestion, a large number of TCP connections can share a
  460.    single, congested link in such a way that bandwidth is shared
  461.    reasonably equitably among similarly situated flows.  The equitable
  462.    sharing of bandwidth among flows depends on the fact that all flows
  463.    are running basically the same congestion avoidance algorithms,
  464.    conformant with the current TCP specification [HostReq89].
  465.  
  466.    We introduce the term "TCP-compatible" for a flow that behaves under
  467.    congestion like a flow produced by a conformant TCP.  A TCP-
  468.    compatible flow is responsive to congestion notification, and in
  469.    steady-state it uses no more bandwidth than a conformant TCP running
  470.    under comparable conditions (drop rate, RTT, MTU, etc.)
  471.  
  472.    It is convenient to divide flows into three classes: (1) TCP-
  473.    compatible flows, (2) unresponsive flows, i.e., flows that do not
  474.    slow down when congestion occurs, and (3) flows that are responsive
  475.    but are not TCP-compatible.  The last two classes contain more
  476.    aggressive flows that pose significant threats to Internet
  477.    performance, as we will now discuss.
  478.  
  479.    o    Non-Responsive Flows
  480.  
  481.         There is a growing set of UDP-based applications whose
  482.         congestion avoidance algorithms are inadequate or nonexistent
  483.         (i.e, the flow does not throttle back upon receipt of congestion
  484.         notification).  Such UDP applications include streaming
  485.         applications like packet voice and video, and also multicast
  486.         bulk data transport [SRM96].  If no action is taken, such
  487.         unresponsive flows could lead to a new congestion collapse.
  488.  
  489.         In general, all UDP-based streaming applications should
  490.         incorporate effective congestion avoidance mechanisms.  For
  491.         example, recent research has shown the possibility of
  492.         incorporating congestion avoidance mechanisms such as Receiver-
  493.         driven Layered Multicast (RLM) within UDP-based streaming
  494.         applications such as packet video [McCanne96; Bolot94]. Further
  495.         research and development on ways to accomplish congestion
  496.         avoidance for streaming applications will be very important.
  497.  
  498.         However, it will also be important for the network to be able to
  499.         protect itself against unresponsive flows, and mechanisms to
  500.         accomplish this must be developed and deployed.  Deployment of
  501.         such mechanisms would provide incentive for every streaming
  502.         application to become responsive by incorporating its own
  503.  
  504.  
  505.  
  506. Braden, et. al.              Informational                      [Page 9]
  507.  
  508. RFC 2309          Internet Performance Recommendations        April 1998
  509.  
  510.  
  511.         congestion control.
  512.  
  513.    o    Non-TCP-Compatible Transport Protocols
  514.  
  515.         The second threat is posed by transport protocol implementations
  516.         that are responsive to congestion notification but, either
  517.         deliberately or through faulty implementations, are not TCP-
  518.         compatible.  Such applications can grab an unfair share of the
  519.         network bandwidth.
  520.  
  521.         For example, the popularity of the Internet has caused a
  522.         proliferation in the number of TCP implementations.  Some of
  523.         these may fail to implement the TCP congestion avoidance
  524.         mechanisms correctly because of poor implementation.  Others may
  525.         deliberately be implemented with congestion avoidance algorithms
  526.         that are more aggressive in their use of bandwidth than other
  527.         TCP implementations; this would allow a vendor to claim to have
  528.         a "faster TCP".  The logical consequence of such implementations
  529.         would be a spiral of increasingly aggressive TCP
  530.         implementations, leading back to the point where there is
  531.         effectively no congestion avoidance and the Internet is
  532.         chronically congested.
  533.  
  534.         Note that there is a well-known way to achieve more aggressive
  535.         TCP performance without even changing TCP: open multiple
  536.         connections to the same place, as has been done in some Web
  537.         browsers.
  538.  
  539.    The projected increase in more aggressive flows of both these
  540.    classes, as a fraction of total Internet traffic, clearly poses a
  541.    threat to the future Internet.  There is an urgent need for
  542.    measurements of current conditions and for further research into the
  543.    various ways of managing such flows.  There are many difficult issues
  544.    in identifying and isolating unresponsive or non-TCP-compatible flows
  545.    at an acceptable router overhead cost.  Finally, there is little
  546.    measurement or simulation evidence available about the rate at which
  547.    these threats are likely to be realized, or about the expected
  548.    benefit of router algorithms for managing such flows.
  549.  
  550.    There is an issue about the appropriate granularity of a "flow".
  551.    There are a few "natural" answers: 1) a TCP or UDP connection (source
  552.    address/port, destination address/port); 2) a source/destination host
  553.    pair; 3) a given source host or a given destination host.  We would
  554.    guess that the source/destination host pair gives the most
  555.    appropriate granularity in many circumstances.  However, it is
  556.    possible that different vendors/providers could set different
  557.    granularities for defining a flow (as a way of "distinguishing"
  558.    themselves from one another), or that different granularities could
  559.  
  560.  
  561.  
  562. Braden, et. al.              Informational                     [Page 10]
  563.  
  564. RFC 2309          Internet Performance Recommendations        April 1998
  565.  
  566.  
  567.    be chosen for different places in the network.  It may be the case
  568.    that the granularity is less important than the fact that we are
  569.    dealing with more unresponsive flows at *some* granularity.  The
  570.    granularity of flows for congestion management is, at least in part,
  571.    a policy question that needs to be addressed in the wider IETF
  572.    community.
  573.  
  574. 5. CONCLUSIONS AND RECOMMENDATIONS
  575.  
  576.    This discussion leads us to make the following recommendations to the
  577.    IETF and to the Internet community as a whole.
  578.  
  579.    o    RECOMMENDATION 1:
  580.  
  581.         Internet routers should implement some active queue management
  582.         mechanism to manage queue lengths, reduce end-to-end latency,
  583.         reduce packet dropping, and avoid lock-out phenomena within the
  584.         Internet.
  585.  
  586.         The default mechanism for managing queue lengths to meet these
  587.         goals in FIFO queues is Random Early Detection (RED) [RED93].
  588.         Unless a developer has reasons to provide another equivalent
  589.         mechanism, we recommend that RED be used.
  590.  
  591.    o    RECOMMENDATION 2:
  592.  
  593.         It is urgent to begin or continue research, engineering, and
  594.         measurement efforts contributing to the design of mechanisms to
  595.         deal with flows that are unresponsive to congestion notification
  596.         or are responsive but more aggressive than TCP.
  597.  
  598.    Although there has already been some limited deployment of RED in the
  599.    Internet, we may expect that widespread implementation and deployment
  600.    of RED in accordance with Recommendation 1 will expose a number of
  601.    engineering issues.  For example, such issues may include:
  602.    implementation questions for Gigabit routers, the use of RED in layer
  603.    2 switches, and the possible use of additional considerations, such
  604.    as priority, in deciding which packets to drop.
  605.  
  606.    We again emphasize that the widespread implementation and deployment
  607.    of RED would not, in and of itself, achieve the goals of
  608.    Recommendation 2.
  609.  
  610.    Widespread implementation and deployment of RED will also enable the
  611.    introduction of other new functionality into the Internet.  One
  612.    example of an enabled functionality would be the addition of explicit
  613.    congestion notification [Ramakrishnan97] to the Internet
  614.    architecture, as a mechanism for congestion notification in addition
  615.  
  616.  
  617.  
  618. Braden, et. al.              Informational                     [Page 11]
  619.  
  620. RFC 2309          Internet Performance Recommendations        April 1998
  621.  
  622.  
  623.    to packet drops.  A second example of new functionality would be
  624.    implementation of queues with packets of different drop priorities;
  625.    packets would be transmitted in the order in which they arrived, but
  626.    during times of congestion packets of the lower drop priority would
  627.    be preferentially dropped.
  628.  
  629. 6. References
  630.  
  631.    [Bolot94] Bolot, J.-C., Turletti, T., and Wakeman, I., Scalable
  632.    Feedback Control for Multicast Video Distribution in the Internet,
  633.    ACM SIGCOMM '94, Sept. 1994.
  634.  
  635.    [Demers90] Demers, A., Keshav, S., and Shenker, S., Analysis and
  636.    Simulation of a Fair Queueing Algorithm, Internetworking: Research
  637.    and Experience, Vol. 1, 1990, pp. 3-26.
  638.  
  639.    [Floyd91] Floyd, S., Connections with Multiple Congested Gateways in
  640.    Packet-Switched Networks Part 1: One-way Traffic.  Computer
  641.    Communications Review, Vol.21, No.5, October 1991, pp.  30-47.  URL
  642.    http://ftp.ee.lbl.gov/floyd/.
  643.  
  644.    [Floyd95] Floyd, S., and Jacobson, V., Link-sharing and Resource
  645.    Management Models for Packet Networks. IEEE/ACM Transactions on
  646.    Networking, Vol. 3 No. 4, pp. 365-386, August 1995.
  647.  
  648.    [Floyd97] Floyd, S., RED: Discussions of Byte and Packet Modes, March
  649.    1997 email, http://www-nrg.ee.lbl.gov/floyd/REDaveraging.txt.
  650.  
  651.    [Gaynor96] Gaynor, M., Proactive Packet Dropping Methods for TCP
  652.    Gateways, October 1996, URL http://www.eecs.harvard.edu/~gaynor/
  653.    final.ps.
  654.  
  655.    [HostReq89] Braden, R., Ed., "Requirements for Internet Hosts --
  656.    Communication Layers", STD 3, RFC 1122, October 1989.
  657.  
  658.    [Jacobson88] V. Jacobson, Congestion Avoidance and Control, ACM
  659.    SIGCOMM '88, August 1988.
  660.  
  661.    [Lakshman96] T. V. Lakshman, Arnie Neidhardt, Teunis Ott, The Drop
  662.    From Front Strategy in TCP Over ATM and Its Interworking with Other
  663.    Control Features, Infocom 96, MA28.1.
  664.  
  665.    [Leland94] W. Leland, M. Taqqu, W. Willinger, and D. Wilson, On the
  666.    Self-Similar Nature of Ethernet Traffic (Extended Version), IEEE/ACM
  667.    Transactions on Networking, 2(1), pp. 1-15, February 1994.
  668.  
  669.  
  670.  
  671.  
  672.  
  673.  
  674. Braden, et. al.              Informational                     [Page 12]
  675.  
  676. RFC 2309          Internet Performance Recommendations        April 1998
  677.  
  678.  
  679.    [McCanne96] McCanne, S., Jacobson, V., and M. Vetterli, Receiver-
  680.    driven Layered Multicast, ACM SIGCOMM
  681.  
  682.    [Nagle84] Nagle, J., "Congestion Control in IP/TCP", RFC 896, January
  683.    1984.
  684.  
  685.    [Ramakrishnan97] Ramakrishnan, K. K., and S. Floyd, "A Proposal to
  686.    add Explicit Congestion Notification (ECN) to IPv6 and to TCP", Work
  687.    in Progress.
  688.  
  689.    [RED93] Floyd, S., and Jacobson, V., Random Early Detection gateways
  690.    for Congestion Avoidance, IEEE/ACM Transactions on Networking, V.1
  691.    N.4, August 1993, pp. 397-413.  Also available from
  692.    http://ftp.ee.lbl.gov/floyd/red.html.
  693.  
  694.    [REDWWW] Floyd, S., The RED Web Page, 1997, URL
  695.    http://ftp.ee.lbl.gov/floyd/red.html.
  696.  
  697.    [RFC 2001] Stevens, W., "TCP Slow Start, Congestion Avoidance, Fast
  698.    Retransmit, and Fast Recovery Algorithms", RFC 2001, January 1997.
  699.  
  700.    [Shenker96] Shenker, S., Partridge, C., and R. Guerin, "Specification
  701.    of Guaranteed Quality of Service", Work in Progress.
  702.  
  703.    [SRM96] Floyd. S., Jacobson, V., McCanne, S., Liu, C., and L. Zhang,
  704.    A Reliable Multicast Framework for Light-weight Sessions and
  705.    Application Level Framing.  ACM SIGCOMM '96, pp 342-355.
  706.  
  707.    [Villamizar94] Villamizar, C., and Song, C., High Performance TCP in
  708.    ANSNET. Computer Communications Review, V. 24 N. 5, October 1994, pp.
  709.    45-60.  URL http://ftp.ans.net/pub/papers/tcp-performance.ps.
  710.  
  711.    [Willinger95] W. Willinger, M. S. Taqqu, R. Sherman, D. V.  Wilson,
  712.    Self-Similarity Through High-Variability:  Statistical Analysis of
  713.    Ethernet LAN Traffic at the Source Level, ACM SIGCOMM '95, pp.  100-
  714.    113, August 1995.
  715.  
  716.    [Wroclawski96] Wroclawski, J., "Specification of the Controlled-Load
  717.    Network Element Service", Work in Progress.
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.  
  730. Braden, et. al.              Informational                     [Page 13]
  731.  
  732. RFC 2309          Internet Performance Recommendations        April 1998
  733.  
  734.  
  735. Security Considerations
  736.  
  737.    While security is a very important issue, it is largely orthogonal to
  738.    the performance issues discussed in this memo.  We note, however,
  739.    that denial-of-service attacks may create unresponsive traffic flows
  740.    that are indistinguishable from flows from normal high-bandwidth
  741.    isochronous applications, and the mechanism suggested in
  742.    Recommendation 2 will be equally applicable to such attacks.
  743.  
  744. Authors' Addresses
  745.  
  746.    Bob Braden
  747.    USC Information Sciences Institute
  748.    4676 Admiralty Way
  749.    Marina del Rey, CA 90292
  750.  
  751.    Phone: 310-822-1511
  752.    EMail: Braden@ISI.EDU
  753.  
  754.    David D. Clark
  755.    MIT Laboratory for Computer Science
  756.    545 Technology Sq.
  757.    Cambridge, MA  02139
  758.  
  759.    Phone: 617-253-6003
  760.    EMail: DDC@lcs.mit.edu
  761.  
  762.    Jon Crowcroft
  763.    University College London
  764.    Department of Computer Science
  765.    Gower Street
  766.    London, WC1E 6BT
  767.    ENGLAND
  768.  
  769.    Phone: +44 171 380 7296
  770.    EMail: Jon.Crowcroft@cs.ucl.ac.uk
  771.  
  772.    Bruce Davie
  773.    Cisco Systems, Inc.
  774.    250 Apollo Drive
  775.    Chelmsford, MA 01824
  776.  
  777.    Phone:
  778.    EMail: bdavie@cisco.com
  779.  
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786. Braden, et. al.              Informational                     [Page 14]
  787.  
  788. RFC 2309          Internet Performance Recommendations        April 1998
  789.  
  790.  
  791.    Steve Deering
  792.    Cisco Systems, Inc.
  793.    170 West Tasman Drive
  794.    San Jose, CA 95134-1706
  795.  
  796.    Phone: 408-527-8213
  797.    EMail: deering@cisco.com
  798.  
  799.    Deborah Estrin
  800.    USC Information Sciences Institute
  801.    4676 Admiralty Way
  802.    Marina del Rey, CA 90292
  803.  
  804.    Phone: 310-822-1511
  805.    EMail: Estrin@usc.edu
  806.  
  807.    Sally Floyd
  808.    Lawrence Berkeley National Laboratory,
  809.    MS 50B-2239,
  810.    One Cyclotron Road,
  811.    Berkeley CA 94720
  812.  
  813.    Phone:  510-486-7518
  814.    EMail: Floyd@ee.lbl.gov
  815.  
  816.    Van Jacobson
  817.    Lawrence Berkeley National Laboratory,
  818.    MS 46A,
  819.    One Cyclotron Road,
  820.    Berkeley CA 94720
  821.  
  822.    Phone: 510-486-7519
  823.    EMail: Van@ee.lbl.gov
  824.  
  825.    Greg Minshall
  826.    Fiberlane Communications
  827.    1399 Charleston Road
  828.    Mountain View, CA  94043
  829.  
  830.    Phone:  +1 650 237 3164
  831.    EMail:  Minshall@fiberlane.com
  832.  
  833.  
  834.  
  835.  
  836.  
  837.  
  838.  
  839.  
  840.  
  841.  
  842. Braden, et. al.              Informational                     [Page 15]
  843.  
  844. RFC 2309          Internet Performance Recommendations        April 1998
  845.  
  846.  
  847.    Craig Partridge
  848.    BBN Technologies
  849.    10 Moulton St.
  850.    Cambridge MA 02138
  851.  
  852.    Phone: 510-558-8675
  853.    EMail: craig@bbn.com
  854.  
  855.    Larry Peterson
  856.    Department of Computer Science
  857.    University of Arizona
  858.    Tucson, AZ 85721
  859.  
  860.    Phone: 520-621-4231
  861.    EMail: LLP@cs.arizona.edu
  862.  
  863.    K. K. Ramakrishnan
  864.    AT&T Labs. Research
  865.    Rm. A155
  866.    180 Park Avenue
  867.    Florham Park, N.J. 07932
  868.  
  869.    Phone: 973-360-8766
  870.    EMail: KKRama@research.att.com
  871.  
  872.    Scott Shenker
  873.    Xerox PARC
  874.    3333 Coyote Hill Road
  875.    Palo Alto, CA 94304
  876.  
  877.    Phone: 415-812-4840
  878.    EMail: Shenker@parc.xerox.com
  879.  
  880.    John Wroclawski
  881.    MIT Laboratory for Computer Science
  882.    545 Technology Sq.
  883.    Cambridge, MA  02139
  884.  
  885.    Phone: 617-253-7885
  886.    EMail: JTW@lcs.mit.edu
  887.  
  888.    Lixia Zhang
  889.    UCLA
  890.    4531G Boelter Hall
  891.    Los Angeles, CA 90024
  892.  
  893.    Phone: 310-825-2695
  894.    EMail: Lixia@cs.ucla.edu
  895.  
  896.  
  897.  
  898. Braden, et. al.              Informational                     [Page 16]
  899.  
  900. RFC 2309          Internet Performance Recommendations        April 1998
  901.  
  902.  
  903. Full Copyright Statement
  904.  
  905.    Copyright (C) The Internet Society (1998).  All Rights Reserved.
  906.  
  907.    This document and translations of it may be copied and furnished to
  908.    others, and derivative works that comment on or otherwise explain it
  909.    or assist in its implementation may be prepared, copied, published
  910.    and distributed, in whole or in part, without restriction of any
  911.    kind, provided that the above copyright notice and this paragraph are
  912.    included on all such copies and derivative works.  However, this
  913.    document itself may not be modified in any way, such as by removing
  914.    the copyright notice or references to the Internet Society or other
  915.    Internet organizations, except as needed for the purpose of
  916.    developing Internet standards in which case the procedures for
  917.    copyrights defined in the Internet Standards process must be
  918.    followed, or as required to translate it into languages other than
  919.    English.
  920.  
  921.    The limited permissions granted above are perpetual and will not be
  922.    revoked by the Internet Society or its successors or assigns.
  923.  
  924.    This document and the information contained herein is provided on an
  925.    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
  926.    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
  927.    BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
  928.    HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
  929.    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954. Braden, et. al.              Informational                     [Page 17]
  955.  
  956.