TCP Vegas

Previous

4.0.- TCP Vegas

In 1994, Brakmo, O'Malley & Peterson presented a new TCP implementation called Vegas that achieves between 40% and 70% better throughput and one-fifth to one-half the losses, when compare with TCP Reno. Vegas is an alternative implementation that interoperates with any other valid implementation of TCP, and all changes are confined to the sending side. This is a summary of their work:

Vegas - New retransmission mechanism

In Reno, RTT and mean variance estimates are computed using a coarse-grained timer (around 500ms), meaning that the RTT estimate is not very accurate. This granularity influence also how often TCP checks to see if it should time out on a segment. Under tests was found that for losses that resulted in a timeout, it took Reno an average of 1100ms from the time it sent a segment that was lost, until it timed out and resent the segment, whereas less that 300ms would have been the correct timeout interval had a more accurate clock been used. Vegas then fixes this problem using a finer coarse-grained timer.

Vegas also extends retransmission mechanism as follows: the system clock is read and recorded each time a segment is sent; when an ACK arrives, the clock is read again and the RTT calculation is done using this time and the timestamp recorded for the relevant segment. Using this more accurate RTT, retransmission is decided as follows:

a.- When a dupack is received, Vegas checks to see if the new RTT (current time - timestamp recorded) is greater than RTO. If it's, Vegas retransmits the segment without having to wait for the third dupack. In many cases third dupack is never received, and therefore, Reno would have to rely on the coarse-grained timeout to catch the loss.

b.- When a non-dupack is received, if it is the first or second one after a retransmission, Vegas checks again to see if RTT > RTO; if so, then the segment is retransmitted. This will catch any other segment that may have lost previous to the retransmission without having to wait for a dupack. In other words, Vegas treats the receipt of certain ACKs as a trigger to check if a timeout should happen; but still contains Reno's coarse-grained timeout code in case these mechanism fail to recognize a lost segment.

Finally, in Reno, it is possible to decrease the congestion window more than once for losses ocurring during one RTT interval. In contrast, Vegas only decreases the congestion window if a retransmitted segment was sent after the last decrease. Any losses that happened before the last decrease are ignore, and therefore, do not imply that it should be decreased again. This change is needed because Vegas detects losses much sooner than Reno.

Vegas - New congestion avoidance mechanism

Reno's congestion detection uses the loss of segments as a signal of congestion. It has no mechanism to detect the incipient stages of congestion - before losses occur - so they can be prevented. Reno is reactive, rather than proactive, in this respect. Reno needs to create losses to find the available bandwidth of the connection.

There are several proposed approaches for proactive congestion detection, for example:

Wang & Crowcroft's DUAL algorithm is based on the increase of the RTT; every 2-RTT delays the algorithm checks to see if the current RTT is greater than the average of the minimum and maximum RTTs seen so far; if so, the congestion window is decreased by one-eighth.
Jain's CARD adjusts the congestion window every 2-RTT delays based on the product (current cwnd-old cwnd) * (current RTT - old RTT); if the result is positive, decrease the window by one-eighth; if negative or zero, increase the window by one mss. This way the window will oscillate around its optimal point.
Wang & Crowcroft's Tri-S scheme increase the window size by one segment every RTT and then compare the throughput achieved to the throughput when the window was one segment smaller; if the difference is less than one-half the throughput achieved when only one segment was in transit - as was the case at the beginning of the connection - they decrease the window by one segment. Tri-S calculates the throughput by dividing the number of bytes outstanding in the network by the RTT.

Vegas implementation uses the idea to measure and control the amount of extra data that a connection has in transit, where extra data means data that would not have been sent if the bandwidth used by the connection exactly matches tha available bandwidth of the link. Vegas's goal is to maintain the "right" amount of extra data in the network. Obviously, if a connection is sending too much extra data, it will cause congestion; if it's sending too little extra data, it cannot respond rapidly enough to transient increase in the available bandwidth.

This algorithm is not in effect during slow-start and its implementation is as follows:

Define a given connection's BaseRTT to be the RTT of a segment when the connection is not congested; in practice it sets BaseRTT to the minimum of all measured RTTs; it is commonly the RTT of the first segment sent by the connection, before the router queues increase due to traffic generated by this connection. If we asume we are not overflowing the connection, the expected throughput is given by: Expected = WndowSize / BaseRTT, where WindowSize is the size of the current congestion window, which we assume to be equal to the number of bytes outstanding.
Calculate the current Actual sending rate recording how many bytes are transmitted between the time that a segment is sent and its ack is received and its RTT, and dividing the number of bytes transmitted by the sample RTT. This calculation is done once per round-trip time.
Then compare Actual to Expected and adjust the window accordingly. Let Diff = Expected - Actual. Note that Diff is positive or zero by definition, since Actual > Expected implies that we have to change BaseRTT to the latest sample RTT. Also define two thresholds a and b, such that, a < b, roughly corresponding to having too little and too much extra data in the network, respectively. When Diff < a, Vegas increases the congestion window linearly during the next RTT, and when Diff > b, Vegas decrease the congestion window linearly during the next RTT. The congestion window is left unchanged when a < Diff < b.

Intuitively, the farther away the actual throughput gets from the expected throughput, the more congestion there is in the network, which implies that the sending rate should be reduced. The b threshold triggers this decrease. On the other hand, when the actual throughput rate gets too close to the expected throughput, the connection is in danger of not utilizing the available bandwidth. The a threshold triggers this increase. The overall goal is to keep between a and b extrabytes in the network.

Vegas - Modified slow-start mechanism

Reno's slow-start mechanism is very expensive in terms of losses; since it doubles the size of the congestion window every RTT while there are no losses - which is equivalent to doubling the attempted throughput every RTT - when it finally overruns the connection bandwidth, we can expect losses in the order of half the current congestion window, more if we encounter a burst from another connection. Vegas tries to find a connection's available bandwidth that does not incur this kind of loss. Toward this end, the congestion detection mechanism is incorporated into slow-start with only minor modifications.

To be able to detect and avoid congestion during slow-start, Vegas allows exponential growth only every other RTT. In between, the congestion window stays fixed so a valid comparison of the expected and actual rates can be made. When the actual rate falls below the expected rate by a certain amount - the γ threshold - Vegas changes from slow-start mode to linear increase/decrease mode.

Discussion about Vegas TCP

Simulations show that if there are enough buffer in the routers - meaning that Vegas' congestion avoidance mechanisms can function effectively - a higher throughput and a faster response time result. As the load increase and/or the number of router buffer decrease, Vegas' congestion avoidance mechanism are not as effective, and Vegas starts to behave more like Reno. Under heavy congestion, Vegas behaves very similar to Reno, since Vegas fallback to Reno's coarse-grained timeout mechanism.

The important point to keep in mind is that up to the point that congestion is bad enough for Vegas' behavior to degenerate into Reno, Vegas is less aggressive in its use of router buffers than Reno. This is because Vegas limits its use of router buffers as specified by the β threshold, whereas Reno increases its window size until there are losses - which means all the router buffers are being used.

Finally Vegas' congestion detection algorithm depends on the accurate value for BaseRTT. If our estimate for the BaseRTT is too small, then the protocol's throughput will stay below the available bandwidth; if it is too large, then it will overrun the connection. Authors tell that their experience is that protocol does well with its current choice of BaseRTT. However, they plan to study this more carefully in the future.

Note: these algorithms were included in what was called Vegas TCP implementation.

Previous

Content

Next