Project Topics
Get Complete Project Material File(s) Now! »
Transmission Control Protocol
Introduction to TCP
TCP is the most important transport level protocol used on the Internet today. The purposes of TCP are:
• Provide an end-to-end reliable link between two hosts by taking care of retransmissions of lost segments and checking the integrity of the data.
• Provide a byte stream between the hosts, letting the user ignore segment boundaries.
• Multiplex several full duplex connections over IP.
• Provide flow control for the connection.
• Be robust in many environments, avoiding the need of fine-tuning.
• Protect the network from congestion by detecting it and slow down transmissions.
TCP has been around for quite a long time and has changed a lot over the years. The original specification [19] is now hopelessly outdated, but it is still the only document that claims to specify what TCP really is. Instead, the ‘Host Requirements RFC’ [22] can be seen as the most authorative document on what a TCP implementation should be like today. Unfortunately, it is getting old too and doesn’t mention the new research on TCP. A lot of textbooks that describes TCP also exists, including [2], [3], [5]and [7] which contain more or less modern descriptions.
TCP is a product of much experimenting and some standardization. The responsible body for Internet standardization is IETF, the Internet Engineering Task Force. IETF publishes RFCs, short for Request for Comments, which can be written by anyone who has a suggestion about the continuing evolution of the Internet. They are assigned a status depending on how well tested and accepted they are in the Internet community. RFC are never withdrawn, but only updated by other RFCs. This results in a situation where a RFC with the status ‘standard’ can be outdated or contain errors. Confusion about whether a ‘proposed standard’ should be implemented or not is not uncommon either. The status of a RFC can be found in the current version of [18].
Eventually, TCP is really defined by the implementations. Amazingly, this works quite well, probably thanks to the most important rule for implementation of Internet software, defined by Jon Postel: ‘Be conservative in what you do, be liberal in what you accept from others’.
Basic TCP Mechanisms
The TCP Header
The TCP data unit is called a segment. The segment consists of the TCP header (Figure 2-1) and the payload, which is the user data. The header is 20 octets long, but can be longer if TCP options (see section 2.5) are appended. The contents of a TCP header are described below.
Source and destination port: An application that wishes to use TCP must acquire one or more ports for sending and receiving data. The IP number and port number pairs (sockets) for both sender and receiver specifies a unique connection. This allows multiple applications on the same host and multiple connections for the same application.
Sequence number: Identifies the data so that TCP can deliver data to the receiver in the correct order. Each byte (octet) in the stream has its own sequence number. The sequence number of a segment is the sequence number of the first octet in that segment.
Acknowledged sequence number: The sequence number of the earliest data that has not yet been received.
Header length: The number of 32-bit words in the TCP header. Indicates where the data begins.
Reserved: Is zero if not used.
PSH (push) bit: All data in the TCP input buffer, including the segment with the bit set, should be made available to the application as soon as possible.
RST (reset) bit: The connection should be aborted.
SYN (synchronize) bit: A new connection is requested.
FIN (finish) bit: One side of the connection is finishing data sending.
Advertised window: The number of free octets that the receiver has in the input buffer. The sender may not have a larger amount of unacknowledged, outstanding data than this number.
Checksum: A checksum of the TCP header, TCP data and some of the fields in the IP (internet Protocol) header.
Urgent pointer: Informs the receiver that data that should be processed as soon as possible has arrived in the stream. Exactly what the pointer points to has historically been under discussion. Different implementations have used different interpretations of the original standard.
Options and padding: See section 2.5.
Sliding Window, Queuing and Acknowledgements
TCP is a sliding window protocol. This means that the receiver is prepared to receive data with sequence numbers within a certain range. If data arrives out-of-order, TCP must wait for the delayed or lost data before delivering all data to the application layer.
The TCP receiver tells the sender which data it has received by setting the acknowledgement field in the TCP header to the next expected sequence number.
TCP must maintain an input queue (buffer) to store segments that has arrived early. TCP receivers tells the sender how much free space it has in the input queue by setting the advertised window field in the TCP header.
After receiving a data segment, TCP responds by sending an acknowledgment segment back to the sender. If new data is acknowledged, the sender can remove the acknowledged data from its output queue. If the advertised window field is larger than the amount of sent, unacknowledged data, then the sender can send more data. This is the way that TCP implements flow control.
Modern TCPs use delayed acknowledgements. When a data segment is received, the receiver waits up to 500 ms before sending an acknowledgement. By not sending the acknowledgement right away, TCP gives the application a chance to respond with data that can be sent back together with the acknowledgment and to update the advertised window. If the data stream consists of full sized segments, TCP should not always wait for the entire delay, but must send an acknowledgment for at least every second segment received.
Retransmission Timer Management
TCP uses a timer to discover loss of segments. The timer is running whenever unacknowledged data is outstanding in the network. It is restarted when data is acknowledged. When the timer expires the first data that hasn’t been acknowledged by the receiver is retransmitted.
When a retransmission timeout occurs, the new RTO (retransmission timeout) value is set to twice the previous value. This is called exponential back off.
The algorithm that is now used for setting the RTO value is called the Van Jacobson algorithm after the inventor [36]. The algorithm works by measuring the time between when a segment is sent and acknowledged. This value is called the round trip time (RTT) of that segment. The algorithm calculates a smoothed round trip time value and the smoothed variance from the newly measured RTT value and the old smoothed RTT and variance. The RTO value is then based on the smoothed RTT and variance. Figure 2-2 shows the algorithm.
RTTVAR is the variance of the RTT, SRTT is a smoothed value of the RTT and RTO is the retransmission timeout value. G is clock granularity.
RTTVAR = 3/4 * RTTVAR + 1/4 * abs(SRTT – RTT) SRTT = 7/8 * SRTT + 1/8 * RTT RTO = SRTT + max(G, 4*RTTVAR) RTO = min(RTO, 240 seconds) RTO = max(1 second, RTO)
These rules applies to the second and all following RTT measurements. For the first measurement, the following rules apply:
SRTT = RTT
RTTVAR = RTT/2
RTO = as above (always evaluates to three times the measured RTT)
When no RTT measurements have been made, RTO is initialized to three seconds. The upper limit of RTO can be anything above 60 seconds, but is typically 240 seconds.
Figure 2-2 – Simplified description of the algorithm for calculating RTO standardized in [32]
To get correct values when measuring RTT, the measurements may not be done on retransmitted segments. This rule is called Karn’s algorithm.
The retransmission timeout algorithm also includes rules for what to do when a segment has been retransmitted so many times that the other side of the connection or the network path can be considered to have crashed. In this case the connection will eventually be closed. See [22] for details.
Connection Establishment and Shutdown
Since one of the purposes with TCP is to provide a connection, not just to transport segments, there is a need to set up and remove the connections in a reliable way. For this purpose TCP uses a finite state automata with eleven states. Both server and client use the same automata. Details on the TCP states and TCP state changes are given in [19]and [22].
Three-Way Handshake
The TCP connection is set up using an algorithm called three-way handshake. It mostly works as shown in Figure 2-3.
The client sends a segment, optionally including user data, with the SYN (synchronize) TCP header bit set. The server responds with a segment that acknowledges the received segment and also has the SYN bit set. Note that the SYN bit is counted as an octet of data, which will allow TCP to acknowledge a segment with a SYN bit with no real data using its ordinary ACK header field. When the client has received the server’s SYN segment and successfully acknowledged it, the connection is established on both sides.
In the figure, numbers j and k are chosen using a clock-driven algorithm, minimizing the possibility of old segments that have been delayed in the network to arrive and be mixed up with the segments of the new connection.
The three-way handshake does not always look like this. For example, if no application on the server is listening to the port that the client is trying to connect to, the server should return a segment with the RST bit set, causing the client to abort the connection attempt. Also, if one of the segments is lost during connection establishment it must be retransmitted using the retransmission timer.
Yet another possibility is that both sides will try to connect (actively open) at the same time.
This works fine, although the notion of TCP client and server is lost in that case.
Symmetric Release
The algorithm for shutting down a TCP connection is called symmetric release, since it is best seen as a way to shut down a pair of simplex (one-way) connections independently of each other. The host that wishes to send no more data sends a segment with the FIN TCP header bit set. This bit is, like the SYN bit, also counted as a bit of data. When the FIN segment has been acknowledged that direction of the connection has been closed.
The other direction will still be open and may be used for (in the first closers perspective) receiving data. The shutdown of the other direction will work in the same way. It is also possible that both sides will try to close simultaneously, which will also work.
The shutdown of a connection includes the TIME_WAIT state, which exists to give old segments time to leave the network before another connection between the same two hosts and ports (sockets) can be established. The wait time is two times the estimated maximum segment lifetime (MSL) for the network, which equals to 2*120 seconds. However, if special precautions are taken (given by [22]), a connection can be reopened (using the three-way handshake) from TIME_WAIT. The waiting time is sometimes confusing to the user of a TCP implementation, because his servers will refuse to restart before the waiting time is up.
TCP Options
The TCP options can be used to implement features that are not part of the original TCP specification without breaking backward compability. By setting the header length field to something above five (a TCP header without options is five 32-bit words) the user can send up to 40 octets of TCP option data. (The header length field is four bits wide and 15*32 bits – 5*32 bits = 40 octets.). The option consists of either a single octet that is an option identifier or one byte octet option identifier plus one octet of option length plus octets of option data. Because the header length is given in a number of 32-bit words, the option space that isn’t used has to be padded with zeros.
Below, three commonly used TCP options are explained. The more complicated SACK/DSACK options are explained in sections 2.6.5 and 2.6.6.
Maximum Segment Size (MSS) Option
This is the only option (besides the end of options list and the no operation options) specified in the original TCP specification. It is used by a TCP to tell the peer the maximum size of segment that it is prepared to receive. This negotiating mostly happens during the three-way handshake when the option is included in the first segment that is sent from each side (that with the SYN bit set). If no MSS option is received TCP falls back to sending segments of the default size of 536 octets data. The segment size field is 16 bits wide, allowing segments to be up to 64 KBytes. Note that this is the same size as the maximum advertised window size. See [22] for details and a discussion of how the segment size affects performance together with IP.
Window Scale Option
The advertised window is limited to 64 KByte by the original TCP specification because the advertised window header field is only 16 bits wide. That is a problem on networks with a large bandwidth*delay product. The product is a measurement of how much data that must be outstanding (in transit in the network) to get full throughput. One example is a 100 Mbit network with a RTT of 10 ms. The bandwidth*delay product is (10^8)/8 bytes/second * 10^-2 seconds = 125 KBytes, which means that the network will only be used to about half of its full capacity with a single TCP connection without the window scale option.
A solution to the problem is given in [24] and is based on a TCP option with an eight-bit data field holding a scaling factor. The scaling is interpreted as how many times to binary left shift the advertised window field. The maximum number allowed is 14 which gives an advertised window of 2^16 * 2^14 = 1 GByte.
Timestamp Option
TCP in Long Fat Networks (LFN), i.e. networks with a large bandwidth*delay product, also has other problems. First, the 32-bit sequence numbers are quickly reused if lots of data is transmitted. In a Gigabit network it takes about 17 seconds to wrap around. This should be compared to the maximum segment lifetime (the time a TCP segment is assumed to remain in the network in the worst case), which is 120 seconds. The problem is that segments may be reordered by the network, making it possible for an old segment to undetected be accepted as new data after the sequence number has wrapped around.
Secondly, the RTT sampling in a standard TCP implementation only occurs about once every RTT seconds. If the throughput is high, only a very small fraction of the segments are sampled. This may lead to poor quality in the RTO calculation. It is desirable to measure RTT for every segment, except retransmitted segments. Instead of keeping a list of all outstanding segments and the times when they were sent, the idea is to keep a 32-bit timestamp in the segment itself. The timestamp is then echoed by the receiving TCP, which also sends back a timestamp of its own. All the TCP needs to do to get the RTT is to subtract the timestamp time from the current time.
The real time clock that records the timestamps ticks much slower than the sequence numbers change, perhaps once every millisecond. The receiver can use both the timestamp and the sequence number to determine if the segment is old or new. This way the first problem is also solved using the timestamp mechanism.
TCP Congestion Control
Early TCP implementations relied only on the receivers advertised window when limiting the amount of data to send. The result was that TCP sent too much data into the network causing routers to be overloaded. When routers don’t have room for more packets in their input buffers (queues), they have to drop segments, causing a timeout in TCP. After the timeout TCP starts sending a lot of data again, overloading the network. Overload in a network is called congestion. A number of new TCP mechanisms were suggested (in [36]) to deal with this problem. They were called congestion avoidance, slow start, fast recovery and fast retransmit and were standardized in [29]. These methods and several others are described below. Note that TCP assumes that all segment losses are caused by congestion.
To limit TCP’s aggressive behavior, implementations are required to keep a congestion window (cwnd) variable for each connection. The minimum of the cwnd and the receivers advertised window is used to limit the amount of outstanding data.
Congestion Avoidance
To utilize available bandwidth the cwnd is increased with one full sized segment every RTT. In practice it is actually done by increasing it by MSS*(MSS/cwnd) every time an acknowledgement is received, because about (cwnd/MSS) acknowledgements will arrive every RTT. This is called addititive increase and is a conservative way to investigate the available bandwidth in the network. When the TCP uses addititive increase it is said to be in congestion avoidance.
Slow Start
Congestion avoidance is too slow to use in the beginning of a connection. Instead an algorithm called slow start is used. Slow start uses an exponential growth in the amount of allowed outstanding data. For each acknowledgement that arrives, the cwnd is increased by one full sized segment. So, for every acknowledgement that is received (at least) two new segments will be sent into the network, one to replace the segment that just left the network and one to use the increased cwnd.
Slow start is continued until the amount of outstanding data reaches the slow start threshold (ssthresh). This value may be arbitrary high, but is often set to the amount of the receivers advertised window [22]. When slow start is discontinued, the connection goes into congestion avoidance.
Retransmission Timeouts
The data sender discovers network congestion when the retransmission timer expires. To protect the network the data sender sets ssthresh to half the amount of outstanding data (which may be much lower than the current cwnd if the sender is limited by the receivers advertised window). This is called multiplicative decrease.
The cwnd is set to one segment (the ‘loss window’), which means that TCP goes back to slow start (because cwnd is now lower than ssthresh).
Also, the RTO value is doubled and the earliest segment not yet acknowledged is retransmitted, as outlined in section 2.3.
(NewReno) Fast retransmit and Fast Recovery
Retransmission timeouts was the only method early TCP implementations could use to discover segment loss. This is clearly inefficient, as TCP first has to wait for the retransmission timeout and then go to slow start each time a segment is lost, even if it is only necessary to decrease the cwnd. The fast retransmit and fast recovery algorithms deals with these two problems. Both algorithms are often implemented together and because of that they are often treated as one.
Both sender and receiver are involved in the algorithms. The data receiver must send an acknowledgment each time an out of order segment arrives and each time a segment that fills a hole in the input queue arrives.
Table of contents :
1 Introduction
1.1 Motivation for This Thesis
1.2 Methodology
1.3 Organization of This Thesis
2 Transmission Control Protocol
2.1 Introduction to TCP
2.2 Basic TCP Mechanisms
2.2.1 The TCP Header
2.2.2 Sliding Window, Queuing and Acknowledgements
2.3 Retransmission Timer Management
2.4 Connection Establishment and Shutdown
2.4.1 Three-Way Handshake
2.4.2 Symmetric Release
2.5 TCP Options
2.5.1 Maximum Segment Size (MSS) Option
2.5.2 Window Scale Option
2.5.3 Timestamp Option
2.6 TCP Congestion Control
2.6.1 Congestion Avoidance
2.6.2 Slow Start
2.6.3 Retransmission Timeouts
2.6.4 (NewReno) Fast retransmit and Fast Recovery
2.6.5 Selective Acknowledgement (SACK)
2.6.6 Duplicate Selective Acknowledgement (D-SACK)
2.6.7 Limited Transmit
2.6.8 Rate-Halving
2.6.9 Automatic Receive Buffer Tuning
2.6.10 TCP Vegas
2.7 Network Based Congestion Control
2.7.1 Drop-Tail Queue Management
2.7.2 Random Early Detection (RED)
2.7.3 Explicit Congestion Notification (ECN)
2.7.4 ICMP Source Quench
2.8 Other TCP Mechanisms
3 The GPRS Subsystem of GSM
3.1 The GSM System
3.2 GSM Nodes
3.3 GSM Radio Interface
3.4 Data in the GSM system
3.5 The GPRS Subsystem
3.6 Changes to the GSM Radio Interface
3.7 GPRS Nodes
3.8 The GPRS Protocol Stack
3.8.1 Application Layer
3.8.2 Transport Layer
3.8.3 Network Layer
3.8.4 Data Link Layer
3.8.5 Physical Layer
3.8.6 Tunneling Protocols
4 A TCP Traffic Generator for GPRS
4.1 Background
4.1.1 The TSS System
4.2 Requirements
4.2.1 Important TCP Mechanisms
4.2.2 Model of the Internet
4.3 Implementation Details
4.3.1 User-Adjustable Parameters
4.3.2 User Models
4.4 Software Setup and Simulation Limitations
4.4.1 The Protocol Stack
4.4.2 The PCU Simulator
4.5 Conclusions
5 TCP Performance over RLC/MAC
5.1 Introduction
5.2 TCP Connection Establishment over RLC/MAC
5.2.1 Access Modes (Different Ways to Establish Uplink TBFs)
5.2.2 Changing between Downlink and Uplink TBFs
5.2.3 Interactive Sessions
5.3 Uplink Acknowledgement Clustering
5.4 RLC and TCP Retransmissions
5.4.1 The TCP Retransmission Timer in GPRS
5.5 Buffers in RLC and TCP
5.5.1 RLC Buffer Sizes
5.5.2 TCP Advertised Window
5.6 Uplink TCP
5.7 Conclusions
6 Conclusions
Appendix A. Additional Figures
Appendix B. TCP Feature Importance Rating
Appendix C. Introduction to Network Software
Bibliography
Copyright Notice
