Chapter 3 Transport Layer

I. General Discussion

Remember that the transport layer allows one to demultiplex traffic to an interface into several streams of traffic to particular processes. In TCP/IP, this is accomplished by making the address be the ordered triple consisting of the transport layer protocol number, the IP number of the interface of a machine, and a port number. Note that this distinguishes TCP port xxx from UDP port xxx.

In addition, it is typical to use checksums which can be checked to give assurance that data is not corrupted. Notice that the checksums do not provide security: in fact, it is a common occurrence in transit that the modifications are made in the headers requiring new checksums to be computed. A trnasport provider might want to verify that all components of the addresses are correct -- since the protocol number and interface ip numbers of the sender and receiver are in the IP header, it would make sense for the transport to include these fields to the actual transport header and data when the checksum is computed. The actual scheme is to put these additional fields into a so-called pseudo header, and compute the checksum on the pseudo header, the transport header, and the transport data.

1. UDP and TCP Checksums

The pseudo header consists of:

Recall that the UDP header looks like:

The checksum involves doing 1's complement adds of 16 bit 1's complement integers. Since nowadays most machines are 2's complement, you may not have done 1's complement arithmetic since CS/EE 280: The idea is that you can calculate the 1's complement sum by taking the 2's complement sum and adding in the overflow bit, should there be one. For details, see the very readable RFC 1071.

Here is the algorithm:

1. Lay out the Pseudo header and the UDP message including its header contiguously in memory. Put zero in for the Checksum field of the UDP header.
2. If the UDP message is of odd length, add a zero byte to the end to make the memory block an even number of bytes long.
3. Treating the block of memory as an array of 16 bit integers in network byte order, calculate the 1's complement sum of all the integers.
4. Take the 1's complement of the result.
5. If the result is zero, replace it with -0 (i.e. all bits set to 1).
6. Store the resulting value into the Checksum field. The pseudo header is not transmitted.

Note that we specifically avoided ever putting zero in for the checksum; a UDP packet with zero for the checksum indicates that the implementation did not compute the checksum at all!

For TCP, the algorithm is the same, including the definition of the pseudo header. The only difference is the location of the Checksum field in the TCP header.

So how do you implement it? Here is the nefarious, secret decoder ring version:

WORD CheckSum(WORD *buf, int nBytes) {
    DWORD sum = 0;
    while (nBytes > 1) {
        sum += *buf++;
        nBytes -= sizeof(WORD);
    }
    if (nBytes) {
        sum += *(UCHAR *)buf;
    }
    sum = (sum >> 16) + (sum & 0xffff);
    sum += sum >> 16;
    return (WORD)(~sum);
}

2. Reliable Data Transport

The goal is to create a data pipe: You should be able to write bytes into the pipe at one end and retrieve them out the other end. The input byte sequence should be identical to the output byte sequence. No data should be corrupted, out of order, duplicated or lost. In more detail:

• Data being corrupted means that certain bits have changed in transit. This might be caused by faulty electronic or photo components. This is relatively rare.
• Data being out of order can occur because packets in the internet may travel different paths.
• Data being duplicated usually occurs because of retransmissions. If a packet is delayed in the network long enough so that the sender retransmits it, both copies of the data may arrive at the destination.
• Data loss can occur as:
  • Lower level protocols may notice corrupted data and discard the packet.
  • Routers discard packets when congestion or errors occur.

The basic tools in combatting these problems are:

1. Checksumming of data, acknowledgments (positive, negative, or both) from the receiver, and retransmission in the case of error.
2. Sequence numbers for the data packets.
3. Sequence numbers for the acknowledgment packets.
4. Retransmission timeouts.

Let's look in detail at each of these:

1. Suppose that data packets are checksummed, the checksum is recalculated at the destination, and that an acknowledge (positive or negative) is sent back to sender. Upon a negative acknowledgment, the sender resends the packet; otherwise, it moves on to the next packet.

   What does this depend on?

   1. One must assume that the checksum is strong enough so that an incorrect packet is not misconstrued to be correct. (In the case of the internet checksum, what are some ways of perturbing the data such that the checksum will still match?)
   2. One must assume that all packets arrive in order.
   3. One must assume that no acknowledgment is corrupted (i.e. a NAK has not been transformed into an ACK or vice versa -- do you need both conditions?)
   4. One must assume that no packets are lost or duplicated. (What happens if an acknowledgment is lost?)
2. Now suppose that in addition, we add in Sequence Numbers for the packets. One can consider two possibilities: either the sequence numbers uniquely define the packets -- or that the sequence numbers repeat after a while, e.g. you might alternate with packet 0 and packet 1. Now the receiver must check both the checksum and the sequence number -- before sending an ACK or a NAK.

   If the set of sequence numbers is not large enough, and if there is reordering and duplication, then it is possible for an acknowledgment for one packet to be misconstrued as the acknowledgment for another.

   Now what are we depending on?

   1. The checksum must detect data corruption.
   2. The acknowledgments must arrive in order.
   3. The acknowledgment must not be corrupted.
   4. No packets are lost and no acknowledgments are duplicated.
3. Just as we protected the data with checksums and sequence numbers, we can do the same for the acknowledgments. Think of the acknowledgments as being simply data from the receiver to the sender. In this case, the sender uses its data packets to acknowledge the sender -- if it receives a corrupt or an NACK or an ACK for the wrong packet, then it resends the previous packet. Otherwise, it goes on to the next packet.

   We now are depending on:

   1. The checksum must detect data corruption in data and acknowledgments.
   2. No packets are lost or duplicated.
4. Finally, let's add retransmission timeouts. Note that these trigger retransmission -- of data or acknowledgments. This is the typical cause of duplicated packets.

   Now we are depending on:

   1. The checksum detects all data corruption.
   2. The sequence number set is large enough so that acknowledgments are always paired with the proper data packet.
   3. Whereas individual packets might be lost, repeated resends eventually cause the data to be delivered correctly.

So far, we have been concerned with making a reliable data channel. We have not been concerned with making an efficient one. In particular, we have:

1. Included loops with no upper bound on the number of times they may be repeated.
2. Also, we have not have not said anything about how to determine the proper length of a timeout. Getting this wrong could mean:
   1. If the timeout is too short, packets will be resent unnecessarily.
   2. If a timeout is too long, the channel is idle as you are waiting for a packet which is never going to arrive.
3. Packet tranmission is in lock step with acknowledgments. So, one does not transmit a new packet until the previous one is acknowledged. It is convenient to keep several transfers in progress at the same time -- otherwise, the sender can be idle waiting for an acknowledgment to arrive. But once, one gets several packets in transit at once, there is a question of what to do when a packet receives a NAK. e.g. Do you just send the particular packet or do you send that packet and all packets after that one.
4. Having made for greater throughput, one needs to be concerned about causing network congestion. So one will need flow control mechanisms.