TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

This paper introduces a new implementation of TCP, modifying TCP Reno for better congestion control. The main points are:

1. New retransmit mechanism: TCP Reno retransmits packet when a timeout occurs before receiving ACK or when n (generally set to 3) duplicate ACKs arrive for a packet. This, the authors show is a rather inefficient way because most of the time is left ununsed waiting for arrival of duplicate ACKs, even when checking of timestamps would make the need for retransmission clear. Vegas takes this approach. It retransmits when the time between sending of a packet and receipt of first duplicate exceeds timeout.
2. Proactive congestion avoidance:While Reno congestion avoidance is reactive, Vegas adjusts the congestion window by measuring expected throughput against actual throughput. It defines thresholds for optimal use of buffers in network routers, and dynamically adjusts bandwidth utilization. Unlike Reno, it does not rely on dropped packets to adjust the TCP window.
3. Modified Slow Start mechanism: Vegas adopts exponential growth for congestion window size only after every second RTT of a sent packet. This maintains the congestion window size constant until the RTT is measured. Now, if the actual throughput rates at the RTT is less than the expected, the window size grows exponentially. Otherwise, it grows linearly.

One reason I find Vegas heavy on the sender side is that it has to maintain the state information (like the timestamp etc) for every packet it has sent. This could introduce scalability problems.

For future research, Vegas could be deployed on current Internet topologies to see whether there is substantial benefit from the current TCP implementations.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

1. Conditions for retransmission — instead of using actual timer for timeout in every case or automatically retransmitting after n duplicate ACKs, assert interval between when a packet was sent and when a corresponding duplicate ACK was seen is within round-trip time.
2. Congestion control — instead of blindly increasing congestion window size until congestion is detected, decreasing the window size to compensate, then repeating the cycle, TCP Vegas makes an estimate based on non-congested round-trip time and the current congestion window size, and compares to the number of unrelated bytes sent between a packet and its ACK.
3. Slow-start — to set a more accurate threshold window for switching to linear expansion of the congestion window from exponential expansion, the experimental Vegas* is proposed. Vegas* sends four packets and waits for ACKs; as they arrive, it schedules congestion window size increases in the future and adjusts the threshold window based on the corresponding bandwidth estimates.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

Even though TCP is a standardized protocol, it leaves room for different interpretations of some of its key features, such as flow control and congestion control. The way this features are implemented can have a significant impact on the performance of the connection. This paper presents an implementation of TCP, called TCP Vegas, that tries to address some of the inefficiencies existing in previous implementations, in particular in the TCP Reno.

The TCP protocol is required to provide reliable communication (all the packets must eventually get to destination and must be reordered) and to deal with congestion control over the network. The hard part with that is that TCP must provide these features without basically having  any knowledge of the status and structure of the network. The only information a sender has is the round trip time (RTT) and the window size of the receiver. Different TCP implementations use these two parameters differently to provide the above mentioned features.

The TCP Vegas has these three main characteristics:

1. Packet lost detection and retransmission. A Reno receiver sends a duplicate ACK whenever it receives a new segment that it cannot acknowledge because the previous one is still missing. The sender instead waits for the third duplicate ACK in order to retransmit the packet. This potentially introduces a non-necessary delay in the transmission. On the contrary, upon the first duplicate ACK is received, TCP Vegas checks the elapsed time between the moment the  packet was sent and the time the duplicate ACK was received. If the elapsed time is bigger than the timeout value, it immediately retransmits the packet without waiting for the third ACK. The first two non-duplicate ACKs the sender receives after the retransmission are checked as well.  Again, if the elapsed time is bigger than the timeout, Vegas retransmits. This expedient allows Vegas to catch any other segment that may have been lost previous the retransmission without having to wait for a duplicate packet. With this retransmission technique, Vegas is able to considerably reduce the delay between the loss of a packet and the its retransmission. If, for any reason, Vegas is not able to catch the loss of the packet before the third ACK is received, it defaults to the Reno’s behavior.
2. Congestion Avoidance. The Vegas approach to congestion avoidance is based on the assumption that as the window size increases, the throughput is supposed to increase too. The limit to that is the available bandwidth, that is if the window size is increased more, the packets sent will only get buffered at the bottleneck link,  increasing congestion. Vegas’ congestion avoidance mechanism first computes the ideal throughput, the so called “expected”. Then it computes the actual throughput value. If their difference gets close to zero, the congestion window is increased and more packets are sent. On the opposite, if their difference increases, the connection is getting congested and therefore the window is reduced. Tests show that this approach not only improves the throughput by managing better the available bandwidth, but also it does that without taking bandwidth away from other connections. Hence this approach is fair.
3. Slow-start. The problem with the slow start mechanism is that it is hard to decide how big the threshold window should be. If it is too small, the connection would not get to use the full available bandwidth for a long time; if it is too large, the congestion window will exceed the bandwidth quickly resulting in many packet losses.Vegas addresses this problem by allowing the congestion window to exponentially grow only every other RTT, so then the sender has the time to observe the network behavior and react accordingly.

As major drawback of this paper I would say that in the performance analysis it focuses only on the Reno TCP implementation, which is not the only one available, even though probably the most common ones. It would therefore interesting to extend the performance comparison to other implementations and see whether all the claimed benefits of Vegas, such as the massive performance improvement over the Reno, still hold.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

