CSC 458: Computer Networks, Fall 2015 Department of Computer Science, University of Toronto Handout # 11 – Sample Midterm Date: Tuesday, October 20th Multiple Choice Questions Instructions: In the following questions, check all listed assertions that appear to be correct. 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. Layering. “Layering” is commonly used in computer networks, because: (a) It forces all network software to be written in ANSI ‘C’. (b) Encapsulation is the lowest overhead method to transmit data. (c) It allows widespread code and implementation re-use. (d) It keeps networks warm enabling them to run faster. 2. Reliable Flooding. Which of the following are true statements about reliable flooding? (a) It is used in Distance Vector table exchange protocols enabling neighboring routers to periodically exchange their tables. (b) It is used in Link State table exchange protocols enabling routers to distribute the state of their links. (c) Can be achieved only if routers always send packets back through the interface through which they entered the router. (d) Can be achieved, in part, if packets contain a sequence number and "time to live" field to prevent packets from looping endlessly in the network. (e) Is an efficient centralized algorithm for calculating routing tables. 3. Longest Prefix Match Lookups. Which of the following are true? (a) 171.64.128/17 cannot be a prefix because it is a Class B address. (b) If a routing table contains prefixes 31.75/16 (for which packets are sent to port 1) and 31.75.93.128/25 (for which packets are sent to port 2) then an arriving packet with IP address 31.75.93.129 will be sent to port 2. (c) A routing table can correctly contain the two prefixes 50.50.128/17 and 50.50.128/18 simultaneously. (d) If a routing table is organized in order of decreasing prefix length, then a routing decision may be performed by finding the first matching prefix. 4. Transmission Rate. What transmission rate is needed to transmit a 4" x 6" photograph (uncompressed, and with a resolution of 1200 dots per inch and 24 bits per pixel) in 1 second? (a) 691,200kb/s (b) 28.8kb/s (c) 28.8kbits (d) 8.29Mb/s (e) None of the above. Longer Questions 5. Routing Protocols. Consider the network topology shown below. The topology consists of multiple routers interconnected by full-duplex links. Each link has a static cost associated with it which represents the cost of sending data over that link. For example, the link from R2 to R4 has a cost of 3. Some of the links are symmetric (i.e. the cost is the same in both directions, such as between R1 and R6), whereas others are asymmetric (i.e. the cost is different in each direction, such as between R2 and R4). a) Write down four different attributes of a link that could determine its “cost”. b) Suppose that we decide to use the distributed Bellman-Ford (distance-vector) algorithm to determine the routing entries in each router, R2, R3, ..., R8 that determines the route to R1. What is an upper bound on the number of steps it will take for the algorithm to converge (i.e. until the routing tables stop changing)? Explain your answer. c) Using Dijkstra’s algorithm, find the shortest-path spanning-tree for routing packets from router R1 to every other router. Clearly show each step of the algorithm, including the evolution of the shortest-path set, S. Write your answer in the table below. Each entry in the second column should be a triple: (New Router in the shortest path set, Next-hop from R1 to reach the new router, Cost to reach the router). Step New entry in shortest path set, S (Router, Next-hop, Cost), S 1 (R1, R1, 0), S = {R1} 2 3 6. Coding. Represent the bit sequence 101110101100011110101010 in NRZ, NRZI, and Manchester encodings. 7. Fragmentation. A TCP message of size 3000 (including the TCP header) bytes is sent over a series of three IP routers. The MTU for the routers (in the order that the message passes through them) are 1500 bytes, 800 bytes, and 1000 bytes. Assume IP header is 20 bytes, link layer headers are 30 bytes, and packets are not reordered in this system. Show the sequence of packets as they arrive to the destination node. For each packet identify the packet length, as well as the offset. 8. End-to-end latency. A message of size 100,000 bytes is sent from a source node A to a destination node B passing through two routers R1 and R2. All three links on the path have a delay of 20 ms. Node A has a transmission rate of 1000 bits/sec, R1 has a transmission rate of 1000,000 bits/sec, and R2 has a transmission rate of 10,000 bits/ sec. Assuming this is a store and forward system, and there is not queueing delay, find the end-to-end latency of the message in each of the following cases. Ignore any header overheads. a) We send it as a whole. b) We break the message into 100 packets each of size 1000 bytes.