rfc1016.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,011 行 · 第 1/4 页

Network Working Group                                            W. Prue
Request for Comments:  1016                                    J. Postel
                                                                     ISI
                                                               July 1987

             Something a Host Could Do with Source Quench:

               The Source Quench Introduced Delay (SQuID)

Status of this Memo

   This memo is intended to explore the issue of what a host could do
   with a source quench.  The proposal is for each source host IP module
   to introduce some delay between datagrams sent to the same
   destination host.  This is an "crazy idea paper" and discussion is
   essential.  Distribution of this memo is unlimited.

Introduction

   A gateway may discard Internet datagrams if it does not have the
   buffer space needed to queue the datagrams for output to the next
   network on the route to the destination network.  If a gateway
   discards a datagram, it may send a source quench message to the
   Internet source host of the datagram.  A destination host may also
   send a source quench message if datagrams arrive too fast to be
   processed.  The source quench message is a request to the host to cut
   back the rate at which it is sending traffic to the Internet
   destination.  The gateway may send a source quench message for every
   message that it discards.  On receipt of a source quench message, the
   source host should cut back the rate at which it is sending traffic
   to the specified destination until it no longer receives source
   quench messages from the gateway.  The source host can then gradually
   increase the rate at which it sends traffic to the destination until
   it again receives source quench messages [1,2].

   The gateway or host may send the source quench message when it
   approaches its capacity limit rather than waiting until the capacity
   is exceeded.  This means that the data datagram which triggered the
   source quench message may be delivered.

The SQuID Concept

   Suppose the IP module at the datagram source has a queue of datagrams
   to send, and the IP module has a parameter "D".  D is the introduced
   delay between sending datagrams from the queue to the network.  That
   is, when the IP module discovers a datagram waiting to be sent to the
   network, it sends it to the network then waits time D before even
   looking at the datagram queue again.  Normally, the value of D is



Prue & Postel                                                   [Page 1]

RFC 1016        Source Quench Introduced Delay -- SQuID        July 1987


   zero.

   Imagine that when a source quench is received (or any other signal is
   received that the host should slow down its transmissions to the
   network), the value of D is increased.  As time goes by, the value of
   D is decreased.

The SQuID Algorithm

          on increase event:

               D <-- maximum (D + K, I)
                                        (where K = .020 second,
                                               I = .075 second)

          on decrease event:

               D <-- maximum (D - J, 0)
                                        (where J = .001 second)

   An increase event is receipt of one or more source quenches in a
   event period E, (where E is 2.000 seconds).

   A decrease event is when S time has passed since D was decreased and
   there is a datagram to send (where S is 1.000 seconds).

   A cache of D's is kept for the last M hosts communicated with.

   Note that when no datagrams are sent to a destination for some time
   the D for that destination is not decreased, but, if a destination is
   not used for a long time that D for that destination may fall out of
   the cache.

Possible Refinements

   Keep a separate outgoing queue of datagrams for each destination
   host, local subnet, or network.

   Keep the cache of D's per network or local subnet, instead of per
   host.

   "I" could be based upon the basic speed of the slowest intervening
   network (see Appendix A).

   "D" could be limited to never go below "I" if the above refinement
   were implemented.

   "S" could be based upon the round trip time.



Prue & Postel                                                   [Page 2]

RFC 1016        Source Quench Introduced Delay -- SQuID        July 1987


   "D" could be adjusted datagram by datagram based upon the length of
   the datagrams.  Wait longer after a long datagram.

   The delay algorithm could be implemented such that if a source
   doesn't send a datagram when it is next allowed (the introduced delay
   interval) or for N such intervals that the source gets a credit for
   one and only one free (no delay) datagram.

Implementation Ideas

   Since IP does not normally keep much state information about things,
   we want the default or idle IP to have no state about these D values.
   Since the default D value is zero, let us propose that the IP will
   keep a list of only those destinations with non zero D's.

   When the IP wants to send a datagram, it searches the D-list to see
   if the destination is noted.  If it is not, the D value is zero, so
   the IP sends the datagram at once.  If the destination is listed, the
   IP must wait D time indicated before sending that particular
   datagram.  It could look at a datagram addressed to a different
   destination, and possibly send it in the mean time.

   When the IP receives a source quench, it checks to see if the
   destination in the datagram that caused the source quench is on the
   list.  If so, it adds K to the D value.  If not, it appends the
   destination to the list with the D value set to "I".

