Comp 343 Fall 1999 Dordal Sample Final Exam Answers 1. The problem is that there is no way to determine whether a packet arrived on the first attempt or whether it was lost and retransmitted. Having the receiver echo back immediately and measuring the elapsed times would help; many Berkeley-derived implementations measure timeouts with a 0.5 sec granularity and round-trip times for a single link without loss would generally be one to two orders of magnitude smaller. But verifying such an implementation is itself rather difficult. 2.(a). A would send an ACK to B for the new data. When this arrived at B, however, it would lie outside the range of "acceptable ACKs" and so B would respond with its own current ACK. B's ACK would be acceptable to A, and so the exchanges would stop. If B later sent less than 100 bytes of data, then this exchange would be repeated. (b). Each end would send an ACK for the new, forged data. However, when these ACKs were received, they would be acknowledging data not yet sent, and so each endpoint would transmit its own current ACK in response. These would again be ACKs of the forged data, and thus would again fail to be "acceptable", and so the two hosts would exchange ACKs again. This exchange of ACKs would continue indefinitely, until one of the ACKs was lost. 3. If a SYN is simply a duplicate, the ISN value will be the same. If the SYN is not a duplicate, and ISN values are clock-generated, then the second SYN's ISN will be different. Here is an algorithm. We will assume the receiver is single-homed; that is, has a unique IP address. Let be the remote sender, and lport be the local port. We suppose the existence of a table T indexed by and containing (among other things) data fields lISN and rISN for the local and remote ISNs if (connections to lport are not being accepted) send RST else if (there is no entry in T for ) Put into a table, Set rISN to be the received packet's ISN, Set lISN to be our own ISN, Send the reply ACK Record the connection as being in state SYN_RECD else if (T[] already exists) if (ISN in incoming packet matches rISN from the table) // SYN is a duplicate; ignore it else send RST to 4.(a). T=0.0 'a' sent T=1.0 'b' collected in buffer T=2.0 'c' collected in buffer T=3.0 'd' collected in buffer T=4.0 'e' collected in buffer T=4.1 ACK of 'a' arrives, "bcde" sent T=5.0 'f' collected in buffer T=6.0 'g' collected in buffer T=7.0 'h' collected in buffer T=8.0 'i' collected in buffer T=8.1 ACK arrrives; "fghi" sent (b). The user would type ahead blindly. Characters would be echoed between 4 and 8 seconds late, and echoing would come in chunks of four or so. (c). With the Nagel algorithm, the mouse would appear to skip from one spot to another. Without the Nagel algorithm the mouse cursor would move smoothly, but it would keep moving for one RTT after the physical mouse were stopped. 5. What is needed is that the receiver is doing reads in small chunks, after the sender has sent everything in its window and thus shrunk the window size to zero. After each read, the receiver frees a small chunk of buffer space and sends back its ACK with a window advertisement for this space. The sender then sends a chunk of data to fill this space, shrinking the window back to zero. The receiver could prevent this by not avertising less than a full-sized segment's worth of space. The sender could by not sending less than a full segment (unless PUSHed), and instead waiting for further window size increases. 6.(a). If every other packet is lost, we transmit each packet twice. We will *never* get an unambiguous measured_RTT, and so we will never update EstimatedRTT. We will stay with the exponentially backed off value (eg 4 sec) forever. An alternative implementation, that backed off on every subsequent loss, would actually have the timeout value increasing exponentially to infinity. (b). In this case we alternate between retransmitting and succeeding on the first try. Here is what happens in a cycle of three; initially EstimatedRTT is 1.0 and TimeOut is 2.0 sec: 1. Send first packet. It is lost, and we back off to 4 sec timeout. 2. Send it again. RTT is 1, but we ignore this. 3. Send the next packet, having returned to using 1.0 as EstimatedRTT. We get a SampleRTT of 1.0 also,so the updated EstimatedRTT is still 1.0. 7. If we detect the lost packet via Fast Retransmit (three duplicate ACKs), then we reduce the congestion window to 4KB but don't change the timeout interval. If we have a full timeout, then we back off the timeout period to 800 ms, and set cwnd=1 segment and begin Slow Start. However, when cwnd reaches 4KB, we then switch to congestion avoidance. 8. With TimeOut = 2 sec, there is no idle time on the R-B link: Time A recvs A sends R1 sends cwnd size 0 data 0 data 0 1 1 ack 0 data 1,2 data 1 2 2 ack 1 data 3,4 (4 dropped) data 2 3 3 ack 2 data 5,6 (6 dropped) data 3 4 4 ack3/timeout4 data 4 data 5 1 5 ack3/timeout5&6 data 4 1 6 ack 5 data 6 data 6 1 7 ack 6 data 7,8 (slow start) data 7 2 This continues with a period of 6. With TimeOut = 3 sec, the above becomes: Time A recvs A sends R1 sends cwnd size 0 data 0 data 0 1 1 ack 0 data 1,2 data 1 2 2 ack 1 data 3,4 (4 dropped) data 2 3 3 ack 2 data 5,6 (6 dropped) data 3 4 4 ack 3 data 7,8 (8 dropped) data 5 5 5 ack3/timeout4 data 4 data 7 1 6 ack3/timeout5&6 data 4 1 7 ack5/timeout7&8 data 6 data 6 1 8 ack 7 data 8 data 8 1 9 ack 8 data 9,10 data 8 2 9. Incrementing the Ack number for a FIN is essential, so that the sender of the FIN can determine that the FIN was received and not just the preceding data. For a SYN, any ACK of subsequent data *would* increment the acknowledgement number, and any such ACK would implicitely acknowledge the SYN as well (data cannot be ACKed until the connection is established). Thus, the incrementing of the sequence number here is a matter of convention and consistency rather than design necessity. 10. TIMEWAIT serves two purposes: to allow the host that sends the final ACK to retransmit it if it is lost, and to prevent the connection's being reopened while there is still a possibility that any lost packets from the first instantiation of the connection might still arrive. TFTP deals with the first issue by dallying; the client remains running for a while in case the sender should resend the final DATA (indicating that the final ACK did not arrive). TFTP deals with the second issue by making sure *both* sides choose new port numbers; this minimizes the chance that an old connection and a new connection would have the same port numbers. Note that TFTP can *not* implement TIMEWAIT literally, because TFTP is merely an ordinary application and there is no way for successive TFTP processes to keep track of which ports are supposed to be in TIMEWAIT and which are not. 11. This is trickier than I thought, and your exact answer may depend on whether you interpret the "queue size" as including the packet currently being transmitted, or not. (a). A gets A sends R's queue ack data T=0 1 T=1 1 2,3 T=2 2 4,5 T=3 3 6,7 T=4 4 8,9 5,6,7,8,9 T=5 5 10,11 6,7,8,9,10 11 lost T=6 6 12,13 13 lost T=7 7 14,15 15 lost T=8 8 16,17 17 lost T=9 9 18,19 19 lost T=10 10 20,21 12,14,16,18,20 21 lost T=11 10 B gets 12 T=12 10 11 B gets 14; 2nd duplicate ACK T=13 10 B gets 16 T=14 10 B gets 18 T=15 10 11? B gets 20; T=16 12 22,23 B gets 11; already has 12 T=17 12 B gets 22 T=18 12 13 B gets 23; 2nd duplicate ACK#12 T=19 14 24,25 B gets 13 T=20 14 B gets 24 (b) A gets A sends R's queue ack data T=0 1 T=1 1 2-3 T=2 3 4-7 T=3 7 8-15 14,15 lost T=4 13 16-21 T=5 13 T=6 14,15 TIMEOUT T=7 21 22 slow start T=8 22 23-24 12. One needs to identify an appropriate notion of a window. One could do this at the CHAN level; a CHAN CID is analogous to a connection. However, CHAN doesn't do the analogue of TCP segmentation, and multiple CHAN connections between the same pair of hosts seems plausible. Thus the BLAST level might be more suitable. At the BLAST level, the notion of window is simply the number of outstanding fragments. As described, however, BLAST has no mechanism for sending less than a full message; BLAST would need to be augmented with a way of marking the last packet of a windowful that wasn't the last packet of a message. With this protocol change, BLAST could pace itself so as not to send more fragments than its current cwnd, much like TCP.