(Spring 2012 - Stoica and Katz) Prelim Question: Datacenter Network Stack (i) What particular features distinguish a datacenter network from other kinds of enterprise local-area networks or Internet-style wide-area networks? (ii) Define a good figure of merit for performance in a datacenter network. (iii) What are the primary contributors to lose of performance in datacenter networks, based on the figure of merit you defined in Part (II). (iv) Given your answer to Part (III), what technical approach would you take to improve network performance in a datacenter network? (v) How would you go about designing a single unified transport protocol that would work well in the opposite extremes of a datacenter network on the one hand and a globe-spanning wide-area network on the other? Prelim Question: Mobile and Wireless Networks (i) Define a good figure of merit for performance for a wireless network that incorporates mobile end hosts. (ii) Given your answer to Part (i), what particular impairments represent challenges for achieving good performance for a wireless mobile network? Organize these according to the link, routing, and transport layers of the network stack. (iii) Describe a "basic" wireless link layer. What changes would you make/features you would add to it to improve end-to-end network performance? Justify your answer. (iv) Describe a "basic" mobile host routing protocol. What changes would you make/enhancements you would add to it to improve end-to-end network performance? Justify your answer. (v) Describe the "basic" behavior of TCP over wireless mobile networks. What changes would you make to the transport protocol to improve end-to-end network performance? Justify your answer. Prelim Question: Multicast (i) What problem does IP multicast aim to solve? Briefly describe how the distance vector multicast protocol (DVRMP) works? (ii) Besides DVRMP, can you name another protocol that has been proposed to implement IP multicast? What are this protocol advantages and disadvantages compared to DVRMP? (iii) Explain the challenges of adding reliability and flow control functionalities to IP multicast. Can you propose solutions to address these challenges? (iv) Comment on why IP multicast is not widely deployed/enabled today? What are the alternatives?
(Fall 2011 - Shenker and Katz) Prelim Question: Datacenter Routing 1. Describe how routing in a datacenter differs from routing in the Internet. 2. Design a routing topology that is particularly well suited for a datacenter rather than a traditional corporate LAN or internetwork. Justify your choices in terms of the network traffic patterns you would expect to see generated by typical datacenter applications. How are your choices different from those you would make for either an enterprise LAN or wide-area internetwork? 3. Given the answer you come up with in (2), develop a routing algorithm for your proposed topology. What is your routing metric, and what are you trying to optimize in your algorithm? How does it compare with the standard routing algorithms that have been developed for traditional networks? Prelim Question: Latency and Transport Protocols 1. Describe a mechanism typically used by transport protocols to determine the end-to-end latency of a transport connection. 2. How is the end-to-end latency determined in this way used to control the behavior of the transport connection? 3. Consider the situation where the end-to-end latency is very high (e.g., a satellite connection). What challenges does this present for transport protocols, and how would you redesign transport protocols to deal with them? 4. Consider the situation where the end-to-end latency is very low (e.g., across the racks in a datacenter). What challenges does this present for transport protocols, and how would you redesign transport protocols to deal with them? 5. What is the role of statistical variance in latency estimation, and what challenges are presented by high variance in frame delivery for transport protocols? 6. How would you attempt to control latency variation in a network architecture design?
(Spring 2011 - Shenker & Stoica): "TCP and congestion control: What network behaviors are difficult for TCP's congestion control algorithm? How might TCP be fixed to prevent these problems? What is the TCP throughput equation? Can you motivate why it takes that form? What changes to TCP might change the dependence on the drop rate? This change need not be wise, we are just looking for an example Basic Principles: What is the end-to-end principle? How does it apply to active networking? Clark lists the basic goals of the Internet. What are the first four How does the Internet achieve them? Answer one of the following: How is cloud computing changing the Internet? How does the multiple access in 802.11 work? What are BGP policy oscillations? Show us an example. Design Question: If you were redesigning the Internet, how would you prevent DDoS?"
(Fall 2010 - Katz & Shenker): "Question #1: Routing Algorithms (i) What is shortest path routing? Describe a shortest path routing algorithm. (ii) Does the Internet use shortest path routing? If not, describe the algorithm actually used. (iii) Existing routing algorithms are designed to maintain a “best” route from Node A to Node B. Consider a variation on traditional routing algorithms that has the ability to maintain more than one route between any pair of nodes. This could be of use, for example, in the context of datacenter interconnection fabrics like fat trees or hypercubes. Why might such a routing algorithm be useful? Describe the design of such a routing algorithm that could be used in a datacenter network. Question #2: Satellite Transport Protocols Take it as a given that satellite “pipes” are very high bandwidth, very high latency, and with the potential for high losses that can persist for many seconds. In particular, assume a 100 gbps link with 250 ms round trip times, and losses due primarily to intermittent conditions of heavy rain (not a daily event, except perhaps in Costa Rica!). (i) How would TCP behave in such an environment? (ii) How could you improve TCP to work better in such an environment? Consider in particular how to improve TCP in the presence of losses that can persist for seconds at a time. (iii) Consider a clean-slate design for transport specifically for a network dominated by satellite links. How would you design such a transport layer? Question #3: Energy Conservation Acme Industries was interested in reducing their power consumption, so they bought a new set of PCs that “sleep” when they aren't in use. Since the PCs weren't used at night, the bean counters at ACME were expecting significant savings, but the network operators discovered that the PCs rarely went to sleep, and the power savings were minimal. (i) Why is that? (ii) How could you fix this problem? (iii) Is there any way that virtualization technology could help? Question #4: Intermittent and Dynamic Connectivity In designing communications for the developing world, many researchers have suggested the use of "opportunistic delivery" in which buses and taxis are equipped with wifi and are used to form a mesh network. Because the buses and taxis are constantly moving, their connectivity changes often, and they are frequently disconnected. (i) Design a transport protocol for this situation (ii) Design a routing system for this situation"
(Fall 2008 - Paxson & Stoica): "(1) The following questions refer to the TCP protocol: (i) Explain the roles of congestion and flow control. How does TCP implement flow and congestion control? (ii) Explain the impact of route fluttering on the TCP throughput. Propose a fix for this problem. (iii) It is a well-known problem that TCP does not perform well in the presence of bursty losses. Explain the problem in detail, and propose a fix that does not require receiver changes. (2) Denial-of-service is a difficult problem to address in networking, and can manifest at different layers. Describe DoS attacks at each of layers 3, 4, and 7, and the general state-of-the-art in defenses at those layers. Are these defenses adequate? (3) Consider a P2P file sharing system like BitTorrent. Upon joining the system, each node contacts a special node (tracker) to obtain a set of neighbors to connect to. The questions refer to the process of selecting these neighbors. (i) Give two strategies that can be used by the tracker to assign nodes to a new node joining the system. Discuss the tradeoffs of these strategies. Assume the tracker knows all nodes in the system. (ii) In practice, the tracker knows only a subset of nodes in the system. Give two strategies to maintain the subset of nodes at the tracker, and discuss their tradeoffs. (4) You are tasked by the start-up you're working for with designing and implementing an instant-messaging service that can scale to millions of users. Walk us through your thinking about developing the design, and what resources the company needs to be prepared to devote to the service. [We expected the student to begin by asking more about the requirements, which were: (1) response should be snappy, in order to support interactive chat, (2) users can also transfer attachments such as photos, documents, and videos, (3) there needs to be an easy way for users to "find" one another, (4) there should be an option for voice-chat, and (5) it all should work for pairs of clients behind NATs.] Follow-on question: suppose now that the chat is used for stock brokers who require absolutely minimal latency. What changes?"
(Fall 2006 - Joseph & Shenker): "Prelim Question #1: Give examples and reasons for why you would use UDP for an application? Give examples and reasons for why you would use TCP for an application? How does TCP congestion control work, in general? What about these varieties of TCP congestion control, how do they work? SACK Vegas ECN What are the main problems with TCP as a long-term congestion control solution? How would you fix them? How can you do congestion control for multicast? Prelim Question #2: You're hired by MyTube as a networking consultant. MyTube provides free Internet hosting of user-uploaded videos. Hundreds of thousands of users download these videos each day, resulting in the need for high bandwidth connectivity. MyTube’s founders are looking for a solution to their high cost for network connectivity, and have hired you as a consultant. (a) A large regional ISP offers MyTube a deal whereby they would host the videos for delivery to their customers (only). Should you recommend that the founders accept this deal? Explain your answer. (b) One of MyTube’s engineers proposes that MyTube develop and deploy a peer-to-peer network-based solution, but the other engineers are skeptical of this approach. What are the various peer-to-peer approaches they might employ? Explain why you think these approaches will or will not work. (c) My-Tube decides to offer a live video conferencing service, where two or more users with web-cams can interact with each other. Explain why their original network is ill-suited for this service. Would it be better suited for audio conferencing? Prelim Question #3: You’re hired to evaluate a new system to enable in-flight cellular phone calls from airplanes. The system will use a micro-basestation on each plane and a geosynchronous (22,000 miles above the earth) satellite plane-to-ground connection. (a) Do you think users will be happy with the service? Why or why not? (b) The company decides to offer a data service for in-flight Internet access. Will users be happy with this service? Explain your answer. (c) What could the company do to improve users experiences with the Internet access service?"
(Fall 2005 - Katz & Stoica): "Prelim Question #1: Fast Network Bulk Copy Your job is to implement an algorithm well matched to the routing and transport layers of the network for rapid copying of very large files from one sender to many receivers. (a) What aspects of the current Internet routing and transport layers make it difficult to efficiently implement large transfers of this kind? (b) Given existing IP and TCP, develop a scheme for fast large bulk transfers. Make it clear what is good and bad about your approach. Consider efficiency of network utilization, completion time, the scalability of your scheme, and the effect it may have on network congestion. (c) How would you change IP and TCP to better support bulk copy applications of this kind? Address the metrics you used in part (b) Prelim Question #2: Network Denial of Service Denial of Service attacks are emerging as a major threat to network operation. This question covers understanding of the problem and its implications for network architecture. (a) Define “denial of service” specifically in a network context. What is the fundamental signature that a denial of service attack against a particular edge network is underway? (b) Suppose you a network administrator of the Berkeley campus network, and you believe that a denial service attack is being directed against the campus network. Given your answer to part (a), just how would you know that you are being attacked? What network-level administrative mechanisms could you invoke to mitigate the attack? (c) Suppose you could add one new mechanism to the Internet architecture to deal with denial of service attacks. Describe that mechanism and how it would work. What are the strengths of your proposal as well as its limitations? Prelim Question #3: Overlay Networks Your job is to use overlay networks to increase the TCP throughput between two end-hosts. (a) What are the main network performance parameters that determine the TCP throughput? (b) Give a solution to increase the TCP throughput without changing the protocol stack at the end-hosts. (c) Now you are allowed to change the protocol stack. Give a solution to increase the TCP throughput in this case."
(Spring 2005 - Katz & Stoica): "Prelim Question #1: Internet Routing Consider the issues of routing in the wide-area at the scale and scope of today’s Internet. (a) Describe the two main algorithmic approaches to routing. What are their respective strengths and weaknesses? Which approach is the dominant one used in the Internet today? Why? (b) Define the terms convergence and stability in the context of routing algorithms. How well do the algorithms you described in Part (a) behave with respect to convergence and stability? (c) Interdomain routing presents special challenges for routing algorithms. What distinguishes interdomain from intradomain routing from the perspective of the algorithms used to construct routing tables? What are the policy dimensions of interdomain routing? How are they actually implemented in the Internet (if you do not know in detail how this is accomplished, invent an approach for implementing policy in interdomain routing)? (d) Define the concept of routing anomaly. Give two examples of how anomalies can arise in wide-area routing. Propose a method that can reduce the instances of anomalies. Prelim Question #2: TCP over wireless networks Consider the issues related to deploying TCP over a wireless network. (a) Describe the main challenges of deploying the TCP over a wireless network. (b) Propose two techniques to address the challenges discussed in part (a) without modifying the TCP protocol. What are the advantages and disadvantages of each technique? (c) If you were allowed to modify the TCP protocol, then propose one change to TCP that can significantly improve its throughput over wireless networks. Prelim Question #3: End-to-end arguments Consider the following issues related to the end-to-end arguments principle: (a) Describe the end-to-end arguments. What is the role of this principle in the Internet architecture? (b) Give two examples of instances in today’s Internet that violate the end-to-end arguments. Explain how is the principle violated in each case. (c) Consider Quality of Service and multicast functionalities. In each case argue whether implementing the functionality at the IP layer is a violation of the end-to-end arguments or not. (d) Propose a change of the Internet architecture that would allow to deploy the functionalities discussed at part (b) without violating the end-to-end arguments.
(Spring 2004 - Katz & Joseph): "Prelim Question #1: Transport Protocols Your task is to design a “pseudo reliable” transport protocol to the following specification. All packets must eventually be received at the receiver, but it is not necessary that they be received in the same order that they are sent. Furthermore, the receiver is at the end of a satellite access network, which is characterized by a high bandwidth, high latency, and high loss last link. (a) Define the term transport layer protocol and describe the considerations in designing such a protocol. (b) The protocol you are asked to design is “pseudo reliable.” Does this simplify your task, or make it harder? Explain your answer! (c) The network environment you are faced with is not the usual one encountered in transport protocol design. How do these specific difference (high b/w, high latency, high loss rate) affect your design? (d) What kind of applications could be constructed on top of such a transport protocol? Prelim Question #2: Programmable Networks Consider the concept of programmable networks, that is, the routing infrastructure provides programmatic interfaces that allow third parties to define rules for packet classification, packet transformation based on such classifications, and packet actions. (a) To illustrate your understanding of these terms, describe how the conventional functionality of a router can be handled by the three step process of packet classification, transformation, and action. (b) Define the concept of a firewall and describe how you could implement such a function using the three step process of packet classification, transformation, and action. (c) List two other network services (beyond firewalls) that could be implemented using this paradigm of programmable networks, and briefly describe how this would be done for each one. (d) Describe three technical challenges in realizing such a vision of programmable networks and your approach for addressing those challenges. Prelim Question #3: Video On Demand Rewind Networks Inc. has asked you to design a video on demand system that works over the Internet. The programs that people will request include limited appeal, specialty shows, and large super bowl-sized events. (a) List the technical challenges and tradeoffs for deploying such a system. (b) Provide an architectural picture of your proposed solution. Discuss your design decisions. (c) Rewind Networks decides to enter the distributed meeting market. How does this change your solution? Should you use the same system architecture, or a new one?
(Fall 2003 - Katz & Stoica): "Network Prelim Question #1 ---------------------------- This question addresses several issues in the area of Overlay Networks. (i) Give two examples of overlay network applications. (ii) Consider an N-node overlay network built as a d-regular graph, and assume that the loss rate on each overlay link is p << 1. What is the optimal degree d of the overlay such that to minimize the loss rate in the network? Assume a communication pattern where the senders and receivers are random nodes in the overlay. (iii) Assume a scenario in which a large number of overlay networks are deployed in the Internet. Explain what can go wrong in this scenario, and propose a solution to address the eventual problem. Network Prelim Question #2 -------------------------- In this question, we will consider the issues of extending the Internet to the Moon. The distance from the Earth to the Moon is approximately 240,000 miles. We will assume laser-based “line of sight” transmitter/receivers that can sustain raw data rates in perfect atmospheric conditions of 10 gigabits per second. Note that while the Moon always presents the same face to the Earth, it is not visible from a given point on the Earth at all times. (i) Calculate the approximate single hop latency between the Earth and the Moon. How does this compare with “typical” network latencies encountered in the terrestrial net today? (ii) Describe your approach for designing a MAC/Link Layer for communicating between the Earth and the Moon. Articulate the factors you must consider in designing such a MAC/Link Layer. (iii) Consider the routing layer, and assume that we wish to maintain very high levels of reachability to the lunar subnet. In what ways does communicating with the Moon affect the standard Internet routing protocols? What changes would you make to support high reliability of routes in such a high latency environment? (iv) Consider the transport layer. Is TCP a good match for the vagaries of communicating with the Moon? a. If so, why? How would you tweak TCP’s parameters to match them to the challenges of communicating reliably with the Moon? b. If not, why not? How would you design an alternative reliable transport protocol better adapted to the challenges of communication with the Moon? Network Prelim Question #3 -------------------------- This question considers the issue of QoS in a packet switching network such as Internet. (i) What are the main operations performed by a QoS router on both data and control planes? Comment on the implementation and algorithmic complexity of each operation. (ii) Describe the Weighted Fair Queueing (WFQ) algorithm. What services can it provide? Explain the concept of virtual time. (iii) Consider a low-delay low-bandwidth application (e.g., audio streaming). Is WFQ appropriate for such traffic? If not propose a change to WFQ to make it better suited for low-delay low-bandwidth traffic.
(Spring 2003 - Joseph & Stoica): The exam contained three questions centered on: (1) congestion and flow control computer networks, (2) multicast protocols , and (3) throughput in wireless networks. In each case the question started from basic knowledge and extended toward open-ended design.
(Fall 2002 - Katz & Stoica): "Problem 1: Transport Concepts and Protocols -------------------------------------------- 1. Define the terms congestion control and flow control. What distinguishes them? 2. What mechanisms does TCP (Transport Control Protocol) use to implement congestion control and flow control. How do they interact? 3. Define the concept of fairness in transport protocols. In what ways are "standard" TCP implementations unfair, given your definition of fairness. 4. Define the term fair queuing. In what ways and for what reasons does fair queuing interact with transport protocols like TCP? 5. Consider the problem of discovering whether two transport-level flows share a common bottleneck link. What approach would you take to determine this for two arbitrary flows? Problem 2: Storage Networking ----------------------------- Fibre Channel (FC) is a point-to-point bit serial interconnect based on fiber optic technology that can operate at gigabit per second speeds spanning tens of kilometers. It is possible to build switched fabrics of FC links to construct a multipoint (many-to-many) interconnection structure. FC fabrics are used to connect many computers to many storage devices like multi-disk systems, possibly miles apart. This question will explore these so-called storage-area networks (SAN). 1. What are the performance issues in using conventional networking technology to connect a computer to a disk drive? Speculate on the ways in which a FC fabric behaves differently from a conventional network given the very specific application it is intended to support. 2. Define the general concept of active network. In a SAN, describe how active networking ideas might be effectively used when the "protocol" embedded in the transport-level flows are actually sequences of I/O commands, such as disk-level seeks, transfers, and device-to-device copies. 3. Consider the application of "emergency copy," whose purpose is to off-load a very large storage device (possibly a terabyte) to a remote location with as low latency as possible. How would you make use of a conventional wide-area network to achieve the lowest possible latency copy? In your answer, consider transport- and routing-layer issues. Could active networking help you? Problem 3: IP Routing --------------------- 1. Explain briefly how link-state and distance-vector routing protocols work? 2. Compare link-state and distance-vector routing protocols? What are the main advantages/disadvantages of each of them? 3. Explain the count-to-infinity problem and give a solution to address this problem. 4. Extend one of the protocols (i.e., either link-state or distance-vector) to discover alternate paths. 5. Assume alternate paths are used to perform load balancing at the packet level. How would this affect TCP flows? Propose a solution to address this problem. Problem 4: Overlay Networks --------------------------- 1. What are overlay networks? What is the main problem they are trying to solve? 2. Resilient Overlay Network (RON) aims to improve the resilience and performance of the Internet by finding two-hop alternate paths in the overlay. However, the current RON architecture requires that every node knows every other node in the overlay. What are the advantages and disadvantages of this architecture? 3. Give one solution to make RON more scalable. What are the tradeoffs?
(Fall 2001 - Joseph & Stoica): "Problem 1: Naming Systems ------------------------- 1. What is the role of a naming system in computer networks? 2. What are the requirements for such a naming system? What features must they provide/attributes they must have and why? 3. What are the problems with DNS as it is currently specified? 4. "Any problem in computer science can be solved by another layer of indirection." Discuss how to extend DNS to deal with problems such as end node mobility and redirection to the "best" instance of a network service. Problem 2: Congestion Control, TCP ---------------------------------- 1. What is congestion control? Why do you need it? 2. What is the difference between congestion control and congestion avoidance? 3. Explain the motivations behind RED. Why is RED superior to drop-tail buffer management? 4. How would you change the design of TCP to work better for very high speed links? What are the problems experienced by TCP in this case? Problem 3: Link Layer --------------------- 1. What services does the data link layer provide? 2. Explain ALOHA and slotted ALOHA protocol. 3. Explain how CSMA/CD (e.g., Ethernet) protocol work? What are the main differences between CSMA/CD and ALOHA? 4. How would you improve the utilization of 100Mb/s Ethernet and of 1 Gb/s Ethernet?"
(Fall 2000 - Katz & Joseph): "Q1: What is the role of a naming system in computer networks? - What are the requirements for such a naming system? What features must they provide/attributes they must have and why? - What is the DNS and how is it organized? - What are the problems with DNS as it is currently specified? - Is the DNS intrinsic to the Internet architecture? Would it be possible to change the naming system within the Internet? - 'Any problem in computer science can be solved by another layer of indirection.' Discuss how to extend DNS to deal with problems such as end node mobility and redirection to the "best" instance of a network service. Q2: Itsy Bitsy Machines, a new Berkeley startup, deploys a new TCP/IP-based file sharing protocol over their internal 10 Mbit/s LAN in their new garage office. Everyone is happy and I.B.M. grows! Outgrowing their current space, I.B.M. opens a new office across the street. The users in the new office find that performance is poor and the system slows to a crawl for them. They threaten to leave en masse for Peach Computers! You are brought in to consult on the problems and save I.B.M. - What steps would you take? You find that to save money, I.B.M. used an 11 Mbit/s wireless link in a public (shared) frequency band for the connection between the buildings. - Is this potentially the cause of the problems? Why? - If they replace the 11 Mbit/s wireless link with a 10 Mbit/s wired link, will the problem go away? To help with the problems, I.B.M. deploys several servers in the new office, but the problems persist. Digging deeper, you find that the internal LAN in each building is switched Ethernet. - Is this observation important? Why or why not? Upon further exploration, you find that employees spend their days listening to streamed music using the Sleepster service. - Is this observation important? Why or why not? What if Sleepster is UDP-based? Or TCP-based? I.B.M. continues to grow across the country. To avoid future problems like these they propose to monitor performance at the server. - Is this a good idea? Why or why not? Q3: Your officemate is tired of waiting for movie trailers to download using a TCP-based True Networks protocol, so she develops a new UDP-based streaming video protocol. After writing a client and a server, she copies her entire 3,000 DVD movie collection onto the server and starts watching movies in the office. You immediately notice that the network grinds to a halt for you, especially when you surf the web. - Why does your performance suffer? - Would a switched network help? Why or why not? To be nice, your officemate modifies the protocol so that it only uses half of the network's specified bandwidth (e.g., 5 Mbit/s of a 10 Mbit/s network). Performance for your applications is once again great. Until the video application becomes popular, and then performance suffers once again. - Why? - What is the underlying problem here? Propose a solution to the problem."
September 2001