Three Important Things:

• TCP Vegas makes several implementation changes on the sending side in order to achieve better bandwidth utilization. This means that it is still fully protocol compliant, but with significant optimizations. The first is an extension to the retransmission mechanism for lost packets. In the Reno implementation, TCP waits for 3 duplicate ACKs before retransmitting. The problem with this is that in many cases these ACKS are not received at all due to loss, and a timeout occurs. In order to reduce the number of timeouts and detect loss early, Vegas proposes to retransmit immediately if it is determined that a sent packet was not received. This is based on the response time for the duplicate ACK compared to the previously observed RTT.
• Another issue with Reno concerns congestion detection. It is a reactive protocol that needs to actually create congestion and loss in order to determine the bottleneck bandwidth. Vegas improves on the by again using a measurement and heuristic approach. It operates under the principle that increased window size should result in increased throughput. If it is observed that it does not, Vegas assumes that the extra segments are starting to fill up the router queues, and reduces the windows size. Also, when the throughput is too close to the expected value, more segments are sent to prevent under-utilization.
• Finally, the TCP slow start mechanism is modified to more quickly arrive at a reasonable window size with less overshoot and losses during the initial phase. Instead of performing exponential increase and the resulting exponential backoff, Vegas doubles its growth only on every other transmission. Using the congestion avoidance heuristc, the decision is made after the intermediate transmission whether to double again or switch to linear growth. The result is that the window size and throughput waveform is more stable initially, and settles faster into the familiar sawtooth shape.

Glaring Problem:

The new implementation relies heavily on the RTT measurement for all of its heuristic rules. This is a possible weakness in the protocol, as it requires the host to have an accurate timing mechanism that must have very low latency. It also makes the protocol susceptible to random flucutations in RTT time that could prompt it to behave erroneously.

Future Work:

The new ideas established in this paper should be further deployed and examined independently by others. Of particular interest is the study of the interactions between Reno and Vegas, since any rollout of Vegas would no doubt need to coexist with Reno for a long time. It might end up being the case that Reno ends up dominating Vegas in many cases and limiting its effectiveness.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

Paper discusses three techniques to increase throughput and decrease loses. These techniques result in timely decision to retransmit a dropped packet, ability to anticipate congestion, nd adjust transmission rate accordingly. Another technique which is modified slow-start mechanism avoids the packet loses while trying to find the available bandwidth during the initial use of slow-start.  Vegas reads and maintains a system clock each time a segment is sent. It does the RTT calculation when ACK arrives and this more accurate RTT estimate is used to retransmit in the following two situations.

Vegas introduces congestion avoidance mechanism which aims to look at changes in throughput rates, or more specifically changes in sending rtes. It compares measured throughput rate with the expected throughput rate . Goal of the Vegas is to maintain right amount of extra data in the network.  Vegas’s congestion avoidance actions are based on changes in the estimated amount of extra data in the network and not only on the dropped data.

Vegas modifies the slow-start. It allows exponential growth only every other RTT. In between congestion window is fixed hence enabling a valid comparison of the expected and actual rates. When actual rate changes below the expected rate by the equivalent of one router buffer, Vegas changes from slow start mode to linear mode. This enables Vegas to send as much data as is acknowledged in the ACK rather than sending more data as in case of Reno.

Paper also proposes a solution to the problems e.g. segments are send at higher rate than the available bandwidth increasing the likelihood of losses during the slow start process, Vegas still can overshoot the available bandwidth. It proposes to use the spacing of acknowledgements to gauge the available bandwidth. This available bandwidth is used to set the threshold window with an appropriate value.

Performance evaluations show that Vegas enhances to the Reno on throughput by 37% and on number of losses (by less than half) under real conditions.  As theses parameters are not only metrics by which a transport protocol is evaluated.  As the Internet community found the Reno’s level of fairness acceptable paper compares the fairness with respect to it. Paper concludes that overall Vegas is no less fair than the Reno though in some cases in outperforms and in other cases it underperforms.

In the initial phase Vegas in much better than Reno at recognizing and avoiding the congestion, Reno does not avoid the congestion but increases it in initial phases. Once load are high both performs similarly because in extreme cases course timeouts are involved and Vegas uses exactly the same coarse grain mechanism as Reno. Overall Paper assumes that there is no reason to expect Vegas to lead to network collapse because its mechanism is more conservative. Vegas uses between one and three buffers along the path for each connection which might lead to persistent queues at bottleneck router if everyone uses Vegas. But simulation results shows that average queue size are approximately same as Reno so it should not be a problem.

Overall Paper introduces several techniques for improving the TCP including timeout mechanism, congestion avoidance, and modified slow-start mechanism which enables it to achieve 37-to71% better throughput, with 1/5 to ½ as many bytes transmitted compared to Reno by the same time being as fair as Reno and without suffering from stability problem.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

This paper talks about Vegas, a different implementation of TCP and its performance comparison with implementation of TCP in Reno distribution of BSD Unix. The paper highlights three main changes made in different areas of TCP implementation, namely, a new timeout mechanism, a novel congestion avoidance scheme and a modified slow start mechanism. The paper also talks in detail about the experiments conducted for measuring this new implementation, both in internet setting and in an indigenously developed network simulator.

