Computer Networks

Computer Networks - CS132/EECS148 - Spring 2013

Instructor: Karim El Defrawy

Assignment 3 - Solutions

Deadline : May 9th

– 9:30pm (hard and soft copies required)

------------------------------------------------------------------------------

Problem 1 (Problem 6, Chapter 3 - 3 points) - Consider our motivation for correcting protocol

rdt2.1. Show that the receiver, shown in figure 3.57 of your book, when operating with the

sender, shown in figure 3.11 of your book, can lead the sender and receiver to enter into a

deadlock state, where each is waiting for an event that will never occur.

Suppose the sender is in state “Wait for call 1 from above” and the receiver (the receiver shown

in the homework problem) is in state “Wait for 1 from below.” The sender sends a packet with

sequence number 1, and transitions to “Wait for ACK or NAK 1,” waiting for an ACK or NAK.

Suppose now the receiver receives the packet with sequence number 1 correctly, sends an

ACK, and transitions to state “Wait for 0 from below,” waiting for a data packet with sequence

number 0. However, the ACK is corrupted. When the rdt2.1 sender gets the corrupted ACK, it

resends the packet with sequence number 1. However, the receiver is waiting for a packet with

sequence number 0 and (as shown in the home work problem) always sends a NAK when it

doesn't get a packet with sequence number 0. Hence the sender will always be sending a

packet with sequence number 1, and the receiver will always be NAKing that packet. Neither will

progress forward from that state.

Problem 2 (Problem 7, Chapter 3 - 3 points) - In protocol rdt3.0, the ACK packets flowing

from the receiver to the sender do not have sequence numbers (although they do have an ACK

field that contains the sequence number of the packet they are acknowledging ). Why is it that

our ACK packets do not require sequence numbers?

To best answer this question, consider why we needed sequence numbers in the first place. We

saw that the sender needs sequence numbers so that the receiver can tell if a data packet is a

duplicate of an already received data packet. In the case of ACKs, the sender does not need

this info (i.e., a sequence number on an ACK) to tell detect a duplicate ACK. A duplicate ACK is

obvious to the rdt3.0 receiver, since when it has received the original ACK it transitioned to the

next