Tcp Congestion Control Methods Tutorial Information Technology Essay

Transmission Control Protocol (TCP) is one of the two core protocols of the Internet protocol suite. Together with IP, they constitute the backbone stack of many internet applications like the World Wide Web, the e-mail and file transfer (FTP). Its main function is to provide a reliable stream service utilizing an unreliable packet delivery system inherited by its underlying IP layer. By the term reliable, we mean the reliable ordered delivery of a stream of bytes from one peer to another that runs the same TCP protocol stack. To add this substantial functionality and reliability, TCP imposes complexity. It is a much more complex protocol than its underlying IP protocol.

The main mechanism TCP uses to offer reliability is the positive acknowledgement and retransmission scheme. Transmitted segments must be acknowledged and if there is a loss, a retransmission takes place. To make the network utilization more efficient, instead of transmitting each segment only after reception of an acknowledgement for the previously transmitted segment, TCP uses the concept of a window. The window includes all those segments that are allowed to be sent without waiting for a new acknowledgment. TCP allows end to end adjustment of the data flow a sender introduces to the network by varying the window size. How can a sender know what is the suitable window size? A receiver indicates it in a window advertisement which comes to the sender as part of the acknowledgment.

Since modern internet applications are hungry for bandwidth, there is a high possibility that network becomes congested at some time. Routers have a finite storage capacity for handling IP packets. If the packet flow rate becomes excessive, router’s queue buffers will become full and their software will start to discard any new packets arrived. This has a negative impact in the TCP operation and performance in general. Increased delays and losses will impose retransmissions and hence increased traffic. In its turn, increased traffic will make congestion more severe and in this way, Internet will experience what is known as congestion collapse, exhibiting a performance fall of several orders of magnitude. To overcome this problem, TCP uses many mechanisms-algorithms to avoid congestion collapse and achieve high performance. The main idea behind these algorithms is to control the rate of data entering the network and keep it below a threshold rate. If this threshold were to be crossed, a new collapse phase could be triggered. Data senders can infer from an increasing number of delays that the network is congested and so adjust the flow in order to mitigate the phenomenon and give the network the necessary time to clear the queues and recover from congestion.

TCP Congestion Algorithms

RFC5681 describes four congestion control algorithms. Slow start, congestion avoidance, fast retransmit and fast recovery. All these algorithms work with the admission that sender infers network congestion by observing segment losses.

As mentioned above, in TCP, receiver’s buffer capability can be advertised backwards in the acknowledgement messages. This helps the sender to adjust its window size. Congestion algorithms introduce a second limit which is named congestion window. This new window is used for restricting the data flow of sender below the limit that main window determines. Actually, in a congested phase, the TCP window size used is the minimum value between the normal and congestion windows sizes. Reducing the congestion window reduces the injecting data flow to the network.

Congestion avoidance algorithm reduces the congestion window by half upon each segment loss. For those segments that remain in the window, it also backs off the retransmission timer exponentially. In this way, quick and significant traffic reduction is achieved. Upon loss of successive segments, the algorithm uses an exponential rate to drop the data flow and increase the retransmission timers. This gives enough time for the network to recover and become stable again.

Slow start algorithm is used when the network has recovered from the congestion and the windows start to increase again. To prevent oscillation between network congestion and normal conditions coming immediately after recovery, slow start indicates that congestion window must start at the size of a single segment and increase by one segment for each acknowledgement arrived. This effectively doubles the transmitted segments during each successive round trip time. To avoid increasing the window size too quickly, once congestion window reaches one half of its size prior to congestion, TCP enters a congestion avoidance phase and the rate of increment is abruptly slowed down. During this phase, congestion window increases by just one segment and only after all segments in the current window have been acknowledged.

Upon detection of a duplicate acknowledgment, sender cannot deduce if there was a loss or a simple delay of a segment. If ordinary out-of-order conditions are present, one or two duplicate acknowledgements are typically expected. If however, sender receives three or more acknowledgements, it can infer that there is loss of segments due to congestion and so it retransmits the segment (indicated by the position of the acknowledgement in the byte stream) without waiting for the retransmission timer expiration. This constitutes the fast retransmit algorithm.

Fast recovery follows fast retransmit algorithm and in the real TCP implementations these two algorithms are usually working together. Since reception of duplicate acknowledgements is a clear sign that data is still flowing in the receiver, fast recovery algorithm puts the sender in the congestion avoidance phase instead of the slow start phase. Therefore, if losses are not due to congestion, there will be a faster recovery of data flow without the penalty experienced by the use of slow start. However, fast recovery only works well for moderate congestion conditions.

Newer algorithms

Although the aforementioned four algorithms offer substantial congestion control, newer techniques have emerged in the bibliography as a result of extensive research in this specific area. These new algorithms try to build upon the old methods, enhancing TCP performance and increasing the responsiveness to congestion.

