Comp 443 Computer Networks Final Exam Study Exercises - Solutions Dordal, June 23, 2000 IN PROGRESS! Chapter 4: Very little of chapter 4 will be on the exam, but here are some of the solutions anyway. 6. 5 Mbps 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. 12. (a) Stored | distance to reach node at node | A B C D E F --------+---------------------------------------------------- A | 0 inf 3 8 inf inf B | inf 0 inf inf 2 inf C | 3 inf 0 inf 1 6 D | 8 inf inf 0 2 inf E | inf 2 1 2 0 inf F | inf inf 6 inf inf 0 (b) Stored | distance to reach node at node | A B C D E F --------+---------------------------------------------------- A | 0 inf 3 8 4 9 B | inf 0 3 4 2 inf C | 3 3 0 3 1 6 D | 8 4 3 0 2 inf E | 4 2 1 2 0 7 F | 9 inf 6 inf 7 0 (c) Stored | distance to reach node at node | A B C D E F --------+---------------------------------------------------- A | 0 6 3 6 4 9 B | 6 0 3 4 2 9 C | 3 3 0 3 1 6 D | 6 4 3 0 2 9 E | 4 2 1 2 0 7 F | 9 9 6 9 7 0 14. A---B---C | | | D---E---F 15.(a) A's table: dest | cost | nexthop --------+-------+-------- B | inf | - C | 3 | C D | inf | - E | inf | - F | 9 | C B's table: dest | cost | nexthop --------+-------+-------- A | inf | - C | inf | - D | 4 | E E | 2 | E F | inf | - D's table: dest | cost | nexthop --------+-------+-------- A | inf | - B | 4 | E C | inf | - E | 2 | E F | inf | - F's table: dest | cost | nexthop --------+-------+-------- A | 9 | C B | inf | - C | 6 | C D | inf | - E | inf | - (c) C's table: dest | cost | nexthop --------+-------+-------- A | 3 | A B | 15 | A D | 11 | A E | 13 | A F | 6 | F 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. 18. 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 arrives; "fghi" sent (b) The user would type ahead blindly at times. Characters would be echoed on the screen between 4 and 8 seconds late, and echoing would come in chunks of four or so. (c) With the Nagle algorithm the mouse wuld appear to skip from one spot to another. Without the Nagle algorithm the mouse cursor would move smoothly, but it would display some "inertia": it would keep moving for one RTT after the physical mouse were stopped. 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. 42. BLAST increments MID for each message; CHAN increments MID for each message with the same CID. Thus, the two can be synchronized only if there is only a single active channel. ========================================================== Chapter 6: 10(a) Pkt size flow Fi 1 100 1 100 2 100 1 200 3 100 1 300 4 100 1 400 5 190 2 190 6 200 2 390 7 110 3 110 8 50 3 170 Packets are sent in increasing order of Fi: Packet 1, Packet 7, Packet 8, Packet 5, Packet 2, Packet 3, Packet 6, Packet 4. 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.