CSE logo University of Washington Computer Science & Engineering
 CSE 561 Syllabus
  CSE Home   About Us    Search    Contact Info 

CSE 561: Computer Networks

Instructor: Tom Anderson (tom@...)
TA: Ivan Beschastnikh (ivan@...)
Meetings: Mon/Wed 10:30-11:50, CSE 503
Pre-requisite: graduate standing in CSE or permission of the instructor

Discussion board: Here

Textbook: Peterson and Davie, Computer Networks: A Systems Approach, 3rd Edition.

Anonymous Feedback: anonymous feedback form

Schedule and Reading List: Below.

Project Webpage: Here

Overview: This course is on how to design (good) computer network protocols.

While it is relatively easy to learn how a specific network protocol works, it is incredibly hard to design a good network protocol. The Internet is a great example -- one can learn most of the aspects of how the Internet protocols work in a relatively short period of time, but that won't help you (much) in designing a new protocol. The Internet is successful for reasons that are mostly hidden in its design, embodying specific, debatable tradeoffs in balancing robustness, interoperability, scale, evolution, flexibility, operator incentives and security. And while you might think that we don't need any new protocols beyond the Internet, industry is developing new protocols all the time, often quite poorly. As a recent example, one need look no farther than 802.11 (WiFi) -- it has fundamental flaws in security, resource allocation, scalability and management. Added to the fact that the Internet itself is poorly designed for many of these same issues, the need for understanding how to design better protocols has never been greater.

Project: The best way to learn how to design protocols is by practice, and so the core of the course is a substantial protocol design project: to build a wireless ad hoc network using software programmable radios. The project is designed to be done in groups of two to three. We will be setting up a lab in Sieg 324 for the class to use.

Phases:

  1. Design and implement a simple but robust connection setup/teardown and sliding window protocol, capable of achieving the full bandwidth of a link despite (a variable amount of) bit errors, as one might find in a wireless network. Demonstrate that your solution works (e.g., with simulated errors). Due: October 12 at 5pm.
  2. Design and implement a simple but robust physical layer for a wireless link capable of achieving the full bandwidth of a channel with variable SNR and clock skew. We will provide you a baseline implementation that works in the absence of noise and skew. Demonstrate that your solution works with the software radio hardware, using your solution to Assignment #1 for transport. Due: November 13 at 5pm.
  3. For assignments #1 and #2, you could assume that the network consisted of a single link, and the two endpoints of the link are the only users in the system. For assignment #3, we remove those assumptions. First, design and implement a simple but robust routing algorithm for a multihop network that delivers a packet whenever a working path exists in the network for a sufficiently long period of time. Second, design and implement a simple but robust congestion control system that achieves the full bandwidth of the network and avoids starvation for any user, for a variable number of users sharing the multihop network. Demonstrate that your solution works. Due: December 7 at noon.
    Project demonstrations will be conducted during the afternoon of December 7.
  4. Make your system interoperate with every other project in the class.

Problem Sets: There will be two relatively short problem sets to test your understanding of the material in the textbook.

Final: There will be a comprehensive, open book final in class on December 10, 8:30-10:30.

Collaboration/Cheating: In my view, students learn more from each other than they do from the faculty. Thus, I encourage you to collaborate with your classmates, including those from other groups, in all aspects of the course, with two exceptions outlined below. The grading in the class is emphatically not curved; I would like nothing better than for all of you to pass.

To draw a very clear line, you may use any idea or code from any other person or group in the class or out, provided you clearly state what you have borrowed and from whom. If you do not provide a citation -- that is, you turn other people's work in as your own -- that's cheating. Anything else is fair game. Of course, we'll be grading you on the ideas you've added, but you should always borrow as much as you can as a starting point - there's no point in reinventing the wheel.

The exceptions are the problem sets and of course the final. You may consult your peers in doing the problem sets, but the writeup of your answers must be done individually.

Readings: The reading list is a mixture of textbook material and research papers. The textbook material is designed to help you understand the basics of the project; the research papers are to bring you to the state of the art. It is a requirement that you do the reading before class, as we will take the research papers as a starting point, not the end point of the class discussion. A goal for each class meeting will be to identify the limits of the research community's knowledge - what are the open research problems for that topic? An illustration of how little we really know about network protocol design is that we will be able to do this even for the most basic of topics. I will attempt to set the stage for the reading by discussing the problems being tackled by the next set of papers at the end of the previous class.

Discussion and Blogs: While I will do some lecturing, most of each class will be taken up with a free form discussion of the papers. For each paper, I'll appoint two people: an advocate and a skeptic, each to speak for 2-3 minutes about the paper. The advocate gives the elevator pitch for the paper: what is the topic of the paper, what are its main results, why the system or idea is better than its competition, why does the result matter and who are the target users. Note that the answers to these questions may be different from the ones the authors gave in the paper! The skeptic speaks on why the conclusions of the paper are not to be trusted. Everyone else (except these two) are to read each paper and blog a unique comment about the paper to the course web site no later than 9:00am on the day of the class. (This is to give time for everyone to read the blog entries before class.) Note that the earlier you post, the easier it is to be unique. Please keep blog entries short: they can be anything that provides insight into the paper, e.g., a summary, the broader context for the work, a question about some aspect of the paper, an answer to someone else's question, a methodogical flaw, or a pointer to related work not described by the paper.

