TCP Vegas revisited

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

1. In Reno, RTT and mean variance estimates arecomputed using a coarse-grained timer (around 500ms), meaning thatthe RTT estimate is not very accurate. This granularity influencealso how often TCP checks to see if it should time out on asegment. Under tests was found that for losses that resulted in a timeout, it took Reno an average of 1100ms from the timeit sent a segment that was lost, until it timed out and resent thesegment, whereas less that 300ms would have been the correcttimeout interval had a more accurate clock been used. Vegasthen fixes this problem using a finer coarse-grained timer.
    
2. Vegas also extends retransmission mechanism as follows: the system clock is read and recorded each time a segment is sent; when anACK arrives, the clock is read again and the RTT calculationis done using this time and the timestamp recorded for the relevantsegment. Using this more accurate RTT, retransmission is decided asfollows:
   
   a.- When a dupack is received, Vegaschecks to see if the new RTT (current time - timestamprecorded) 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 theloss.

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

3. Finally, in Reno, it is possible to decrease the congestionwindow more than once for losses ocurring during one RTT interval.In contrast, Vegas only decreases the congestion window if aretransmitted segment was sent after the last decrease. Any lossesthat happened before the last decrease are ignore, and therefore, do notimply 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 theloss of segments as a signal of congestion. It has no mechanism to detectthe incipient stages of congestion - before losses occur - so theycan be prevented. Reno is reactive, rather than proactive, in thisrespect. Reno needs to create losses to find the availablebandwidth of the connection.

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

1. Wang & Crowcroft's DUAL algorithm is based on the increase ofthe RTT; every 2-RTT delays the algorithm checks to see ifthe current RTT is greater than the average of the minimum andmaximum RTTs seen so far; if so, the congestion window isdecreased by one-eighth.
    
2. 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 byone-eighth; if negative or zero, increase the window by one mss.This way the window will oscillate around its optimal point.
    
3. Wang & Crowcroft's Tri-S scheme increase the window size by onesegment every RTT and then compare the throughput achieved to thethroughput when the window was one segment smaller; if the difference isless than one-half the throughput achieved when only one segment was intransit - as was the case at the beginning of the connection - theydecrease the window by one segment. Tri-S calculates thethroughput by dividing the number of bytes outstanding in the network bythe RTT.

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

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

1. Define a given connection's BaseRTT to be the RTT of asegment when the connection is not congested; in practice it setsBaseRTT to the minimum of all measured RTTs; it is commonlythe RTT of the first segment sent by the connection, before therouter queues increase due to traffic generated by this connection. If weasume we are not overflowing the connection, the expected throughput isgiven by: Expected = WndowSize / BaseRTT, where WindowSizeis the size of the current congestion window, which we assume to be equalto the number of bytes outstanding.
    
2. Calculate the current Actual sending rate recording how manybytes are transmitted between the time that a segment is sent and its ack is received and its RTT, and dividing the number of bytestransmitted by the sample RTT. This calculation is done once perround-trip time.
    
3. Then compare Actual to Expected and adjust the windowaccordingly. Let Diff = Expected - Actual. Note that Diffis positive or zero by definition, since Actual > Expected impliesthat 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 muchextra data in the network, respectively. When Diff < a, Vegasincreases the congestion window linearly during the next RTT, andwhen Diff > b, Vegas decrease the congestion window linearlyduring the next RTT. The congestion window is left unchangedwhen a < Diff < b.

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

Vegas - Modified slow-start mechanism

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

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

Discussion about Vegas TCP

Simulations show that if there are enoughbuffer in the routers - meaning that Vegas' congestion avoidancemechanisms can function effectively - a higher throughput and a fasterresponse time result. As the load increase and/or the number of routerbuffer decrease, Vegas' congestion avoidance mechanism are not aseffective, and Vegas starts to behave more like Reno. Underheavy congestion, Vegas behaves very similar to Reno,since Vegas fallback to Reno's coarse-grained timeoutmechanism.

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

Finally Vegas' congestion detectionalgorithm depends on the accurate value for BaseRTT. If ourestimate for the BaseRTT is too small, then the protocol's throughputwill stay below the available bandwidth; if it is too large, then it willoverrun the connection. Authors tell that their experience is that protocoldoes well with its current choice of BaseRTT. However, they plan tostudy this more carefully in the future.