The new retransmission mechanism talked about in this paper extends the Reno’s retransmission mechanism. The Vegas implementation first reads and records the system clock each time the segment is sent. When an ACK arrives, it reads the clock again and calculates the RTT using the previous time recorded and this new time. It decides to retransmit the segment if the difference is greater than the timeout value instead of waiting for 3 ACK’s as implemented in Reno. This mechanism reduces the coarse-grain timeouts in RENO by more than half. The next novel feature of the implementation talked about in detail is the congestion avoidance mechanism. Vega uses the idea of measuring and controlling the amount of extra data (that fill up the buffers of the bottleneck router).  Therefore, Vegas’s congestion avoidance actions are based on changes in the estimated amount of extra data in the network, and not only on dropped segments. They calculate an expected throughput (using base RTT) and the actual throughput for a single RTT. The difference leads to increase/decrease in the sending rate depending on the two thresholds α and β respectively. The idea is to utilize the bandwidth available to the maximum and at the same time, not overflowing the network with data and congesting the other connections using the same path. These thresholds signify the number of buffers to be utilized at the bottleneck router. The third contribution of this paper is a modified slow-start mechanism. Vegas accomplish this by incorporating their congestion detection mechanism into slow-start with slight modifications.  Vegas allow exponential growth of sending rate every other RTT rather than in every RTT as done in Reno. This avoids congestion during the slow-start. They introduce an experimental slow-start mechanism incorporated in Vegas as Vegas* which uses the spacing between the acknowledgements to gauge the available bandwidth. This bandwidth estimate is used to set the threshold window with an appropriate value which makes it less likely to shoot the available bandwidth as in Vegas.

The paper discusses the simulation results at length, both in the internet setting as well as in network simulator. The authors report that Vegas achieves 37% to 71% better throughput, with one-fifth to one-half as many bytes being retransmitted, as compared to Reno. The authors also discuss the fairness argument for bandwidth allocation in context of multiple connections through same bottleneck router and comment that Vegas is as fair as Reno. Further, they report that Vegas doesn’t hurt network stability because it is conservative in its congestion window estimates and never increases its congestion window faster than Reno.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

This paper describes they modifications the authors made to the Reno version of the TCP protocol as implemented in BSD Unix in order to improve the behavior of the protocol in the face of network congestion.

They describe three major improvements to the TCP protocol, all of which affect the sender only, which makes this modification desirable from a deployment point of view:

1. The first mechanism modifies the retransmission behavior. Reno retransmits only when a coarse-grain timer event occurs or when it receives a certain number of duplicate ACKs. The problem with this is that these events do not occur very quickly and thus harm throughput as the sender waits to retransmit data. Vegas improves on this by timestamping segments and using ACKs as a trigger to check the timestamps on the next relevant segment against the RTT. This enables it to retransmit much sooner than waiting for a number of duplicate ACKs, in some cases even before it has received one duplicate ACK. This had the effect of reducing the number of coarse-grain timeouts by half, which they showed could have a considerable effect on throughput (19% if all coarse-grain timeouts could be removed).
2. The second mechanism involves how Vegas deals with congestion. Reno tends to be very reactive to congestion, and in fact it relies on generating some amount of congestion in order to determine the bandwidth of the network. Clearly, this is less than desirable, so Vegas takes a more proactive approach. It measures the achieved throughput versus the theoretical maximum throughput (measured in terms of RTT and window size), and then changes the congestion window to keep the achieved throughput between two thresholds which are relative to the theoretical maximum. The version that the authors settle on tries to keep between one and three buffers in use through the bottleneck router. They try to use at least one so that they can adapt to the bottleneck bandwidth increasing, and restrict it to three to keep from overrunning the bottleneck. This is probably the most important contribution of this paper, since it allows an increase in throughput while reducing the load on the bottleneck router relative to Reno.
3. The third mechanism involves the slow-start behavior of TCP. Their mechanism in many ways mimics the congestion avoidance mechanism described above in that it measures achieved throughput versus expected throughput and uses that threshold to switch from exponential to linear segment growth in order to mitigate overrunning the bandwidth of the network. This provides the same general slow-start behavior without generating nearly as much packet loss as Reno does during its slow-start period. Their performance numbers show that Reno’s packet loss numbers flatten out over time because of the relatively large amount of packet loss during the initial slow-start. In contrast, Vegas’s packet loss numbers scale linearly with transfer size, which indicates that there is no additional penalty incurred by its slow-start mechanism.

In addition to the performance validations performed for the three major enhancements, the authors also performed fairness, stability, and queue behavior experiements to ensure that Vegas would not harm existing Internet users as a result of small- or large-scale deployment. All of these experiments show that Vegas either outperforms, or at least does not significantly underperform Reno in all of the various metrics tested.

The main weakness of this paper is that the experiments were all relatively small-scale. This is probably an artifact of the age of the paper, but the Internet is so much larger than it was then, with so many different classes of traffic, that their performance numbers may not be as meaningful in a modern context. I would like to see their experiments rerun with modern bandwidth-delay products on the Internet today.

Future research in this field should examine the remaining performance left “on the table” in terms of TCP transmissions to determine the best parts of the protocol to improve. This paper focused exclusively on the sender’s side of the transmission, which makes their performance numbers all the more impressive. Even though the receiver is supposed to be passive in TCP, it might be interesting to see what kinds of further performance gains could be achieved by collusion between sender and receiver, with each taking an active role in maximizing throughput.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