One limitation of normal TCP operation is that if a transmitted segment is lost but subsequent segments in the same window are delivered normally, the receiver cannot send acknowledgements for these last segments. The reason for this is that receiver can acknowledge only contiguous bytes that it has received. Sender will be forced, once retransmission timer for the lost segment expires, to resend not only the lost segment, but all subsequent segments in the window too. This was identified as a potential case for improvement which led to the creation of the selective acknowledgments (SACK) algorithm (Jacobson and Braden, Oct. 1988). The algorithm helps to reduce the number of unnecessary retransmissions by allowing the receiver to send some feedback to the sender about the contiguous byte stream blocks it has already received. In order to take advantage of the new technique though, the two TCP endpoints must agree on using SACK upon negotiation (by using the option field of the TCP header).

Two TCP original software implementations in the BSD Unix environment were named Tahoe and Reno. Tahoe includes the slow start, congestion avoidance and fast recovery algorithms whereas Reno includes all four basic algorithms described in the second section of this tutorial. NewReno is a slight modification of the Reno implementation and aims in boosting the performance during the fast retransmit and fast recovery phases. It is based on the notion of partial acknowledgements. In the case where multiple segments are dropped from a single window, sender enters fast retransmit phase and gets information about the retransmitted segments in terms of the first acknowledgment it gets. If only a single segment was dropped, then the acknowledgment will probably contain all segments previously transmitted before entering fast retransmit phase. If on the other hand, there were losses of multiple segments, the acknowledgment will be partial and will not contain all segments transmitted prior to fast retransmit phase entry. Using partial acknowledgements, fast recovery performance is enhanced as described in RFC2582. NewReno also improves round-trip and back-off timer calculations. In the literature, it is found that its main drawback is the poor performance in bursts of losses of segments within the same window (Wang and Shin, 2004).

Non-TCP congestion control

There are also some non-TCP techniques that can indirectly affect congestion control performance of TCP. These methods are not directly implemented in TCP software. The most popular technique of this kind is Random Early Detection (RED).

In order to understand the method, one first has to consider what is called the global synchronization problem (D. Comer, 2000). Routers in the global Internet use the tail-drop policy for handling datagrams. When their input queue is full, any incoming datagram is discarded. Since datagrams are usually multiplexed in the Internet, severe problems can occur regarding congestion. Instead of dropping many segments of one TCP connection, tail-drop router policy actually causes single segment drops from many TCP connections. This, in turn, put the senders of these connections in slow start mode at almost the same time causing the global synchronization problem, which degrades performance considerably.

To overcome this problem, RED (which is implemented in router software) defines two different thresholds that are associated with its internal queue, Tmin and Tmax. The following three rules govern the operation of RED

It the queue size is less that Tmin, add any new incoming datagrams to it

If the queue size is bigger that Tmax, drop any new incoming datagrams

If the queue size is between Tmin and Tmax, randomly discard incoming datagrams with the help of a probability p.

The main reason for this approach is to drop datagrams as congestion increases so as to avoid a queue overflow and a subsequent transition of many TCP connections to the slow start phase. As it is obvious, success of RED algorithm is based upon careful selection of the two thresholds Tmin and Tmax along with the probability p. Tmin must ensure high network utilization whereas Tmax must take into account the TCP round trip time so that it can accommodate the increase in queue size. Usually, Tmax is at least twice large as Tmin, or otherwise the same global synchronization problem may occur. Probability p computation is a complex task that is repeated for every new datagram. Non-linear schemes are used for this calculation in order to avoid overreacting to short bursts and protect TCP from unnecessary discards. These schemes usually take into account a weighted average queue size and use that size for determining the probability p. Details of RED are described in (S. Floyd and V. Jacobson, Aug. 1993). Research simulations show that RED works pretty well. It successfully handles congestion, eliminates the global synchronization problem that results from tail-drop policy seen before, and manages to allow short bursts without the need for extensive discards that could compromise TCP performance. When implemented by routers together with the TCP congestion control methods already built in the various network software implementations, it provides the necessary protection for network performance, securing its high utilization.

Conclusions

TCP performance is essential for providing true experience to single users, enterprises and everyone connected to the global Internet. One of the biggest challenges TCP faces as years come by, is congestion control (along with security which is another hot topic for TCP and other protocols). The original TCP standards described four methods that succeeded to almost eliminate congestion. As Internet increases in size and applications are becoming bandwidth hungry, new techniques that enhance inherent limitations of the four original algorithms are introduced and overall performance is kept in acceptable levels. Ongoing TCP research still focuses on congestion control and many new methods or variations are coming to fill any gaps that are gradually discovered by the ever-increasing Internet utilization.