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

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

Instructors

Prof. David O'Hallaron, droh@cs.cmu.edu, WeH 8125, (412) 268-8199,
Office hours: Thu 3-4pm. (These are my nominal hours. Drop by any time.)

Michael Abd-El-Malek (TA), mabdelmalek@cmu.edu, CIC 2220F, (412) 268-5658,
Office hours: Tue 5-6pm in CIC 2206.

Organization

Class times: Tue and Thu, 1:30-2:50, WeH 5328
Admistrative Asst: Barb Grandillo, bag@cs.cmu.edu, WeH 8018, (412) 268-7550
Web page: www.ece.cmu.edu/~ece845
Newsgroup: cmu.ece.class.ee845 (not monitored by teaching staff)
Course directory: /afs/ece/class/ece845

Reference material

There is no required textbook for 18-845.

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.
The CS:APP text, which is available in the campus bookstore and on reserve in the Engineering library, covers system-level programming topics such as dynamic linking, process control, Unix I/O, the sockets interface, writing Web servers, and application level concurrency and synchronization:

Course schedule

Legend: IP: individual project, GP: group project

Class Date Day Topic Projects Discussion Leader(s)
1 01/16 Tue Welcome Dave O'Hallaron
2 01/18 Thu A tour of Internet services IP out Dave O'Hallaron
3 01/23 Tue System design principles Dave O'Hallaron
4 01/25 Thu Server design - basics Dave O'Hallaron
5 01/30 Tue Server design - events Dave O'Hallaron
6 02/01 Thu Server design - threads Dave O'Hallaron
7 02/06 Tue Measuring server capacity IP due, 1:30pm Dave O'Hallaron
8 02/08 Thu Clustering - architecture Dan Granahan
9 02/13 Tue Clustering - request routing Michael Abd-El-Malek
10 02/15 Thu Web services and SOAP Shivani Kirubanandan
11 02/20 Tue Monitoring - network-based measurement and diagnosis Syed Wasif Haider
12 02/22 Thu Monitoring - fault diagnosis GP abstract due, 1:30pm Joe Laws
13 02/27 Tue Monitoring - scalability Adrian Ng
14 03/01 Thu Availability through replication Michael Abd-El-Malek
15 03/06 Tue Security - buffer-overflows and the Morris worm Orathai Sukwong
16 03/08 Thu Security - worm defense Keetaek Hong
17 03/13 Tue No class - Spring break
18 03/15 Thu No class - Spring break
19 03/20 Tue Content delivery - P2P overview Xiao (Eric) Tang
20 03/22 Thu Content distribution - BitTorrent I GP Mid-term oral reports due Hiroshi Isozaki
21 03/27 Tue Content distribution - BitTorrent II Xiaohui Wang
22 03/29 Thu Content distribution - reputation Michael Abd-El-Malek
23 04/03 Tue Google - search Mark Hairgrove
24 04/05 Thu Google - architecture and file system Ryan Frishberg
25 04/10 Tue Google - programming abstractions Ajay Surie
26 04/12 Thu Google - storage abstractions Supriya Kher
27 04/17 Tue Virtual machines Ka Wing (Michael) Ho
28 04/19 Thu No class - Spring carnival
29 04/24 Tue No class - GP prep
30 04/26 Thu No class - GP reports due GP reports due, 1:30pm
31 05/01 Tue No class - GP reviews due GP reviews due, 1:30pm
32 05/03 Thu GP poster session (HH 1112) GP poster session, 1:30pm
05/06 Sun GP final reports due, 11:59pm

Detailed course schedule

Students who are not leading the discussion for a particular class should prepare a single 1-page critique. Unless explictly noted, the critique should cover all papers with a "*".

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

Class 1: Welcome (Tue 1/16)

Discussion leader: Dave O'Hallaron

Welcome and overview of course organization.

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

Discussion leader: Dave O'Hallaron