(i) The three most important things the paper says:

1. TCP Vegas implements a new retransmission mechanism that keeps a timeout timer. Instead of just resubmitting if it receives 3 duplicate acks like TCP Reno does if when it receives any ack it checks if any of the previous unacknowledged packets has timed out it then resubmits those packets. This avoids doing a costly coarse grain timeout in the cases where the sender never receives 3 duplicate acks. This reduces the number of coarse-grain timeouts from TCP Reno by over half.

2. Another alteration implemented by TCP Vegas is in the congestion avoidance mechanism. TCP Reno relied on creating enough congestion that packets are dropped. This is not especially costly because of the retransmit and recovery mechanisms but it also creates losses for other connections using the same bottleneck router. Vegas instead keeps an average bounds of high and low transmission times and if a the new RTT is greater then it cuts the congestion window by 1/8. Vegas is able to keep the utilization of bottleneck links much higher than its predecessor.

3. The last major deviation brought by TCP Vegas is a modification to slow start. Slow start is used to gradually increase traffic until the maximum bandwidth is reached. Reno does this by increasing the dataflow exponentially every RTT while Vegas increases by only increasing the flow every other RTT. This gives the network a chance to react to the increase and bandwidth and reduces the probability of saturating bandwidth already near its peak.

(ii) The most glaring problem with the paper:

The biggest problem I had with he paper is they present the idea of a different slow start mechanism and say that it out performs the current implementation but then say they chose not to implement this technique because the benefit was only marginal. That is not good justification without indicating the cost of implementing this technique. If there is no extra cost or risk it would have been implemented but it would have been nice to know their reasoning.

(iii) The future research directions of the work:

The author believes there are still many advances to made towards congestion avoidance and that Vegas is only the first step. This is a call for this to be a continued research effort since the results are probably still suboptimal. The author also obviously presented his second slow start approach in hopes others could find a way to make the gain more than marginal. A seperate area of research is to consider congestion control not end-to-end but with help from the inner network at the router layer. With these details reactions should be able to be much quicker to the changing conditions of the network.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

(i) the three most important things the paper says

The first most important topic that the paper covers is the fact that TCP Reno relies on congesting a network in order for it to be detected.  This is a huge observation, as TCP Reno must effectively make the congestion situation worse in order for it to get better.  The authors claim (and thereby show) that TCP Vegas handles this situation much differently.  TCP Vegas attempts to predict a congestion-based situation before it leads to significantly decreased performance on the network as a whole (by clogging up buffers at each intermediate router).  What the authors are effectively saying here is that the anti-congestion measures in place in TCP should be based upon preventative measures instead of failure-based measures.

The next observation that the authors make deals with the conservativeness of the Reno retransmit algorithm.  The authors claim that the retransmit algorithm doesn’t quite detect when there’s been a lost packet quite fast enough (fast enough meaning before the next global timeout).  TCP Vegas addresses this by, instead of waiting for a third consecutive repeated ACK, attempting to guess based upon the timeout value of each individual outstanding packet (versus the global timeout).

A third important observation made by the authors stated that the slow start mechanism used by Reno was too aggressive.  The exponential start could basically create a congestion problem just by how quickly it can ramp up (without testing out the current network condition).  TCP Vegas handles this by providing more time in between exponential growth periods, allowing the TCP connection to gauge its progress slowly (a slower ramp up) without congesting the connection on a wrong guess.

(ii) the most glaring problem with the paper

One of the biggest problems with this paper is the fact that it introduces quite a bit of complexity to (what was) a relatively simple protocol.  This means that the TCP connection itself will require more processing power.  While this may not be of great concern to higher-computation capable modern PCs, this could become a problem for lower powered embedded systems that use TCP as a mode of communication.  With lower powered devices on the rise (internet phones, etc.) increasing the complexity of TCP might not be the greatest idea.

(iii) the future research directions of the work

I feel that a larger scale study could be done with TCP Vegas on a TCP Reno based Internet.  The study that was done contained a small set of Vegas connections over the internet, but what would be interesting would be assigning a large subset of the Internet to use the TCP Vegas design on top of the TCP Reno Internet.  I feel that this will reveal more information about the usefulness of TCP Vegas in a TCP Reno world (and whether or not the conservativeness of Vegas will fall prey to the aggressive actions of TCP Reno).

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

The paper proposes implements and evaluates a new implementation of TCP which is bound to contribute significant improvements over the current TCP implementation at that time, TCP Reno. The authors seek to improve upon the excessive network congestion problems posed by TCP Reno. TCP Vegas uses the same TCP specification, but implements a more robust retransmission strategy that can significantly reduce network load. The authors briefly describe their simulation environment running on their x-kernel platform and using the tcplib which gives them the flexibility to model different forms of TRAFFIC, like HTTP, FTP, and TELNET etc by a simple change in the way generation is specified. All the implementation is done in C by the authors to make sure the system emulates reality network traffic. The main points discussed in the paper include the three pronged strategy used by the authors to address Reno’s congestion, TCP Vegas’ performance and a brief discussion on the stability, fairness like attributes of the two protocols.

