Internet Engineering Task Force Dohy Hong Internet Draft INRIA draft-hong-ftcp-00.txt February 2002 Expires: August 2002 FTCP Fluid Congestion Control Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." 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. Abstract The goal of this document is to propose an improvement of TCP congestion control algorithm based on a very simple idea. One specific goal of FTCP is to smooth TCP traffic in order to improve the throughput, reduce losses and delay variation. FTCP algorithm is fully TCP-compatible [RFC 2914]. 1. Introduction. There are two properties, synchronization of different TCP sessions and burstiness of packets generated by each session, that may cause a bad utilization of the bandwidth, high packet losses, end-to-end delay variation and timeouts. Current TCP (Tahoe, Reno, NewReno, Sack etc.) protocols sends packets as soon as the congestion window size enables it. As a consequence, packets are very likely to be concentrated in the beginning of the RTT. This is responsible for the burstiness of TCP traffic and also for the high synchronization of different sessions. Hong [Page 1] Internet Draft FTCP Fluid Congestion Control October 2001 This document claims that this burstiness created by current TCP algorithm is unnecessary and unjustified. There is a simple and natural way to avoid it by smoothing the TCP traffic. 2. Definitions This section provides the definition of some terms that will be used throughout the remainder of this document (also cf.[BH]). CONGESTION EPOCH: At a given router, the congestion epoch is the time at which there are one or many packet losses due to buffer overflow or possibly due to AQM mechanism (e.g. RED). SYNCHRONIZATION RATE: At a given router, the synchronization rate gives the proportion of sessions that experience at least one packet loss at congestion epoch. The synchronization rate is equal to 1 when all sessions experience at least one packet loss at a given congestion epoch. IMPATIENT-TCP: An impatient-TCP is a TCP protocol that sends packets as soon as the sender's congestion window size and the receiver's window size enables it, mainly in slow start (SS) and congestion avoidance (CA) phases. PATIENT-TCP: A patient-TCP is a TCP protocol that may delay packet send even if the sender's congestion window size and the receiver's window size enables it, mainly in SS and CA phases. FTCP is in this category. 3. FTCP fundamental principle The main principle is the fact that FTCP aims to send packets in a way that packets are uniformly distributed along the RTT. Based on this principle, many different variants of algorithms can be proposed. In practice, there are four ways to impose this principle on the existing TCP traffic, depending on whether it is done - inside the TCP codes (FTCP) or - outside the TCP codes (FTCP regulation) and on whether it is done - at the TCP source level or - at the TCP destination level. Hong [Page 2] Internet Draft FTCP Fluid Congestion Control October 2001 3.1 Modification at the source level There are two ways acting on the TCP source packet sending behavior. The first is to directly modify the existing TCP algorithm. The second is to keep the existing TCP algorithm and add a regulation on its output port in order to smooth the packet repartition in each RTT as the FTCP does. 3.1.1 FTCP: Sender's TCP algorithm modification The TCP source's algorithm modification should be the most efficient. Here is a simple example of a patient-TCP compatible FTCP algorithm: 1. Choose any existing TCP protocol model and follow its rules (R) except for the following points. 2. Each packet to send receives a SEND_DATE at which it should be sent. A packet which is not associated to a SEND_DATE should be sent according to the rule R. 3. Each time a packet is sent, save its send date in LAST_SENT_DATE. 4. Each time an ACK is received, test if the rule R allows to send more packets. If K packets should be sent according to R, attribute SEND_DATEs to those K (normally K=1 or 2) packets and send packets as follow: RTT is the last updated Round Trip Time estimation and CWND is last updated congestion window size (in packet number). 1. Slow Start: #each time an ACK is received DO: if ( no patient packets ) LAST_TO_SEND := LAST_SENT_DATE; else LAST_TO_SEND := MAX(SEND_DATE[patient packets]); for k=1..K; SEND_DATE[packet k] := MAX(Current_Time, LAST_TO_SEND + RTT/Fss(CWND)); LAST_TO_SEND := MAX(SEND_DATE[patient packets]); with Fss(CWND) = pow( 2, ceil(log2(CWND)) ). (1) Fss(CWND) = CWND or CWND+1 could be more simple choices leading to similar effect. Such choices could be interesting if the practical implementation cost justifies it. Hong [Page 3] Internet Draft FTCP Fluid Congestion Control October 2001 If the RTTs are almost constant, the choice (1) leads to the optimal situation where packets are equidistant on successive RTTs as follow: pkt 1 pkt 2 pkt 3 ... |---------------|-------|-------|---|---|---|---|-|-|-|-|-|-|-|-| : : : : : ................................................................. RTT 1 RTT 2 RTT 3 RTT 4 2. Congestion Avoidance: #each time an ACK is received DO: if ( no patient packets ) LAST_TO_SEND := LAST_SENT_DATE; else LAST_TO_SEND := MAX(SEND_DATE[patient packets]); for k=1..K; SEND_DATE[packet k] := MAX(Current_Time, LAST_TO_SEND + RTT/Fca(CWND)); LAST_TO_SEND := MAX(SEND_DATE[patient packets]); with Fca(CWND) = CWND or CWND+1. A global simple choice of Fss() and Fca() could be: Fss(CWND) = Fca(CWND) = CWND+1. 5. Each time TCP leaves SS or CA phase, disable the FTCP mechanism: keep all patient packets, if there exist, and reset their SEND_DATE. 6. Enable the FTCP mechanism: 1. each time SS starts; 2. each time CA starts. 7. If there are large variations of RTT in the network, it could be useful to define a MPPN (Maximum Patient Packet Number), such that when this threshold is reached, the most patient packet is immediately sent. Taking MPPN=1 should already do a very good smoothing. 8. To delay packet send date as it is proposed above, it is probably necessary to introduce an independent timer which can activate the packet send. Its granularity should be small enough to be efficient (of the order 1/bandwidth with bandwidth in pkt/s). It may be simpler to introduce a FTCP regulation on the output port. Hong [Page 4] Internet Draft FTCP Fluid Congestion Control October 2001 Here is another variant: Follow the rule R until a packet loss or a timeout is detected. Then: 1. Save the value CWND in CWND_CONG each time a packet loss or timeout is detected (before the multiplicative decrease). 2. Separate successive packet send dates by RTT/MAX(CWND_CONG,CWND+1). 3.1.2 FTCP Regulation on the output port of the source This regulation is based on the identification of each TCP session and on the estimation of its RTT, its SS or CA phase on the output port of the source. It introduces delays on the packet send date so as to produce the same effect as if the source was FTCP controlled (e.g. as 3.1.1). Here is a possible simple FTCP Regulator: 1. It represents an output buffer of size (MPPN+1)*MTU at the output port. 2. It sends packet every T seconds (with T an updatable variable) if there are packets in the buffer. The timer could go on indepedently of the presence of the packets. 3. Each time a new packet arrives, update T, e.g. T=RTT/(CWND+1) assuming that the regulator can send one packet much faster than in T seconds. 3. If a new packet arrives and the MPPN size is reached, send immediately the oldest packet and reset the timer. 4. FTCP Regulator should never loss packets. This implies that it need to be faster then the source or that MPPN should be large enough to avoid losses. 3.2 Modification at the destination level This is not optimal, but could lead to almost the same results as 3.1. Here one cannot prevent the source to send two packets back-to -back when the sender increases its congestion window size by one. 3.2.1 FTCP: Destination's TCP algorithm modification This algorithm could be useful only when the source does not use FTCP protocol or has not FTCP regulation. The aim of this algorithm is to delay ACK send date so as to make at least the distribution of pairs of packets uniform on the RTTs. Hong [Page 5] Internet Draft FTCP Fluid Congestion Control October 2001 Here is a simple example of what it could do: 1. Each time a new packet arrive, do an estimation of RTT and the current CWND of the source. 2. Based on the above estimations, delay ACK send date such that two successive ACK send dates are separated at least by RTT/CWND. This does not apply to the SYN ACK packet. 3.2.2 FTCP Regulation on the output port of the destination The regulation does exactly what we propose in 3.2.1, but instead of doing it inside TCP algorithm, it is only done on the output port of the destination. The same regulation could also be done ont the input port of the source. 4. Comments on the Performance issue and other Consequences The idea of patient-TCP may considerably reduce the burstiness of TCP traffic. Here are possible consequences of the deployment of such an algorithm: 1. Reducing burstiness has a main consequence of reducing the synchronization rate and the packet loss probability. If all sessions use FTCP protocol, this could lead to an improvement of the throughput up to 25% (cf.[BH]). 2. Reduction of the end-to-end delay variation should be an indirect consequence. 3. In a homogeneous environment where sessions compete for bandwidth along the same route, one patient-TCP user against impatient-TCP users may hope to improve a huge throughput improvement. Simple NS simulations show that this can be much more than 100% (cf. Table 1): in these simulation, the FTCP mechanism is very partially and indirectly imitated reducing the source's capacity. The performance improvement comes directly from the loss probability reduction, confirming the intuition of point 1. Comparison of cases 1-2-3s and cases 1-2-3d shows that the FTCP could be implemented at the source or at the destination level: both of them should be efficient. 4. As the number of patient-TCP users increases, their performance improvement decreases, but the impatient-TCP users' performance degrades more and more (cf Table 2: case 4 and 5). Such a phenomenon encourages impatient-TCP users to use patient-TCP algorithm and to become "socially good". Hong [Page 6] Internet Draft FTCP Fluid Congestion Control October 2001 Table 1: | class | goodput | loss prob | TO prob | tcp0/tcp1 | -------------------------------------------------------------- case 1s | tcp0 | 188.9 2.1e-04 0.0 | | | tcp1 | 74.6 9.0e-04 4.6e-07 | 2.53 | | | | | case 2s | tcp0 | 937.0 2.2e-05 7.5e-07 | | | tcp1 | 1.8 1.6e-02 5.7e-03 | 520.56 | | | | | case 3s | tcp0 | 99.7 6.1e-04 0.0 | | | tcp1 | 86.5 8.1e-04 2.3e-07 | 1.15 | | | | | case 1d | tcp0 | 234.3 1.2e-04 0.0 | | | tcp1 | 70.3 1.0e-03 1.2e-07 | 3.33 | | | | | case 2d | tcp0 | 710.6 4.0e-05 0.0 | | | tcp1 | 26.4 5.5e-03 2.3e-04 | 26.92 | | | | | case 3d | tcp0 | 99.1 5.9e-04 0.0 | | | tcp1 | 86.1 8.0e-04 5.2e-07 | 1.15 | -------------------------------------------------------------- case 1s: bottleneck router capacity = 1000 pkt/s, tcp0 : sender capacity = 1000 pkt/s, tcp1 : sender capacity = 10000 pkt/s, NS simulation: 1 tcp0 against 9 tcp1. RTTmin = 600 ms, overhead_ = 0.005. case 2s: as case 1 with overhead_ = 0. case 3s: as case 1 with tcp0: sender capacity = 200 pkt/s. cases 1-2-3d: as cases 1-2-3s but the destination capacity (in fact we modify the router capacity after the bottleneck router because the destination sends ACK that has a small size) is modified instead of the source capacity. 5. In any case FTCP can only improve performance since on every RTT, FTCP sends the same number of packets than an impatient -TCP. 6. In a heterogeneous environment, important throughput improvement may also be obtained: FTCP should be also more efficient in presence of TCP-incompatible traffics, like UDP. Indeed, FTCP is roughly speaking a reliable rate adaptive UDP (cf. Table 2, case 1, 2, 3). 7. FTCP is "optimal" for its users but also for the point of view of the router performance. The end user performance improvement comes mainly from the fact that the FTCP algorithm avoids indirectly unnecessary packet losses and leads to a better use of router capacity. Hong [Page 7] Internet Draft FTCP Fluid Congestion Control October 2001 Table 2: | class | goodput | loss prob | TO prob | tcp/udp | ---------------------------------------------------------- case 1 | udp | 99.95 4.9e-04 - | | | tcp | 91.34 6.6e-04 8.7e-07 | 0.91 | | | | | case 2 | udp | 99.89 1.1e-03 - | | | tcp | 94.90 7.4e-04 1.3e-06 | 0.95 | | | | | case 3 | udp | 99.93 7.1e-04 - | | | tcp | 95.67 7.3e-04 6.2e-07 | 0.96 | | | | | case 4 | udp | 99.96 4.4e-04 - | | | tcp0 | 232.5 1.2e-04 0.0 | 2.32 | | tcp1 | 77.4 9.1e-04 9.7e-07 | 0.77 | | | | | case 5 | udp | 99.93 7.1e-04 - | | | tcp0 | 151.33 2.8e-04 3.3e-07 | 1.51 | | tcp1 | 56.80 2.0e-03 7.0e-07 | 0.57 | ---------------------------------------------------------- case 1: bottleneck router capacity = 1000 pkt/s, udp : send rate = 100 pkt/s, tcp : sender capacity = 10000 pkt/s, NS simulation: 1 udp against 9 tcp. RTTmin = 600 ms, overhead_ = 0.001. case 2: as case 1 with tcp sender capacity = 1000 pkt/s. case 3: as case 1 with tcp sender capacity = 200 pkt/s. case 4: bottleneck router capacity = 1000 pkt/s, udp : send rate = 100 pkt/s, tcp0 : sender capacity = 1000 pkt/s, tcp1 : sender capacity = 10000 pkt/s, NS simulation: 1 udp, 1 tcp0, 8 tcp1. RTTmin = 600 ms, overhead_ = 0.001. case 5: as case4 with 1 udp, 4 tcp0, 5 tcp1. 8. Another variant of FTCP could be to separate inter-departure times of packets by a time proportinnel to RTT/CWND: alpha * RTT / CWND, with alpha < 1. 9. If existing TCPs become all patient-TCP compatible, aggregated TCP traffic should change many of its currently attributed properties, in particular for its high variability. Indirectly, this situation could facilitate or simplify Hong [Page 8] Internet Draft FTCP Fluid Congestion Control October 2001 Internet traffic studies and all Internet traffic linked engineering tasks. 10. The above NS simulations (Table 1 and Table 2) are results obtained with 10000s simulation time. The results obtained over a small simulation time shows similar performance improvement. It seems that one can already hope a very good improvement with FTCP-type algorithm for transient traffic like HTTP-type traffic that does not reach stationary behavior. 5. References [BH] F. Baccelli and D. Hong, "AIMD, Fairness and Fractal Scaling of TCP Traffic", Technical Report, RR-4155, INRIA Rocquencourt, 2001. http://www.inria.fr/rrrt/rr-4155.html [APS] M. Allman, V. Paxson, W. Stevens, "TCP Congestion Control", RFC 2581, April 1999. 6. Authors' Addresses Dohy Hong Ecole Normale Superieure Computer Science Department TREC, INRIA-ENS joint project 45 rue d'Ulm 75005 Paris, FRANCE Email: Dohy.Hong@ens.fr URL: http://www.di.ens.fr/~hong Hong [Page 9]