6.02 Spring 2010, Quiz 3 Page 1 of 11Name:Department of Electrical Engineering and Computer ScienceMASSACHUSETTS INSTITUTE OF TECHNOLOGY6.02 Spring 2010Quiz IIIThere are 12 questions (many with multiple parts) and 11 pages in this quiz booklet. Answer eachquestion according to the instructions given. You have 120 minutes to answer the questions.If you find a question ambiguous, please be sure to write down any assumptions you make. Pleasebe neat and legible. If we can’t understand your answer, we can’t give you credit! Please showyour work for partial credit.Use the empty sides of this booklet if you need scratch space. You may also use them for answers,although you shouldn’t need to. If you do use the blank sides for answers, make sure to clearlysay so!Before you start, please write your name CLEARLY in the space at the top of this page.One two-sided “crib sheet” allowed. No other notes, books, calculators, computers, cellphones, PDAs, information appliances, carrier pigeons carrying answer slips, etc.!Do not write in the boxes below1-2 (x/22) 3 (x/12) 4-6 (x/24) 7-10 (x/22) 11 (x/10) 12 (x/10) Total (x/100)6.02 Spring 2010, Quiz 3 Page 2 of 11I MAC Protocols1. [3 + 2 + 5 = 10 points]: Ben Bitdiddle is writing a slotted Aloha protocol with contentionwindows. His goal is to achieve high fairness and come close to the theoretically optimal utilizationfor slotted Aloha. As in Lab 7, he needs to write the code for two functions: on xmit success(called whenever a packet transmission succeeds) and on collision (called whenever there is acollision). He writes the following lines of code:def on_xmit_success(self,packet):self.cw = 1 # we set the minimum contention window to 1self.nextslot = self.network.time + self.cwdef on_collision(self,packet):......................... # incomplete: see belowself.nextslot = self.network.time + random.random()*self.cwA. What should the incomplete dotted line in on collision be to satisfy Ben’s goals? Feel freeto introduce additional variables if you need to.(Explain your answer in the space below.)B. Why does Ben need to multiply by random.random() (which generates a random numberbetween 0 and 1) in the second line of on collision?(Explain your answer in the space below.)C. Ben would like to try out quadratic backoff, a different scheme from part A. Here, the kthcon-tention window value, self.cw, is equal to k2, so the backoffs go as 1, 4, 9, . . .. What shouldthe incomplete dotted line in on collision be for quadratic backoff?(Explain your answer in the space below.)6.02 Spring 2010, Quiz 3 Page 3 of 112. [3 + 4 + 4 + 1 = 12 points]: Alyssa P. Hacker is designing a MAC protocol for a network used bypeople who: live on a large island, never sleep, never have guests, and are always on-line. Supposethe island’s network has N nodes, and the island dwellers always keep exactly some four of thesenodes backlogged. The nodes communicate with each other by beaming their data to a satellite inthe sky, which in turn broadcasts the data down. If two or more nodes transmit in the same slot,their transmissions collide (the satellite uplink doesn’t interfere with the downlink). The nodes on theground cannot hear each other, and each node’s packet transmission probability is non-zero. Alyssauses a slotted protocol with all packets equal to one slot in length.A. For the slotted Aloha protocol with a fixed per-node transmission probability, what is the max-imum utilization of this network? (Note that there are N nodes in all, of which some four areconstantly backlogged.)(Explain your answer in the space below.)B. In this network, as mentioned above, four of the N nodes are constantly backlogged, but the setof backlogged nodes is not constant. Suppose Alyssa must decide between slotted Aloha witha transmission probability of 1/5 or time division multiple access (TDMA) among the N nodes.For what N does the expected utilization of this slotted Aloha protocol exceed that of TDMA?(Explain your answer in the space below.)C. Alyssa implements a stabilization protocol to adapt the node transmission probabilities on col-lisions and on successful transmissions. She runs an experiment and finds that the measuredutilization is 0.5. Ben Bitdiddle asserts that this utilization is too high and that she must haveerred in her measurements. Explain whether or not it is possible for Alyssa’s implementation ofstabilization to be consistent with her measured result.(Explain your answer in the space below.)D. Ben now suggests that Alyssa should make packet sizes much bigger than a slot and use carriersensing to improve utilization. The nodes can’t hear each other. Will this approach increase theutilization of this network?(Explain your answer in the space below.)6.02 Spring 2010, Quiz 3 Page 4 of 11II Tweet-and-wait3. [4 + 8 = 12 points]: Lem E. Tweetit is designing a new protocol for Tweeter, a Twitter rip-off. Alltweets in Tweeter are 1000 bytes in length. Each tweet sent by a client and received by the Tweeterserver is immediately acknowledged by the server; if the client does not receive an ACK within atimeout, it re-sends the tweets, and repeats this process until it gets an ACK.Sir Tweetsalot uses a device whose data transmission rate is 100 Kbytes/s, which you can assume isthe bottleneck rate between his client and the server. The round-trip propagation time between hisclient and the server is 10 milliseconds. Assume that there is no queueing on any link between clientand server and that the processing time along the path is 0. You may also assume that the ACKs arevery small in size, so consume neglible bandwidth and transmission time (of course, they still need topropagate from server to client). Do not ignore the transmission time of a tweet.A. What is the smallest value of the timeout, in milliseconds, that will avoid spurious retransmis-sions?(Explain your answer in the space below.)B. Suppose that the timeout is set to 90 milliseconds. Unfortunately, the probability that a givenclient transmission gets an ACK is only 75%. What is the utilization of the network?(Explain your answer in the space below.)6.02 Spring 2010, Quiz 3 Page 5 of 11III Sliding Windows4. [10 points]: Consider the sliding window protocol described in lecture and implemented in Lab9 this term. The receiver sends “ACK k” when it receives a packet with sequence number k. Denotethe window size by W . The sender’s packets start with sequence number 1. Which of the followingis true of