next up previous
Next: TCP Santa Cruz - Up: Improving TCP Congestion Control Previous: Introduction

   
Previous Work

Congestion control for TCP is an area of active research; solutions to congestion control for TCP address the problem either at the intermediate routers in the network [8,13,6] or at the endpoints of the connection [2,7,20,21,22].

Router-based support for TCP congestion control can be provided through RED gateways [6], a solution in which packets are dropped in a fair manner (based upon probabilities) once the router buffer reaches a predetermined size. As an alternative to dropping packets, an Explicit Congestion Notification (ECN) [8] bit can be set in the packet header, prompting the source to slow down. Current TCP implementations do not support the ECN method. Kalampoukas et.al. [13] propose an approach that prevents TCP sources from growing their congestion window beyond the bandwidth delay product (BWDP) of the network by allowing the routers to modify the receiver's advertised window field of the TCP header in such a way that TCP does not overrun the intermediate buffers in the network.

End-to-end congestion control approaches can be separated into three categories: using rate-control, looking at changes in packet round-trip time (RTT), and modifying the source and/or receiver to return additional information beyond what is specified in the standard TCP header [20]. A problem with rate-control and relying upon RTT estimates is that variations of congestion along the reverse path cannot be identified. Therefore, an increase in RTT due to reverse-path congestion or even link asymmetry will affect the performance of these algorithms in an adverse manner. In the case of RTT monitoring the window size could be decreased (due to increased RTT) resulting in decreased throughput; in the case of rate-based algorithms, the window could be increased in order to bump up throughput, resulting in increased congestion along the forward path.

Wang and Crowcroft's DUAL algorithm [21] uses a congestion control scheme that examines the RTT variation as the indication of delay through the network. The algorithm keeps track of the minimum and maximum delay observed to estimate the maximum queue size in the bottleneck routers and keep the window size such that the queues do not fill and thereby cause packet loss. An adjustment of $\pm
\frac{1}{8}cwnd$ is made to the congestion window every other round-trip time whenever the observed RTT deviates from the mean of the highest and lowest RTT ever observed. RFC 1185 [7] uses the TCP Options to include a timestamp in every data packet from sender to receiver in order to obtain a more accurate RTT estimate. The receiver echoes this timestamp in any acknowledgment (ACK) packet and the round-trip time is calculated with a single subtraction. This approach encounters problems when delayed ACKs are used because it is unclear to which packet the timestamp belongs. RFC1185 suggests that the receiver return the earliest timestamp so that the RTT estimate takes into account the delayed ACKs, as segment loss is assumed to be a sign of congestion, and the timestamp returned is from the SN which last advanced the window. When a hole is filled in the sequence space, the receiver returns the timestamp from the segment which filled hole. The downside of this approach is that it cannot provide accurate timestamps when segments are lost.

Two notable rate-control approaches are the Tri-S [22] scheme and TCP Vegas [2]. Wang and Crowcroft's Tri-S algorithm [22] is a rate-based scheme that computes the achieved throughput by measuring the RTT for a given window size (which represents the amount of outstanding data in the network). It compares the throughput for a given window and then for the same window increased by one segment. If the throughput is less than one-half that achieved with the smaller window, they reduce the window by one segment.

With TCP Vegas, an RTT estimate is performed for every transmitted segment, excluding retransmissions, and the granularity of the retransmission timer is reduced from 500ms to 100ms. TCP Vegas is comprised of three main components: a retransmission mechanism, a congestion avoidance mechanism, and a modified slow-start algorithm. TCP Vegas does not necessarily wait for the receipt of three duplicate ACKs from the receiver before performing a retransmission. Upon receipt of a duplicate ACK, the sender compares the time elapsed for the relevant segment with the timeout value and retransmits if it is greater. In addition, when a non-duplicate ACK is received, a time comparison is made if it is the first or second since a retransmission to determine if additional retransmissions should occur. The congestion avoidance mechanism is based upon a once per round-trip time comparison between the ideal (expected) throughput and the actual throughput. The ideal throughput is based upon the best RTT ever observed and the observed throughput is the throughput observed over a RTT period. The goal is to keep the actual throughput between two threshhold values, $\alpha$ and $\beta$, which represent too little and too much data in flight, respectively.

Because we are interested in solutions to TCP's performance problems that can be applicable over any type of networks and link, our approach focuses on end-to-end solutions. However, our work is closely related to a method of bandwidth probing introduced by Keshav [10]. In this approach, two back-to-back packets are transmitted through the network and the interarrival time of their acknowledgment packets is measured to determine the bottleneck service rate (the conjecture is that the ACK spacing preserves the data packet spacing). This rate is then used to keep the bottleneck queue at a predetermined value. For the scheme to work, it is assumed that the routers are employing round-robin or some other fair service discipline. The approach does not work over heterogeneous networks, where the capacity of the reverse path could be orders of magnitude slower than the forward path because the data packet spacing is not preserved by the ACK packets. In addition, a receiver could employ a delayed ACK strategy as is common in many TCP implementations, and congestion on the reverse path can interfere with ACK spacing and invalidate the measurements made by the algorithm.


next up previous
Next: TCP Santa Cruz - Up: Improving TCP Congestion Control Previous: Introduction
Chris Parsa
2000-01-25