F AST FAQ

What is FAST TCP?

FAST TCP is an alternative congestion control algorithm in TCP. It is designed for high speed data transfers over large distance, e.g., tens of gigabyte files across the Atlantic. Our current implementation is in TCP on Linux platform, though the principles and design can be implemented in other contexts than TCP.

It is built on theoretical work done since the late 1990s at Cambridge University, Melbourne University, Caltech, UCLA, University of Illinois, and University of Massachusetts, etc. The first prototype was demonstrated in SuperComputing Conference in November 2002 in collaboration with, and using the state-of-the-art infrastructure of, the High Energy Physics groups at Caltech, CERN and SLAC, with major support from DataTAG, StarLight, TeraGrid, SciNet, Cisco and Level(3).

Good starting points for understanding FAST are:

• FAST TCP: motivation, architecture, algorithm, performance by Cheng Jin, David X. Wei and Steven H. Low: IEEE Infocom, March 2004 .

• FAST TCP: From Theory to Experiments by C. Jin, D. Wei, S. H. Low, G. Buhrmaster, J. Bunn, D. H. Choe, R. L. A. Cottrell, J. C. Doyle, W. Feng, O. Martin, H. Newman, F. Paganini, S. Ravot, S. Singh; submitted for publication, April 1, 2003. 

• http://netlab.caltech.edu/FAST/

Major funding for FAST TCP is from the National Science Foundation and Caltech Lee Center for Advanced Networking, with additional supports from Army Research Office, Air Force Office of Scientific Research, DARPA and Cisco.

Our first public demonstration in SuperComputing Conference in November 2002 was widely reported in the media; see some old news.

Where can FAST TCP help?

TCP is useful whenever the availability of resources and the set of competing users vary over time unpredictably, yet efficient sharing is desired.

In order to get high throughput end-to-end between applications, we must have a network infrastructure that can provide large raw capacity, and a protocol that can make efficient use of the high capacity infrastructure.  The efficiency of the (congestion control algorithm in the) current TCP implementation drops steadily, and the protocol eventually becomes a performance bottleneck itself, as the network infrastructure scales up in capacity. FAST TCP aims to remove this bottleneck: it is scalable to networks with large bandwidth-delay product.

FAST TCP does not solve the infrastructure problem: if the underlying hardware has low speed, no TCP implementation can increase the throughput beyond the limit imposed by the underlying hardware. It can at best be at the limit.

Can FAST TCP boost my xDSL or cable connection to Gbps?

No. See previous question.

Can FAST TCP provide significant performance improvement in low speed networks?

We do not yet have enough experience in the low speed regime. FAST TCP has been optimized to provide great performance improvement over the current TCP implementation at Gbps speed. In low speed networks, e.g., if the bottleneck in the end-to-end path is the 10Mbps or 100Mbps Ethernet card, we expect the current TCP implementation to be quite efficient, so there is not much to improve. If the performance of the current TCP implementation is poor even at such speeds, then FAST TCP may or may not provide significant improvement depending on the reason for the poor performance.

Can FAST TCP help in wireless environment?

The current TCP performs poorly in two types of networks: high speed networks and wireless networks. We have optimized FAST TCP for the former. We believe it can be tailored to provide significant benefit in wireless networks as well, but we have not started this work yet.

The reason for our optimism is as follows. The current TCP assumes all packet losses are due to buffer overflows. There are two types of packet losses in wireless networks: those due to buffer overflows and those due to the wireless environment such as hand-offs, interference, fading, etc. They confuse the current TCP, driving down performance. FAST TCP does not make this assumption and hence can potentially maintain performance in the face of wireless losses.

Why delay-based congestion control?

Delay-based congestion control has been proposed since the late 80s by Jain and many others, notably Brakmo and Peterson in TCP Vegas. We believe its advantage over loss-based approach is small at low speed, but decisive at high speed.