A Closer Look At the Problem

   Some implementations of IP send one SQ for every N datagrams they
   discard (for example, N=20) so the SQ messages will not make the
   congestion problem much worse [3].  In such situations any of the
   sources of the 20 datagrams may get the SQ not necessarily the one
   causing the most traffic.  However if a host continues to send
   datagrams at a high rate it has a high probability of receiving a SQ
   message sooner or later.  It is much like a speeder on a highway.
   Not all speeders get speeding tickets but the ones who speed most
   often or most excessively are most likely to be ticketed.  In this
   case they will get a ticket and their car may be destroyed.

   With memory becoming so inexpensive many IP nodes put an artificially
   low limit on the size of their queues so that through node delay will
   not be excessive [4].  For example, if one megabyte of data is
   buffered to be sent over a 56 kb/s line the last datagram will wait
   over 2 minutes before being sent.

   One problem with SQ is that the IP or ICMP specification does not
   have a well defined event to indicate receipt of SQ to higher level



Prue & Postel                                                   [Page 3]

RFC 1016        Source Quench Introduced Delay -- SQuID        July 1987


   protocols.  Therefore many TCP implementations do not get notified
   about SQ events and thus do not react to SQ.  TCP is not the only
   source of IP datagrams either.  Other protocols should also respond
   to SQ events in some appropriate way.  TCP and other protocols at
   that level should do something about a source quench, however,
   discussion of their behavior is beyond the scope of this memo.  Note
   that implementation of SQ processing at one level of protocol should
   not interfere with the behavior of higher level protocols.  This
   however, is difficult to do.

   For protocols using IP which are trying to transfer large amounts of
   data the data flow is most typically very bursty.  TCP for example,
   might send 5-10 segments into a window of 5-10 K bytes then wait for
   the acknowledgment of the data which opens the window again.  NETBLT
   as defined by RFC-998 is a rate based protocol which has parameters
   for burst size and burst rate.

   One purpose of the bursts is to allow the source computer to generate
   several datagrams at once to provide more efficient scheduling.  An
   other reason is to keep the network busy accepting data to maximize
   effective throughput in spite of a potentially large network round
   trip delay.  To send a datagram then wait for an acknowledgment is a
   simple but not efficient protocol on a large wide area network.

   The reasons for efficiencies obtained at the source node by
   generating many datagrams at once are not as applicable in an
   intermediate IP node.  Since each datagram is potentially from a
   different node they must all be treated individually.  Datagrams
   received in a burst may also overload the queue of an intermediate
   node losing datagrams and causing SQs to be generated.  If the queue
   is near a threshold and a burst comes, possibly all of the datagrams
   will be lost.  When datagrams arrive evenly spaced, less datagrams
   are likely to be lost because the inter-arrival time allows the queue
   a little time to empty out.  Therefore datagrams spaced with some
   delay between them may be better for intermediate IP nodes.

   Congestion is most likely to occur at IP nodes which are gateways
   between a slower network and a faster one.  The congestion will be in
   the send queue from the slow network to the fast network.  An SQ
   being returned to the sender will return on the faster network.  (See
   diagram below.)

A Gateway Source Quench Concept

   In order for the SQuID algorithm to work we rely upon the gateways to
   send SQs to us to tell us how we are doing.  Because the loss of a
   single datagram affects data flow so much (see lost datagram
   discussion in Observed Results below) it would be much better for the



Prue & Postel                                                   [Page 4]

RFC 1016        Source Quench Introduced Delay -- SQuID        July 1987


   source IP node if it got a warning before datagrams were discarded.

   We propose gateway IP nodes start SQing before the node is flooded at
   a level we call SQ Keep (SQK) but forward the datagram.  If the queue
   level reaches a critical level, SQ Toss level (SQT), the gateway
   should toss datagrams to resolve the problem unless the datagram is
   an ICMP message.  Even ICMP messages will be tossed if the MaxQ level
   is reached.  Once the gateway starts sending SQs it should continue
   to do so until the queue level goes below a low water mark level
   (SQLW) as shown below.  This is analogous to methods some operating
   systems use to handle memory space management.

   The gateway should try to send SQ to as many of the contributors of
   the congestion as possible but only once per contributor per second
   or two.

   Source Quench Queue Levels

         +--------------+ MaxQ level
         |              |> datagrams tossed & SQed (but not ICMP msgs.)
         +--------------+ SQT level (95%)
         |              |\
         |              | > datagrams SQed but forwarded