TCP Vegas makes a more timely decision to retransmit a dropped packet as against Reno which uses a method called coarse-grain timeouts which calls for the receiver to send out duplicate acknowledgements for missing packets. Reno waits for 3 duplicates before retransmitting, whereas Vegas compares the timeout with the difference between time when packet was sent and current time. If the latter is greater, a packet is retransmitted immediately. This results in a reduction of coarse-grained timeouts by a
half, leading to faster retransmission of lost packets. Also this is a huge advantage because in a highly congested network, 3 duplicates may never be received by the sender, and the receiver will keep sending duplicates, which further congest the network. The second improvement in Vegas is on the congestion control by attempting to anticipate congestion and using a proactive congestion avoidance strategy as opposed to Reno’s reactive one. In addition to adjustment the congestion window due to packet loss, Vegas uses a BaseRTT to compute an expected throughput and compares it with the actual throughput. The congestion window is thus managed using upper and lower thresholds (alpha and beta) to compare with the difference DIFF between and actual and expected throughputs. Lastly, Vegas improves the slow-start strategy by reducing the doubling of the congestion window size to every two RTT. After every intermediate RTT, it compares expected and actual sending rates. If the rates decrease by a router buffer, then Vegas stops the exponential increase and uses linear increase in congestion window size. This strategy can still make sure that as much bandwidth as possible is used, but not too much that the network becomes congested so quickly.

In the experiments conducted, Vegas is clearly shown to have outperformed Reno and equal it in the worst case of high packet rates when even Vegas’ timeout strategy becomes coarse-grained. Also TCP Vegas was shown to be more stable and resilient to parametric changes in the network when compared to TCP Reno. However, as stated by the authors, the main weakness in their approach is that alpha and beta throughput thresholds depends on a good minimum RTT estimate. In order for the system to be robust it is required that either alpha and beta must be made responsive to network conditions (they are currently chosen statically), or the formula for expected throughput changes. The formula for expected throughput assumes that the minimum achievable RTT does not increase, but it might change considerably if the path traversed by the connections is unstable. This suggests that dynamic adjustments to the alpha and beta parameters may be required in the future. Also another broad future requirement would arise if systems were to migrate to Vegas, at which point a harmonious interface needs to be developed to interconnect Reno and Vegas together in the network.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

i)

1. TCP Reno’s retransmit mechanism for dealing with packet loss is slow because TCP Reno checks to see if a timeout has occurred every 500 ms. To deal with this a fast retransmit mechanism was added to retransmit a segment after 3 duplicate ACKs were received which halved the number of retransmissions that had to wait for a timeout. TCP Vegas however proposes recording the system clock when each segment is sent and then retransmits if it receives a duplicate ACK for a segment that was sent greater than a timeout interval ago or in the case of if it just retransmitted some packet, then if it receives a non-duplicate ACK it will still check the timeout for that segment. This allows TCP Vegas to keep more precise timeout intervals because it checks them on a per ACK basis and also when packetloss occurs it allows TCP Vegas to quickly retransmit other subsequent packets that may have also been loss.

2. TCP Reno creates congestion to detect the bottleneck bandwidth by continually increasing the size of its window until packet loss starts to occur. TCP Vegas however avoids causing congestion and packetloss by dynamically determining when the available bandwidth is changing. It has two thresholds alpha and beta. When the difference between the actual throughput and expected throughput is less than alpha the congestion window is increased linearly and if it is greater than beta it is decreased linearly. In this manner TCP Vegas can detect when the available bandwidth is changing without having to saturate the bandwidth so much that packet loss begins to occur.

3. The mechanism proposed for TCP Vegas does not work well with TCP’s slow start. To address this issue the authors propose exponentially increasing the congestion window every other RTT instead of each RTT as is normal. By holding the congestion window fixed for two RTTs they can make a valid comparison of the actual throughput. They note however that this mechanism can send packets at rates higher than the available bandwidth and that they can overshoot the available bandwidth. They propose a mechanism that adjusts the estimation of available bandwidth based on ACK frequency, but then dismiss it saying that it does not really impact throughput or loss rate.

ii) I think one flaw in this paper is their simulations seem to be a bit simplistic. I don’t think they really emulate the internet infrastructure and how traffic flows on the internet. It would have been nice if their traffic simulations were a little more realistic.

iii) TCP Vegas concentrated only on the sending end and required no assistance from anyone else in the network. What would be interesting to explore would be if the performance of TCP could be increased by adding some option to the TCP header and have the other end of the connection or even routers along the path of the connection work together to provide better performance for everyone using that option.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

The paper by Brakmo and Peterson out of University of Arizona introduces a new TCP implementation, which improves on congestion avoidance mechanisms in TCP. The authors present the new techniques in contrast to the older TCP implementation called Reno, and evaluate simulation and measurement results of the two implementations. The three key techniques in Vegas are:

1) Retransmission mechanism: In both implementations, the goal is to avoid relying on coarse grained timers, and allow faster retransmission of lost packets in between coarse timer ticks. In Reno, this simply happens after three duplicate ACKs for an old packet are received. In Vegas, a timestamp is recorded for each sent packet and when the appropriate ACK for this packet is received, the Round-Trip-Time is updated. This RTT is used to see whether the first duplicate ACK already indicates a packet loss (because it arrives later than the estimate arrival time of the ACK of the lost packet) or if the first two ACK packets after a retransmission are also late, in which case more packets have been lost shortly before retransmission.

