Comp 443 Computer Networks Final Exam Study Exercises - Solutions Dordal, June 25, 2001 Chapter 4 6. The ident field is 16 bits, so we can send 576 * 2^16 bytes per 60 seconds, or about 5 Mbps. If we send more than this, then fragments of one packet could conceivably have the same Ident value as fragments of a different packet. 11(a). If multiple packets after the first arrive at the IP layer for outbound delivery, but before the first ARP response comes back, then we send out multiple unnecessary ARP packets. (b). We should maintain a list of currently outstanding ARP queries. Before sending a query, we first check this list. 27b: Ethernet bridges learn locations from the *source* field as they process forwarding packets to the *destination*. The main difference is that they are *able* to process packets with unknown destination, by falling back to "broadcast mode". IP routers do not have that option; they must have their forwarding tables complete in advance of being able to handle traffic. 32. A can reach B and D but not C. 38. (a):B (b):A (c):E (d):F (e):C (f):D 39ab. P's table: address nexthop C2.0.0.0/8 Q C3.0.0.0/8 R C1.A3.0.0/16 PA C1.B0.0.0/12 PB Q's table: address nexthop C1.0.0.0/8 P C3.0.0.0/8 R C2.0A.10.0/20 QA C2.0B.0.0/16 QB R's table: address nexthop C1.0.0.0/8 P C2.0.0.0/8 Q (b): The same, except for the following changes of one entry each to P's and R's tables: P: C3.0.0.0/8 Q // was for R R: C1.0.0.0/8 Q // was for P 40. The longest-match rule is intended for this. Note that *all* providers now have to include entries for PA and QB though. ========================================================== Chapter 5: 5. The two-segment-lifetime timeout results from the need to purge old late duplicates, and uncertainty of the sender of the last ACK as to whether it was received. For the first issue we only need one connection endpoint in TIMEWAIT; for the second issue, a host in the LAST_ACK state expects to receive the last ACK, rather than send it. 21. Whichever endpoint remains in TIMEWAIT must retain a record of the connection for the duration of TIMEWAIT; as the server typically is involved in many more connections than clients, the server's recordkeeping requirements would be much more onerous. 31.(a) The first incarnation must have closed successfully and the second must have opened; this implies the exchange of FIN and SYN packets and associated ACKs. The delayed data must also have been successfully retransmitted. (b) The most plausible scenario involves use of two parallel links, one of which developed massive congestion causing subsequent traffic to be routed via the other link. 34(a). One would now need some sort of connection number assigned by the client side to play the role of the port number in demultiplexing traffic; with this in place, headers might not change much at all. Client and server sockets will now be fundamentally different objects. Server sockets would be required to bind() themselves to a port number (perhaps at creation time); clients would be forbidden to do this. (b). We still need to make sure that a client connection number is not reused within the 2xMSL period, at least not with the same server port. However, this is now a TCP-layer responsibility, not an application concern. 37. 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 implicitly 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. ========================================================== Chapter 6: 14(a) In slow start, the size of the window doubles every RTT. At the end of the ith RTT, the window size is 2^i KB. It will take 10 RTTs before the send window has reached 2^10 KB = 1 MB. (b) After 10 RTTs, 1023 KB = 1 MB - 1 KB has been transferred, and the window size is now 1 MB. Since we have not yet reached the maximum capacity of the network, slow start continues to double the window each RTT, so it takes 4 more RTTs to transfer the remaining 9MB (the amounts transferred during each of these last 4 RTTs are 1MB, 2MB, 4MB, 1MB). Therefore, the file is transferred in 14 RTTs. (c). It takes 1.4 seconds (14 RTTs) to send the file. The effective throughput is (10MB / 1.4s) = 7.1MBps = 57.1Mbps. This is only 5.7% of the available link bandwidth. 20(a). Here is the table of events with TimeOut = 2 sec. There is no idle time on the R--B link. Time A recvs A sends R sends cwnd size 0 Data0 Data0 1 1 Ack0 Data1,2 Data1 2 2 Ack1 Data3,4 (4 dropped) Data2 3 3 Ack2 Data5,6 (6 dropped) Data3 4 4 Ack3/timeout4 Data 4 Data5 1 5 Ack3/timeout5&6 Data4 1 6 Ack5 Data 6 Data6 1 7 Ack 6 Data7,8 (slow start) Data7 2 24. The router is able in principle to determine the actual number of bytes outstanding in the connection at any time, by examining sequence and acknowledgement numbers. This we can take to be the congestion window except for immediately after when the latter decreases. Slow start after a coarse-grained timeout is trickier. The main problem is that the router has no way to know when such a timeout occurs; the TCP might have inferred a lost packet by some other means. After any packet is retransmitted, however, we should see the congestion window fall at least in half. This amounts to verifying multiplicative decrease, though, not slow start. 25. The new feature is fast retransmit; you can tell that at about T=5.5 because there is not a full timeout. Fast recovery, though, is still not shown. 28. Suppose the first two connections keep the queue full 95% of the time, alternating transmissions in lockstep and timed so that their packets always arrive just as a queue vacancy opens. Suppose also that the third connection's packets happen always to arrive when the queue is full. The third connection's packets will thus be lost, whether we use slow start or not. The first two connections will not be affected. 39(a). If we send 1 packet, then in either case we see a 1 sec RTT. If we send a burst of 10 packets, though, then in the first case ACKs are sent back at 1 sec intervals; the last packet has a measured RTT of 10 sec. The second case gives a 1 sec RTT for the first packet and a 2 sec RTT for the last.