doc: Add RFC documents

1 files changed, 1235 insertions, 0 deletions

diff --git a/doc/rfc/rfc3124.txt b/doc/rfc/rfc3124.txt
new file mode 100644
index 0000000..db57bc3
--- /dev/null
+++ b/doc/rfc/rfc3124.txt
@@ -0,0 +1,1235 @@
+
+
+
+
+
+
+Network Working Group                                    H. Balakrishnan
+Request for Comments: 3124                                       MIT LCS
+Category: Standards Track                                      S. Seshan
+                                                                     CMU
+                                                               June 2001
+
+
+                         The Congestion Manager
+
+
+Status of this Memo
+
+   This document specifies an Internet standards track protocol for the
+   Internet community, and requests discussion and suggestions for
+   improvements.  Please refer to the current edition of the "Internet
+   Official Protocol Standards" (STD 1) for the standardization state
+   and status of this protocol.  Distribution of this memo is unlimited.
+
+Copyright Notice
+
+   Copyright (C) The Internet Society (2001).  All Rights Reserved.
+
+Abstract
+
+   This document describes the Congestion Manager (CM), an end-system
+   module that:
+
+   (i) Enables an ensemble of multiple concurrent streams from a sender
+   destined to the same receiver and sharing the same congestion
+   properties to perform proper congestion avoidance and control, and
+
+   (ii) Allows applications to easily adapt to network congestion.
+
+1. Conventions used in this document:
+
+   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
+   document are to be interpreted as described in RFC-2119 [Bradner97].
+
+   STREAM
+
+      A group of packets that all share the same source and destination
+      IP address, IP type-of-service, transport protocol, and source and
+      destination transport-layer port numbers.
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 1]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   MACROFLOW
+
+      A group of CM-enabled streams that all use the same congestion
+      management and scheduling algorithms, and share congestion state
+      information.  Currently, streams destined to different receivers
+      belong to different macroflows.  Streams destined to the same
+      receiver MAY belong to different macroflows.  When the Congestion
+      Manager is in use, streams that experience identical congestion
+      behavior and use the same congestion control algorithm SHOULD
+      belong to the same macroflow.
+
+   APPLICATION
+
+      Any software module that uses the CM.  This includes user-level
+      applications such as Web servers or audio/video servers, as well
+      as in-kernel protocols such as TCP [Postel81] that use the CM for
+      congestion control.
+
+   WELL-BEHAVED APPLICATION
+
+      An application that only transmits when allowed by the CM and
+      accurately accounts for all data that it has sent to the receiver
+      by informing the CM using the CM API.
+
+   PATH MAXIMUM TRANSMISSION UNIT (PMTU)
+
+      The size of the largest packet that the sender can transmit
+      without it being fragmented en route to the receiver.  It includes
+      the sizes of all headers and data except the IP header.
+
+   CONGESTION WINDOW (cwnd)
+
+      A CM state variable that modulates the amount of outstanding data
+      between sender and receiver.
+
+   OUTSTANDING WINDOW (ownd)
+
+      The number of bytes that has been transmitted by the source, but
+      not known to have been either received by the destination or lost
+      in the network.
+
+   INITIAL WINDOW (IW)
+
+      The size of the sender's congestion window at the beginning of a
+      macroflow.
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 2]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   DATA TYPE SYNTAX
+
+      We use "u64" for unsigned 64-bit, "u32" for unsigned 32-bit, "u16"
+      for unsigned 16-bit, "u8" for unsigned 8-bit, "i32" for signed
+      32-bit, "i16" for signed 16-bit quantities, "float" for IEEE
+      floating point values.  The type "void" is used to indicate that
+      no return value is expected from a call.  Pointers are referred to
+      using "*" syntax, following C language convention.
+
+      We emphasize that all the API functions described in this document
+      are "abstract" calls and that conformant CM implementations may
+      differ in specific implementation details.
+
+2. Introduction
+
+   The framework described in this document integrates congestion
+   management across all applications and transport protocols.  The CM
+   maintains congestion parameters (available aggregate and per-stream
+   bandwidth, per-receiver round-trip times, etc.) and exports an API
+   that enables applications to learn about network characteristics,
+   pass information to the CM, share congestion information with each
+   other, and schedule data transmissions.  This document focuses on
+   applications and transport protocols with their own independent per-
+   byte or per-packet sequence number information, and does not require
+   modifications to the receiver protocol stack.  However, the receiving
+   application must provide feedback to the sending application about
+   received packets and losses, and the latter is expected to use the CM
+   API to update CM state.  This document does not address networks with
+   reservations or service differentiation.
+
+   The CM is an end-system module that enables an ensemble of multiple
+   concurrent streams to perform stable congestion avoidance and
+   control, and allows applications to easily adapt their transmissions
+   to prevailing network conditions.  It integrates congestion
+   management across all applications and transport protocols.  It
+   maintains congestion parameters (available aggregate and per-stream
+   bandwidth, per-receiver round-trip times, etc.) and exports an API
+   that enables applications to learn about network characteristics,
+   pass information to the CM, share congestion information with each
+   other, and schedule data transmissions.  When the CM is used, all
+   data transmissions subject to the CM must be done with the explicit
+   consent of the CM via this API to ensure proper congestion behavior.
+
+   Systems MAY choose to use CM, and if so they MUST follow this
+   specification.
+
+   This document focuses on applications and networks where the
+   following conditions hold:
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 3]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   1. Applications are well-behaved with their own independent
+      per-byte or per-packet sequence number information, and use the
+      CM API to update internal state in the CM.
+
+   2. Networks are best-effort without service discrimination or
+      reservations.  In particular, it does not address situations
+      where different streams between the same pair of hosts traverse
+      paths with differing characteristics.
+
+   The Congestion Manager framework can be extended to support
+   applications that do not provide their own feedback and to
+   differentially-served networks.  These extensions will be addressed
+   in later documents.
+
+   The CM is motivated by two main goals:
+
+   (i) Enable efficient multiplexing.  Increasingly, the trend on the
+   Internet is for unicast data senders (e.g., Web servers) to transmit
+   heterogeneous types of data to receivers, ranging from unreliable
+   real-time streaming content to reliable Web pages and applets.  As a
+   result, many logically different streams share the same path between
+   sender and receiver.  For the Internet to remain stable, each of
+   these streams must incorporate control protocols that safely probe
+   for spare bandwidth and react to congestion.  Unfortunately, these
+   concurrent streams typically compete with each other for network
+   resources, rather than share them effectively.  Furthermore, they do
+   not learn from each other about the state of the network.  Even if
+   they each independently implement congestion control (e.g., a group
+   of TCP connections each implementing the algorithms in [Jacobson88,
+   Allman99]), the ensemble of streams tends to be more aggressive in
+   the face of congestion than a single TCP connection implementing
+   standard TCP congestion control and avoidance [Balakrishnan98].
+
+   (ii) Enable application adaptation to congestion.  Increasingly,
+   popular real-time streaming applications run over UDP using their own
+   user-level transport protocols for good application performance, but
+   in most cases today do not adapt or react properly to network
+   congestion.  By implementing a stable control algorithm and exposing
+   an adaptation API, the CM enables easy application adaptation to
+   congestion.  Applications adapt the data they transmit to the current
+   network conditions.
+
+   The CM framework builds on recent work on TCP control block sharing
+   [Touch97], integrated TCP congestion control (TCP-Int)
+   [Balakrishnan98] and TCP sessions [Padmanabhan98].  [Touch97]
+   advocates the sharing of some of the state in the TCP control block
+   to improve transient transport performance and describes sharing
+   across an ensemble of TCP connections.  [Balakrishnan98],
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 4]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   [Padmanabhan98], and [Eggert00] describe several experiments that
+   quantify the benefits of sharing congestion state, including improved
+   stability in the face of congestion and better loss recovery.
+   Integrating loss recovery across concurrent connections significantly
+   improves performance because losses on one connection can be detected
+   by noticing that later data sent on another connection has been
+   received and acknowledged.  The CM framework extends these ideas in
+   two significant ways: (i) it extends congestion management to non-TCP
+   streams, which are becoming increasingly common and often do not
+   implement proper congestion management, and (ii) it provides an API
+   for applications to adapt their transmissions to current network
+   conditions.  For an extended discussion of the motivation for the CM,
+   its architecture, API, and algorithms, see [Balakrishnan99]; for a
+   description of an implementation and performance results, see
+   [Andersen00].
+
+   The resulting end-host protocol architecture at the sender is shown
+   in Figure 1.  The CM helps achieve network stability by implementing
+   stable congestion avoidance and control algorithms that are "TCP-
+   friendly" [Mahdavi98] based on algorithms described in [Allman99].
+   However, it does not attempt to enforce proper congestion behavior
+   for all applications (but it does not preclude a policer on the host
+   that performs this task).  Note that while the policer at the end-
+   host can use CM, the network has to be protected against compromises
+   to the CM and the policer at the end hosts, a task that requires
+   router machinery [Floyd99a].  We do not address this issue further in
+   this document.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 5]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   |--------| |--------| |--------| |--------|       |--------------|
+   |  HTTP  | |  FTP   | |  RTP 1 | |  RTP 2 |       |              |
+   |--------| |--------| |--------| |--------|       |              |
+       |          |         |  ^       |  ^          |              |
+       |          |         |  |       |  |          |   Scheduler  |
+       |          |         |  |       |  |  |---|   |              |
+       |          |         |  |-------|--+->|   |   |              |
+       |          |         |          |     |   |<--|              |
+       v          v         v          v     |   |   |--------------|
+   |--------| |--------|  |-------------|    |   |           ^
+   |  TCP 1 | |  TCP 2 |  |    UDP 1    |    | A |           |
+   |--------| |--------|  |-------------|    |   |           |
+      ^   |      ^   |              |        |   |   |--------------|
+      |   |      |   |              |        | P |-->|              |
+      |   |      |   |              |        |   |   |              |
+      |---|------+---|--------------|------->|   |   |  Congestion  |
+          |          |              |        | I |   |              |
+          v          v              v        |   |   |  Controller  |
+     |-----------------------------------|   |   |   |              |
+     |               IP                  |-->|   |   |              |
+     |-----------------------------------|   |   |   |--------------|
+                                             |---|
+
+                                      Figure 1
+
+   The key components of the CM framework are (i) the API, (ii) the
+   congestion controller, and (iii) the scheduler.  The API is (in part)
+   motivated by the requirements of application-level framing (ALF)
+   [Clark90], and is described in Section 4.  The CM internals (Section
+   5) include a congestion controller (Section 5.1) and a scheduler to
+   orchestrate data transmissions between concurrent streams in a
+   macroflow (Section 5.2).  The congestion controller adjusts the
+   aggregate transmission rate between sender and receiver based on its
+   estimate of congestion in the network.  It obtains feedback about its
+   past transmissions from applications themselves via the API.  The
+   scheduler apportions available bandwidth amongst the different
+   streams within each macroflow and notifies applications when they are
+   permitted to send data.  This document focuses on well-behaved
+   applications; a future one will describe the sender-receiver protocol
+   and header formats that will handle applications that do not
+   incorporate their own feedback to the CM.
+
+3. CM API
+
+   By convention, the IETF does not treat Application Programming
+   Interfaces as standards track.  However, it is considered important
+   to have the CM API and CM algorithm requirements in one coherent
+   document.  The following section on the CM API uses the terms MUST,
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 6]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   SHOULD, etc., but the terms are meant to apply within the context of
+   an implementation of the CM API.  The section does not apply to
+   congestion control implementations in general, only to those
+   implementations offering the CM API.
+
+   Using the CM API, streams can determine their share of the available
+   bandwidth, request and have their data transmissions scheduled,
+   inform the CM about successful transmissions, and be informed when
+   the CM's estimate of path bandwidth changes.  Thus, the CM frees
+   applications from having to maintain information about the state of
+   congestion and available bandwidth along any path.
+
+   The function prototypes below follow standard C language convention.
+   We emphasize that these API functions are abstract calls and
+   conformant CM implementations may differ in specific details, as long
+   as equivalent functionality is provided.
+
+   When a new stream is created by an application, it passes some
+   information to the CM via the cm_open(stream_info) API call.
+   Currently, stream_info consists of the following information: (i) the
+   source IP address, (ii) the source port, (iii) the destination IP
+   address, (iv) the destination port, and (v) the IP protocol number.
+
+3.1 State maintenance
+
+   1. Open: All applications MUST call cm_open(stream_info) before
+      using the CM API.  This returns a handle, cm_streamid, for the
+      application to use for all further CM API invocations for that
+      stream.  If the returned cm_streamid is -1, then the cm_open()
+      failed and that stream cannot use the CM.
+
+      All other calls to the CM for a stream use the cm_streamid
+      returned from the cm_open() call.
+
+   2. Close: When a stream terminates, the application SHOULD invoke
+      cm_close(cm_streamid) to inform the CM about the termination
+      of the stream.
+
+   3. Packet size: cm_mtu(cm_streamid) returns the estimated PMTU of
+      the path between sender and receiver.  Internally, this
+      information SHOULD be obtained via path MTU discovery
+      [Mogul90].  It MAY be statically configured in the absence of
+      such a mechanism.
+
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 7]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+3.2 Data transmission
+
+   The CM accommodates two types of adaptive senders, enabling
+   applications to dynamically adapt their content based on prevailing
+   network conditions, and supporting ALF-based applications.
+
+   1. Callback-based transmission.  The callback-based transmission API
+   puts the stream in firm control of deciding what to transmit at each
+   point in time.  To achieve this, the CM does not buffer any data;
+   instead, it allows streams the opportunity to adapt to unexpected
+   network changes at the last possible instant.  Thus, this enables
+   streams to "pull out" and repacketize data upon learning about any
+   rate change, which is hard to do once the data has been buffered.
+   The CM must implement a cm_request(i32 cm_streamid) call for streams
+   wishing to send data in this style.  After some time, depending on
+   the rate, the CM MUST invoke a callback using cmapp_send(), which is
+   a grant for the stream to send up to PMTU bytes.  The callback-style
+   API is the recommended choice for ALF-based streams.  Note that
+   cm_request() does not take the number of bytes or MTU-sized units as
+   an argument; each call to cm_request() is an implicit request for
+   sending up to PMTU bytes.  The CM MAY provide an alternate interface,
+   cm_request(int k).  The cmapp_send callback for this request is
+   granted the right to send up to k PMTU sized segments.  Section 4.3
+   discusses the time duration for which the transmission grant is
+   valid, while Section 5.2 describes how these requests are scheduled
+   and callbacks made.
+
+   2. Synchronous-style.  The above callback-based API accommodates a
+   class of ALF streams that are "asynchronous."  Asynchronous
+   transmitters do not transmit based on a periodic clock, but do so
+   triggered by asynchronous events like file reads or captured frames.
+   On the other hand, there are many streams that are "synchronous"
+   transmitters, which transmit periodically based on their own internal
+   timers (e.g., an audio senders that sends at a constant sampling
+   rate).  While CM callbacks could be configured to periodically
+   interrupt such transmitters, the transmit loop of such applications
+   is less affected if they retain their original timer-based loop.  In
+   addition, it complicates the CM API to have a stream express the
+   periodicity and granularity of its callbacks.  Thus, the CM MUST
+   export an API that allows such streams to be informed of changes in
+   rates using the cmapp_update(u64 newrate, u32 srtt, u32 rttdev)
+   callback function, where newrate is the new rate in bits per second
+   for this stream, srtt is the current smoothed round trip time
+   estimate in microseconds, and rttdev is the smoothed linear deviation
+   in the round-trip time estimate calculated using the same algorithm
+   as in TCP [Paxson00].  The newrate value reports an instantaneous
+   rate calculated, for example, by taking the ratio of cwnd and srtt,
+   and dividing by the fraction of that ratio allocated to the stream.
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 8]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   In response, the stream MUST adapt its packet size or change its
+   timer interval to conform to (i.e., not exceed) the allowed rate.  Of
+   course, it may choose not to use all of this rate.  Note that the CM
+   is not on the data path of the actual transmission.
+
+   To avoid unnecessary cmapp_update() callbacks that the application
+   will only ignore, the CM MUST provide a cm_thresh(float
+   rate_downthresh, float rate_upthresh, float rtt_downthresh, float
+   rtt_upthresh) function that a stream can use at any stage in its
+   execution.  In response, the CM SHOULD invoke the callback only when
+   the rate decreases to less than (rate_downthresh * lastrate) or
+   increases to more than (rate_upthresh * lastrate), where lastrate is
+   the rate last notified to the stream, or when the round-trip time
+   changes correspondingly by the requisite thresholds.  This
+   information is used as a hint by the CM, in the sense the
+   cmapp_update() can be called even if these conditions are not met.
+
+   The CM MUST implement a cm_query(i32 cm_streamid, u64* rate, u32*
+   srtt, u32* rttdev) to allow an application to query the current CM
+   state.  This sets the rate variable to the current rate estimate in
+   bits per second, the srtt variable to the current smoothed round-trip
+   time estimate in microseconds, and rttdev to the mean linear
+   deviation.  If the CM does not have valid estimates for the
+   macroflow, it fills in negative values for the rate, srtt, and
+   rttdev.
+
+   Note that a stream can use more than one of the above transmission
+   APIs at the same time.  In particular, the knowledge of sustainable
+   rate is useful for asynchronous streams as well as synchronous ones;
+   e.g., an asynchronous Web server disseminating images using TCP may
+   use cmapp_send() to schedule its transmissions and cmapp_update() to
+   decide whether to send a low-resolution or high-resolution image.  A
+   TCP implementation using the CM is described in Section 6.1.1, where
+   the benefit of the cm_request() callback API for TCP will become
+   apparent.
+
+   The reader will notice that the basic CM API does not provide an
+   interface for buffered congestion-controlled transmissions.  This is
+   intentional, since this transmission mode can be implemented using
+   the callback-based primitive.  Section 6.1.2 describes how
+   congestion-controlled UDP sockets may be implemented using the CM
+   API.
+
+3.3 Application notification
+
+   When a stream receives feedback from receivers, it MUST use
+   cm_update(i32 cm_streamid, u32 nrecd, u32 nlost, u8 lossmode, i32
+   rtt) to inform the CM about events such as congestion losses,
+
+
+
+Balakrishnan, et. al.       Standards Track                     [Page 9]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   successful receptions, type of loss (timeout event, Explicit
+   Congestion Notification [Ramakrishnan99], etc.) and round-trip time
+   samples.  The nrecd parameter indicates how many bytes were
+   successfully received by the receiver since the last cm_update call,
+   while the nrecd parameter identifies how many bytes were received
+   were lost during the same time period.  The rtt value indicates the
+   round-trip time measured during the transmission of these bytes.  The
+   rtt value must be set to -1 if no valid round-trip sample was
+   obtained by the application.  The lossmode parameter provides an
+   indicator of how a loss was detected.  A value of CM_NO_FEEDBACK
+   indicates that the application has received no feedback for all its
+   outstanding data, and is reporting this to the CM.  For example, a
+   TCP that has experienced a timeout would use this parameter to inform
+   the CM of this.  A value of CM_LOSS_FEEDBACK indicates that the
+   application has experienced some loss, which it believes to be due to
+   congestion, but not all outstanding data has been lost.  For example,
+   a TCP segment loss detected using duplicate (selective)
+   acknowledgments or other data-driven techniques fits this category.
+   A value of CM_EXPLICIT_CONGESTION indicates that the receiver echoed
+   an explicit congestion notification message.  Finally, a value of
+   CM_NO_CONGESTION indicates that no congestion-related loss has
+   occurred.  The lossmode parameter MUST be reported as a bit-vector
+   where the bits correspond to CM_NO_FEEDBACK, CM_LOSS_FEEDBACK,
+   CM_EXPLICIT_CONGESTION, and CM_NO_CONGESTION.  Note that over links
+   (paths) that experience losses for reasons other than congestion, an
+   application SHOULD inform the CM of losses, with the CM_NO_CONGESTION
+   field set.
+
+   cm_notify(i32 cm_streamid, u32 nsent) MUST be called when data is
+   transmitted from the host (e.g., in the IP output routine) to inform
+   the CM that nsent bytes were just transmitted on a given stream.
+   This allows the CM to update its estimate of the number of
+   outstanding bytes for the macroflow and for the stream.
+
+   A cmapp_send() grant from the CM to an application is valid only for
+   an expiration time, equal to the larger of the round-trip time and an
+   implementation-dependent threshold communicated as an argument to the
+   cmapp_send() callback function.  The application MUST NOT send data
+   based on this callback after this time has expired.  Furthermore, if
+   the application decides not to send data after receiving this
+   callback, it SHOULD call cm_notify(stream_info, 0) to allow the CM to
+   permit other streams in the macroflow to transmit data.  The CM
+   congestion controller MUST be robust to applications forgetting to
+   invoke cm_notify(stream_info, 0) correctly, or applications that
+   crash or disappear after having made a cm_request() call.
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 10]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+3.4 Querying
+
+   If applications wish to learn about per-stream available bandwidth
+   and round-trip time, they can use the CM's cm_query(i32 cm_streamid,
+   i64* rate, i32* srtt, i32* rttdev) call, which fills in the desired
+   quantities.  If the CM does not have valid estimates for the
+   macroflow, it fills in negative values for the rate, srtt, and
+   rttdev.
+
+3.5 Sharing granularity
+
+   One of the decisions the CM needs to make is the granularity at which
+   a macroflow is constructed, by deciding which streams belong to the
+   same macroflow and share congestion information.  The API provides
+   two functions that allow applications to decide which of their
+   streams ought to belong to the same macroflow.
+
+   cm_getmacroflow(i32 cm_streamid) returns a unique i32 macroflow
+   identifier.  cm_setmacroflow(i32 cm_macroflowid, i32 cm_streamid)
+   sets the macroflow of the stream cm_streamid to cm_macroflowid.  If
+   the cm_macroflowid that is passed to cm_setmacroflow() is -1, then a
+   new macroflow is constructed and this is returned to the caller.
+   Each call to cm_setmacroflow() overrides the previous macroflow
+   association for the stream, should one exist.
+
+   The default suggested aggregation method is to aggregate by
+   destination IP address; i.e., all streams to the same destination
+   address are aggregated to a single macroflow by default.  The
+   cm_getmacroflow() and cm_setmacroflow() calls can then be used to
+   change this as needed.  We do note that there are some cases where
+   this may not be optimal, even over best-effort networks.  For
+   example, when a group of receivers are behind a NAT device, the
+   sender will see them all as one address.  If the hosts behind the NAT
+   are in fact connected over different bottleneck links, some of those
+   hosts could see worse performance than before.  It is possible to
+   detect such hosts when using delay and loss estimates, although the
+   specific mechanisms for doing so are beyond the scope of this
+   document.
+
+   The objective of this interface is to set up sharing of groups not
+   sharing policy of relative weights of streams in a macroflow.  The
+   latter requires the scheduler to provide an interface to set sharing
+   policy.  However, because we want to support many different
+   schedulers (each of which may need different information to set
+   policy), we do not specify a complete API to the scheduler (but see
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 11]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   Section 5.2).  A later guideline document is expected to describe a
+   few simple schedulers (e.g., weighted round-robin, hierarchical
+   scheduling) and the API they export to provide relative
+   prioritization.
+
+4. CM internals
+
+   This section describes the internal components of the CM.  It
+   includes a Congestion Controller and a Scheduler, with well-defined,
+   abstract interfaces exported by them.
+
+4.1 Congestion controller
+
+   Associated with each macroflow is a congestion control algorithm; the
+   collection of all these algorithms comprises the congestion
+   controller of the CM.  The control algorithm decides when and how
+   much data can be transmitted by a macroflow.  It uses application
+   notifications (Section 4.3) from concurrent streams on the same
+   macroflow to build up information about the congestion state of the
+   network path used by the macroflow.
+
+   The congestion controller MUST implement a "TCP-friendly" [Mahdavi98]
+   congestion control algorithm.  Several macroflows MAY (and indeed,
+   often will) use the same congestion control algorithm but each
+   macroflow maintains state about the network used by its streams.
+
+   The congestion control module MUST implement the following abstract
+   interfaces.  We emphasize that these are not directly visible to
+   applications; they are within the context of a macroflow, and are
+   different from the CM API functions of Section 4.
+
+   - void query(u64 *rate, u32 *srtt, u32 *rttdev): This function
+     returns the estimated rate (in bits per second) and smoothed
+     round trip time (in microseconds) for the macroflow.
+
+   - void notify(u32 nsent): This function MUST be used to notify the
+     congestion control module whenever data is sent by an
+     application.  The nsent parameter indicates the number of bytes
+     just sent by the application.
+
+   - void update(u32 nsent, u32 nrecd, u32 rtt, u32 lossmode): This
+     function is called whenever any of the CM streams associated with
+     a macroflow identifies that data has reached the receiver or has
+     been lost en route.  The nrecd parameter indicates the number of
+     bytes that have just arrived at the receiver.  The nsent
+     parameter is the sum of the number of bytes just received and the
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 12]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+     number of bytes identified as lost en route.  The rtt parameter is
+     the estimated round trip time in microseconds during the
+     transfer.  The lossmode parameter provides an indicator of how a
+     loss was detected (section 4.3).
+
+   Although these interfaces are not visible to applications, the
+   congestion controller MUST implement these abstract interfaces to
+   provide for modular inter-operability with different separately-
+   developed schedulers.
+
+   The congestion control module MUST also call the associated
+   scheduler's schedule function (section 5.2) when it believes that the
+   current congestion state allows an MTU-sized packet to be sent.
+
+4.2 Scheduler
+
+   While it is the responsibility of the congestion control module to
+   determine when and how much data can be transmitted, it is the
+   responsibility of a macroflow's scheduler module to determine which
+   of the streams should get the opportunity to transmit data.
+
+   The Scheduler MUST implement the following interfaces:
+
+   - void schedule(u32 num_bytes): When the congestion control module
+     determines that data can be sent, the schedule() routine MUST be
+     called with no more than the number of bytes that can be sent.
+     In turn, the scheduler MAY call the cmapp_send() function that CM
+     applications must provide.
+
+   - float query_share(i32 cm_streamid): This call returns the
+     described stream's share of the total bandwidth available to the
+     macroflow.  This call combined with the query call of the
+     congestion controller provides the information to satisfy an
+     application's cm_query() request.
+
+   - void notify(i32 cm_streamid, u32 nsent): This interface is used
+     to notify the scheduler module whenever data is sent by a CM
+     application.  The nsent parameter indicates the number of bytes
+     just sent by the application.
+
+     The Scheduler MAY implement many additional interfaces.  As
+     experience with CM schedulers increases, future documents may
+     make additions and/or changes to some parts of the scheduler
+     API.
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 13]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+5. Examples
+
+5.1 Example applications
+
+   This section describes three possible uses of the CM API by
+   applications.  We describe two asynchronous applications---an
+   implementation of a TCP sender and an implementation of congestion-
+   controlled UDP sockets, and a synchronous application---a streaming
+   audio server.  More details of these applications and CM
+   implementation optimizations for efficient operation are described in
+   [Andersen00].
+
+   All applications that use the CM MUST incorporate feedback from the
+   receiver.  For example, it must periodically (typically once or twice
+   per round trip time) determine how many of its packets arrived at the
+   receiver.  When the source gets this feedback, it MUST use
+   cm_update() to inform the CM of this new information.  This results
+   in the CM updating ownd and may result in the CM changing its
+   estimates and calling cmapp_update() of the streams of the macroflow.
+
+   The protocols in this section are examples and suggestions for
+   implementation, rather than requirements for any conformant
+   implementation.
+
+5.1.1 TCP
+
+   A TCP implementation that uses CM should use the cmapp_send()
+   callback API.  TCP only identifies which data it should send upon the
+   arrival of an acknowledgement or expiration of a timer.  As a result,
+   it requires tight control over when and if new data or
+   retransmissions are sent.
+
+   When TCP either connects to or accepts a connection from another
+   host, it performs a cm_open() call to associate the TCP connection
+   with a cm_streamid.
+
+   Once a connection is established, the CM is used to control the
+   transmission of outgoing data.  The CM eliminates the need for
+   tracking and reacting to congestion in TCP, because the CM and its
+   transmission API ensure proper congestion behavior.  Loss recovery is
+   still performed by TCP based on fast retransmissions and recovery as
+   well as timeouts.  In addition, TCP is also modified to have its own
+   outstanding window (tcp_ownd) estimate.  Whenever data segments are
+   sent from its cmapp_send() callback, TCP updates its tcp_ownd value.
+   The ownd variable is also updated after each cm_update() call.  TCP
+   also maintains a count of the number of outstanding segments
+   (pkt_cnt).  At any time, TCP can calculate the average packet size
+   (avg_pkt_size) as tcp_ownd/pkt_cnt.  The avg_pkt_size is used by TCP
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 14]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   to help estimate the amount of outstanding data.  Note that this is
+   not needed if the SACK option is used on the connection, since this
+   information is explicitly available.
+
+   The TCP output routines are modified as follows:
+
+      1. All congestion window (cwnd) checks are removed.
+
+      2. When application data is available.  The TCP output routines
+      perform all non-congestion checks (Nagle algorithm, receiver-
+      advertised window check, etc).  If these checks pass, the output
+      routine queues the data and calls cm_request() for the stream.
+
+      3. If incoming data or timers result in a loss being detected, the
+      retransmission is also placed in a queue and cm_request() is
+      called for the stream.
+
+      4. The cmapp_send() callback for TCP is set to an output routine.
+      If any retransmission is enqueued, the routine outputs the
+      retransmission.  Otherwise, the routine outputs as much new data
+      as the TCP connection state allows.  However, the cmapp_send()
+      never sends more than a single segment per call.  This routine
+      arranges for the other output computations to be done, such as
+      header and options computations.
+
+   The IP output routine on the host calls cm_notify() when the packets
+   are actually sent out.  Because it does not know which cm_streamid is
+   responsible for the packet, cm_notify() takes the stream_info as
+   argument (see Section 4 for what the stream_info should contain).
+   Because cm_notify() reports the IP payload size, TCP keeps track of
+   the total header size and incorporates these updates.
+
+   The TCP input routines are modified as follows:
+
+      1. RTT estimation is done as normal using either timestamps or
+      Karn's algorithm.  Any rtt estimate that is generated is passed to
+      CM via the cm_update call.
+
+      2. All cwnd and slow start threshold (ssthresh) updates are
+      removed.
+
+      3. Upon the arrival of an ack for new data, TCP computes the value
+      of in_flight (the amount of data in flight) as snd_max-ack-1
+      (i.e., MAX Sequence Sent - Current Ack - 1).  TCP then calls
+      cm_update(streamid, tcp_ownd - in_flight, 0, CM_NO_CONGESTION,
+      rtt).
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 15]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+      4. Upon the arrival of a duplicate acknowledgement, TCP must check
+      its dupack count (dup_acks) to determine its action.  If dup_acks
+      < 3, the TCP does nothing.  If dup_acks == 3, TCP assumes that a
+      packet was lost and that at least 3 packets arrived to generate
+      these duplicate acks.  Therefore, it calls cm_update(streamid, 4 *
+      avg_pkt_size, 3 * avg_pkt_size, CM_LOSS_FEEDBACK, rtt).  The
+      average packet size is used since the acknowledgments do not
+      indicate exactly how much data has reached the other end.  Most
+      TCP implementations interpret a duplicate ACK as an indication
+      that a full MSS has reached its destination.  Once a new ACK is
+      received, these TCP sender implementations may resynchronize with
+      TCP receiver.  The CM API does not provide a mechanism for TCP to
+      pass information from this resynchronization.  Therefore, TCP can
+      only infer the arrival of an avg_pkt_size amount of data from each
+      duplicate ack.  TCP also enqueues a retransmission of the lost
+      segment and calls cm_request().  If dup_acks > 3, TCP assumes that
+      a packet has reached the other end and caused this ack to be sent.
+      As a result, it calls cm_update(streamid, avg_pkt_size,
+      avg_pkt_size, CM_NO_CONGESTION, rtt).
+
+      5. Upon the arrival of a partial acknowledgment (one that does not
+      exceed the highest segment transmitted at the time the loss
+      occurred, as defined in [Floyd99b]), TCP assumes that a packet was
+      lost and that the retransmitted packet has reached the recipient.
+      Therefore, it calls cm_update(streamid, 2 * avg_pkt_size,
+      avg_pkt_size, CM_NO_CONGESTION, rtt).  CM_NO_CONGESTION is used
+      since the loss period has already been reported.  TCP also
+      enqueues a retransmission of the lost segment and calls
+      cm_request().
+
+   When the TCP retransmission timer expires, the sender identifies that
+   a segment has been lost and calls cm_update(streamid, avg_pkt_size,
+   0, CM_NO_FEEDBACK, 0) to signify that no feedback has been received
+   from the receiver and that one segment is sure to have "left the
+   pipe."  TCP also enqueues a retransmission of the lost segment and
+   calls cm_request().
+
+5.1.2 Congestion-controlled UDP
+
+   Congestion-controlled UDP is a useful CM application, which we
+   describe in the context of Berkeley sockets [Stevens94].  They
+   provide the same functionality as standard Berkeley UDP sockets, but
+   instead of immediately sending the data from the kernel packet queue
+   to lower layers for transmission, the buffered socket implementation
+   makes calls to the API exported by the CM inside the kernel and gets
+   callbacks from the CM.  When a CM UDP socket is created, it is bound
+   to a particular stream.  Later, when data is added to the packet
+   queue, cm_request() is called on the stream associated with the
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 16]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   socket.  When the CM schedules this stream for transmission, it calls
+   udp_ccappsend() in the UDP module.  This function transmits one MTU
+   from the packet queue, and schedules the transmission of any
+   remaining packets.  The in-kernel implementation of the CM UDP API
+   should not require any additional data copies and should support all
+   standard UDP options.  Modifying existing applications to use
+   congestion-controlled UDP requires the implementation of a new socket
+   option on the socket.  To work correctly, the sender must obtain
+   feedback about congestion.  This can be done in at least two ways:
+   (i) the UDP receiver application can provide feedback to the sender
+   application, which will inform the CM of network conditions using
+   cm_update(); (ii) the UDP receiver implementation can provide
+   feedback to the sending UDP.  Note that this latter alternative
+   requires changes to the receiver's network stack and the sender UDP
+   cannot assume that all receivers support this option without explicit
+   negotiation.
+
+5.1.3 Audio server
+
+   A typical audio application often has access to the sample in a
+   multitude of data rates and qualities.  The objective of the
+   application is then to deliver the highest possible quality of audio
+   (typically the highest data rate) its clients.  The selection of
+   which version of audio to transmit should be based on the current
+   congestion state of the network.  In addition, the source will want
+   audio delivered to its users at a consistent sampling rate.  As a
+   result, it must send data a regular rate, minimizing delaying
+   transmissions and reducing buffering before playback.  To meet these
+   requirements, this application can use the synchronous sender API
+   (Section 4.2).
+
+   When the source first starts, it uses the cm_query() call to get an
+   initial estimate of network bandwidth and delay.  If some other
+   streams on that macroflow have already been active, then it gets an
+   initial estimate that is valid; otherwise, it gets negative values,
+   which it ignores.  It then chooses an encoding that does not exceed
+   these estimates (or, in the case of an invalid estimate, uses
+   application-specific initial values) and begins transmitting data.
+   The application also implements the cmapp_update() callback.  When
+   the CM determines that network characteristics have changed, it calls
+   the application's cmapp_update() function and passes it a new rate
+   and round-trip time estimate.  The application must change its choice
+   of audio encoding to ensure that it does not exceed these new
+   estimates.
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 17]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+5.2 Example congestion control module
+
+   To illustrate the responsibilities of a congestion control module,
+   the following describes some of the actions of a simple TCP-like
+   congestion control module that implements Additive Increase
+   Multiplicative Decrease congestion control (AIMD_CC):
+
+   - query(): AIMD_CC returns the current congestion window (cwnd)
+     divided by the smoothed rtt (srtt) as its bandwidth estimate.  It
+     returns the smoothed rtt estimate as srtt.
+
+   - notify(): AIMD_CC adds the number of bytes sent to its
+     outstanding data window (ownd).
+
+   - update(): AIMD_CC subtracts nsent from ownd.  If the value of rtt
+     is non-zero, AIMD_CC updates srtt using the TCP srtt calculation.
+     If the update indicates that data has been lost, AIMD_CC sets
+     cwnd to 1 MTU if the loss_mode is CM_NO_FEEDBACK and to cwnd/2
+     (with a minimum of 1 MTU) if the loss_mode is CM_LOSS_FEEDBACK or
+     CM_EXPLICIT_CONGESTION.  AIMD_CC also sets its internal ssthresh
+     variable to cwnd/2.  If no loss had occurred, AIMD_CC mimics TCP
+     slow start and linear growth modes.  It increments cwnd by nsent
+     when cwnd < ssthresh (bounded by a maximum of ssthresh-cwnd) and
+     by nsent * MTU/cwnd when cwnd > ssthresh.
+
+   - When cwnd or ownd are updated and indicate that at least one MTU
+     may be transmitted, AIMD_CC calls the CM to schedule a
+     transmission.
+
+5.3 Example Scheduler Module
+
+   To clarify the responsibilities of a scheduler module, the following
+   describes some of the actions of a simple round robin scheduler
+   module (RR_sched):
+
+   - schedule(): RR_sched schedules as many streams as possible in round
+     robin fashion.
+
+   - query_share(): RR_sched returns 1/(number of streams in macroflow).
+
+   - notify(): RR_sched does nothing.  Round robin scheduling is not
+     affected by the amount of data sent.
+
+6. Security Considerations
+
+   The CM provides many of the same services that the congestion control
+   in TCP provides.  As such, it is vulnerable to many of the same
+   security problems.  For example, incorrect reports of losses and
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 18]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   transmissions will give the CM an inaccurate picture of the network's
+   congestion state.  By giving CM a high estimate of congestion, an
+   attacker can degrade the performance observed by applications.  For
+   example, a stream on a host can arbitrarily slow down any other
+   stream on the same macroflow, a form of denial of service.
+
+   The more dangerous form of attack occurs when an application gives
+   the CM a low estimate of congestion.  This would cause CM to be
+   overly aggressive and allow data to be sent much more quickly than
+   sound congestion control policies would allow.
+
+   [Touch97] describes a number of the security problems that arise with
+   congestion information sharing.  An additional vulnerability (not
+   covered by [Touch97])) occurs because applications have access
+   through the CM API to control shared state that will affect other
+   applications on the same computer.  For instance, a poorly designed,
+   possibly a compromised, or intentionally malicious UDP application
+   could misuse cm_update() to cause starvation and/or too-aggressive
+   behavior of others in the macroflow.
+
+7. References
+
+   [Allman99]        Allman, M. and Paxson, V., "TCP Congestion
+                     Control", RFC 2581, April 1999.
+
+   [Andersen00]      Balakrishnan, H., System Support for Bandwidth
+                     Management and Content Adaptation in Internet
+                     Applications, Proc. 4th Symp. on Operating Systems
+                     Design and Implementation, San Diego, CA, October
+                     2000.  Available from
+                     http://nms.lcs.mit.edu/papers/cm-osdi2000.html
+
+   [Balakrishnan98]  Balakrishnan, H., Padmanabhan, V., Seshan, S.,
+                     Stemm, M., and Katz, R., "TCP Behavior of a Busy
+                     Web Server:  Analysis and Improvements," Proc. IEEE
+                     INFOCOM, San Francisco, CA, March 1998.
+
+   [Balakrishnan99]  Balakrishnan, H., Rahul, H., and Seshan, S., "An
+                     Integrated Congestion Management Architecture for
+                     Internet Hosts," Proc. ACM SIGCOMM, Cambridge, MA,
+                     September 1999.
+
+   [Bradner96]       Bradner, S., "The Internet Standards Process ---
+                     Revision 3", BCP 9, RFC 2026, October 1996.
+
+   [Bradner97]       Bradner, S., "Key words for use in RFCs to Indicate
+                     Requirement Levels", BCP 14, RFC 2119, March 1997.
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 19]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+   [Clark90]         Clark, D. and Tennenhouse, D., "Architectural
+                     Consideration for a New Generation of Protocols",
+                     Proc. ACM SIGCOMM, Philadelphia, PA, September
+                     1990.
+
+   [Eggert00]        Eggert, L., Heidemann, J., and Touch, J., "Effects
+                     of Ensemble TCP," ACM Computer Comm. Review,
+                     January 2000.
+
+   [Floyd99a]        Floyd, S. and Fall, K.," Promoting the Use of End-
+                     to-End Congestion Control in the Internet,"
+                     IEEE/ACM Trans. on Networking, 7(4), August 1999,
+                     pp. 458-472.
+
+   [Floyd99b]        Floyd, S. and T. Henderson,"The New Reno
+                     Modification to TCP's Fast Recovery Algorithm," RFC
+                     2582, April 1999.
+
+   [Jacobson88]      Jacobson, V., "Congestion Avoidance and Control,"
+                     Proc. ACM SIGCOMM, Stanford, CA, August 1988.
+
+   [Mahdavi98]       Mahdavi, J. and Floyd, S., "The TCP Friendly
+                     Website,"
+                     http://www.psc.edu/networking/tcp_friendly.html
+
+   [Mogul90]         Mogul, J. and S. Deering, "Path MTU Discovery," RFC
+                     1191, November 1990.
+
+   [Padmanabhan98]   Padmanabhan, V., "Addressing the Challenges of Web
+                     Data Transport," PhD thesis, Univ. of California,
+                     Berkeley, December 1998.
+
+   [Paxson00]        Paxson, V. and M. Allman, "Computing TCP's
+                     Retransmission Timer", RFC 2988, November 2000.
+
+   [Postel81]        Postel, J., Editor, "Transmission Control
+                     Protocol", STD 7, RFC 793, September 1981.
+
+   [Ramakrishnan99]  Ramakrishnan, K. and Floyd, S., "A Proposal to Add
+                     Explicit Congestion Notification (ECN) to IP," RFC
+                     2481, January 1999.
+
+
+   [Stevens94]       Stevens, W., TCP/IP Illustrated, Volume 1.
+                     Addison-Wesley, Reading, MA, 1994.
+
+   [Touch97]         Touch, J., "TCP Control Block Interdependence", RFC
+                     2140, April 1997.
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 20]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+8. Acknowledgments
+
+   We thank David Andersen, Deepak Bansal, and Dorothy Curtis for their
+   work on the CM design and implementation.  We thank Vern Paxson for
+   his detailed comments, feedback, and patience, and Sally Floyd, Mark
+   Handley, and Steven McCanne for useful feedback on the CM
+   architecture.  Allison Mankin and Joe Touch provided several useful
+   comments on previous drafts of this document.
+
+9. Authors' Addresses
+
+   Hari Balakrishnan
+   Laboratory for Computer Science
+   200 Technology Square
+   Massachusetts Institute of Technology
+   Cambridge, MA 02139
+
+   EMail: hari@lcs.mit.edu
+   Web: http://nms.lcs.mit.edu/~hari/
+
+
+   Srinivasan Seshan
+   School of Computer Science
+   Carnegie Mellon University
+   5000 Forbes Ave.
+   Pittsburgh, PA 15213
+
+   EMail: srini@cmu.edu
+   Web: http://www.cs.cmu.edu/~srini/
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 21]
+
+RFC 3124                 The Congestion Manager                June 2001
+
+
+Full Copyright Statement
+
+   Copyright (C) The Internet Society (2001).  All Rights Reserved.
+
+   This document and translations of it may be copied and furnished to
+   others, and derivative works that comment on or otherwise explain it
+   or assist in its implementation may be prepared, copied, published
+   and distributed, in whole or in part, without restriction of any
+   kind, provided that the above copyright notice and this paragraph are
+   included on all such copies and derivative works.  However, this
+   document itself may not be modified in any way, such as by removing
+   the copyright notice or references to the Internet Society or other
+   Internet organizations, except as needed for the purpose of
+   developing Internet standards in which case the procedures for
+   copyrights defined in the Internet Standards process must be
+   followed, or as required to translate it into languages other than
+   English.
+
+   The limited permissions granted above are perpetual and will not be
+   revoked by the Internet Society or its successors or assigns.
+
+   This document and the information contained herein is provided on an
+   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
+   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
+   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
+   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
+   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+
+Acknowledgement
+
+   Funding for the RFC Editor function is currently provided by the
+   Internet Society.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Balakrishnan, et. al.       Standards Track                    [Page 22]
+