2) Congestion Avoidance: The authors describe Reno as an reactive implementation in the sense that Reno always pushes the bandwith over the “limit” of the optimal bandwidth by filling up router buffers on the way until packet loss occurs. This leads to oscillations in the send speed over long-going connections, filling up buffers unnecessarily. Their Vegas implementation, in contrast, tries to be proactive when increasing or decreasing the send window size. It does this by calculating the Expected and Actual throughput when changing the send window size, to find out if increases or decreases are necessary. This is done by comparing the rate to thresholds, so unnecessary oscillations are avoided.

3) Slow-Start: To optimize the slow-start period in TCP, the authors propose to use the congestion avoidance mechanism also during the slow-start phase, changing also the point in time where the send window size is doubled. This can only happen in Vegas once every two RTT, whereas Reno did it every RTT. This slows down the start a little, but avoids overshooting the available bandwith and reduces the need for retransmission.

The most glaring problem of the paper is the fact that the simulations don’t take different networks into accounts, no variations of the delay or available bandwith are simulated. Seeing the behavior in a multi-hop simulation with changing environmental conditions would have made a stronger point.

Future research directions for these TCP mechanisms are looking into congestion avoidance mechanisms that have minimal support from the routers on the way, which can signal end hosts and warn them about upcoming congestions or there optimal sending rate in a more direct way. These mechanisms could be simulated and evaluated.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

This paper talks about TCP Vegas, a TCP implementation based on TCP Reno but with better throughput and fewer packet losses. The basic idea is to try to predict congestion and avoid it, as opposed to Reno’s approach which creates congestion and then adjusts afterwards. The main contributions of the paper are:

1. Retransmission Mechanism: Reno uses a coarse timeout for retransmissions, thus typically taking too long before retransmitting. It also retransmits when 3 duplicate ACKs are received. However, Vegas realizes eliminating dependency on this coarse-grain timer would reduce timeouts further, and increase throughput. Vegas recalculates RTT times each time an ACK arrives, thus giving better estimates of RTT. Then it takes advantage of this accurate RTT and uses certain ACKs as a hint to check if a timeout should occur: (1) rather than waiting for N duplicate ACKs, each time a duplicate ACK is received, check to see if any of the relevant segments have timed out. If so retransmit them. (2)Check the timeout for segments in question for the first or second non-duplicate ACK is received after a retransmission. By using this policy, Vegas can quickly detect if a retransmission is necessary, rather than having to wait for the coarse grain timeout to expire.
2. Congestion Avoidance and modified Slow-start: Reno needs to create losses before it can detect congestion. It has to continually increase its window size for higher bandwidth, until it congests the network. Vegas on the other hand tries to predict congestion by comparing the current throughput to an expected throughput calculation. Vegas tries to keep bandwidth between two predetermined threshold values (indicating the number of extra buffers to use in the network). As for slow-start, Reno always sets the threshold window to half the congestion window when a retransmit timeout occurs.  The congestion window will exponentially increase until the slowstart threshold, after which it will be a linear increase. Vegas on the other hand only uses exponential growth every other RTT, and between the RTTs it keeps the window fixed to calculate an accurate throughput rate.
3. Implementation can play a significant role in performance of a protocol: TCP Vegas is an implementation of the TCP protocol, in the same manner that TCP Reno is. This goes to prove how implementation details that are typically left out of the protocol specification can play a significant role on the performance of the end-system, and thus careful considerations should be made for the implementation.

Problems: Vegas tries to always keep a few extra buffers filled up in the network. That is, it sends enough traffic to ensure that some segments are buffered up on the routers. While this might result in good performance for a few nodes, when there are thousands or millions of Vegas nodes all doing the same thing, the routers’ buffers could easily be overwhelmed and start dropping packets. It seems like a greedy idea to aim to buffer packets on the routers all the time.

Future Research: Vegas was the basis for RenoNew and therefore provided the groundwork for the current popular TCP implementation. I don’t know anything about RenoNew, but I would assume some research was done to change the buffering mechanism of Vegas, as it would have most likely overwhelmed routers’ buffers.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

Important things:
1) Vegas improves the “Reno” fast retransmission mechanism by checking for timeouts upon the receipt of certain ACKS (first two duplicate ACKs or the  two ACKs following a retrasmission), sometimes detecting packet loss before Reno does.
2) Vegas adds a congestion avoidance mechanism that tries to detect congestion before packet loss occurs. It is based on the idea that you want to maintain a reasonable amount of “extra data” in the network. If it is too high, it causes congestion. If it is too low, it will limit your ability to probe for more available bandwidth.
3) The Vegas implementation of TCP is still compliant with specification and interoperates correctly with other implementations. Also, it has been shown in real tests and in simulation to perform better than Reno, to utilize bandwidth more efficiently than Reno, and to be fair.

Problems:
In describing the retransmission mechanism, the authors state that a duplicate ACK is a rare occasion, and therefore the overhead is small. They also argue against reducing the threshold for fast retrasmission from 3 to 2 or 1 “because it makes assumptions about the likelihood that packets will be delivered out of order.” First of all, they had just made the assumption that the likelihood of out-of-order delivery was low in their reasoning that the overhead is small. Furthermore, having any threshold, be it 3 or less, makes assumptions about the likelihood that packets will be delivered out of order. This assumption of mostly-in-order delivery has effectively put restrictions on routing protocols when multiple paths are available.

