Transport: TCP

The transport layer of Internet implements two protocols: UDP and TCP. TCP, the transmission control protocol, implements reliable bi-directional byte streams between two applications on different computers. The end points of the streams are called TCP ports and one says that a connection is established between the ports. Thus, a TCP connection is identified by the IP addresses of the two computers and the two TCP ports.

We focus on TCP and explain how it provides reliability and how it adjusts the rates of the streams.

Reliability: Sliding Window Protocol. Internet uses a simple scheme to guarantee that every packet is received correctly. The sender can send N packets before getting any acknowledgment (ACK) (N = 4 in the figure). When it gets a packet, the receiver sends an ACK with the sequence number of the next packet it expects to receive in order so that it does not miss any packet. Thus, if the receiver gets the packets 1, 3, 4, it sends the ACKs 2, 2, 2 because it is waiting for packet 2. If an ACK for a packet fails to arrive after some time, the sender retransmits that packet and the subsequent N1 packets. The sender slides its window so that it starts with the last packet that has not been acknowledged in sequence.

Adjusting the Rate. As long as no packet gets lost, the sliding window protocol sends N packets every round trip time (the time to get an ACK after sending a packet). TCP adjusts the rate by adjusting the window size N. The basic idea is to approximate AIMD. Whenever it gets an ACK, the sender replaces N by N + 1/N. In a round-trip time, since it gets N ACKs, the sender ends up adding approximately 1/N about N times during that round-trip time, thus increasing the window size by 1 packet. Thus, the source increases its rate by 1 packet per round trip time every round trip time. When the source misses an ACK, it divides its window size by 2. Note that the connections with a shorter round trip time increase their rate faster that others, which results in an unfair advantage.

This scheme might take a long time to increase the window size to the acceptable rate on a fast connection. To speed the initial phase, the connection starts by doubling its window size every round trip time, until it misses an ACK. At that time, it divides the window size it was using by 2 and starts increasing it by 1 packet every round trip time.

A typical sequence of window sizes is then

1, 2, 4, 8, 16, 32, 64 [loss] 32, 33, 34, 35, 36 [loss], 18, 19, .

The version TCP Tahoe and TCP Reno contain a number of refinements of this basic scheme.

UDP, the user datagram protocol, implements an unreliable unidirectional packet delivery service from one UDP port in one computer to a UDP port in another computer.