The Transport Layer: TCP

Overview

We have seen that UDP is not a reliable transport protocol. Now, we will look at the TCP protocol which is reliable. TCP is a very complex protocol. We will look at the ideas behind at, but it is a large and deep topic.

Handling Errors

A packet sent with TCP may potentially be corrupted. Like UDP, TCP packets contain checksums which are checked when a packet is received. Unlike UDP, TCP will resend packets which are corrupted.

TCP sends acknowledgement packets (ACKs) when a packet was received successfully and negative acknowledgement packets (NAKs) when one was corrupted:

When a packet is lost, it is re-transmitted until it receives the ACK message.

One issue with this, however, is that the ACK and NAK packets themselves can be corrupted!

If the sender receives a garbled response, what should it do? There are two possible approaches:

1. It could ask the receiver to re-send the acknowledgement. This would be sort of a meta-NAK. However, what if that communication is corrupted? We would need a meta-meta-NAK. This would lead us to the Two Generals problem again.
2. If the acknowledgement is garbled, the sender could just re-send the packet anyway. If it was a NAK, everything is fine. However, if the acknowledgement was actually an ACK, then the receiver will now be receiving a duplicate packet.

TCP takes option 2. Now the receiver needs to distinguish a new packet from a duplicate one. To do this, TCP includes a "sequence number" field with all packets. When it receives a packet, it checks if the sequence number is a new one or not.

Handling Dropped Packets

In addition to corrupted packets, TCP handles lost packets. When a sender sends a packet, it is responsible for ensuring that the packet is received. When a packet (or the ACK for it) is lost, it must re-send the packet.

However, how can a sender know if a packet was lost or just delayed? From the sender's point of view, the only evidence of a dropped packet is the lack of an ACK for it. But maybe the ACK is on its way and just taking a while.

The sender has 2 constraints:

1. If they wait a long time to re-send, they are delaying the communication.
2. If they don't wait long enough, they will send many duplicate packets which is wasteful.

TCP has the sender wait long enough that packet loss is likely but not guaranteed.

Handling Order

TCP also handles the problem of packets received out of order. This is also handled with the sequence numbers. Whenever a packet is sent, there is a sequence number sent along with it. This sequence number starts at 0, and increments for each byte which is sent.

So if a sender wants to send a 5 kilobyte file, which gets broken into 4 packets (1500 bytes is about as big as packets get). It could then send the packets with the following sequence numbers:

When the receiver gets a packet, it will check if the sequence number is a duplicate (to avoid duplicate packets), and also use it to put the packets back into the correct order.

Pipelining

This is enough to give TCP the reliability that it promises. However, being reliable isn't the only goal of TCP. It also strives to be as fast as it can be. As described thus far, a sender basically will do this:

1. Send the next packet.
2. Wait for the acknowledgement.
3. If the ACK comes within a set timeout, go to step 1.
4. If not, re-send the same packet and go to step 2.

This is called a "stop and wait" protocol. Because we wait for a response after each send. The following figure depicts this:

Here the data transmissions are represented with the thicker bars. The sender only sends data after receiving a response.

A faster approach is to pipeline the transmission. This will entail sending multiple packets, one after the other, before hearing back on whether the first was received correctly or not.

Here we are pipelining by sending three packets before waiting for acknowledgement. This decreases transfer time because we can send three packets in a little less than the time to send one packet.

However it complicates the protocol somewhat. Now the receiver may receive packets 0 and 2, but not packet 1. How should it address these issues?

Go-Back-N

One approach to allowing for pipelining is the Go-Back-N (GBN) protocol. Here, we have some maximum number of packets that are allowed to be in flight at any one time.

We can send up to N packets before getting acknowledgement, but cannot go past that number. The following diagram gives an example of a GBN protocol when N is 8:

Here we have sent 5 packets that have not yet been acknowledged. Because N is 8, we can send 3 more, but cannot go past that.

The set of packets that can be in flight is sometimes called a "window". As the sender receives acknowledgement for sent packets, the window moves to the right. For this reason, GBN is referred to as a "sliding window protocol".

Below is what the sender and receiver each do:

• Sender

  When a NAK packet is received, or if a timeout is reached, the sender will resend the packet in question, and all subsequent packets. When an ACK is received, the window slides forward and the sender sends a new packet of data.

• Receiver

  When packets are received successfully, we send back an ACK for the most recently received packet only. For instance, if we receive 8 packets, we will only send an ACK for #8. This tells the sender we got them all and it can move along.

Selective Repeat

Another way of implementing pipelining is called selective repeat. It aims to avoid resending packets unnecessarily, as GBN sometimes will. In order to do this, the receiver sends ACKs for each packet individually, whether it is in order or not.

The sender must keep track of the status of each packet in the window individually. If one needs to be resent, it can resend only that one. Hence the name "selective repeat".

The sender/receiver operation is outlined below:

• Sender

  When a NAK packet is received, or if a timeout is reached, the sender will resend just the packet in question. When an ACK is received, we mark that packet has being acknowledged. If that was the oldest unacknowledged packet, then slide the window 1 to the right.

• Receiver

  When packets are received successfully, we send back an ACK for that packet. For instance, if we receive 8 packets, we will acknowledge all 8.

What are the trade-offs between the two protocols?

TCP Packets

TCP actually uses sort of a hybrid of these two schemes. Like GBN, it allows the receiver to acknowledge multiple packets at once. However, like SR, it allows the receiver to request the resending of specific packets, in any order.

Below is a diagram of a TCP packet:

The fields are described below:

• Source and destination ports are used for multiplexing, as in UDP.
• The sequence number we have discussed, it is the byte number for this packet from sender to receiver. It is used for re-ordering packets, and checking for duplicates.
• The acknowledgement number serves a similar purpose as the sequence number, but is for the other direction. TCP works in both directions, so this number is the byte that the sender expects back from the receiver from its data stream.
• The length field is the length of the packet header.
• The receive window is used for flow control. It is used for specifying the number of bytes the receiver can accept.
• The checksum is used the same way as it is in UDP.
• The "urgent data pointer" is used for sending "urgent" data. This is not normally used.
• Like IP, TCP includes options in the packet. These include setting time stamps on packets, and some optimizations. Also like IP, these are not normally used.
• The data field contains the application-layer data which is being sent.
• Finally, there are 8 1-bit flags (labelled A-F in the diagram). These are:
  1. The congestion window flag is used by TCP's congestion control.
  2. The explicit congestion flag is also used for congestion control.
  3. The urgent flag indicates that this packet contains urgent data.
  4. The ACK flag indicates that this packet is an acknowledgement.
  5. The push flag is used to indicate that the data in this packet should not be buffered, but should be sent to the application layer as soon as possible.
  6. The reset flag gets sent when a packet was not expected. For instance, if a host receives a packet from a host that it does not have an established TCP connection with.
  7. The synchronize flag is sent in a packet which establishes a TCP connection. This packet is sent first, then an acknowledgement of it, and finally an acknowledgement of the acknowledgement. This is called a "three-way handshake".
  8. Lastly the finished flag is sent when the sender has no more data to send.