G22.2260 Networks and Distributed Systems
Prof. Lakshminarayanan Subramanian
Thu 5:00-6:50, WWH 102
Office Hours: Wed 5:00- 6:00, 715 Broadway, Room 706
This is a graduate level course on computer networks and large-scale
distributed systems. In this class, we will teach the design and
implementation techniques essential for engineering both robust
networks and Internet-scale distributed systems.There's no textbook, you
many research papers (with our guidance) to learn the current
solutions in networking and large-scale systems.
If you have been exposed to a networking course in your
you know the basics of TCP/IP, socket programming), we highly encourage
you to take this class.
The goal of this class is to guide students so that they
- initiate and critique research ideas in networks and distributed systems.
- implement and evaluate a working system that can handle real world workload.
This course will have three components
- reading/lecture/discussion of research papers (summary + class discussion 20% + 10%).
- one systems programming lab assignment (10%)
- a final course project (60%).
We will read about 40-50 research papers on various aspects of
networks and distributed systems. Topics include routing protocols,
network congestion control, multicast, wireless networking,
overlay networks and applications, distributed storage systems and
network security. Students are expected to read papers before the
class and participate in the discussion during the class. The lecture
will be conducted in an
interactive fashion. We will lead the discussion, but we expect
everyone to participate. You will be graded for class discussion and paper summaries. Each student
will be individually responsible for writing up a short summary of every
paper. The summaries are due before 5 PM on the day of the corresponding class.
Submission instructions will be posted before class begins. There will be no exams in this class.
The final course project (conducted in a group of 2-3
students) should be a research-oriented project which should be a
design/implementation of a new concept in networking or distributed
systems. Research projects are a critical aspect of the course.
is to do some quality systems research; that is, to add to our
understanding of how to build systems. Research projects must be
written up in
a term paper, and will be presented in a poster in a departmental
mini-conference in the Spring Showcase. Suggested project ideas
will be provided by the instructor.
1. Undergraduate Networks and/or Operating Systems
2. Programming experience in C/C++ or Java is helpful for the final
Lectures and Readings
There is no textbook required. We will read and discuss 2 papers per week. All of the
papers for the class will be available on-line (if paper is not on the class web-page, search for the paper online).
Lecture 1: Basic concepts of Networks + Internet Structure and Evolution + OSI layer
Lecture 2: End-to-end principle, Naming
- J. Postel, "Internet
Protocol", RFC 791, Sept 1981.
- J. Postel, "Transmission
Control Protocol", RFC 793, Sept 1981.
- H. Zimmerman, "OSI Reference
Model -- The ISO Model of Architecture for Open Systems
Interconnection", IEEE Transactions on Communications, 28(4), April,
1980, pp. 425-432.[pdf]
Lecture 3: Routing in the Internet World
Lecture 4: Routing in Wireless and P2P networks
- T. Griffin, "An Introduction
to Interdomain Routing and BGP", ICNP 2002 Tutorial. [ppt]
- T. G. Griffin, F. B. Shepherd and
G. Wilfong, "The Stable Paths Problem and Interdomain Routing",
IEEE Transactions on Networking, April 2002. [link]
- Craig Labovitz, Abha Ahuja,
Abhijit Bose, Farnam Jahanian, "Delayed Internet Routing
Convergence", IEEE/ACM Transactions on Networking, Vol. 9, No. 3
(April 2001), Pages 293-306. [pdf]
- A. Shaikh and A. Greenberg, "OSPF
Monitoring: Architecture, Design and Deployment Experience", Proc.
USENIX Symposium on Networked System Design and Implementation (NSDI),
- W. B. Norton, "Internet
Service Providers and Peering", Draft paper, 2000. [pdf]
- Douglas S. J. De Couto, Daniel
Aguayo, John Bicket, and Robert Morris, "A High-Throughput Path
Metric for Multi-Hop Wireless Routing", Mobicom '03 PDF
- Karp, B. and Kung, H.T. "GPSR: Greedy
Perimeter Stateless Routing for Wireless Networks", Mobicom '00 PS
- Ion Stoica, Robert Morris, David
Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari
Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Protocol for
Internet Applications", IEEE/ACM Transactions on Networking '02 PDF
Other related (optional) readings:
- Rodrigo Fonseca, Sylvia Ratnasamy, Jerry Zhao, Cheng Tien
Ee, David Culler, Scott Shenker, Ion Stoica, "Beacon Vector Routing:
Scalable Point-to-Point Routing in Wireless Sensornets", NSDI '05, PDF
Li, John Jonnotti, Douglas De Couto, David R. Karger and Robert Morris,
"A scalable location service for geographic ad hoc routing", Mobicom
Lecture 5: TCP and Congestion Control
Lecture 6: Network Services: QoS, Fair Queuing
- D.-M. Chiu and R. Jain,
"Analysis of the Increase and Decrease Algorithms for Congestion
Avoidance in Computer Networks", Computer Networks and ISDN Systems,
Vol. 17, 1989, pp. 1-14. [PDF]
- D. Katabi, M. Handley, C. Rohr,
"Congestion Control for High Bandwidth-Delay Product Networks".
ACM SIGCOMM 2002. [PDF]
- V. Jacobson, "Congestion
Avoidance and Control", SIGCOMM '88, Sept. 1988, pp. 314-329.[PDF]
- I. Stoica and H. Zhang,
"Providing Guaranteed Services Without Per Flow Manage ment". ACM
SIGCOMM'99 , Boston, MA, Sept 1999.[PDF]
- Alan Demers, Srinivasan Keshav and Scott Shenker. Analysis and Simulation of a Fair Queuing Algorithm. SIGCOMM 1989
Lecture 7: Multicast and Anycast: IP and Overlays
- S. Blake et al, "An
Architecture for Differentiated Services", RFC 2475, December 1998.
- R. Braden, D. Clark & S.Shenker.
"Integrated Services in the Internet Architecture: an Overview",
RFC 1633, June 1994.
Lecture 8: Overlay based services
Lecture 9: Peer to Peer Services
- L. Subramanian, I. Stoica, H.
Balakrishnan and R. H. Katz."OverQoS: An Overlay based Architecture for
Enhancing Internet QoS", ACM/USENIX NSDI, March, 2004. PDF
- D.G. Andersen, H. Balakrishnan, F.
Kaashoek and R. Morris. "Resilient Overlay Networks", ACM SOSP. PDF
- M. J. Freedman, E. Freudenthal and D. Mazieres, "Democratizing Content Publication using Coral. NSDI 2004. PDF
Lecture 10: Wireless Basics
- V. Ramasubramanian and E. Sirer "The Design and Implementation of a Next Generation Name Service for the Internet"PDF
- F. Dabek, M. F. Kaashoek, R. Morris, I. Stoica, "Wide-area cooperative storage with CFS". PDF. SOSP 2001.
No Papers for this Class.
Lecture 11: Analog Network Coding
Lecture 12: Wireless protocols
- Sachin Katti, Shyamnath Gollakota, and Dina Katabi,
"Embracing Wireless Interference: Analog Network Coding,"
ACM SIGCOMM, 2007.
- Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, and Jon Crowcroft
"XORs In The Air: Practical Wireless Network Coding,"
ACM SIGCOMM, 2006.
- Shyamnath Gollakota and Dina Katabi,
"ZigZag Decoding: Combating Hidden Terminals in Wireless Networks,"
ACM SIGCOMM, 2008.
Lecture 13: Software Routers
- Sanjit Biswas and Robert Morris,
"Opportunistic Routing in Multi-Hop Wireless Networks", SIGCOMM
- Rabin Patra, Sergiu Nedevschi, Sonesh Surana, Anmol Sheth, Lakshminarayanan Subramanian and Eric Brewer. WiLDNet: Design and Implementation of High-Performance Wifi-based Long Distance Networks. ACM/USENIX NSDI,
Lecture 14: Networks Security
Lecture 15: Enterprise Security
- V. Paxson, "Bro: A System for Detecting Network Intruders in Real-Time", Computer Networks, 31(23-24) pp. 2435-2463, Dec. 14, 1999.
- L. Subramanian, V. Roth, I. Stoica, S. Shenker and R.H. Katz. "Listen and Whisper: Security Mechanisms for BGP". ACM/USENIX NSDI 2004.
- S. Singh, C. Estan, G. Varghese and S. Savage. "Automated Worm Fingerprinting". USENIX OSDI 2004.
- J. Newsome, B. Karp, and D. Song, "Polygraph: Automatically Generating Signatures for Polymorphic Worms", Proceedings of the IEEE Symposium on Security and Privacy (Oakland 2005), Oakland, CA, May, 2005.
- Ethane: Taking Control of the Enterprise. Martin Casado, Michael J. Freedman, Justin Pettit, Jianying Luo, Nick McKeown, and Scott Shenker Proc. ACM SIGCOMM Conference (SIGCOMM '07) Kyoto, Japan, August 2007.
- SANE: A Protection Architecture for Enterprise Networks Martin Casado, Tal Garfinkel, Aditya Akella, Michael Freedman, Dan Boneh, Nick McKeown, Scott Shenker In Usenix Security, August 2006