Re: Router Requirements Inactivity

[[e-mail]]

> So, those of you who have writing assignments, and you should know who you
> are, really should get them submitted to the RR mailing list in the next 2
> weeks or so.  If there are no contributions, then there will be nothing to
> discuss, the agenda will be empty, and we'll have no meeting... 

Below is a draft of text to deprecate the ICMP Source Quench messages.
It goes a bit beyond this in terms of discussion, including more
information and references on what people are doing or theorizing
about congestion control.  Most of the text was borrowed from the
latest rreq draft.  

I believe this will be sort of parallel to the main document, since
there was a feeling at the meeting that this was a quick and dirty
thing that could be finished in short order.  (I know that it still
needs page numbers, etc. to be a real draft...)

Comments/concerns?

--Jamshid


Router Requirements (RREQ)				J. Mahdavi
INTERNET DRAFT				  Pgh. Supercomputing Ctr.
						   [e-mail]

	Congestion Control Requirements for IP Routers

	<draft-ietf-rreq-cong-control-require-00.txt>

Status of this Memo

     This document is an Internet-Draft.  Internet-Drafts are working
     documents of the Internet Engineering Task Force (IETF), its
     areas, and its working groups.  Note that other groups may also
     distribute working documents as Internet-Drafts.

     Internet-Drafts are draft documents valid for a maximum of six
     months and may be updated, replaced, or obsoleted by other
     documents at any time.  It is inappropriate to use Internet-
     Drafts as reference material or to cite them other than as
     ``work in progress.''

     To learn the current status of any Internet-Draft, please check
     the ``1id-abstracts.txt'' listing contained in the Internet-
     Drafts Shadow Directories on ds.internic.net (US East Coast),
     nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or
     munnari.oz.au (Pacific Rim).

ABSTRACT

     This memo updates the status of congestion control algorithms
     described in RFC1009 to conform with today's practices.
     Specifically, it deprecates the use of ICMP Source Quench in
     routers as a means of congestion control.  It includes
     discussion of current ad hoc congestion control practices in
     routers, but does not specify further requirements in this
     area. 

1.  Introduction

     This memo updates the status of congestion control algorithms
     described in RFC 1009 to conform with today's practices.  RFC
     1009 specifies that routers must use ICMP Source Quench messages
     to enforce congestion control in cases where routers are forced
     to drop IP datagrams due to congestion.  However, research seems
     to suggest that Source Quench consumes network bandwidth but is
     an ineffective (and unfair) antidote to congestion.  See, for
     example, [Mankin90] and [Finn89].  Section 2 depricates
     the use of ICMP Source Quench as a means of congestion control.
     Section 3 discusses the current thinking on how routers ought to
     deal with overload and network congestion.

2.  ICMP Source Quench Should Not Be Implemented.

     A router SHOULD NOT originate ICMP Source Quench messages.  As
     specified below, a router which does originate Source Quench
     messages MUST be able to limit the rate at which they are
     generated.

     A router MAY ignore any ICMP Source Quench messages it receives.

     A router which sends ICMP Source Quench messages MUST be able to
     limit the rate at which the messages can be generated.  A router
     SHOULD also be able to limit the rate at which it sends other
     sorts of ICMP error messages (Destination Unreachable, Redirect,
     Time Exceeded, Parameter Problem).  The rate limit parameters
     SHOULD be settable as part of the configuration of the router.
     How the limits are applied (e.g., per router or per interface) is
     left to the implementor's discretion.

         DISCUSSION:
            Two problems for a router sending ICMP error
            message are:
            (1)  The consumption of bandwidth on the reverse
                 path, and
            (2)  The use of router resources (e.g., memory,
                 CPU time)

            To help solve these problems a router can limit
            the frequency with which it generates ICMP error
            messages.  For similar reasons, a router may limit
            the frequency at which some other sorts of
            messages, such as ICMP Echo Replies, are
            generated.


         IMPLEMENTATION:
            Various mechanisms have been used or proposed for
            limiting the rate at which ICMP messages are sent:

            (1)  Count-based -- for example, send an ICMP
                 error message for every N dropped packets
                 overall or per given source host.  This
                 mechanism might be appropriate for ICMP
                 Source Quench, but probably not for other
                 types of ICMP messages.

            (2)  Timer-based -- for example, send an ICMP
                 error message to a given source host or
                 overall at most once per T milliseconds.

            (3)  Bandwidth-based -- for example, limit the
                 rate at which ICMP messages are sent over a
                 particular interface to some fraction of the
                 attached network's bandwidth.

     ICMP Source Quench error messages MUST have their IP Precedence
     field set to the same value as the IP Precedence field in the
     packet which provoked the sending of the ICMP Source Quench
     message.  All other ICMP error messages (Destination Unreachable,
     Redirect, Time Exceeded, and Parameter Problem) MUST have their
     precedence value set to 6 (INTERNETWORK CONTROL) or 7 (NETWORK
     CONTROL), SHOULD be 7.  The IP Precedence value for these error
     messages MAY be settable.

     An ICMP reply message MUST have its IP Precedence field set to
     the same value as the IP Precedence field in the ICMP request
     that provoked the reply.

