CS 655: Computer Networks Fall 2024

Homework 3

To be completed individually or in groups of size 2. Please review the academic conduct rules mentioned in the syllabus.

Answer all questions. Submit on Gradescope.

1. The stop-and-wait protocol that we discussed in the lecture actually cannot work properly if the underlying channel reorders packets. Draw a diagram showing why reordering packets could cause the stop-and-wait protocol (with 1-bit sequence number) to not work correctly. Make sure you clearly identify the sense in which it will not work correctly. Your diagram should have the sender on the left and the receiver on the right, with the time axis running down the page, showing data (D) and acknowledgement (A) message exchange. Make sure you indicate the sequence number associated with any data or acknowledgement segment.

2. Consider the GBN and SR protocols. Suppose the sequence number is encoded in 2-bit (sequence number range [0, 3]). What is the largest allowable send window for each protocol? Please explain your answer by drawing diagrams showing why the largest allowable send window size + 1 does not work properly. Assume the underlying channel can corrupt or lose packets but not reorder packets. Your diagram should have the sender on the left and the receiver on the right, with the time axis running down the page, showing data (D) and acknowledgement (A) message exchange. Make sure you indicate the sequence number associated with any data or acknowledgement segment.

3. Consider the GBN and SR protocols. Suppose the sequence number is encoded in 3-bit (sequence number range [0, 7]). Assume the underlying channel can corrupt or lose packets but not reorder packets. Sender sends packets 0, 1, 2, 3 and 1 gets lost. Please draw timing diagrams for following protocols to show how the lost packet gets recovered by the sender. Please indicate the packet number of each sent packet and ACK number for each acknowledgement.

   1. GBN with send window size = 4 and receive window size = 1

   2. SR with send window = 4 and receive window = 4

4. UDP and TCP checksum.

   1. UDP and TCP use 1s complement for their checksums. Suppose you have the following three 8-bit bytes: 01010011, 01100110, 01110100. What is the 1s complement of the sum of these 8-bit bytes? (Note that UDP and TCP use 16-bit words in computing the checksum, you are being asked to consider 8-bit sum for simplicity.) Show all work. With the 1s complement scheme, how does the receiver detect errors? Is it possible that a 1-bit error will go undetected? How about a 2-bit error?

   2. The sender of a UDP packet can choose not to calculate the checksum. In this case, the checksum field is filled with all 0s. What if the sender decides to calculate the checksum, but it happens that the result is all 0s? Please explain why this does not create confusion on the receiver side.

5. A client tries to communicate with the server over TCP. Client port is 50324 and server port is 80. Suppose the initial sequence numbers chosen by client and server are 8000 and 15000, respectively. For simplicity, assume the underlying channel is reliable (i.e., does not corrupt, duplicate, lose or reorder packets)

   1. Please draw a diagram showing the 3-way handshake. For each segment, please indicate the source and destination ports, sequence number and acknowledgement number (if valid) and control flags. Please note, you can ignore the sequence number of the ACK only packet.

   2. After the handshake, suppose the client sends one segment containing 200 bytes of data and closes the TCP connection with a FIN + ACK segment (half-close). Those two segments are sent to the server back-to-back. After receiving the FIN

      + ACK segment, the server sends one segment of 1000 bytes of data and closes the connection with a FIN + ACK segment. Suppose both endpoints send an acknowledgment whenever it receives a segment from the peer. Please draw a diagram showing the 4-way connection termination (FIN + ACK sent by client, ACK sent by server, FIN + ACK sent by server and last ACK sent by client). For each segment, please indicate the source and destination ports, sequence number and acknowledgement number (if valid) and control flags. Please note, you can ignore the sequence number of the ACK only packet.

6. A client communicates with a server over TCP. After 3-way handshake, suppose both client send window and server rwnd sizes are 800 bytes. 5 segments are exchanged between the client and server:

   1. The client sends 200 bytes to the server. Suppose the sequence number of the segment is 8001.

   2. The server receives 200 bytes and sends acknowledgement.

   3. The client receives acknowledgement.

   4. The client sends 300 bytes.

   5. The server receives 300 bytes and 100 bytes are consumed by the application. Server sends acknowledgement.

   6. The client receives acknowledgement.

   7. The server application consumes 200 bytes and the server sends acknowledgement.

      Please fill in the missing SeqNo, AckNo and rwnds. Also, please draw the send window in 4 time points: 1) after 1st ACK is received, 2) after sending the segment containing 300 bytes of data, 3) after 2nd ACK is received and 4) after 3rd ACK is received. When you draw the send window. Please indicate the send window size and the send window is divided into 2 parts, bytes outstanding and bytes that can be sent.

7. TCP is a reliable transport, and needs to tolerate reordering and loss of packets. For this example, assume a SmoothedRTT (aka EstimatedRTT) of 100ms and RTTVariation (aka DevRTT) of 50ms and that other forms of delay are negligible. 5 packets are sent at the same time. Assume no delayed ACKs, so an ACK is sent by the receiver immediately upon receipt of a packet.

   1. How much time will it take to detect and retransmit the lost data if any one of the 5 packets are lost and what mechanism is used?

   2. If there is reordering and any one of the first 4 packets arrives last instead of in transmission order, are there any cases data will be retransmitted spuriously?

   3. What changes in the above two cases if delayed ACKs are used and there is a delayed ACK timer of 200ms?

8. Consider the figure below. Assuming TCP Reno is the protocol experiencing the behavior shown, answer the following questions. In all cases, please provide a short discussion justifying your answer.

   1. Identify the interval of time when TCP slow start is operating.

   2. Identify the intervals of time when TCP congestion avoidance is operating.

   3. After the 16th transmission round, is segment loss detected by a triple duplicate ACK or by a timeout?

   4. After the 22nd transmission round, is segment loss detected by a triple duplicate ACK or by a timeout?

   5. What is the initial value of ssthresh at the first transmission round

   6. What is the value of ssthresh at the 18th transmission round?

   7. What is the value of ssthresh at the 24th transmission round?

   8. During what transmission round is the 70th segment sent?

   9. Assuming a packet loss is detected after the 26th round by the receipt of a triple duplicate ACK, what will be the value of the congestion window size and of ssthresh?

   10. Suppose TCP Tahoe is used (instead of TCP Reno), and assume that triple duplicate ACKs are received at the 16th round. What are the ssthresh and the congestion window size at the 19th round?

   11. Again suppose TCP Tahoe is used, and there is a timeout event at 22nd round. How many packets have been sent out from 17th round till 22nd round, inclusive?