18-845: Internet Services
Carnegie Mellon University, Spring 2004

Syllabus (ps, pdf) | Critiques | Individual Project (IP) | Group Project (GP)

Instructors

Patrick Shih (TA), pcshih@ece.cmu.edu, (412)268-3029, Office hours:

• Mon: 3-5pm, Room 206, INI Bldg, 4616 Henry Street
• Wed: 3-5pm, ECE Cluster, Hamerschlag Hall

Reference material

The following books by Stevens are the standard references for Unix network programming:

• W. Richard Stevens, Unix Network Programming: Networking APIs, Volume 1 (2nd Ed), Prentice Hall, 1998.
• W. Richard Stevens, Unix Network Programming: Interprocess Communication, Volume 2 (2nd Ed), Prentice Hall, 1999.

• Randal E. Bryant and David R. O'Hallaron, Computer Systems: A Programmer's Perspective, Prentice Hall, 2003.

Course schedule

Class	Date	Day	Topic	Projects	Discussion Leader(s)
1	01/13	Tue	Welcome		O'Hallaron
2	01/15	Thu	Tour of Internet services	IP out	O'Hallaron
3	01/20	Tue	End-to-end Arguments [R1: I/O]		O'Hallaron [Shih]
4	01/22	Thu	High performance servers [R2: Server design]		O'Hallaron [Shih]
5	01/27	Tue	No papers [R3: Threads]		[Shih]
6	01/29	Thu	Measuring server performance [R4: Linking]		Kevin Lee (kclee) [Shih]
7	02/03	Tue	Improving server performance (R5: DNS)		Rajiv Motwani (rmotwani) [Shih]
8	02/05	Thu	Clustering - Lard	IP due, 12:30pm	Roberto Aravelo (rarevalo)
9	02/10	Tue	Clustering - Porcupine		Arseniy Khobotkov (akhobotk)
10	02/12	Thu	Clustering - Resource Mgmt		Andrew Boyer (aboyer)
11	02/17	Tue	Monitoring - Sting		Soila Pertet (spertet)
12	02/19	Thu	Monitoring - Path Diagnosis		Hassan Moin Khan (hkhan)
13	02/24	Tue	Geographic mapping		Jeffrey Lin (jtlin)
14	02/26	Thu	Global network positioning	GP proposals due 12:30pm	Mike Merideth (mmeridet)
15	03/2	Tue	No class - NSF site review
16	03/4	Thu	No class - NSF site review
17	03/9	Tue	No class - Spring break
18	03/11	Thu	No class - Spring break
19	03/16	Tue	Unstructured overlays - Freenet		Rahul Dhar (rdhar)
20	03/18	Thu	Unstructured overlays - ESM		Phillipe Wilson (pmwilson)
21	03/23	Tue	Consistent hashing		Boris Jabes (sjabes)
22	03/25	Thu	Structured Overlays - Chord/Pastry		Harvey Versalovic (harveyv)
23	03/30	Tue	Structured Overlays - CAN		Harvey Versalovic (harveyv)
24	04/1	Thu	P2P applications - Backup		Debmallo Ghosh (dsghosh)
25	04/6	Tue	P2P applications - Search		Matt Brown (mcbrown)
26	04/8	Thu	Project summaries		Dave O'Hallaron
27	04/13	Tue	Security - Program vulnerabilities		Ryan Ungaratti (rju)
28	04/15	Thu	No class - Carnival
29	04/20	Tue	Security - Morris worm case study		Boris Jabes (sjabes)
30	04/22	Thu	No class - GP prep	GP reports due (5:00pm)
31	04/27	Tue	No class - GP prep	GP reviews due (5:00pm)
32	04/29	Thu	GP poster session (HH 1112)
	05/2	Sun		Final GP reports due (11:59pm)

Detailed course schedule

Students who are not leading the discussion for a particular class should prepare
a 1-page critique for each paper denoted by a "*".

Bring a hardcopy (no email) of your critique with you to class and give it to Patrick before class.
He will grade it and return it to you next class.

Class 1: Welcome (Tue 1/13)

• Welcome and overview of course organization.

Class 2: A tour of Internet services (Thu 1/15)

• Note: No critique due today.
• Committee on Research Horizons in Networking, National Research Council, Looking Over the Fence at Networks, 2001. (pdf)

