This file contains model solutions to selected homework problems. Homework for 04/09/05 Internet II is an association of universities, research labs, etc. that has built a ``very high data rate'' network. NJIT is a member. Internet II is connected to the ``ordinary'' (commercial) Internet. The Pittsburgh Supercomputer Centre and the San Diego Supercomputer Centre both are member of Internet II. Suppose the Pittsburgh SCC has a file of half a Terabyte (500 GBytes, 5 x 10^{11} Bytes) that must be sent to the San Diego SCC. ``Internet II'' has promised to make sure the connection has a data rate of at least 400 Mbits/sec asvailabe for this transport. In preparation of the transfer, the sysad people in the SCCs have measured the RTT between the two SCCs and found it is close to 100 Msec. Questions: a. How large must the send buffer in the Pittsburgh SCC be (in Bytes) to make it possible to utilize the data rate of 400 Mbit/sec? b. How large must the receive buffer in the San Diego SCC be (in Bytes) to make it possible to utilize the data rate of 400 Mbit/sec? c. What must the window scale shift (I prefer to call it shift, instead of factor) the San Diego SCC uses at least be to make it possible to utilize the data rate of 400 Mbit/sec? d. If the two sysad groups do things right, how long will it take to transmit this file? (Assume the Internet II people are on the dot with their estimate.) e. If the San Diego sysad person sits on the beach too long and forgets to modify the window scale shift (keeps it at zero), how long will it take, at least, to transfer the file? f. How often will the TCP sequence number in Pittsburgh rotate back to the original value (to the initial seqence number)? g. At the data rate the SCCs expect to achieve, how much time does it take for the TCP sequence number to rotate? Hand in. Model Solution: (.GEQ. stands for ``greater than or equal''. Similar .LEQ.) We know that the throughput is at most (Effective Window)/RTT, and the (Effective Window), that is, the number of bytes that (``typically'' or ``at most'' is outstanding) is at most: minimum of (cwnd, advertised_window, send_window). We also know that the advertised_window is at most the rcve_window. Hence: a. Send_window .GEQ. effective_window .GEQ. throughput x RTT = 400,000,000 x .1 = 40,000,000 bits = 5,000,000 Bytes = 5MBytes. b. rcve_window .GEQ. effective_window .GEQ. throughput x RTT = 400,000,000 x .1 = 40,000,000 bits = 5,000,000 Bytes = 5 MBytes. c. When the advertised_window as in the TCP packet is adv_w, while scale factor is k (i prefer to call k the shift) the ``real'' advertised_window is adv_w x 2^{k} (left shift by k). As in a and b, the real advertised window must be at least 5,000,000 Bytes. The adv_w as in the packet is at most 65535. Hence k must be such, that 2^{k} x 65535 .GEQ. 5,000,000 . 2^{k} .GEQ. 5,000,000/65535 = 76.295 . Hence k must be at least 7. (2^{6} = 64 , 2^{7} = 128 .) d. If the two sysad people do things right (and assuming Internet II indeed delivers 400,000,000 bits/sec to this one flow) it will take (Size of file)/(Rate) = (500,000,000,000)/(50,000,000) = (500,000)/(50) = 10,000 sec = 10,000/60 = 166.667 minutes = 166.667/60 = 2.7778 hours. e. Suppose the window shift remains at zero. Then the effective window is at most 65535 Bytes. (65535 x 2^{0} = 65535). In that case the maximal throughput is at most 65535/RTT = 65535/(.1) = 655350 Bytes/sec. In that case transporting the file will take at least (500,000,000,000)/(655350) = 50,000,000,000)/(65535) = (10,000,000,000)/(13107) = 762951.0948 seconds = 12715.85158 minutes = 211.9308597 hours = 8.83045 days, over a week. NOT good enough for data needed in weather forecasting! f. (``the second d'' :-) ). The TCP Sequence Number and Ack number ``rotate'' (get back to the starting value) once every 2^{32} = 4,294,967,296 Bytes. If the whole file is 500,000,000,000 Bytes, the sequence numbers will get back to the initial values (500,000,000,000)/(4,294,967,296) = 116.4153218 times. So they will get back to the initial position 116 times and then make another .415 of a circle. g. (``the second e'' :-) ). At 400,000,000 bits/sec = 50,000,000 Bytes/sec it takes (2^{32})/(50,000,000) = 85.8993 seconds per rotation. Check: 85.89934592 x 116.4153218 = 9999.999998 sec, indeed, 10,000 sec. So it seems I did not make an error in the arithmetic. ------- In the problem due 04/09: If the two supercomputer centers indeed succeed in maintaining almost exactly 400 Mbits/sec almost all the time, at a RTT of of 100msec: h. How many bytes are there, almost all the time, in the send buffer in Pittsburgh, that have been sent but have not been acknowledged yet? i. How much ``unused space'' is there, almost all the time, in the receive buffer in San Diego? Hand in. Model Solution: h. Suppose at some point the sender sends some databytes and right after there are C bytes in the send_buffer that have been sent but have not been acknowledged yet. (Some of these were sent just now, some may have been sent a while ago). For how many bytes will the sender receive acknowledgements in the next RTT time units? Clearly: AT MOST C Bytes. So if the number of ``outstanding'' (sent but not yet acknowledged) Bytes in the send_buffer often is significantly below 5,000,000 Bytes, the throughput ( (number of sent bytes)/(sec) = (number of acked bytes)/(sec) ) can not be .GEQ. 50,000,000 Bytes/sec: must be < 50,000,000 Bytes/sec. i. When the ``free space'' in the rcve_buffer is C Bytes, the receiver can not send and advertised_window larger than C. (Assuming no packets or bytes get lost and the receiver does not lie about the ``next_expected'' Byte). So, if the ``free space'' in the receive_buffer often is significantly below 5,000,000 Bytes, the throughput can not be .GEQ. 50,000,000 Bytes/sec. Another way of thinking about the send_buffer: When the receiver receives an acknowledgement with ACK_SEQ = Acked, and a ``sufficiently large'' advertised_window, how far past Acked must it be able to send (bytes already in the buffer) in order to achieve the required throughput? --- Aside: Items h and i indicate the send_buffer and the receive_buffer should not have the sizes given in a and b, but somewhat larger. For ``safety''. In the send_buffer because there may be bytes that have been acknowledged but have not been removed yet, and because there must be some space for bytes that have been accepted from the sending application but have not been sent yet. In the receive buffer because there must be space for bytes that have been acknowledged but have not been given to the receiving application yet. Also, because the value of a window of 5,000,000 bytes is a minimum and it is better to advertise a somnewhat larger value. In order to advertise a larger value, the free space must be larger. In both cases: Say 10 % larger, or even a bit larger. Say 7.5 MBytes instead of the minimal required 5 MBytes. At the receiver side we have a funny situation: The receive buffer must be large and mostly empty! --- The next part I will not ask about, but it is a good idea for you to understand it. Suppose we use a window shift of 7 and suppose the sender has a send_buffer of at least 10,000,000 bytes and the receiver has a receive_buffer of at least 10,000,000 Bytes. Even suppose the receiver always sends received bytes ``immediately'' to the receiving application, so it always has practically 10,000,000 bytes of free space, and advertises a window of 65535 x 128 = 8,388,480 bytes. Why wouldn't the throughput increase to 8,388,480/(.1) = 83,884,800 Bytes/sec. ? Well, it might, if the network can handle it. If the network can not handle it, several things might happen: There might be drop, with resulting reduction in cwnd. (That would be bad: if the cwnd halves it gets below 5,000,000 Bytes, and then it takes a LONG, LONG time to grow back up: increase by 1 MSS per RTT! figure out how long it takes to grow back up!) Or, there might be queueing in the network: In front of the bottleneck link there is a queue which becomes large. As result, the RTT increases, and finally we have that throughput = (effective_window)/(RTT) but now with a larger RTT and a larger effective_window. It is instructive the look at the special case where there is one special link with a capacity of exactly 400,000,000 databits / sec (plus some more for headers etc to make the arithmetic easy) and a large buffer in front of the link, and no other flows using the link.