Future Work:
A big question going forward is, what is the right way to detect packet loss? Should duplicate ACKs be used? In environments where multipath routing is used and packets belonging to one connection don’t all follow the same path, out-of-order delivery may be common, and an appropriate-length timeout may be the only way to go. The work done here could be very slightly modified, making any duplicate ACK, including the third or fourth, merely an occasion to check for timeouts. The overhead of this would of course have to be evaluated in environments where duplicate ACKs are very common.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

(i) Three most important things

1. TCP Reno uses coarse-grain timeouts in addition to the Fast Retransmit and Fast Recovery mechanisms to detect and transmit lost segments but eliminating the dependency on coarse-grain timeouts would result in a 19% increase in throughput. TCP Vegas proposes a new retransmission mechanism that treats the receipt of certain ACKs as a hint to check if a timeout should occur to reduce the time to detect lost packets.

2.  TCP Reno’s congestion detection and control mechanism uses the loss of segments as a signal that there is congestion in the network. TCP Vegas proposes that it looks at the changes in the sending rate to detect congestion. TCP Vegas compares the measure throughput rate with an expected throughput rate to determine the rate at which to send packets.

3. TCP Reno sets the threshold window for slow-start to one half of the congestion window. The slow-start period ends when the exponentially increasing congestion window reaches the threshold window and then increases linearly from then on but if the initial threshold window value is too small then throughput suffers or if value is too larger then packets will be lost. TCP Vegas allow exponential grown only every other RTT to able to detect and avoid congestion during slow-start and when the actual rate falls below the expected rate by the equivalent of one router buffer then Vegas changes from slow-start mode to linear increase/decrease mode.

(ii) Most glaring problem

The most glaring problem would be that when TCP Vegas is intermixed with other versions of TCP like Reno then the performance of TCP Vegas degrades because TCP Vegas reduces the sending rate before TCP Reno since Vegas detects congestion earlier and thus gives more bandwidth to the TCP Reno connections.

(iii) Future Research Directions

Future research directions for this work would be to study how the network congestion avoidance algorithm affects fairness when TCP Vegas connections need to compete with more aggressive TCP implementations like TCP Reno.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

The paper describes  a new implementation of TCP called the TCP Vegas which achieves between 37 and 71% better throughput on the internet with one-fifth to one-half of the losses as compared to implementation of TCP in Reno distribution of BSD Unix. The TCP Vegas essentially implements a new re-transmission mechanism than the Reno which depended on course clock ticks to time out and retransmit a segment. It was found that due to the coarseness of the clock, much time is wasted before it is realized that a packet is dropped and retransmitted, thus wasting a lot of time in waiting. Vegas on the other hand ignores any losses that happened before the last window size since it does not indicate congestion if the network for the current window size. It uses a notion of extra bandwidth available in the network computed from the current RTT times. It maintain two limits a and b which represents the lower and upper limit of the bandwidth available in the network respectively. The extra available bandwidth of the network is calculated as the difference of the actual RTT and expected RTT. The idea is to use this extra bandwidth estimate to always keep the links full and hence at full utilization. If the extra bandwidth falls below lower limit a it indicates congestion and hence the window size is reduced while if it is greater the upper limit b, the size is increased as it indicates more bandwidth is available. Hence it tries to keep the difference between the two limits a and b for full utilization. TCP Vegas also modifies the slow start policy of Reno which does not have any apriori knowledge of the available bandwidth thus leading to assumption of an arbitrary window size which might be too large or too small for the current congestion of the network and hence underutilizing or causing more packet drops during the initial phase of slow start. Vegas solves this problem by using their expected RTT estimation in the slow start mechanism. If the actual RTT is less than the expected RTT it continues exponential increase of window size while a greater RTT starts a linear increase to cope with the indicated congestion. Finally they also show that Vegas is as fair as Reno and it does not have any stability problems or adversely affect the latency.

The overhead of using extra computation to determine congestion in the network might have a slight adverse effect on the TCP Vegas compared to the previous versions of TCP. This might lead to a lower reactivity of the TCP congestion mechanism. But with todays increasing computing power, more complex congestion control mechanisms to be implemented in the TCP are becoming more feasible. Future directions may include using more sophisticated techniques like machine learning or artificial intelligence to determine congestion in the network and take appropriate measures to control it.

TCP Vegas: End to End Congeestion Avoidance on a Global Internet May 15, 2009

TCP Vegas is an improvement of TCP Reno that has better throughput by 37 to 71 % on the internet with 1/5 to 1/2 the losses. They achieve this better throughput by more efficiently using the available bandwidth by finding losses from packet delays instead of packet losses. They made 3 improvements that are listed in the major points.