Class 3: End-to-end arguments (Tue 1/20)

• Note: Your critique should list three other examples (not discussed by the authors) of end-to-end arguments in system design.
• *J. Saltzer, D. Reed, and D. Clark, End-to-End Arguments in System Design, ACM Transactions on Computer Systems, Vol 2, No 4, Nov, 1984. (pdf)
• M. Blumenthal and D. Clark, Rethinking the Design of the Internet: The End to End Arguments vs. the Brave New World, ACM Transactions on Internet Technology, Vol 1, No 1, Aug, 2001. (pdf)
• D. Clark, J. Wroclawski, K. Sollins, and R. Braden, Tussle in Cyberspace: Defining Tomorrow's Internet SIGCOMM'02, August, 2002, Pittsburgh, PA. (pdf)

Class 04: High-performance servers (Thu 1/22)

• Note: Please write two separate critiques.
• *V. Pai, P. Druschel, and W. Zwaenepoel, Flash: An efficient and portable Web server, Proceedings of the USENIX 1999 Annual Technical Conference, Monterey, CA, June 1999 (html)
• *Gaurav Banga, Jeff Mogul and Peter Druschel, A scalable and explicit event delivery mechanism for UNIX, in the Proceedings of the USENIX 1999 Technical Conference, Monterey, CA, June 1999. Winner of Outstanding Paper Award (ps)

Class 5: No papers. (Tue 1/27)

• Note: No critiques due today.

Class 6: Measuring server performance (Thu 1/29)

• *G. Banga and P. Druschel, Measuring the capacity of a Web server, Usenix Symposium on Internet Technologies and Systems, cMonterrey, CA, Dec, 1997 (html).

Class 7: Improving server performance (Tue 2/3)

• *T. Faber, J. Touch, and W. Yue, The TIME-WAIT state in TCP and its effect on busy servers, Proceedings of IEEE INFOCOM, pp. 1573-1584, IEEE, New York, NY, March 21-25 1999 (ps | pdf | html)

Class 8: Clustering (Thu 2/5)

• *V. Pai, M. Aron, G. Banga, M. Svendsen, P. Drushel, W. Zwaenepoel, E. Nahum, Locality-aware request distribution in cluster-based network services. In Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII). San Jose, California, October 1998 (html)

Class 9: Clustering (Thu 2/10)

