(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