1 NAME: Login name: Computer Science 461 Midterm Exam March 30, 2009 1:30-2:50pm This test has six (6) questions. Put your name on every page, and write out and sign the Honor Code pledge before turning in the test. Please look through all of the questions at the beginning to help in pacing yourself for the exam. The exam has 100 points and lasts for 80 minutes, so the number of minutes spent per question should be less than its point value. You should spend no more than 10-12 minutes per question. Show your work for all problems. Partial credit will often be given. "I pledge my honor that I have not violated the Honor Code during this examination.'' Question Score 1 / 15 2 / 16 3 / 17 4 / 14 5 / 16 6 / 22 Total / 1002 QUESTION 1: Transporting a file (15 POINTS) Suppose your boss calls you up while visiting a client and says he left a 250,000 byte file on a server at the office, and he needs you to send it to him. The connection between the office and his current site is 2 million bits/second. 1A. [2 points] Assuming that all bandwidth is consumed by your data (e.g., there aren’t any packet headers, there’s no other traffic on the link, etc.) and that you can immediately start sending data at the maximum rate, how long will it take to transmit the file? (Easy) 250,000 bytes * (8 bits / 1 byte) * 1/2,000,000 bits/s = 1 second 1B. [5 points] Now assume that you are sending the file via TCP, with a maximum segment size of 1000 bytes. You have to follow TCP’s transport algorithm, so you start transmitting the file at a low rate. How many network round trip times (RTTs) will it take to transmit the entire file? Again assume that all bandwidth is consumed by your data. TCP needs to first establish a connection via a handshake (SYN/SYN-ACK) - 1 RTT TCP then enters slow-start to transmit the file, so we run slow-start either until we've transmitted the file or until we experience a loss (at 2Mbps). In slow-start, TCP will initially transmit a window of 1 MSS (=1000 bytes) per RTT, then double the window size each round (RTT). So, we have: 1 MSS, 2 MSS, 4, 8, 16, 32, 64, 128 The sum of the above 8 transfers is 255 MSS = 255,000 bytes > 250,000 byte file, so we declare ourselves finished after the 8th RTT. Thus, the total time to transmit the file would be 1 + 8 = 9 RTT. Note: One might debate what "transfer" means, so we also accepted 7.5 RTTs for the number of runs in slow-start, as the final transfer of 128 might not strictly need to ACK. We did not take off any points if people also included 1 RTT for FINs.3 1C. [4 points] Let’s now consider how TCP reacts when it encounters packet loss (the “basic” variant we learned in class). Your boss now wants you to transmit a much larger file (say, 1 GB). This time around, after TCP reaches an instantaneously transmission rate of 32,000 bytes per second, you notice that a single packet is lost. Assuming that you don’t currently have any other packets in transmission, what is the instantaneous rate TCP will send at after noticing that loss? How long (in terms of RTTs) will it take to reach 32,000 bytes per second again? This question was meant to seek how TCP reacts to detecting loss via a triple duplicate ACK. In that case, TCP reacts by "MD" -- multiplicative decrease -- cutting its window size by half and continuing by "AI" -- additive increase. So the next transmission rate is 16,000 bytes per second, and it will take 16 RTTs to recover to its prior levels (each RTT increases by 1 MSS = 1000 bytes). 1D. [4 points] In the previous example of 1c, would anything be different if all packets were lost after you reached 32,000 bytes per second, instead of just a single packet? If so, what is the next instantaneous rate TCP will send at in this example, and how long (in terms of RTTs) would it now take to reach 32,000 bytes per second again? Because all packets are lost, we only detect loss through a timeout. This causes the sender's window to be reduced to a single MSS (1000 bytes / RTT), at which time it enters "slow-start restart". Namely, it will perform slowstart until half of its prior cwnd (16,000 bytes/second), then do additive-increase from 16,000 to 32,000 bytes/second. (In fact, the question as written didn't include quite enough information, as you actually do need to know the RTT in this example in order to calculate the window size for "16,000 bytes / seconds", i.e., if RTT is 500ms, window size is 8 MSS/RTT, while window size would be 16 MSS/RTT if RTT is 1s. Everybody just assumed implicitly that RTT=1s, and that the next rate after the timeout was 1000 bytes/sec. We initially had written these questions with an explicit RTT and asked you to solve the question in terms of time, rather than RTTs, but subsequently removed this information to reduce needed calculations.) That said, assuming RTT=1s, then the answer is: Slow-start from 1 MSS to 16 MSS = 4 RTTs, then additive increase 16-32 MSS = 16 RTTs Total = 20 RTTs (we also accepted 21 RTTs given various ways to "count" these values)4 QUESTION 2: Sockets (16 POINTS) 2A. [10 points] In the first assignment, you used the socket API to write a simple client/server. For this question, there is a single client communicating with a single server using TCP. The client sends a very small amount of data using the send() function, and the server receives the data with a recv() call. Each of the following scenarios shows a different order in which the socket calls are called on both the client and the server. Assume all system calls are blocking, and there may be some latency between the client and server. We write the system call when it is initiated by the client and/or server; it returns sometime between then and when the next local system call is executed. For each scenario, answer the following: Can the server ever get the data sent by the client? (Yes or No). If not, explain why not. i) Client Server socket() connect() send() close() socket() bind() listen() accept() recv() close() No. connect() wouldn't successfully return, allowing you to send(), before client accepts(). ii) Client Server socket() connect() send() close() socket() bind() listen() accept() recv() close() No. Same explanation as (i). Also valid reason is that server isn't listening() when client attempts to connect().5 iii) Client
View Full Document
Unlocking...