Big picture and intellectual overview.

  • Note: No critiques are due today.
  • Eric A. Brewer, Lessons from Giant-Scale Services, IEEE Internet Computing, Vol 5, Num. 4, Aug, 2001. (pdf)

Class 3: System design principles (Thu 1/23)

Discussion leader: Dave O'Hallaron
  • 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)
  • *Butler Lampson, Hints for Computer System Design ACM Operating Systems Rev. 15, 5 (Oct. 1983), pp 33-48. Reprinted in IEEE Software 1, 1 (Jan. 1984), pp 11-28. (html)

Class 4: Server design - basics (Thu 1/25)

Discussion leader: Dave O'Hallaron
  • *V. Pai, P. Druschel, and W. Zwaenepoel, Flash: An efficient and portable Web server, Proceedings of the USENIX 1999 Annual Technical Conference, 1999. (pdf)
  • *Tim Brecht , David Pariag, and Louay Gammo, accept()able Strategies for Improving Web Server Performance, Proceedings of the USENIX 2004 Annual Technical Conference, June, 2004. (pdf)
  • D. Mosberger and T. Jin. httperf: A Tool for Measuring Web Server Performance. Performance Evaluation Review, Volume 26, Number 3, December 1998, 31-37. (Originally appeared in Proceedings of the 1998 Internet Server Performance Workshop, June, 1998.) ( pdf, download )

Class 5: Server design - events (Tue 1/30)

Discussion leader: Dave O'Hallaron
  • *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, June 1999. (pdf)
  • *Matt Welsh, David Culler, and Eric Brewer, SEDA: An Architecture for Well-Conditioned, Scalable Internet Services, in Proceedings of the Eighteenth Symposium on Operating Systems Principles, October, 2001. (pdf)

Class 6: Server design - threads (Thu 2/1)

Discussion leader: Dave O'Hallaron
  • *R. von Behren, J. Condit and E. Brewer, Why Events Are A Bad Idea (for high-concurrency servers), Proceedings of HotOS IX, Lihue, Kauai, Hawaii, May, 2003. (pdf)
  • *R. von Behren, J. Condit, F. Zhou, G. C. Necula, and E. Brewer, Capriccio: Scalable Threads for Internet Services, Proceedings of the ACM Symposium on Operating Systems Principles, October, 2003. (pdf)

Class 7: Measuring server capacity (Tue 2/6)

