State machine diagram

The STCP spec from PA4's description is provided here as a starting point. Note that this diagram does not account for timeouts, retransmissions or windowing.

Task 1

Draw the sequence diagram representing the full communication between the sender and the receiver for a successful data transfer with no losses. Include the full conversation from the sender's point of view, from CLOSED to CLOSED again. All packets shown in the diagram should include the sequence number used in the packet. Clearly indicate what is the number of data bytes included in each data packet. Your connection should include at least five data packets, and you should consider that the sender is able to send at least three data packets before an ACK is received for the first data packet, and the window size is large enough to accommodate this.

Once you're familiar with the process, repeat the same exercise for the ten scenarios listed under Process Analysis in PA4's description.

Reference Solution:

Checksums

Read the example here. For both of the tasks below, list the steps in constructing and verifying the checksums.

  1. The sender has a newly constructed packet and the fields in the header are in host byte order
  2. The receiver has just received a packet over the network and wants to verify the checksum

Determine if or when one would use the following steps

  1. Network to host byte order conversion
  2. Host to network byte order conversion
  3. Initialize the checksum field in the header
  4. Compute the checksum
  5. Assign the checksum field in the header

Reference Solution:

  1. We need to first convert the byte order into network byte order. Then we compute the checksum and put the checksum into the tcp header.
  2. Receiver verifies the checksum first. Then it converts the rest of the tcp header into host byte order.

The packet struct

typedef struct packet {
    unsigned char data[STCP_MTU];
    tcpheader *hdr;
    int len;
} packet;

Tasks

Write an expression in C for the following

  1. The checksum field on the TCP header
  2. The first byte of this segment's payload
  3. The last byte of this segment's payload
  4. Maximum length of this segment
  5. Maximum length of this segment's payload
  6. Size of the TCP header

Reference Solution:

// Assuming we have some pointer to packets
// This varies based on your design and implementation
packet *p;                              

// 1. The checksum field on the TCP header
p->hdr->checksum = ipchecksum();       

// 2. The first byte of this segment's payload
p->data + sizeof(tcpheader);            // Gets us the actual byte
p->hdr->seqNo                           // Gets us the seqNo of that byte

// 3. The last byte of this segment's payload
p->hdr->seqNo + payloadSize(p) - 1;     // Gets us the seqNo of that byte

// 4. Maximum length of this segment
STCP_MTU 

// 5. Maximum length of this segment's payload
STCP_MSS

// 6. Size of the TCP header
sizeof(tcpheader)

Flow Control

In PA4, we are also implementing flow control by limiting the sender to NOT send more bytes than the receiver's window. One naive way to achieve this is to use windowSize field from the ACK segments. For instance, if the sender receives an ACK with windowSize =600, in the next few segments the sender sends 600 bytes in a row (assuming that the sender has more than 600 bytes of data to send in the buffer).

There is a problem with this approach. Consider the following case:

What would happen if we send 600 bytes while there are 300 bytes of in-flight segments(data segments delivered but not yet received by the receiver)? Can we do better?

Task 2

Let's think about a slightly better way than just trust the windowSize to determine how many bytes the sender should send in the next segments.

Reference Solution: We need to count the in-flight packets! For example, we can do last_unacknowledged_seqno - first_unacknowledged_seqno + 1 to get the number of in-flight bytes. Then we can subtract that from the rdwn to get the actual receiver window.

Task 3: Retransmission

How many consequtive acks with the ackNo are required for fast retransmission? Suppose we need k consequtive acks for fast retransmission, what happens if the k+1th ack still has the same ackNo? What about k+2, k+3, ...

Reference Solution: We shall not retransmit the packet until we get 2k duplicated ackNo. This is because that we just made a fast retransmission when we get k consequtive acks; our retransmitted packet is highly likely on its way to the receiver. If we just retransmit every time we get k+1, k+2, ... ackNos, we are sending too much more packets than we need.