• *Y. Saito, B. Bershad, and H. Levy, Manageability, availability, and performance in Porcupine: a highly scalable, cluster-based mail service , 17th ACM Symposium on Operating Systems Principles (SOSP'99), Kiawah Island, SC, Dec, 1999 (ps)
• Yasushi Saito, Brian Bershad and Hank Levy. Manageability, availability and performance in Porcupine: a highly scalable, cluster-based mail service, ACM Transactions on Computer Systems, Aug 2000. (ps)

Class 10: Clustering (Thu 2/12)

• *Kai Shen, Hong Tang, Tao Yang, Lingkun Chu, Integrated Resource Management for Cluster-based Internet Services, Proceedings of the 5th Symposium on Operating Systems Design and Implementation, Boston, Dec, 2002. ( ps)

Class 11: Monitoring (Tue 2/17)

• Note: Please write two separate critiques.
• *Stefan Savage, Sting: a TCP-based Network Measurement Tool, Proceedings of the 1999 USENIX Symposium on Internet Technologies and Systems, pp. 71-79, Boulder, CO, October 1999. ( pdf )
• *Stefan Savage, Neal Cardwell, David Wetherall, and Tom Anderson, TCP Congestion Control with a Misbehaving Receiver, ACM Computer Communications Review, October 1999. ( html )

Class 12: Monitoring (Thu 2/19)

• *Ratul Mahajan, Neil Spring, David Wetherall, Thomas Anderson User-level Internet Path Diagnosis, Proceedings of the 19th ACM Symposium on Operating Systems Principles, Lake George, NY, Oct, 2003. (pdf)

Class 13: Geographic mapping (Tue 2/24)

• *Venkata N. Padmanabhan, Lakshminarayanan Subramanian An Investigation of Geographic Mapping Techniques for Internet Hosts, Proc. ACM SIGCOMM Conf., San Diego, CA, September 2001. (pdf)

Class 14: Global network positioning (Thu 2/26)

• *T. S. Eugene Ng and Hui Zhang, Predicting Internet Network Distance with Coordinates-Based Approaches, INFOCOM'02, New York, NY, June 2002 (pdf)

Class 15: No class - NSF site review (Tue 3/2)

Class 16: No class - NSF site review (Thu 3/4)

Class 17: No class - Spring break (Tue 3/9)

Class 18: No class - Spring break (Thu 3/11)

Class 19: Unstructured overlays - Freenet (Tue 3/16)

• *I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, Freenet: A Distributed Anonymous Information Storage and Retrieval System,ICSI Workshop on Design Issues in Anonymity and Unobservability, LNCS 2009, July 2001. (html)

Class 20: Unstructured overlays - ESM (Thu 3/18)

• NOTE: Please write a single critique covering both papers.
• *Yang-hua Chu, Sanjay G. Rao, Srinivasan Seshan and Hui Zhang, A Case for End System Multicast, IEEE Journal on Selected Areas in Communication (JSAC), Special Issue on Networking Support for Multicast, vol 20, num 8, Oct, 2002. (pdf)
• *Y. Chu, S. Rao, S. Seshan, and H. Zhang, Enabling Conferencing Applications on the Internet using an Overlay Multicast Architecture, SIGCOMM '01, Aug, 2001, San Diego, CA. (pdf)

Class 21: Consistent hashing (Tue 3/23)

• *David Karger, Eric Lehman, Tom Leighton, Mathhew Levine, Daniel Lewin, Rina Panigrahy, Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, ACM Symposium on Theory of Computing", May 1997. (html)

Class 22: Structured overlays - Chord/Pastry (Thu 3/25)

• NOTE: Please write one critique covering both papers
• *I. Stoica, R. Morris, D. Karger, M. Kaashoek, H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Proc. ACM SIGCOMM, San Diego, CA, August 2001. (pdf)
• *Antony Rowston and Peter Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, in Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany, November 2001. (pdf)

Class 23: Structured overlays - CAN (Tue 3/30)

• *Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, A Scalable Content-Addressable Network, ACM SIGCOMM, 2001. (pdf)

Class 24: P2P applications - Backup (Thu 4/1)

• *Mark Lillibridge, Sameh Elnikety, Andrew Birrell, Mike Burrows, and Michael Isard. A Cooperative Internet Backup Scheme, In Proceedings of the 2003 Usenix Annual Technical Conference (General Track), pp. 29-41, San Antonio, Texas, June 2003. ( pdf)
• L. P. Cox, C. Murray, and B. D. Noble, Pastiche: making backup cheap and easy, USENIX Symposium on Operating Systems Design and Implementation, December, 2002, Boston, MA. (pdf)

Class 25: P2P applications - Keyword search (Tue 4/6)

• NOTE: Please write two separate critiques.
• *S. Brin and L. Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, Seventh International World Wide Web Conference / Computer Networks 30(1-7): 107-117. 1998. ( pdf )
• *Patrick Reynolds and Amin Vahdat, Efficient Peer-to-Peer Keyword Searching, Middleware 2003, (pdf)
• Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The PageRank Citation Ranking: Bringing Order to the Web, 1998. ( html )

Class 26: Project summaries (Thu 4/8)

• Each group will give a 10 minute summary of the current state of their project.

Class 27: Security - Program vulnerabilities (Tue 4/13)

• Note: Please write a single critique covering all three papers.
• *Crispin Cowan, Perry Wagle, Calton Pu, Steve Beattie, and Jonathan Walpole. Buffer Overflows: Attacks and Defenses for the Vulnerability of the Decade. In DARPA Information Survivability Conference and Expo (DISCEX), January 2000. (pdf)
• *aleph one, Smashing the Stack for Fun and Profit, Nov, 1996. (txt)
• *team teso, Exploiting Format String Vulnerabilities, Mar, 2001. (pdf)

Class 28: No class - Spring Carnival (Thu 4/15)

Class 29: Security - Morris worm case study (Tue 4/20)

• Note: Please write a single critique covering both papers
• *Eugene H. Spafford, The Internet worm incident, Technical Report CSD-TR-933, Dept. of Computer Sciences, Purdue University, Sept. 1991. (pdf)
• *M. Eichin and J. Rochlis, With microscope and tweezers: An analysis of the Internet Virus of November 1988, IEEE Symposium on Research in Security and Privacy, 1989. (pdf)