Grading: Blogs/Class Discussion: 20%; Project: 40%; Problem Sets: 10%; Final: 30%.


Syllabus and Reading List:
Date Topic P&D Chapters Papers Advocate Skeptic
9/26 Transport 1.5, 2.5, 5.2 None! N/A N/A
10/1 Physical Layer 2.2-2.4

Jamieson and Balakrishnan, PPR: Partial Packet Recovery. SIGCOMM 07

Halperin et al., Interference Cancellation: Better Receivers for a New Wireless MAC. Submitted.

Open

Open

Open

Open

10/3 Ethernet and Wireless MAC 2.6, 2.8

Cheng et al., Jigsaw: Solving the Puzzle of Enterprise 802.11 Analysis. SIGCOMM 06.

Patra et al., WiLDNet: Design and Implementation of High Performance WiFi Based Long Distance Networks, NSDI 07

Michael

Karl

Kate

Open

10/8 Internetworks 1.3, 4.1

David Clark. The Design Philosophy of the DARPA Internet Protocols. SIGCOMM 88.

Saltzer et al. End to end arguments in system design. ACM TOCS 1984.

Matthew

Xiaoyu

Andrey

Michael

10/10 Addressing and Naming 4.3, 9.1

Ramasubramanian and Sirer, The Design and Implementation of a Next Generation Name Service for the Internet. SIGCOMM 04.

Thach

Matthew

10/15 Routing: wired 3.1, 3.2, 4.2 Khanna and Zinky, The Revised ARPAnet Routing Metric. SIGCOMM 86.

Andrey

Karl

10/17 Routing: wireless  

Johnson and Maltz, Dynamic Source Routing in Ad Hoc Networks, Mobile Computing, 1996.

Biswas and Morris, Opportunistic Routing in Multihop Wireless Networks, SIGCOMM 05.

Michael

Richa

Alexei

Thach

10/22 Routing: interdomain  

Balakrishnan, Interdomain routing. (background, no blog needed)

John et al., Routing by Consensus, Submitted.

Chan et al., Modeling the Adoptability of Secure BGP Protocols. SIGCOMM 2006.

N/A

Xiaoyu

Andrey

N/A

Alexei

Karl

10/24 Congestion Control: TCP 6.1-6.3

V. Jacobson. Congestion Avoidance and Control. SIGCOMM '88, pp. 314-329.

Michael Kate
10/29 Congestion Control: RED, WFQ, PCP 6.2, 6.4

Demers, Keshav, and Shenker. Analysis and Simulation of a Fair Queueing Algorithm. SIGCOMM 89.

T. Anderson et al. PCP: Efficient Endpoint Congestion Control. NSDI 06.

Matthew

Thach

Richa

Xiaoyu

10/31

QoS: IntServ vs. DiffServ

Class in 403 today!

6.5

D. Clark, S. Shenker, and L. Zhang. Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanisms. SIGCOMM 1992.

Alexei Michael
11/5 Network Management 4.5

Yan et al., Tesseract: A 4D Network Control Plane. NSDI 07.

Casado et al., Ethane: Taking Control of the Enterprise. SIGCOMM 07.

Karl

Xiaoyu

Matthew

Richa

11/7

Denial of Service

Class in 624 today!

 

Shieh et al. Trickles: A Stateless Network Stack for Improved Scalability, Resilience and Flexibility. NSDI 2005.

Dixon et al., Phalanx, Submitted.

Kate

Karl

Thach

Michael

11/14 Content Distribution 9.4

Breslau et al. Web Caching and Zipf-like Distributions, INFOCOM 1999.

Wang et al., Reliability and Security in the CoDeeN CDN. USENIX 2004.

Matthew

Richa

Kate

Xiaoyu

11/19 File Sharing  

Cohen, Incentives Build Robustness in BitTorrent

Do incentives build robustness in BitTorrent

Walsh and Sirer. Experience with an Object Reputation System for Peer-to-Peer Filesharing. NSDI 06.

Alexei

Kate

Andrey

Thach

Richa

Alexei

11/26 DHTs  

Maymounkov and Mazieres, Kademlia: A P2P Information System Based on the XOR Metric. IPTPS 02.

Bharambe et al., Mercury: Supporting Scalable Multi-Attribute Range Queries. SIGCOMM 04

Karl

Richa

Matthew

Xiaoyu

11/28 Overlays  

Andersen et al. Resilient Overlay Networks, SOSP 2001.

Madhyastha et al. iPlane: An Information Plane for Distributed Services, OSDI 06.

Andrey

Michael

Alexei

Matthew

12/3 Alternate Architectures  

Wetherall, Active Network Vision and Reality. SOSP 1999.

Peterson et al. Overcoming the Internet Impasse through Virtualization. IEEE Computer, 2005.

Kate

Xiaoyu

Thach

Richa

12/5 Evolution  

Handley, Why the Internet Only Just Works, BT Technology Journal, July 2006.

Clark et al. Tussle in Cyberspace: Defining Tomorrow's Internet. SIGCOMM 02.

Thach

Karl

Alexei

Andrey


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to dhalperi]