Comp 443 Computer Networks Final Exam Study Exercises - Solutions Chapter 4 8/6. The ident field is 16 bits, so we can send 576 * 2^16 bytes per 60 sec, 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. 14/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. 34/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. 39/32. A can reach B and D but not C. A "thinks" that B and C are local, and attempts to send directly to their ethernet addresses. The packet sent to B's ethernet address is bridged by RB, and so is delivered, but the packet sent to C's Ethernet address is NOT forwarded by R1. R1 doesn't really even see the packet; routers forward only packets addressed at the link level directly to them. A knows that D is nonlocal, and so sends directly to R2. Like the packet to C, though, this packet is forwarded by RB. Actually, A would not even *have* the Ethernet addresses for C, B, and R2, initially. So it would attempt to use ARP. This would succeed for B and R2, but not for C; R1 would certainly not forward ARP packets. 45/38. (a):B (b):A (c):E (d):F (e):C (f):D 47/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 48/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/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. 22/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. 33/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. 36/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. 39/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. 41/39: If a crash occurs in the middle of a connection, it leads to a "half-open" connection where one endpoint has lost all state regarding the connection. Because TCP (unlike BLAST) keeps such connection state, the broken connection will be discovered as soon as the other side sends anything; the crashed side will respond with RST. Another possibility is for one host, say A, to send a SYN, and then crash, and then send another SYN for a new connection. Normally this is detected because the second SYN will have a different ISN, but even if not the problem is not terribly serious. 44/42: (a) Blast increments MID for each message while 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. (b) CHAN's MID must be sequential in order for implicit ACKs to work. BLAST's MID is simply a unique identifier, and could be chosen at random. ========================================================== Chapter 6: 16/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. If the RWS is 1MB, we do *not* continue to increase the actual window size, and so the transfer takes another 9 RTTs, one for each of the remaining 9 MB of file (technically we're 1KB short, so maybe there will be a 10th RTT for that last 1KB). If the RWS is 10MB, then cwnd never stops increasing. At the end of the 13th RTT the window size is 8MB, and a total of almost 8MB has been transferred. During the next RTT, though, there are only 2MB of file left, and so that is all that is sent (not a full window of 8MB). The last four RTTs transfer 1, 2, 4, 2 MB respectively. (c). In the RWS=10MB case, 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. 22/20(a). Here is the table of events with TimeOut = 2 sec. I made a mistake here; the table has timeouts handled *before* ACKs; that is, at T=4, when Ack3 arrives and Data4 timeouts, I time out and resend Data4 (and set cwnd=1). If I followed the instructions, I would process the ACK and send Data7 and Data8, and *then* handle the timeout. In that case, Data7 would go into the queue, but Data8 and the resent Data4 would be lost. 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 nothing Data4 1 6 Ack5 Data 6 Data6 1 7 Ack 6 Data7,8 (slow start) Data7 2 26/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. 27. (I don't have the question in front of me. I think it was about ACKing data not actually received, in order not to force the transport pipeline to stall. If this is done, it will work in the (very) short run, but in the medium run it will cause the sender to continue to increase cwnd, leading to massive losses.) 28/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. 31/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. 43/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.