(Spring 2013 - Ratnasamy* & Shenker):
Answer brief questions (~20 minutes)
Pick two out of the following three questions:
Answer the two selected questions (~10 minutes each)
(Fall 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
(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
(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
6. How would you attempt to control latency variation in a network
(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
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.
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
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
(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
[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
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?
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
(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
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,
(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
(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
(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
(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
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
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
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
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
- 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.
- What is the underlying problem here? Propose a solution to the problem."