Discussion leader: Dave O'Hallaron
  • *G. Banga and P. Druschel, Measuring the Capacity of a Web Server under Realistic Loads, World Wide Web Journal (Special issue on World Wide Web Characterization and Performance Evaluation), 2(1), May 1999. (Earlier version appeared in Usenix Symposium on Internet Technologies and Systems, December, 1997. (pdf)

Class 8: Clustering - architecture (Thu 2/8)

Discussion leaders: Dan Granahan
  • *A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, P. Gauthier, Cluster-Based Scalable Network Services. In Proceedings of the Sixteenth Symposium on Operating Systems Principles (SOSP-16). Saint Malo, France, October, 1997. (pdf)
  • *S. D. Gribble, E. A. Brewer, J. M. Hellerstein, D. Culler, Scalable, Distributed Data Structures for Internet Service Construction. In Proceedings of the Symposium on Operating Systems Design and Implementation, 2000. (pdf)

Class 9: Clustering - request routing (Tue 2/13)

Discussion leaders: Michael Abd-El-Malek
  • *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, October 1998. (pdf)
  • *M. Aron, D. Sanders, P. Druschel, and W. Zwaenepoel. Scalable Content-aware Request Distribution in Cluster-based Network Servers. In Proceedings of the USENIX 2000 Annual Technical Conference, June, 2000. (pdf)

Class 10: Web services and SOAP (Thu 2/15)

Discussion leaders: Shivani Kirubanandan
  • *G. Coulouris, J. Dollimore, and T. Kindberg. Chapter 19 of "Distributed Systems Concepts and Design, Fourth Edition". Addison Wesley, 2005.

Class 11: Monitoring - network-based measurement and diagnosis (Tue 2/20)

Discussion leader: Syed Wasif Haider
  • *S. Savage, Sting: a TCP-based Network Measurement Tool, In Proceedings of the 1999 USENIX Symposium on Internet Technologies and Systems, October, 1999. (pdf)
  • *S. Savage, N. Cardwell, D. Wetherall, and T. Anderson, TCP Congestion Control with a Misbehaving Receiver, ACM Computer Communications Review, October, 1999. ( pdf )

Class 12: Monitoring - problem diagnosis (Thu 2/22)

Discussion leader: Joe Laws
  • Note: Please write two separate critiques.
  • *M. Chen and E. Kiciman and E. Fratkin and A. Fox and E. Brewer, Pinpoint: Problem Determination in Large, Dynamic, Internet Services, In Proceedings of the International Conference on Dependable Systems and Networks, 2002. (pdf)
  • *Ratul Mahajan, Neil Spring, David Wetherall, Thomas Anderson, User-level Internet Path Diagnosis, In Proceedings of the ACM Symposium on Operating Systems Principles, October, 2003. (pdf)

Class 13: Monitoring - scalability (Tue 2/27)

Discussion leader: Adrian Ng
  • *M. L. Massie, B. N. Chun, and D. E. Culler, The Ganglia Distributed Monitoring System: Design, Implementation, and Experience, Parallel Computing, Vol. 30, Issue 7, July, 2004. (pdf)
  • *C. Verbowski, E. Kıcıman, A. Kumar, B. Daniels, S. Lu, J. Lee, Yi-Min Wang, and R. Roussev, Flight Data Recorder: Monitoring Persistent-State Interactions to Improve Systems Management, In Proceedings of the Seventh Symposium on Operating Systems Design and Implementation, December, 2006. (pdf)

Class 14: Availability through replication (Thu 3/1)

Discussion leader: Michael Abd-El-Malek
  • *G. Coulouris, J. Dollimore, and T. Kindberg. Chapter 15 of "Distributed Systems Concepts and Design, Fourth Edition". Addison Wesley, 2005.
  • Leslie Lamport Paxos Made Simple. SIGACT News 32(4):18-25, 2001. (pdf)

Class 15: Security - buffer-overflows and the Morris worm (Tue 3/6)

Discussion leader: Orathai Sukwong
  • *aleph one, Smashing the Stack for Fun and Profit, Nov, 1996. (txt)
  • *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)

Class 16: Security - worm defense (Thu 3/8)

Discussion leader: Keetaek Hong
  • *J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proceedings of the 12th Annual Network and Distributed System Security Symposium, February, 2005. (pdf)
  • *M. Costa, J. Crowcroft, M. Castro, A. Rowstron, L. Zhou, L. Zhang, and P. Barham. Vigilante: End-to-End Containment of Internet Worms, in Symposium on Operating System Principles, October, 2005. (pdf)

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

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

Class 19: Content delivery - P2P overview (Tue 3/20)

Discussion leader: Xiao (Eric) Tang
  • *G. Coulouris, J. Dollimore, and T. Kindberg. Chapter 10 of "Distributed Systems Concepts and Design, Fourth Edition". Addison Wesley, 2005.

Class 20: Content distribution - BitTorrent I (Thu 3/22)

Discussion leader: Hiroshi Isozaki
  • *Bram Cohen, Incentives Build Robustness in BitTorrent, white paper. (pdf)
  • *M. Izal, G. Urvoy-Keller, E.W. Biersack, P.A. Felber, A. Al Hamra, and L. Garces-Erice, Dissecting BitTorrent: Five Months in a Torrent's Lifetime, Passive and Active Measurement Workshop (PAM), April, 2004. ( pdf, RedHat9 tracker log and instrumented client code )
  • Clive Thompson, The BitTorrent Effect, Wired, Jan, 2005. (html)
  • BitTorrent Protocol Specification, bittorrent.org. (html)
  • Stephanos Androutsellis-Theotokis and Diomidis Spinellis A survey of peer-to-peer content distribution technologies, Computing Surveys, 36(4), Dec 2004. (pdf)