3.  Congestion Control Techniques

     Congestion in a network is loosely defined as a condition where
     demand for resources (usually bandwidth or CPU time) exceeds
     capacity.  Congestion avoidance tries to prevent demand from
     exceeding capacity, while congestion recovery tries to restore an
     operative state.  It is possible for a router to contribute to
     both of these mechanisms.  A great deal of effort has been spent
     studying the problem.  The reader is encouraged to read
     [Mankin91] for a survey of the work.  Important papers on the
     subject include [Nagle87], [Jain], [Jacobson88], and
     [Finn89], among others.

     The amount of storage that router should have available to handle
     peak instantaneous demand when hosts use reasonable congestion
     policies, such as described in [Jacobson88], is a function of the
     product of the bandwidth of the link times the path delay of the
     flows using the link, and therefore storage should increase as
     this Bandwidth*Delay product increases.  The exact function
     relating storage capacity to probability of discard is not known.

     When a router receives a packet beyond its storage capacity it
     must (by definition, not by decree) discard it or some other
     packet or packets.  Which packet to discard is the subject of
     much study but, unfortunately, little agreement so far.

     A router MAY discard the packet it has just received; this is the
     simplest but not the best policy.  It is agreed that some form of
     "strategic drop" algorithm will provide better stability under
     congestion.  Some examples of strategic drop algorithms are
     Random Drop [Hashem89], Early Random Drop [Zhang91], and Random
     Early Detection (RED) [Floyd93].  A router MAY use any of these
     strategic drop algorithms to implement congestion control.

     If a router implements a strategic drop policy (such as RED)
     under which it chooses a packet to discard from among a pool of
     eligible packets:

      +  If precedence-ordered queue service is implemented and
         enabled, the router MUST NOT discard a packet whose IP
         precedence is higher than that of a packet which is not
         discarded.

      +  A router MAY protect packets whose IP headers request
         the "maximize reliability" TOS, except where doing so
         would be in violation of the previous rule.

      +  A router MAY protect fragmented IP packets, on the
         theory that dropping a fragment of a datagram may
         increase congestion by causing all fragments of the
         datagram to be retransmitted by the source.

      +  To help prevent routing perturbations or disruption
         of management functions, the router MAY protect
         packets used for routing control, link control, or
         network management from being discarded.  Dedicated
         routers (i.e.. routers which are not also general
         purpose hosts, terminal servers, etc.) can achieve an
         approximation of this rule by protecting packets
         whose source or destination is the router itself.

     Advanced methods of congestion control include a notion of
     fairness, so that the 'user' that is penalized by losing a packet
     is the one that contributed the most to the congestion.  No
     matter what mechanism is implemented to deal with bandwidth
     congestion control, it is important that the CPU effort expended
     be sufficiently small that the router is not driven into CPU
     congestion also.

     Because a router must (by necessity) discard packets under
     conditions of severe congestion, a router will, by definition,
     implement SOME congestion control algorithm.  While it is not
     specified what algorithm must be implemented, a router SHOULD
     document the congestion control algorithm it uses.  As described
     in Section 2, this document recommends that a router SHOULD NOT
     send a Source Quench to the sender of the packet that it is
     discarding.  ICMP Source Quench is a very weak mechanism, so it
     is not necessary for a router to send it, and host software
     should not use it exclusively as an indicator of congestion.

4.  Acknowledement

     Much of the text for this document was taken from an
     internet-draft router requirements document prepared by Philip
     Almquist.

5.  References

[Finn89]
     G. Finn, "A Connectionless Congestion Control Algorithm,"
     Computer Communications Review, vol. 19, no. 5,
     Association for Computing Machinery, October 1989.

[Floyd93]
     S. Floyd, V. Jacobsen, "Random Early Detection Gateways for 
     Congestion Avoidance", IEEE/ACM Transactions on Networking,
     August 1993.

[Hashem89]
     Hashem, E., "Analysis of random drop for gateway congestion
     control", Report LCS TR-465, Laboratory for Computer Science,
     MIT, Cambridge, MA, 1989, p. 103.

[Jacobson88]
     V. Jacobson, "Congestion Avoidance and Control,"
     Proceedings of SIGCOMM '88, Association for Computing
     Machinery, August 1988.

[Jain]
     R. Jain, K. Ramakrishnan, and D. Chiu, "Congestion
     Avoidance in Computer Networks With a Connectionless
     Network Layer", Technical Report DEC-TR-506, Digital
     Equipment Corporation.

[Mankin90]
     A. Mankin, G. Hollingsworth, G. Reichlen, K. Thompson, R.
     Wilder, and R. Zahavi, "Evaluation of Internet
     Performance -- FY89", Technical Report MTR-89W00216,
     MITRE Corporation, February, 1990.

[Mankin91]
     A. Mankin and K. Ramakrishnan, Editors, "Gateway
     Congestion Control Survey", Request For Comments (RFC)
     1254, DDN Network Information Center, SRI International,
     Menlo Park, California, USA, August 1991.

[Nagle87]
     J. Nagle, "On Packet Switches with Infinite Storage,"
     IEEE Transactions on Communications, vol. COM-35, no. 4,
     April 1987.

[Zhang91]
     L. Zhang, S. Shenker, and D.D. Clark, "Observations on the
     Dynamics of a Congestion Control Algorithm: The Effects of
     Two-Way Traffic," Proc. ACM SIGCOMM '91, pp. 133-148.