It has been pointed out that delay can be a poor or untimely predictor of packet loss (e.g., see Martin, Nillson and Rhee's paper in Trans. on Networking, 11(3):356-369, June 2003). This does not mean that it is futile to use delay as a measure of congestion, but rather, that using a delay-based algorithm to predict loss in the hope of helping a loss-based algorithm adjust its window is the wrong approach to address problems at large windows. Instead, a different approach that fully exploits delay as a congestion measure, augmented with loss information, is needed. Vegas and FAST explore such an approach.

Delay as a congestion measure has two advantages. First, each measurement of loss (whether a packet is lost or not) provides 1 bit of congestion information for the filtering of noise in loss probability, whereas each measurement of RTT provides multi-bit information, and hence queueing delay can probably be more accurately estimated than loss probability, especially in networks with large bandwidth-delay product.

Second, delay has the right scaling with respect to network capacity, which helps stabilize congestion control as network scales up in capacity. This scaling property is also, in a sense, what underlies Matt Mathis's idea of large MTUs.

This is not to say that there are no challenges in implementing a delay-based approach - there are many.

FAST TCP does not attempt to reconstruct the "delay signal" from its samples. Note that Nyquist theorem applies to the reconstruction of a signal that is independent of the sampling process. In our case, the sampling feeds into a control that modifies the signal, and this feedback invalidates the straightforward application of the Nyquist theorem. Ideally, the sampling-control process in FAST TCP will drive the delay signal to a constant (when queue stabilizes), and in this case, a single sample is enough to measure the whole signal (as a function of time)!

Of course, in practice, delay will never be exactly constant, due to random noise and due to flows coming and going. In the former case, FAST TCP does not track the noise but filters it out. In the latter case, the hope is that these are slow-changing, and so, with appropriate filtering, the picture of the ideal case roughly holds in between these changes. Otherwise, there is no hope of feedback control, not due to inability to sample delay signal, but due to feedback delay.

What are the difficulties of the current TCP at large windows?

Four difficulties contribute to the poor performance of current TCP implementation in networks with large bandwidth-delay product:

• At the packet level, linear increase by one packet per Round-Trip Time (RTT) is too slow, and multiplicative decrease per loss event is too drastic.

• At the flow level, maintaining large average congestion windows requires an extremely small equilibrium loss probability that is hard to achieve in practice.

• At the packet level, oscillation is unavoidable because of the binary nature of the congestion signal (packet loss).

• At the flow level, the dynamics is unstable, leading to severe oscillations that can only be reduced by the accurate estimation of packet loss probability and a stable design of the flow dynamics.

The first two problems are really the same problem that manifests itself at the packet and flow levels. The last two problems, however, are of different nature and must be solved using different means. Oscillations at the packet level can be removed by doing equation-based control, as in TFRC, that uses multi-bit congestion signal (explicit estimation of loss probability). Oscillation at the flow level can be removed by stabilizing the flow dynamics, i.e., by proper design of the dynamic equation in equation-based control.

How is FAST TCP different from the current TCP implementation?

Can I use FAST TCP with FTP or application X,Y,Z?

FAST TCP is just like TCP in the sense that any application, such as FTP, using TCP will use FAST TCP once the patch is installed. You dont need any special programs to use FAST TCP.

Does FAST TCP work with IPV6?

In principle FAST TCP can be transported over IPV6 or IPV4. Unfortunately the Linux implementation splits the TCP source into an IPV6 and IPV4 part and we only have an IPV4 implementation presently. An IPV6 implementation is on the roadmap.

Why does FAST come as two patches?

FAST comes as two separate patches, an operating system (OS) independent patch and an OS dependent patch. The OS independent part contains the FAST algorithm and is covered by a patent and the Caltech open source agreement . The OS dependent part simply interfaces hooks into the TCP implementation of the particular OS to the separate FAST algorithm. The OS dependent part is not restricted by the Caltech open source agreement but covered under the GPL (Gnu Public License). Also, having two patches allows us to have just one version of the FAST algorithm for a variety of OSs.

Why does FAST output messages to /var/log/messages?

The current beta FAST release outputs debugging messages into /var/log/messages. When reporting bugs or performance issues, please keep a copy of the /var/log/messages file for reference.

How do I install FAST?

Currently, FAST is available as a patch to the linux kernel. You will need to have the correct version of the Linux kernel source installed on your machine (that is, a version compatible with the downloadable patch as specified on the download page). You will need to download two patches from this site and apply the patches to the Linux kernel source. The complete install instructions are included in the file install.txt which is part of the downloadable archive.

How do I configure FAST?

From the download section of this website you can download a script which does the following:

• Sets up the TCP send and receive buffers for high performance.

• Sets up the network device buffers for high performance.

You will need to modify this script to suit your network device configuration.

How do I view or change FAST parameters?

FAST is configured by system control parameters in the /proc/sys/net/ipv4 directory. To read, for example, the alpha parameter, use:
cat /proc/sys/net/ipv4/tcp_fast_alpha
To set the alpha parameter to 200 use:
echo 200 >> tcp_fast_alpha

What are the FAST configuration parameters?

The patch is preconfigured with default parameters which should work in most situations. In case fine-tuning is required, the parameters are listed in this section.

General Parameters

tcp_fast	0 = disable FAST (revert to normal TCP) 1 = enable FAST (default)
tcp_fast_alpha	Minimum number of packets source aims to maintain in network queue. Ideally, if the network capacity is C pkts/ms then we set alpha to equal to 2C so that the source generates 2 ms of queuing delay. In practice C is not known, so we set alpha to a value that works well for a range of capacities expected. With alpha tuning enabled, ie. tcp_fast_sec not 0, this alpha value is ignored and an automatic alpha estimation is used. With alpha tuning, the maximum throughput achieved is detected, and the alpha value is set according to whether it is a low,medium or high speed environment.
tcp_fast_beta	Maximum number of packets source aims to maintain in network queue. Must be greater than alpha. Typically set to equal to or be close to alpha. By default it is set to 17/16 of alpha.
tcp_fast_gamma	Slow start parameter.
tcp_fast_bc	Burstiness control. When enabled, spreads large packet transmission bursts over time, so that instantenous transmission rate is smoother. 0 = disable 1 = enable
tcp_fast_kmon_rtt	Used for FAST debugging
tcp_fast_kmon_t	Used for FAST debugging

Alpha Tuning Parameters

The alpha parameter is dynamically set during the connection to one of three values based on the network speed environment. Alpha tuning is not intended to perform congestion control, but simply select an appropriate alpha for each environment. The mode selection is done by detecting the maximum throughput pkts/sec achieved over the previous update period. All the pkt/sec threshold values are calculated assuming 1500 byte packets.

tcp_fast_at_sec	Alpha tuning update period in seconds. Default = 200 secs. A value of 0 disables automatic alpha tuning.
tcp_fast_at_mode	Current alpha mode. Mode 0 = low speed (default <15Mbps). Mode 1 = medium speed (default 15-180Mbps). Mode 2 = high speed (default >180Mbps).
tcp_fast_at_m0a	Alpha in mode 0.
tcp_fast_at_m1a	Alpha in mode 1.
tcp_fast_at_m2a	Alpha in mode 2.
tcp_fast_at_m0u	Pkts/sec threshold for mode 0 -> 1 switch.
tcp_fast_at_m1l	Pkts/sec threshold for mode 1 -> 0 switch.
tcp_fast_at_m1u	Pkts/sec threshold for mode 1 -> 2 switch.
tcp_fast_at_m2l	Pkts/sec threshold for mode 2 -> 1 switch.

Reverse path congestion reduces throughput

If significant congestion builds up on the destination-host to source-host acknowledgement-packet path after the connection from source-host to destination-host has established, the throughput will be reduced. This occurs because the current version of FAST uses the round-trip-time to sense congestion, which includes reverse path congestion. Future versions will include one-way congestion measurement, so that FAST only reacts to forward path congestion.

Many FAST sources cause buffer overflow and packet loss

Currently each source maintains ‘alpha’ packets in the forward path queues. If there are N FAST sources sharing the same links, then N times alpha packets are maintained in the queues for these links. If N times alpha exceeds the buffering capacity of the path, then packet loss will occur and FAST will behave more like TCP Reno.

Route change may reduce throughput

If a route change occurs during the period of a connection, FAST may under-utilize the link. This occurs when the new route has a longer propagation delay, leading to an incorrect estimate of the number of packets queued in the path. Future versions of FAST will be more robust to route changes by improving route change detection.

What are the planned future improvements?

• Measurement of Backward Queuing delay to avoid reverse path congestion affecting throughput.

• Detection of route change.

• Tuning of Socket Buffers.

• Reducing number of ACKs processed to improve CPU utilization.

• Introduce 'TCP Friendliness' parameter to control sender aggressiveness in lossy environments.

• SACK processing optimization.