Class 21: Content distribution - BitTorrent II (Tue 3/27)

Discussion leader: Xiaohui Wang
  • *M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani, Do incentives build robustness in BitTorrent?, To appear in the 4th USENIX Symposium on Networked Systems Design & Implementation, 2007. (pdf)
  • *C P. Fry, and M. K. Reiter, Really Truly Trackerless BitTorrent, CMU-CS-06-148 Technical Report, August, 2006. (pdf)

Class 22: Content distribution - reputation (Thu 3/29)

Discussion leader: Michael Abd-El-Malek
  • *J. Douceur, The Sybil Attack, In Proceedings of IPTPS, 2002. (pdf)
  • *K. Walsh, and E.G. Sirer, Experience with an Object Reputation System for Peer-to-Peer Filesharing, In Proceedings of Networked System Design and Implementation, May, 2006. (pdf)

Class 23: Google - search (Tue 4/3)

Discussion leader: Mark Hairgrove
  • *Sergey Brin and Larry 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 )
  • *Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The PageRank Citation Ranking: Bringing Order to the Web, 1998. ( html )
  • Ian Rogers, The Google Pagerank Algorithm and How It Works (html) May, 2002.

Class 24: Google - architecture and file system (Thu 4/5)

Discussion leaders: Ryan Frishberg
  • *Luiz Barroso, Jeffrey Dean, and Urs Hoelzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro. (pdf)
  • *Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, The Google File System, in Proceedings of the 19th ACM Symposium on Operating Systems Principles, October, 2003. (pdf)

Class 25: Google - programming abstractions (Tue 4/10)

Discussion leader: Ajay Surie
  • Note: Please write two separate critiques.
  • *J. Dean, and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, in Proceedings of Sixth Symposium on Operating System Design and Implementation, December, 2004. (pdf)
  • *M. Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, in Proceedings of the Seventh Symposium on Operating System Design and Implementation, December, 2006. (pdf)

Class 26: Google - storage abstractions (Thu 4/12)

Discussion leaders: Supriya Kher
  • *F. Chang, J. Dean, S. Ghemawat, W.C. Hsieh, D.A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, Bigtable: A Distributed Storage System for Structured Data, in Proceedings of the Seventh Symposium on Operating System Design and Implementation, December, 2006. (pdf)

Class 27: Virtual machines (Tue 4/17)

Discussion leader: Ka Wing (Michael) Ho
  • *P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfiel, Xen and the Art of Virtualization, In Proceedings of the 19th ACM Symposium on Operating Systems Principles, October, 2003. (pdf)
  • *K. Adams, and O. Agesen, A Comparison of Software and Hardware Techniques for x86 Virtualization, In Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, 2006. (pdf)
  • Partho Nath, Michael Kozuch, David O'Hallaron, M. Satyanarayanan, N. Tolia, and Matt Toups, Design Tradeoffs in Applying Content Addressable Storage to Enterprise-scale Systems Based on Virtual Machines. USENIX '06, Boston, MA, May, 2006. (pdf)
  • M. Satyanarayanan, Michael Kozuch, Casey Helfrich, and David R. O'Hallaron, Towards seamless mobility on pervasive hardware. Pervasive & Mobile Computing, Elsevier, vol 1, num 2, 2005. (pdf)

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

Class 29: No class (Tue 4/24)

Class 30: No class - GP reports due (Thu 4/26)

Class 31: No class - GP reviews due (Tue 5/1)

Class 32: GP poster session (location TBD, Thu 5/3)


Dave O'Hallaron
Last modified: Fri Feb 16 14:56:18 EST 2007