From owner-ecm@wyvern.aciri.org Tue Nov 14 19:33:08 2000 Received: from wyvern.aciri.org (wyvern.aciri.org [192.150.187.14]) by ietf.org (8.9.1a/8.9.1a) with SMTP id TAA21137 for ; Tue, 14 Nov 2000 19:33:07 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.9.3/8.9.3) id QAA82877 for ecm-outgoing; Tue, 14 Nov 2000 16:30:48 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from breeze.lcs.mit.edu (breeze.lcs.mit.edu [18.31.0.83]) by wyvern.aciri.org (8.9.3/8.9.3) with ESMTP id QAA82872 for ; Tue, 14 Nov 2000 16:30:46 -0800 (PST) (envelope-from hari@breeze.lcs.mit.edu) Received: from breeze.lcs.mit.edu (IDENT:hari@localhost.localdomain [127.0.0.1]) by breeze.lcs.mit.edu (8.11.0/8.9.3) with ESMTP id eAF0Ubn01853 for ; Tue, 14 Nov 2000 19:30:45 -0500 Message-Id: <200011150030.eAF0Ubn01853@breeze.lcs.mit.edu> X-Mailer: exmh version 2.1.1 10/15/1999 X-url: http://nms.lcs.mit.edu/~hari/ From: Hari Balakrishnan Reply-to: Hari Balakrishnan To: ecm@aciri.org Subject: draft-ietf-ecm-cm-03.txt Mime-Version: 1.0 Content-Type: multipart/mixed ; boundary="==_Exmh_-1253858980" Date: Tue, 14 Nov 2000 19:30:37 -0500 Sender: owner-ecm@aciri.org Precedence: bulk This is a multipart MIME message. --==_Exmh_-1253858980 Content-Type: text/plain; charset=us-ascii Has been submitted today. It's attached to this message. The only difference from -02 is the correction of a reference to "persistent congestion" that Vern pointed out. Hari --==_Exmh_-1253858980 Content-Type: text/plain ; name="draft-ietf-ecm-cm-03.txt"; charset=us-ascii Content-Description: draft-ietf-ecm-cm-03.txt Content-Disposition: attachment; filename="draft-ietf-ecm-cm-03.txt" Internet Engineering Task Force Hari Balakrishnan INTERNET DRAFT MIT LCS Document: draft-ietf-ecm-cm-03.txt Srinivasan Seshan CMU November, 2000 Expires: May 2001 The Congestion Manager Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC-2026 [Bradner96]. 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 1. 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. 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. 2. 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. MACROFLOW A group of 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. Streams that experience identical congestion behavior in the Internet 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. 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. 3. Introduction 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. All data transmissions MUST be done with the explicit consent of the CM via this API to ensure proper congestion behavior. This document focuses on applications and networks where the following conditions hold: 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], [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. |--------| |--------| |--------| |--------| |--------------| | 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. 4. 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. 4.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. 4.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. 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. 4.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, successful receptions, type of loss (timeout event, Explicit Congestion Notification [Ramakrishnan98], 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) acknowledgements 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. 4.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. 4.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 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. 5. 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. 5.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 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. 5.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. 6. Examples 6.1 Example applications The following describes the possible use of the CM API by an asynchronous application (an implementation of a TCP sender) and a synchronous application (an audio server). More details of these applications and CM implementation optimizations for efficient operation are described in [Andersen00]. We emphasize that the protocols in this section are examples and suggestions for implementation, rather than requirements of any conformant implementation. 6.1.1 TCP A TCP MUST 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 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). 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 acknowledgements 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(). 6.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 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. 6.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. To use the CM, the application MUST incorporate feedback from the receiver. In this 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 CM changing its estimates and calling cmapp_update() of the streams of the macroflow. 6.3 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. 6.4 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. 7. 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 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. The more dangerous form of attack is giving 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 the security problems that arise with congestion information sharing in more detail. 8. References [Allman99] Allman, M. and Paxson, V., TCP Congestion Control, RFC-2581, April 1999. [Andersen00] Andersen, D., Bansal, D., Curtis, D., Seshan, S., and 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. [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 Henderson, T., "The NewReno Modification to TCP's Fast Recovery Algorithm," RFC-2582, April 1999. (Experimental.) [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 Deering, S., "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 Allman, M., "Computing TCP's Retransmission Timer," Internet Draft draft-paxson-tcp-rto-01.txt, April 2000. (Expires October 2000.) [Postel81] Postel, J. (ed.), "Transmission Control Protocol," RFC-793, September 1981. [Ramakrishnan98] Ramakrishnan, K. and Floyd, S., "A Proposal to Add Explicit Congestion Notification (ECN) to IP," RFC-2481. (Experimental.) [Stevens94] Stevens, W., TCP/IP Illustrated, Volume 1. Addison-Wesley, Reading, MA, 1994. [Touch97] Touch, J., "TCP Control Block Interdependence," RFC-2140, April 1997. (Informational.) 9. 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 and patience, and Sally Floyd, Mark Handley, and Steven McCanne for useful feedback on the CM architecture. 10. 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/ Full Copyright Statement "Copyright (C) The Internet Society (date). 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 the final draft output. --==_Exmh_-1253858980-- From owner-ecm@wyvern.aciri.org Wed Nov 15 07:52:56 2000 Received: from wyvern.aciri.org (wyvern.aciri.org [192.150.187.14]) by ietf.org (8.9.1a/8.9.1a) with SMTP id HAA06670 for ; Wed, 15 Nov 2000 07:52:55 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.9.3/8.9.3) id EAA87678 for ecm-outgoing; Wed, 15 Nov 2000 04:51:32 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from cantvc.canterbury.ac.nz (cantvc.canterbury.ac.nz [132.181.30.1]) by wyvern.aciri.org (8.9.3/8.9.3) with ESMTP id EAA87673 for ; Wed, 15 Nov 2000 04:51:29 -0800 (PST) (envelope-from hai22@student.canterbury.ac.nz) Received: from CONVERSION-DAEMON.it.canterbury.ac.nz by it.canterbury.ac.nz (PMDF V6.0-24 #45723) id <01JWLA1G4TO08ZIT5V@it.canterbury.ac.nz> for ecm@aciri.org; Thu, 16 Nov 2000 01:51:13 +1300 (NEW ZEALAND DAYLIGHT TIME) Received: from student.canterbury.ac.nz (cae2-15.elec.canterbury.ac.nz [132.181.51.16]) by it.canterbury.ac.nz (PMDF V6.0-24 #45723) with ESMTP id <01JWLA1FXYWK8ZIRLS@it.canterbury.ac.nz> for ecm@aciri.org; Thu, 16 Nov 2000 01:51:12 +1300 (NEW ZEALAND DAYLIGHT TIME) Date: Thu, 16 Nov 2000 01:51:11 +1300 From: hai22 Subject: Draft. To: ecm@aciri.org Reply-to: hai22@student.canterbury.ac.nz Message-id: <3A1286BF.244EF826@student.canterbury.ac.nz> MIME-version: 1.0 X-Mailer: Mozilla 4.7 [en] (WinNT; I) Content-type: multipart/mixed; boundary="Boundary_(ID_Wh+Ls3W+2e0jjiYFXQCnaQ)" X-Accept-Language: en Sender: owner-ecm@aciri.org Precedence: bulk This is a multi-part message in MIME format. --Boundary_(ID_Wh+Ls3W+2e0jjiYFXQCnaQ) Content-type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7BIT Respected Sir , Please find enclosed the copy of a draft algorithm for your worthy comments please . Thanks. Aun Haider University of Canterbury Christ Church New Zealand ****************************************************************** --Boundary_(ID_Wh+Ls3W+2e0jjiYFXQCnaQ) Content-type: text/plain; charset=iso-8859-1; name=ratehalving.txt Content-disposition: inline; filename=ratehalving.txt X-MIME-Autoconverted: from 8bit to quoted-printable by wyvern.aciri.org id EAB87678 Content-Transfer-Encoding: quoted-printable = = = Aun Haider. Harsha Sirisena .. November 2000. Modified Rate Halving Algorithm for TCP Congestion control Status of this Memo =09 This document is an Internet-Draft and is in full conformance with all pr= ovisions of section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Fo= rce (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 =93 work in progress.=94 The list of current Internet-Drafts can be accessed at http://www.ietf.or= g/ietf/lid-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://w= ww.ietf.org/shadow.html. Abstract This draft presents an improvement to the Rate Halving aAlgorithm for TCP= Congestion Control. . The Rate Halving aAlgorithm as well its modificat= ion presented in this documenthere areis largely independent of the detai= ls of the data retransmission strategy. . Thus bothrate halving algorith= m as well as its modified versions described in this document can be easi= ly used with several standard and experimental TCP implementations such a= s New Reno, SACK, and ECN. However, tThe present modified algorithm will able to capture all the fee= dback information of all feed back available through SACK and Duplicate S= ACK. . Thus using it will ensure that spurious retransmission will avoid= ed in large extent. 1. Introduction: All Reno TCP implementations include TCP Fast Retransmit and Fast Recover= y algorithms [RFC 2581]. . In these implementations the Fast Retransmit = relies on three duplicate acknowledgements to trigger the retransmission = of of a single lost segment. . Once the Fast Retransmit has occurred TC= P then waits for additional duplicate ACKs after receiving whichthen it w= ill send the additional new data. The result of this waiting is that the full new window of data is being t= ransmitted in one half of one Round Trip Time (RTT). . The burst of data= usually causes the repeated bursts in successive RTTs following the reco= very. . ThisIt can lead to a positive contribution in theoverall burstin= ess of network traffic. J.Hoe [1] suggested that during Fast Recovery the TCP data sender should = space out retransmissions and send new data on alternate ACKs across the = entire recovery RTT. . This It eliminates the half RTT lull in the sendi= ng of data that which occurs in normal Reno TCP. This is the Rate Halvin= g algorithm. The ideas of J.Hoe were further developed by M. Mathis, J. Semke, J.Mahda= vi and Kevin Lahey in their paper available at [8]. TheyIt explains how = to implement the Rate Halving Aalgorithm in under NewReno, SACK and ECN s= tyle TCP implementations. This document proposes an improvement toin the original Rrate Hhalving al= gorithm in SACK environments in the particular situations where the recei= ver is supportsing the Duplicate SACKs describedas mentioned in RFC 2883 = (July 2000). . Consequently it will also change the FACK algorithm as de= scribed given in [4]. The FACK algorithm also uses the SACK information about the amount of out= of order data queued at the receiver to avoid the unnecessary retranmiss= ions ..It updates the snd_una variable and retran_data to calculate the a= wnd using SACK. The RFC 2883 is being proposed and standardised to incorp= orate the duplicate data enqueued at the receiver. . Thus it is necessar= y to modify all the algorithms using SACK information for intelligent gue= ssing ?? data stored in the receiver. The Selective Acknowledgement (SACK) option defined in RFC 2018 is used b= y the TCP data receiver to acknowledge non-contiagiuous blocks of data no= t covered by the Cumulative Acknowledgement field. . However, RFC 2018 d= oes not specify the use of the SACK option when duplicate segments are re= ceived. The RFC 2883 specifies the use of the SACK option when acknowledg= ing the receipt of a duplicate packet [6]. The RFC 2883 specifies that the use of D-SACK does not require athe separ= ate negotiation between a TCP sender and receiver that have already negot= iated SACK capability. . The absence of a separate negotiation for D-SAC= K means that the TCP receiver could send D-SACK blocks when the TCP sende= r does not understand this extension to SACK. . In this case, the TCP se= nder will simply discard any D-SACK blocks, and process the other SACK bl= ocks in the SACK option field as it normally would.. However, RFC 2018 d= oes not address the use of the SACK option when acknowledging a duplicate= SACK.. The issues relating to D-SACK haves been discussed at length in = RFC 2883. 2. A bBrief aOver view of the Rate Halving aAlgorithm: =20 The Rate Halving aAlgorithm is a four-state finite state machine. . It i= s designed to reduce the congestion window following the detection of con= gestion in the network. . In order to differentiate between the usage of= cwnd within Rate Halving from the cwnd used by Reno and New Reno (RFC 25= 82) an alternate and comparable congestion window variable rhcwnd is defi= ned. rhcwnd is not inflated by dupacks during congestion .. It represents the= amount of data that a sender is allowed to keep. . It is not considered= as an offset to snd.una but ratherit is count of data in flight , regar= dless of whether the segments contain new or retransmitted data. The choice of which segment to send to send is completely independent of = the algorithm itself thus giving us broad freedom to use the Rate Halving= machinery with ECN (where no retransmissions occur) [RFC 2481], New Reno= (where retransmissions are spread out one per RTT)[RFC 2582], or SACK (= where holes are filled in after detection at the receiver)[RFRC 2018]. This document does not discuss the reaction of the Rate Halvingh algorith= m with ECN, Reno, and New Reno - that is left. Which might be next topic = of our studies in for further study.future. This document deals specifica= lly with SACK TCP with the Fast Recovery algorithm replaced by awith more= intelligent Rate Halving algorithm with incorporating the extensions toi= n SACK as proposed in RFC 2883. =20 3. Modified Rate Halving Algorithm The original Rate Hhalving aAlgorithm has the following four state= s in it: 1. RH_INCR 2. RH_EXACT 3. RH_EST_REPAIR=20 4. RH_EST Note: In the following discussion we will refer these above states by the= aboveir index sequence numbers given above.=20 The transition from state RH_INCR(1) to RH_EXACT(2) occurs when we receiv= e a new ACK carrying either a SACK or an ECN- Echo bit. Here we requireneed the original algorithm to be modified when introducin= g in the light of D-SACK. The rules of carrying the D-SACK are given in R= FC-2883. Specifically, iIf we receive the new ACK thatwhich carries the D= -SACK then we need not to modify or update those variables are introduced= to show the amount of data outstanding at the receiver in thewhich case = where some sequence numbers are missing that havewhich are to be filed in= by the transmitter of data by means of retransmissions. Thus this modif= ication will avoidsave us from many extra retransmissions therebywhich wi= ll improvinge the overall efficiency of Internet. By using our modification in Rate Halving Algorithm, many spurious retran= smissions will be avoided. Thus overall load on Internet for the transmit= ting of packet data will be decreased many folds. Because the retransmiss= ions for duplicated data will be totally avoided at receiver. Only those = segments will be transmitted which are really lost in path during transmi= ssion from transmitter to receiver. The duplicated or reordered segment w= ill not be retransmitted at all. The Modified Rate halving algorithm will not reduce its transmission rate= for D-SACK. It is at this point the Modified rate halving will differ ra= dically from the original version. The original algorithm will change its= states from 1 to 2 on receiving any kindsort of SACK signal in the ACK a= nd it will reduce the value of thevariable rhcwnd by =BD the distance fac= k has advanceds plus the size of any new holes. ThisIt is incorrect. Bbecause the original RFC2018 upon which the Rate Halving was designed do= es not differentiate between duplicated data at receiver and non- duplica= ted data at the receiver that inwhere by if both cases are out of sequenc= e by some lost sequencegment numbers. We are notdo no concerned here about preciselyat all that why the data is= duplicated or reordered in the network which may again be our next futur= e topic of study as well. But according tojust to mention that RFC 2581 c= ould see duplicate packets could arise fromin on of the following four co= nditions (there may be other conditions as well): a) Duplication by network itself due to intermediate routers etc. b) Reordering.=20 c) Timeouts due to ack losses. d) Early RTO. In the [7], Yin Zhang , Vern Paxon and Sscot Shenker haves listed some st= atistics about the pPacket reordering and replications ..They have used t= he definition of reordered packet as a =96packet arriving with a sending = sequence number lower than a packet that arrived previously .. They have = recently found that about 0.3% of 136 million packets arrived out of orde= r. Only 7% of measured hours have no reordering at all .. The highest sus= tained reordering rate was observed was to be sustained at 8.9% for one h= our. The 25 data sets had rates exceeding 5%. These statistics show that there= is sufficient enough chance ofs for packet reordering to cause retransmi= ssions triggeredrequested by a receiver. AndAll of these reordering will cause the spurious retransmissions from a= transmitter, which should be avoided for the sake ofmore efficiency. 3.1 Limitations of RFC 2883: The RFC 2883 does not specify what action a TCP implementation should tak= e forin the case of duplicated data (wWhatso ever its cause is) indicated= by D-SACK. This extension to the SACK option only enables the sender of data to dete= ct these cases of duplicate data enqueued at the receiver, when there are= alsowhich is also having some missing sequence numbers. This extension to the SACK option enables the receiver to accurately repo= rt the reception of duplicate data. We should also keep in mind that, the= loss of a single ACK will prevent this information from reaching the sen= der or transmitter of the packet data in net. There are also certain cas= es in which receiver can send wrong information to the sender as mentione= d in [9]. These cases merit to be further research.=20 3.2 How to detect the D- SACK at sender or transmitter of data: As per RFC 2883, in order for the sender or transmitter of packet data to= check that the first D-SACK block of an acknowledgment in fact acknowled= ges duplicate data, the sender or transmitter should compare the sequence= space in the first SACK block to the cumulative ACK which is carried in = same ACK packet. =20 If the SACK sequence space is less than this cumulative ACK, it is an ind= ication that the segment indicated by the SACK block has been received mo= re than once by the receiver. Further more an implementation must not compare the sequence space in the= SACK block to the TCP state variable snd.una (which carries the total cu= mulative ACK), as this may result in the wrong conclusion if ACK packets = are reordered. If the sequence space in the first SACK block is greater = than the cumulative ACK, then the sender next compares the sequence space= in the first SACK block with the sequence space in the second SACK block= , if there exits any. This check can ensure that the first SACK block is = reporting duplicate data that lies above the cumulative ACK. 3.3 Puroposed changes: The original Rate Halving algorithm uses the variables fack and retran_da= ta for increasing Rhcwnd and data transmission as per the following equat= ions: a). Upon the recipt of a new ACK in state 1 apply Congestion avoidance (C= A) or slow start (SS) as per RFC 2581 only when following condition holds. snd.nxt =96 fack + retran_data + SMSS >=3Drhcwnd b). While honouring all other constraints (such as receiver window), in a= ny state transmit the data of length " len " if ( snd.nxt =96 fack + retran_data + len); Thu, 16 Nov 2000 03:45:26 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.9.3/8.9.3) id AAA96107 for ecm-outgoing; Thu, 16 Nov 2000 00:42:22 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from daffy.ee.lbl.gov (daffy.ee.lbl.gov [131.243.1.31]) by wyvern.aciri.org (8.9.3/8.9.3) with ESMTP id AAA96102 for ; Thu, 16 Nov 2000 00:42:22 -0800 (PST) (envelope-from vern@daffy.ee.lbl.gov) Received: (from vern@localhost) by daffy.ee.lbl.gov (8.10.0/8.10.0) id eAG8gB624158; Thu, 16 Nov 2000 00:42:11 -0800 (PST) Message-Id: <200011160842.eAG8gB624158@daffy.ee.lbl.gov> To: hai22@student.canterbury.ac.nz Cc: ecm@aciri.org Subject: Re: Draft. In-reply-to: Your message of Thu, 16 Nov 2000 01:51:11 +1300. Date: Thu, 16 Nov 2000 00:42:11 PST From: Vern Paxson Sender: owner-ecm@aciri.org Precedence: bulk > Please find enclosed the copy of a draft algorithm for your worthy > comments please . > ... > Modified Rate Halving Algorithm for TCP Congestion control This topic is not within the charter of the ECM working group. What you should do instead is contact the Transport area directors (sob@harvard.edu and mankin@east.isi.edu) and ask them whether it might make sense as a work item for TSVWG. Vern From owner-ecm@wyvern.aciri.org Thu Nov 16 06:27:19 2000 Received: from wyvern.aciri.org (wyvern.aciri.org [192.150.187.14]) by ietf.org (8.9.1a/8.9.1a) with SMTP id GAA08682 for ; Thu, 16 Nov 2000 06:27:18 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.9.3/8.9.3) id DAA97346 for ecm-outgoing; Thu, 16 Nov 2000 03:26:57 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from ietf.org (odin.ietf.org [132.151.1.176]) by wyvern.aciri.org (8.9.3/8.9.3) with ESMTP id DAA97341 for ; Thu, 16 Nov 2000 03:26:56 -0800 (PST) (envelope-from nsyracus@cnri.reston.va.us) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id GAA08472; Thu, 16 Nov 2000 06:26:54 -0500 (EST) Message-Id: <200011161126.GAA08472@ietf.org> Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; Cc: ecm@aciri.org From: Internet-Drafts@ietf.org Reply-to: Internet-Drafts@ietf.org Subject: I-D ACTION:draft-ietf-ecm-cm-03.txt Date: Thu, 16 Nov 2000 06:26:54 -0500 Sender: owner-ecm@aciri.org Precedence: bulk --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the Endpoint Congestion Management Working Group of the IETF. Title : The Congestion Manager Author(s) : H. Balakrishnan, S. Seshan Filename : draft-ietf-ecm-cm-03.txt Pages : Date : 15-Nov-00 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. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-ecm-cm-03.txt Internet-Drafts are also available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-ecm-cm-03.txt". A list of Internet-Drafts directories can be found in http://www.ietf.org/shadow.html or ftp://ftp.ietf.org/ietf/1shadow-sites.txt Internet-Drafts can also be obtained by e-mail. Send a message to: mailserv@ietf.org. In the body type: "FILE /internet-drafts/draft-ietf-ecm-cm-03.txt". NOTE: The mail server at ietf.org can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e. documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ietf.org" Content-Type: text/plain Content-ID: <20001115091448.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-ecm-cm-03.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-ecm-cm-03.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20001115091448.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-ecm@wyvern.aciri.org Wed Nov 22 15:36:54 2000 Received: from wyvern.aciri.org (wyvern.aciri.org [192.150.187.14]) by ietf.org (8.9.1a/8.9.1a) with SMTP id PAA00095 for ; Wed, 22 Nov 2000 15:36:54 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.9.3/8.9.3) id MAA60056 for ecm-outgoing; Wed, 22 Nov 2000 12:31:27 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from ietf.org (odin.ietf.org [132.151.1.176]) by wyvern.aciri.org (8.9.3/8.9.3) with ESMTP id MAA60051 for ; Wed, 22 Nov 2000 12:31:26 -0800 (PST) (envelope-from scoya@cnri.reston.va.us) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA27802; Wed, 22 Nov 2000 15:30:23 -0500 (EST) Message-Id: <200011222030.PAA27802@ietf.org> To: IETF-Announce: ; Cc: ecm@aciri.org From: The IESG SUBJECT: Last Call: The Congestion Manager to Proposed Standard Reply-to: iesg@ietf.org Date: Wed, 22 Nov 2000 15:30:23 -0500 Sender: owner-ecm@aciri.org Precedence: bulk The IESG has received a request from the Endpoint Congestion Management Working Group to consider The Congestion Manager as a Proposed Standard. The IESG plans to make a decision in the next few weeks, and solicits final comments on this action. Please send any comments to the iesg@ietf.org or ietf@ietf.org mailing lists by December 6, 2000. Files can be obtained via http://www.ietf.org/internet-drafts/draft-ietf-ecm-cm-03.txt From owner-ecm@wyvern.aciri.org Wed Nov 29 09:36:19 2000 Received: from wyvern.aciri.org (wyvern.aciri.org [192.150.187.14]) by ietf.org (8.9.1a/8.9.1a) with SMTP id JAA15403 for ; Wed, 29 Nov 2000 09:36:18 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.11.1/8.11.1) id eATEWmm52763 for ecm-outgoing; Wed, 29 Nov 2000 06:32:48 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from bill.hayeslemmerz-man.es ([194.224.192.172]) by wyvern.aciri.org (8.11.1/8.11.1) with ESMTP id eATEWfa52758 for ; Wed, 29 Nov 2000 06:32:43 -0800 (PST) (envelope-from V@tzw.de) Received: from h809 (1Cust25.tnt1.mia5.da.uu.net [63.30.194.25]) by bill.hayeslemmerz-man.es (8.9.3/8.7.3) with SMTP id QAA18391; Wed, 29 Nov 2000 16:32:58 +0100 Date: Wed, 29 Nov 2000 16:32:58 +0100 From: V@tzw.de Message-Id: <200011291532.QAA18391@bill.hayeslemmerz-man.es> To: V@tzw.de Subject: Lady V: The Pleasure Pill for Women! Sender: owner-ecm@aciri.org Precedence: bulk LADY V: The Pleasure Pill for Women! Men Have Their Viagra®! Finally, A Pill for Women! It's Here! The Revolutionary Woman's Sexual Sensation is Now Available. Researchers are calling Lady V the greatest breakthrough for women since the Birth Control Pill. And you don't even need a prescription to get it! Welcome to the New Sexual Revolution! It's no secret that men have been having the time of their lives since the wonder pill Viagra® was made available. But, women were left out in the cold with no pill... nothing! Well now thanks to an all-star team of medical researchers who have been working around the clock, those days are finally over. The perfect female "pleasure pill" has been created and you don't even need a prescription. You can now get it from Lion Sciences! Lady V is the world's first pleasure pill scientifically designed for women. Lady V is an all-natural proprietary herbal blend of prosexual nutrients from around the world synergistically blended to naturally stimulate neurotransmitter endorphin signals. This magical combination increases targeted blood flow, unleashes natural stimulator for maximum stimulation, triggering pleasure responses quickly. Lady V is safe, natural and doctor-recommended. Since its introduction Lady V has been taking the world by storm! From Malibu to Miami women are enjoying the most intense pleasure of their lives! • 100% Natural • Safe • The Highest Quality Pharmaceutical Pure Nutraceuticals • Guaranteed Potency • Certified Purity Lady V is Sweeping the Nation! Women are going crazy over Lady V. Suddenly couples are falling in love all over again. The passion and pleasure that women are reporting is off the charts! Lady V has an incredible 88% success rate. Best of all, while Viagra costs $10 a pill, Lady V costs less than $1 a pill! It's not just a man's world anymore! Just look at what a few women have to say: "I thought my love life was good before, but now it is out of this world! Lady V is remarkable." — Mary J., Interior Designer "I haven't smiled like this in a long time. My husband and I feel like a couple of 19 year olds again!" — Debra T, Assistant Buyer "Imagine what it would feel like to have incredible passion and pleasure anytime you want." — Jennifer C., Film Editor "Suddenly my husband and I are spending more time in the bedroom instead of the TV room." — Angie R., Realtor Ingredients: Vitamin D, Niacin, Vitamin B6, Folic Acid, Vitamin B12, Avena Sativa, Kava Kava, Guarana, White Willow Extract, Mura Puama, St. John's Wort, Siberian Ginseng, Cordyceps, Damiana, and L-Taurine. Each bottle of Lady V contains 30 tablets. Take three capsules one hour before romantic activity as a dietary supplement. Risk Free: Double Your Money Back Guarantee If Lady V does not give the desired results as stated above, simply return the unused portion for a double-your money back refund. No questions asked! Order Now: Safe, Fast, Secure, Private Lady V with its DOUBLE YOUR MONEY BACK GUARANTEE is available only through this special promotional offer. Herbal V arrives in plain packaging for your privacy. Any and all information is kept strictly confidential. Payment Methods You may FAX or Postal Mail Checks, MasterCard, Visa, & American Express.payments. Money Orders are accepted only by Postal Mail. Each bottle of Lady V contains 30 tablets. Step 1: Place a check by your desired quanity. ______ 1 Bottle of Lady V $24 ______ 2 Bottles of Lady V $44 ______ 3 Bottles of Lady V $59 Please add $6 shipping and handling for any size order. [ Total cost including shipping & handling, 1 bottle=$30, 2 bottles=$50, 3 bottles=$65 ] International Orders Please add $18 shipping and handling for any size order. [ Total cost including shipping & handling, 1 bottle=$42, 2 bottles=$62, 3 bottles=$77 ] We cannot accept foreign checks. International money orders or credit cards only. Step 2: Place a check by your desired payment method and complete fields if necessary. _____Check or CHECK-BY-FAX [details below] _____Money Order _____American Express Account Number__________________ Exp____/____ _____Visa Account Number__________________ Exp____/____ _____MasterCard Account Number__________________ Exp____/____ Please make your check or money order payable to "Lion Sciences National". Step 3: Please complete and print the following fields clearly. Name ___________________________________________________ Address _________________________________________________ City ____________________________________________________ State ___________________________________________________ Zip _____________________________________________________ E-mail __________________________________________________ Signature _________________________________________________ [ required for check and credit card orders] Toll Free FAX Order Line: 1-800-940-6590 If faxing in your order, please state whether you require a fax, email, or no confirmation at all. Allow up to one day for confirmation, if requested. FAX orders are processed immediately. Or, print & mail to: LSN 273 S. State Rd. 7, #193 Margate, FL 33068-5727 ______________________________________________________ *CHECK BY FAX ORDERS: Complete the check as normal. Tape the check in the area below. Below the check, clearly write the check number, all numbers at the bottom of the check, & your name. Tape the check below and fax the check to the toll free FAX number above. Void the check. Our merchant will electronically debit your account for the amount of the check; your reference number for this transaction will be your check number. Nothing could be safer & easier ! TAPE CHECK BELOW _____________________________________________________________ This is a one time mailing: Removal is automatic and no further contact is necessary. Please Note: Lady V is not intended to diagnose, treat, cure or prevent any disease. As individuals differ, so will results. Lady V helps provide herbal and nutritional support for female sexual performance. The FDA has not evaluated these statements. For details about our double your money back guarantee, please write to the above address, attention consumer affairs department; enclose a self addressed stamped envelope for this and any requested contact information. Thank You. From owner-ecm@wyvern.aciri.org Thu Nov 30 16:36:14 2000 Received: from wyvern.aciri.org (wyvern.aciri.org [192.150.187.14]) by ietf.org (8.9.1a/8.9.1a) with SMTP id QAA27294 for ; Thu, 30 Nov 2000 16:36:14 -0500 (EST) Received: (from majordomo@localhost) by wyvern.aciri.org (8.11.1/8.11.1) id eAULX4a67181 for ecm-outgoing; Thu, 30 Nov 2000 13:33:04 -0800 (PST) (envelope-from owner-ecm@smtp.aciri.org) X-Authentication-Warning: wyvern.aciri.org: majordomo set sender to owner-ecm@smtp.aciri.org using -f Received: from mail.dreach.com (szptt103-190.szptt.net.cn [202.103.190.44] (may be forged)) by wyvern.aciri.org (8.11.1/8.11.1) with ESMTP id eAULX3m67176 for ; Thu, 30 Nov 2000 13:33:03 -0800 (PST) (envelope-from Younger@bdsm.at) Received: from aks011 ([63.30.194.54]) by mail.dreach.com (Lotus Domino Build 166.1) with SMTP id 2000120103293966:2875 ; Fri, 1 Dec 2000 03:29:39 +0800 To: Younger@bdsm.at From: Subject: REVERSE the AGING PROCESS 10-20 Years! MIME-Version: 1.0 X-MIMETrack: Itemize by SMTP Server on mail/Dreach(R5.0 (Intl)|30 March 1999) at 2000-12-01 03:29:47 AM, Serialize by Router on mail/Dreach(R5.0 (Intl)|30 March 1999) at 2000-12-01 05:29:21 AM, Serialize complete at 2000-12-01 05:29:21 AM Date: Thu, 30 Nov 2000 19:29:47 GMT Message-ID: X-Priority: 3 (Normal) Content-Type: text/plain; charset=unknown-8bit Sender: owner-ecm@aciri.org Precedence: bulk HAVE YOU HEARD OF HUMAN GROWTH HORMONE (HGH)??? Released by your own pituitary gland, HGH starts declining in your 20s, even more in your 30s and 40s, eventually resulting in the shrinkage of major organs-plus all other symptoms related to old age. THIS CAN NOW BE REVERSED!!! IN THOUSANDS OF CLINICAL STUDIES, HGH HAS BEEN SHOWN TO ACCOMPLISH THE FOLLOWING: * Reduce Body Fat Without Dieting Build Lean Muscle WITHOUT EXERCISE! * Enhance Sexual Performance * Remove Wrinkles and Cellulite * Lower Blood Pressure and improve Cholesterol Profile * Improve Sleep, Vision and Memory * Restore Hair Color and Growth * Strengthen the Immune System * Increase Energy and Cardiac Output * Turn back your body's Biological Time Clock 10-20 years in 6 months of usage !!! You don't have to spend thousands of dollars on shots. You don't have to spend the $139.00 per bottle that HGH is selling for at some Clinics in the United States. For the next 30 Days, you can obtain a complete one-month supply of our HGH releaser for our special "New Customers" price of just $69.95 plus $6.00 shipping and handling. To ensure a constant supply and to SAVE EVEN MORE, you can order with confidence 3 bottles of HGH and GET 1 FREE - that's just $209.85 for 4 bottles, plus $6.00 shipping and handling. You SAVE $69.95! ORDER TODAY! Payment Methods You may FAX or Postal Mail Checks, MasterCard, Visa, & American Express payments. Money Orders are accepted only by Postal Mail. Step 1: Place a check by your desired quanity. ______ 1 Bottle of HGH $69.95 ______ 2 Bottles of HGH $131.90 ($65.95 a bottle) ______ 4 Bottles of HGH (Buy 3 get 1 FREE. SAVE $69.95) $209.85 Please add $6 shipping and handling for any size order. [ Total cost including shipping & handling, 1 bottle=$75.95, 2 bottles=$137.90, 4 bottles=$215.85 ] International shipping, please add $35 for any size order [ Total cost including shipping & handling, 1 bottle=$104.95, 2 bottles=$166.90, 4 bottles=$244.85 ] Foreign checks are not accepted. Credit cards & international money orders only. Step 2: Place a check by your desired payment method and complete fields if necessary. _____Check or CHECK-BY-FAX [details below] _____Money Order _____American Express Account Number__________________ Exp____/____ _____Visa Account Number__________________ Exp____/____ _____MasterCard Account Number__________________ Exp____/____ Please make your check or money order payable to "Lion Sciences National". Step 3: Please complete and print the following fields clearly. Name ___________________________________________________ Address _________________________________________________ City ____________________________________________________ State ___________________________________________________ Zip _____________________________________________________ E-mail __________________________________________________ Signature _________________________________________________ [ required for check and credit card orders] Toll Free FAX Order Line: 1-800-940-6590 If faxing in your order, please state whether you require a fax, email, or no confirmation at all. Allow up to one day for confirmation, if requested. FAX orders are processed immediately. Or, print & mail to: Lion Sciences National 273 S. State Rd. 7 #193 Margate, FL 33068-5727 ______________________________________________________ *CHECK BY FAX ORDERS: Complete the check as normal. Tape the check in the area below. Below the check, clearly write the check number, all numbers at the bottom of the check, & your name. Tape the check below and fax the check to the toll free FAX number above. Void the check. Our merchant will electronically debit your account for the amount of the check; your reference number for this transaction will be your check number. Nothing could be safer & easier ! TAPE CHECK BELOW _____________________________________________________________ This is a one time mailing: Removal is automatic and no further contact is necessary. Please Note: HGH is not intended to diagnose, treat, cure or prevent any disease. The FDA has not evaluated these statements.