CS244a: An Introduction to Computer Networks

1 Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?_____ _____ Page 1 of 9 Grade: S MC:___ 11:____ 12:___ 13:___ 14:____ 15: _____ 16: _____ 17:____ Total: cs244a : An Introduction to Computer Networks Midterm Exam: Tuesday February 20, 2007 You are allowed 1 hour to complete this exam. (i) This exam is closed book and closed notes. However, you may refer to a sheet of "x11" paper (single-sided) of your own design. (ii) Write your solution directly onto this exam. Be sure to write your name and student ID clearly on the front of the exam. (iii) Don t panic! Be sure to start by reading the exam all the way through. Then answer the questions in whatever order you choose.

2 (iv) Show your reasoning clearly. If your reasoning is correct, but your final answer is wrong, you will receive most of the credit. If you just show the answer without reasoning, and your answer is wrong, you may receive no points at all. (v) You may assume that the speed of propagation along a cable or optical fiber is 2 x 108m/s. The Stanford Honor Code In accordance with both the letter and spirit of the Honor Code, I didn't cheat on this exam. Signature:_____ Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?_____ _____ Page 2 of 9 Short Multiple Choice Questions. Instructions: in the following questions, check all listed assertions that appear to be correct.

3 There is at least one correct assertion per question, but there may be more. Each correct assertion checked will earn you one point. For each incorrect assertion you check, you will lose one point. If you don t know an answer, checking no assertion will neither earn you nor lose you any points. 1. General. It takes a single bit ten times longer to propagate over a 10Mb/s link than over a 100Mb/s link. (a.) True (b.) False (c.) There is insufficient information to answer the question (d.) I should have dropped the class two weeks ago 2. General. You rip a 3 minute long stereo (it s underlined to give you a hint!) music track by sampling it at 8kHz with 16bits per sample and store it in a file in raw format. How long would it take to send the file over a 1Mb/s link? (a.) About 46 seconds. (b.) seconds. (c.) 2 minutes and 17 seconds. (d.) 3 minutes. (e.) It depends on the volume setting.

4 3. General. What is the bandwidth delay product (in bits) of a network that contains 5,000km of optical fiber operating at , and three routers (each with a fixed processing delay of 100 s)? (a.) 750,000 bits (b.) 62,500,000 bits (c.) 63,250,000 bits (d.) 625,000 bits (e.) We need to know how wide the network is to determine how many bits will fit in the pipe. 4. Address lookup. Which of the following are true statements about how routers lookup IPv4 addresses in their forwarding tables (a.) They can use regular hashing algorithms to perform lookups of address prefixes. (b.) Binary search trees and tries are different names for the same algorithms and data structures. (c.) TCAMs (ternary CAMs) are commonly used because they are well suited to longest-prefix match lookups. (d.) TCAMs are commonly used for address lookups because they require less space, less power and cost less per bit of storage than SRAM.

5 Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?_____ _____ Page 3 of 95. Packet switching (from textbook). Which of the following are true about the design of packet switches ( routers): (a.) Packet switches always place arriving packets directly and immediately into a queue at the output port. (b.) Input queues are commonly used for high speed routers because they can run slower than the equivalent output queue. (c.) Routers always have a fast internal shared data bus that all the input and output ports connect to, so as to transfer packets between them. (d.) A router that does virtual cut-through (instead of store and forward), does not need packet buffers.

6 6. TCP. Which of the following are true statements about TCP: (a.) A source s retransmission timeout value (RTO) is always set equal to the most-recently measured RTT. (b.) Setting RTO too small may lead to unnecessary retransmissions. (c.) A source s retransmission timeout value is usually set to a value that increases with the variance in measured RTT values. (d.) RTO is picked randomly when a TCP connection starts, and remains fixed for the duration of the flow. 7. Packet switching. The original reasons for the Internet to use packet switching were: (a.) Statistical multiplexing enables efficient sharing of expensive long-haul links. (b.) It is less work for a router to process a packet than to process the data in a circuit. (c.) If the routers contain no per-flow state, then it is easy to re-route flows around link and router failures. (d.) Packet switching enables routers to be built faster than circuit switches.

7 8. Queues. You are at the post office where there is a single line of people waiting to be served by four different tellers. You watch for a while and notice that, on average, a new person joins the line every 30 seconds, and there are, on average, 10 people in the line. What s a good estimate of the average time someone spends waiting in line? (a.) 1200 seconds (b.) 300 seconds (c.) 75 seconds (d.) 3 seconds (e.) There isn t enough information in the question to make a good estimate. 9. Queues. You are standing in line at a ski lift. A new chair arrives every 10 seconds and can carry two people, except that every third chair is broken. If no more than 6 people arrive in any one minute period, what s the longest time that someone needs to wait in line? (a.) 30 seconds (b.) 40 seconds (c.) 50 seconds (d.) 60 seconds (e.) An average of 8 seconds. Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?

8 _____ _____ Page 4 of 9 10. Queues. For the same ski lift as in question (9), assume that smoeone arrives to the lift when the line is empty. On average, how long do they have to wait for a chair? Assume the arrival time is independent of the time chairs depart. (a.) 30 seconds (b.) seconds (c.) 5 seconds (d.) seconds (e.) seconds Short Questions. 11. (9 points) Inter-AS routing (from textbook). Consider a router inside one AS that receives a packet for a network inside another AS. (a.) Briefly explain how the router decides which router to send it to in its own AS so that it can reach the other AS. (b.) Why do many network operators use hot-potato routing ? (c.) Explain how loops in paths can be detected in BGP. Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?

9 _____ _____ Page 5 of 9 12. (3 points) Routing. Explain why a network operator might not use traffic load as a cost metric for their routing protocol. 13. (3 points) RED. The RED mechanism for active queue management will drop packets before the packet buffer is full. To do this, it keeps track of the average queue occupancy, and drops packets if the average exceeds a threshold. (a.) Explain why RED uses the average queue occupancy instead of the instantaneous queue occupancy. (b.) What would happen if it used the instantaneous value instead? 14. (8 points) Addresses. Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: Prefix Match Interface 00 0 01 1 10 2 11 3 For each of the four interfaces, write down the associated range of destination host addresses and the number of addresses in the range.

10 Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?_____ _____ Page 6 of 9 Longer questions 15. (15 points) Routing. Use Dijkstra s shortest path first algorithm to find the shortest path from Computer A to every other Computer in the network below. At each stage of the algorithm, clearly show the candidate set and the shortest path set. Assume all the links are bidirectional and symmetric ( the cost of using a link is the same in both directions). R1R1R2R2R5R5R6R6R3R3R4R4R7R712436529 ACDBGHFE Name:_____ cs244a Midterm February 20, 2007 Student ID #:_____ Professor Nick McKeown Campus/SITN-Local/SITN-Remote?