Major Points:
1.) New Retransmission Mechanism
The old mechanism for Reno suffer from accuracies of clock that delayed timeouts for packets. To compensate that, Fast Retransmit and Fast Recovery were introduced. Through their measurements though, they found that getting rid of the coarse-grain timeout could increase throughput by at least 19 percent. Also Fast Retransmit requires at least 3 duplicate acks to be lost before a retransmit which requires at least 3 packets to always be in transmit. Vegas uses a slightly different mechanism to warrant a retransmission. They basically use certain acks as a receipt to hint whether or not a timeout should occur. Their timeouts are calculated using rtts and time stamps on packets. If the time stamp of an unorder ack comes in we check to see if the difference between the timestamps and current time is over the timeout; if so retransmit.
2.) Congestion Avoidance Mechanism
Reno does not use any congestion avoidance mechanism which can create losses and use up valuable buffers on the bottleneck router in the network. Vegas tries to avoid this by looking at window sizes and expected throughput.  It uses some special threshold with the difference of expected throughput, which is WindowSize/BaseRTT, with actual throughput to decide whether or not to increase the window size or decrease it.
3.) Modified Slow-Start Mechanism
To avoid the overshooting that causes congestion in slow-start, Vegas allows exponential growth only after every other RTT. In between, the congestion windows are fixed to calculate expected and actual rates. If the actual rate falls below the expected rate by the equivalent of one router buffer, Vegas changes to linear increase/decrease mode. There are two problems with this that Vegas address in Vegas* but simulation results show that Vegas* does not measurably impact throughput.

Glaring Problem:
A major problem that Vegas has is deciding the threshold values. The threshold values rely on finding the expected throughput which relies on a good minimum RTT. These values are constantly changing in a network which should call for dynamic assignments to threshold values.

Future Work:
Vegas presents new techniques that give better throughput while still being as fair as Reno. It also adds congestion avoidance mechanism that should improve the overall utilization of the network. Vegas only requires changes to the sender side in TCP so it should be easy to deploy. Vegas also created a simulation that should benefit future protocol testing.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

The paper introduces TCP Vegas and compares it against TCP Reno in terms of throughput and retransmission rate. The results show that Vegas makes uses of available bandwidth and avoids congestion (indeed avoids creating congestion) more effectively than Reno. Furthermore, these results are not at the expense of other non-Vegas TCP flows. TCP Vegas achieves these results even when all the flows are TCP Vegas flows.

The major contributions of Vegas are a new algorithm for determining retransmission, a new measurement for detecting (and thus avoiding) congestion, and a modified slow start mechanism that avoids overrunning bottleneck router buffers.

The new retransmission algorithm uses system clock timestamps to estimate RTTs instead of the BSD-based 500ms “ticks”. This means RTT estimates are more accurate. Further, Vegas uses ACKs to check if a timeout has occurred instead of waiting for a “tick” to pass. Lastly, instead of waiting for n (3) duplicate ACKs to be received before retransmitting, Vegas retransmits after the RTT has been exceeded.

The second contribution is the new congestion avoidance mechanism. Using a base RTT and accurately measuring the change in RTTs between segment sends and ACKs, Vegas can calculate an expected and actual throughput. Vegas then defines two thresholds, a lower and upper threshold. By adjusting the send window size to keep the throughput between the lower and upper thresholds, Vegas can keep between 1 and 3 segments in the bottleneck router’s buffer full. This means Vegas can effectively utilize available bandwidth without overrunning the bottleneck router’s buffer.

Lastly, Vegas uses the expected and actual throughput measurements to avoid overrunning the bottleneck router’s buffers during slow start. Instead of doubling the window size every RTT, Vegas doubles every other RTT. Every other RTT, it measures the throughput. If the throughput begins to decrease, Vegas switches to linear growth mode to avoid causing congestion in the network.

It seems clear from the results presented that TCP Vegas is a better implementation of TCP than TCP Reno. However, it would also seem that TCP Vegas is considerably more difficult to implement. The algorithms for the improved features are more complex than even TCP Reno (which is by no means simple).

I’d like see how quality of service implementations/mechanisms work with Vegas. Because Vegas is very adept at consuming available bandwidth without causing congestion, I expect that some QoS implementations will suffer because of the lack of “slack” bandwidth now available.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 14, 2009

The purpose of this article was to describe the TCP congestion control algorithm Vegas and list it’s key features, especially when compared to the Reno algorithm that was predominant when this article was written. The key points in this article were:

1.Vegas implements a more accurate RTT in the attempt to utilize packet delay, not just packet loss, as a condition to slow the flow of traffic. Reno was based purely on lost packets while the method that Vegas employs provides it with a more proactive solution. It also introduces a modified slow start mechanism that experimented with the standard Reno algorithm in an attempt to prevent overshooting the available boundary while simultaneously getting up to the available speed more quickly.

2.Vegas produced about a 40-50% improvement over Reno in most test cases in both throughput and loss rate. It also produced significantly less fluctuation in performance as it had the ability to slow its flow prior to the congestion reaching a critical level. This also allowed performance to degrade much more gracefully than what was observed under Reno.

3.In the areas of fairness and stability, Vegas was approximately equal to Reno with only slight variations on the measurements taken by each going either way. There was also little actual benefit gained from the modified slow start mechanism, as it did not significantly change the throughput or drop rate compared to the packet delay based control mechanism.

I really did not see any major issues with this paper. The authors were extremely thorough in explaining what they had done and why and were also extensive in their testing. One thing that could have possibly improved the paper would be to provide at least some preliminary results of test conducted against other TCP protocols but Reno.

The future research that this paper could lead to is primarily further development in the area of a TCP replacement algorithm. While the amount of bandwidth increasing, the number of services that require a large portion of it is increasing also and there is a great deal of discussion about how to optimize packet transmission and congestion control to provide the best service to all people depending on what they are doing. Better real-time streaming applications as well as more efficient large file transfer are just a couple of areas that could be improved. The other side of that is modifying the protocol to avoid the available bandwidth being dominated by a few. All are considerations that are being researched today.