Internet DRAFT - draft-hong-ftcp
draft-hong-ftcp
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]
