Networks and Distributed Systems
 
Spring 2010
Prof. Lakshminarayanan Subramanian
Wed 5:00-6:50, CIWW 201
Office Hours:  Thu 5:00- 6:00, 715 Broadway, Room 706
Overview
This is a graduate level course on computer networks and Internet-scale 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 need read many research papers (with our guidance) to learn the current challenges and solutions in networking and large-scale systems. If you have been exposed to a networking course in your undergrad (i.e. 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 can:
    •    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  15% weightage)
    •    a series of labs (40% weightage) + final class project (20% weightage)
    •    a midterm (15% weightage)
 
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, peer-to-peer systems, 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 labs in this course will expose the students to the essential topics of networking. This course will strongly encourage a “learning by doing it yourself” approach to networking, where the students will implement or measure different concepts learnt
in class. The final course project (conducted in a group of 2 students) should be a research-oriented project which should be a design/implementation of a new concept in networking or distributed systems. Several suggested projects may build on the labs for the class and will be a natural continuation of a specific lab.  Your goal in the labs and the final projects is to understand how networks work and how to build systems.  Research projects will be presented in a poster in a departmental mini-conference in the Spring Showcase.  Suggested project ideas will be provided by the instructor.
Prerequisites:
1. Undergraduate Networks and/or Operating Systems
2. Programming experience in C/C++ or Java is helpful for the labs and final project.
 
Lectures and Readings (from 2009 - subject to change)
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
    •    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 2:  End-to-end principle, Naming
    •    J. Saltzer, D. Reed, and D. Clark, "End-to-end Arguments in System Design". ACM Transactions on Computer Systems (TOCS), Vol. 2, No. 4, 1984, pp. 195-206.[pdf]
    •    P. Mockapatris, K.J. Dunlap, "Development of the Domain Name System",ACM SIGCOMM 1988. [pdf]
    
Suggested Additional Reading:
    •    B. Ford, J. Strauss, C. Lesniiewski-Laas, S. Rhea, F. Kaashoek and R. Morris. "User-Relatives Names for Globally Connected Personal Devices", USENIX OSDI 2006.
    •    D. Clark. "Rethinking the Design of the Internet: end to end arguments vs. the brave new world." Presented at TPRC 2000, Alexandria, Va., September 23-25th, 2000.[pdf]
 
Lecture 3: Routing in the Internet World 
    •    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]
 
Suggested Additional reading:
    •    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), March 2004.[pdf]
    •    W. B. Norton, "Internet Service Providers and Peering", Draft paper, 2000. [pdf]
 
Lecture 4: Routing in Wireless and P2P networks
 
    •    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
    •    Jinyang Li, John Jonnotti, Douglas De Couto, David R. Karger and Robert Morris, "A scalable location service for geographic ad hoc routing", Mobicom '00, PDF
 
Lecture 5: TCP  and Congestion Control
    •    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]
 
Lecture 6: Network Services: QoS, Fair Queuing
    •    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
Additional Reading
    •    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 7: Multicast and Anycast: IP and Overlays
    •    J. Jannotti and D. Gifford and K. Johnson and M. F. Kaashoek and J. O'Toole. "Overcast: Reliable Multicasting with an Overlay Network", OSDI 2000, PDF
    •    S. Deering and D. Cheriton, "Multicast Routing in Datagram Internetworks and Extended LANs", ACM Transactions on Computer Systems (TOCS) '90, PDF
    •    Dina Katabi and John Wroclawski ,  " A Framework for Scalable Global IP-Anycast (GIA)." SIGCOMM 2000. 
 
Lecture 8: Overlay based 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 9: Peer to Peer Services
    •    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.
 
Lecture 10: Wireless Basics
No Papers for this Class.
 
Lecture 11:  Analog Network Coding
    •    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 12: Wireless protocols
    •    Sanjit Biswas and Robert Morris, "Opportunistic Routing in Multi-Hop Wireless Networks", SIGCOMM 2005, PDF
    •    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, 2007. [pdf]
 
Lecture 13: Software Routers
    •    The Click modular router. (ACM Digital LibraryPDFPostScript)Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. ACM Transactions on Computer Systems 18(3), August 2000, pages 263-297.
    •    Designing Extensible IP Router Software. (PDF) Mark Handley, Eddie Kohler, Atanu Ghosh, Orion Hodson, and Pavlin Radoslavov.Proc. 2nd Symposium on Networked Systems Design & Implementation (NSDI '05), Boston, Massachusetts, May 2005, pages 189-207
 
Lecture 14: Networks 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.
 
Lecture 15: Enterprise Security
    •    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