6.02 Spring 2009, Quiz 3 Page 1 of 9Department of Electrical Engineering and Computer ScienceMASSACHUSETTS INSTITUTE OF TECHNOLOGY6.02 Spring 2009Quiz IIIThere are 24 questions and 9 pages in this quiz booklet. Answer each question according to theinstructions given. You have 120 minutes to answer the questions.If you find a question ambiguous, be sure to write down any assumptions you make. Please beneat and legible. If we can’t understand your answer, we can’t give you 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 below.One two-sided “crib sheet” and calculator allowed. No other notes, books, computers, cellphones, PDAs, information appliances, carrier pigeons carrying answer slips, etc.!Do not write in the boxes below1-8 (x/31) 9-14 (x/22) 15-17 (x/14) 18-20(x/19) 21-24 (x/14) Total (x/100)Name:6.02 Spring 2009, Quiz 3 Page 2 of 9I Warmup1. [2 points]: To stabilize Aloha, a node should its packet transmissionprobability on a collision and it on a successful transmission.2. [8 points]: A switch uses time division multiplexing (rather than statistical multiplexing) to sharea link between four concurrent connections (A, B, C, and D) whose packets arrive in bursts. The link’sdata rate is 1 packet per time slot. Assume that the switch runs for a very long time.A. The average packet arrival rates of the four connections (A through D), in packets per time slot,are 0.2, 0.2, 0.1, and 0.1 respectively. The average delays observed at the switch (in time slots)are 10, 10, 5, and 5. What are the average queue lengths of the four queues (A through D) at theswitch?(Answer legibly in the space below.)B. Connection A’s packet arrival rate now changes to 0.4 packets per time slot. All the other con-nections have the same arrival rates and the switch runs unchanged. What are the average queuelengths of the four queues (A through D) now?(Answer legibly in the space below.)3. [8 points]: Under some conditions, a distance vector protocol finding minimum cost paths suffersfrom the “count-to-infinity” problem.(Circle True or False for each choice.)A. True / False The count-to-infinity problem may arise in a distance vector protocol when thenetwork gets disconnected.B. True / False The count-to-infinity problem may arise in a distance vector protocol even whenthe network never gets disconnected.C. True / False The “split horizon” technique always enables a distance vector protocol to con-verge without counting to infinity.D. True / False The “path vector” enhancement to a distance vector protocol always enables theprotocol to converge without counting to infinity.6.02 Spring 2009, Quiz 3 Page 3 of 94. [3 points]: Which of these statements is true of layering in networks, as discussed in 6.02?(Circle True or False for each choice.)A. True / False The transport layer runs only at the communicating end points and not in theswitches on the path between the end points.B. True / False The same transport layer protocol can run unchanged over a network path with avariety of different link technologies.C. True / False The lower layers perform error detection on behalf of the higher layers, eliminat-ing the need for higher layers to perform this function.5. [4 points]: The exponential weighted moving average in a reliable transport protocol is:(Circle True or False for each choice.)A. True / False A single-pole low-pass filter to estimate the smoothed round trip time (RTT).B. True / False A low-pass filter with a pole and a zero to estimate the smoothed RTT.C. True / False Not necessary if the RTT is constant.D. True / False Not necessary if the RTT samples are from an unknown Gaussian distribution.6. [2 points]: In lecture we learned that the JPEG encoding for images was a “lossy” encoding.Which step of the JPEG encoding process loses information?(Answer legibly in the space below.)7. [2 points]: The human genome consists of approximately 109codons where each codon can bethought of as one of 21 “symbols” coding for one of the twenty amino acids or serving as a “stop”symbol. Give an expression for the number of bits of information in the genome assuming that eachcodon occurs independently at random with equal probability.(Answer legibly in the space below.)8. [2 points]: You are trying to determine the registration number on Alice’s Belize license plate.License plates in Belize have four characters, each either a digit or an upper-case letter, and areselected at random. Alice tells you that her license plate contains only digits. How much informationhas Alice given you about her license plate? You can give your answer in the form an expression.(Answer legibly in the space below.)6.02 Spring 2009, Quiz 3 Page 4 of 9II AlohaBen Bitdiddle sets up a shared medium wireless network with one access point and N client nodes. Unlessmentioned otherwise, assume that the N client nodes are backlogged and that the access point has no packetsto send. Each of the N clients wants to send its packets to the access point. The network uses slotted Alohawith each packet fitting exactly in one slot. Recall that each backlogged node in Aloha sends a packet withsome probability p.9. [4 points]: Suppose each node uses the same, fixed value of p. If two or more client nodestransmit in the same slot, a collision occurs at the access point and both packets are lost. The graphbelow shows the utilization of this protocol as a function of p with N backlogged nodes. Fill in thethree blanks shown in the graph below.!!!!!!!!!!!!!!! ! !!!!!!!!!!!Sending!probability,!p!U2liza2on!Maximum!u2liza2on!when!N!=!4!is!________.!Maximum!u2liza2on!when!N!is!large!is!________.!For!any!N,!p!when!u2liza2on!is!maximum!=!_______.!A B C 10. [2 points]: The graph above shows three values of p: A, B, and C. Rank them in decreasingorder of collision probability.6.02 Spring 2009, Quiz 3 Page 5 of 9Now assume that the access point is also backlogged and each of its packets is destined for some client.As before, any two or more nodes (including the access point) sending in the same slot causes a collision.Ben sets the transmission probability, p, of each client node to 1/N and sets the transmission probability ofthe access point to a value pa.11. [5 points]: What is the utilization of the network in terms