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

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

Instructors

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

Mike Merideth (TA), mgm@cs.cmu.edu, CIC 2224A, (412) 268-9595,
Office hours: Tue, Thu 3-4pm

Organization

Class times: Tue and Thu, 1:30-2:50, WeH 8427
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:
  • Randal E. Bryant and David R. O'Hallaron, Computer Systems: A Programmer's Perspective, Prentice Hall, 2003.

Course schedule

Legend: IP: individual project, GP: group project

Class Date Day Topic Projects Discussion Leader(s)
1 01/17 Tue Welcome Dave O'Hallaron
2 01/19 Thu Tour of Internet services IP out Dave O'Hallaron
3 01/24 Tue System design principles Dave O'Hallaron
4 01/26 Thu High performance servers Dave O'Hallaron
5 01/31 Tue Measuring server capacity Dave O'Hallaron
6 02/02 Thu Improving server performance Dave O'Hallaron
7 02/07 Tue Clustering - LARD IP due, 1:30pm Gesly George
8 02/09 Thu Clustering - SCARD Keisuke Ito
9 02/14 Tue Monitoring - Sting Ben Gilbert
10 02/16 Thu Monitoring - TaintCheck Abhinav Mishra
11 02/21 Tue Availability - Replication I Theta Maxino
12 02/23 Thu Availability - Replication II Clive Leung
13 02/28 Tue Availability - Byzantine FT I GP abstracts due, 1:30pm Mike Merideth
14 03/02 Thu Availability - Byzantine FT II Mike Abd-El-Malik
15 03/07 Tue Availability - Thema Mike Merideth
16 03/09 Thu Availability - BAR-B Sean O'Loughlin
17 03/14 Tue No class - Spring break
18 03/16 Thu No class - Spring break
19 03/21 Tue Search - Google Himanshu Khurana
20 03/23 Thu Search - Google FS Rahul Iyer
21 03/28 Tue Content distribution - BitTorrent I Dave O'Hallaron
22 03/30 Thu Content Distribution - BitTorrent II Joseph Mou
23 04/04 Tue Content Distribution - ESM Sachin Kulkarni
24 04/06 Thu Content distribution - Gia Paul Cheong
25 04/11 Tue Virtual machines Chutika Udomsinn
26 04/13 Thu VM migration Mike Merideth
27 04/18 Tue ISR Dave O'Hallaron
28 04/20 Thu No class - Carnival
29 04/25 Tue No class - GP prep
30 04/27 Thu No class - GP prep GP reports due, 1:30pm
31 05/02 Tue No class - GP poster prep GP reviews due, 1:30pm
32 05/04 Thu GP poster session (Location HH 1112) GP poster session, 1:30pm Entire class
05/07 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 the TA before class.
He will grade it and return it to you next class.

Class 1: Welcome (Tue 1/17)

Discussion leader: Dave O'Hallaron

Welcome and overview of course organization.

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

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/24)

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: High-performance servers (Thu 1/26)

Discussion leader: Dave O'Hallaron
  • 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 (pdf)
  • *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 (pdf)
  • Tim Brecht , David Pariag, and Louay Gammo, accept()able Strategies for Improving Web Server Performance, Proceedings of the USENIX 2004 Annual Technical Conference: General Track, June, 2004. (pdf)

Class 5: Measuring server capacity (Tue 1/31)

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 appeard in Usenix Symposium on Internet Technologies and Systems, Monterrey, CA, Dec, 1997. Winner of Best Paper and Best Student Paper Awards.) ps.gz
  • 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, 59-67.) ( pdf, download )

Class 6: Improving server performance (Thu 2/2)

Discussion Leader: Dave O'Hallaron
  • *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 (pdf)

Class 7: Clustering - LARD (Tue 2/7)

Discussion leaders: Gesly George
  • *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 (pdf)
  • Valeria Cardellini, Emiliano Casalicchio, Michele Colajanni, Philip S. Yu The state of the art in locally distributed Web-server systems, Computing Surveys, 34(2), June 2002. (pdf)

Class 8: Clustering - SCARD (Thu 2/9)

Discussion leaders: Keisuke Ito
  • *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, San Diego, CA, June 2000. Winner of Best Paper Award (pdf)
  • Mohit Aron, Peter Druschel, and Willy Zwaenepoel, Efficient Support for P-HTTP in Cluster-Based Web Servers Proceedings of the USENIX Annual Technical Conference Monterey, California, USA, June 6-11, 1999 (pdf)

Class 9: Monitoring - Sting (Tue 2/14)

Discussion leader: Ben Gilbert
  • 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. ( pdf )

Class 10: Monitoring - TaintCheck (Thu 2/16)

Discussion leader: Ahbinav Mishra
  • *James Newsome and Dawn 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 (NDSS), February, 2005. (pdf)

Class 11: Availability - Replication I (Tue 2/21)

Discussion leader: Theta Maxino
  • Note: Please write a single critique covering both papers.
  • *F. B. Schneider. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys, 22(4), 1990. (pdf)
  • *R. Guerraoui and A. Schiper. Software-Based Replication for Fault Tolerance. IEEE Computer - Special Issue on Fault Tolerance, 30:68-74, April 1997. (pdf)
  • Yasushi Saito and Marc Shapiro, Optimistic replication, ACM Computing Surveys, 37(1), March 2005. (pdf)
  • Xavier Defago, Andre Schiper, and Peter Urban, Total order broadcast and multicast algorithms: Taxonomy and survey ACM Computing Surveys, 36(4), Dec 2004. (pdf)
  • Swaminathan Sivasubramanian, Michal Szymaniak, Guillaume Pierre, Maarten van Stee, Replication for web hosting systems, ACM Computing Surveys, 36(3), Sep 2003. (pdf)

Class 12: Availability - Replication II (Thu 2/23)

Discussion leader: Clive Leung
  • *M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, G. Alonso. Understanding Replication in Databases and Distributed Systems. 20th IEEE International Conference on Distributed Computing Systems (ICDCS'00). Taipei, Taiwan. April 2000. (pdf)

Class 13: Availability - Byzantine Fault Tolerance I (Tue 2/28)

Discussion leader: Mike Merideth
  • *M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. Third Symposium on Operating Systems Design and Implementation (OSDI 1999). New Orleans, Louisiana. Feb. 1999. (pdf)

Class 14: Availability - Byzantine Fault Tolerance II (Thu 3/2)

Discussion leader: Mike Abd-El-Malek
  • *M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, J. J. Wylie. Fault-Scalable Byzantine Fault-Tolerant Services. 20th ACM Symposium on Operating Systems Principles (SOSP 2005). Brighton, United Kingdom. October 2005. (pdf)
  • Garth R. Goodson, Jay J. Wylie, Gregory R. Ganger, Michael K. Reiter. Efficient Byzantine-tolerant erasure-coded storage. International Conference on Dependable Systems & Networks, June, 2004 (pdf)
  • Mike Mesnier, Greg Ganger, and Erik Riedel, Object based storage, IEEE Communications Magazine, Aug 2003. (pdf)

Class 15: Availability - BFT Apps: Thema (Tue 3/7)

Discussion leader: Mike Merideth
  • *M. G. Merideth, A. Iyengar, T. Mikalsen, S. Tai, I. Rouvellou, P. Narasimhan. Thema: Byzantine-Fault-Tolerant Middleware for Web-Service Applications. The 24th IEEE Symposium on Reliable Distributed Systems (SRDS 2005). Orlando, FL. October 2005. (pdf)

Class 16: Availability - BFT Apps: Bar-B (Tue 3/9)

Discussion leader: Sean O'Loughlin
  • *Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement Mike Dahlin, Jean-Philippe Martin, Carl Porth, BAR Fault Tolerance for Cooperative Services, 20th ACM Symposium on Operating Systems Principles (SOSP 2005). Brighton, United Kingdom. October 2005. (pdf)

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

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

Class 19: Search - Google (Tue 3/21)

Discussion leader: Himanshu Khurana
  • *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 20: Search - Google file system (Thu 3/23)

Discussion leaders: Rahul Iyer
  • *Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, The Google File System, 19th ACM Symposium on Operating Systems Principles, Lake George, NY, October, 2003, Winner of Best Paper Award. (pdf)

Class 21: Content distribution - BitTorrent I (Tue 3/28)

Discussion leader: Dave O'Hallaron
  • Note: Please write a single critique that covers both papers.
  • *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), Antibes Juan-les-Pins, France, April, 2004. ( pdf, RedHat9 tracker log and instrumented client code )
  • Clive Thompson, The BitTorrent Effect, Wired, Jan, 2005. (html)
  • Stephanos Androutsellis-Theotokis and Diomidis Spinellis A survey of peer-to-peer content distribution technologies, Computing Surveys, 36(4), Dec 2004. (pdf)

Class 22: Content distribution - BitTorrent II (Thu 3/30)

Discussion leader: Joseph Mou
  • *Ashwin R. Bharambe, Cormac Herley Venkata, and N. Padmanabhan, Analyzing and Improving a BitTorrent Network's Performance Mechanisms, Infocom2006, Barcelona, Spain, April, 2006. (pdf)
  • D. Qiu and R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks SIGCOMM 2004 (pdf)
  • L. Guo et al., Measurements, analysis, and modeling of BitTorrent-like systems, IMC 2005 (html)
  • Daniel Stutzbach, Daniel Zappala, Reza Rejaie The Scalability of Swarming Peer-to-Peer Content Delivery Proceedings of Networking 2005, Waterloo Ontario Canada, May 2005, (pdf)
  • Gang Wu and Tzi-cker Chiueh, Peer to Peer File Download and Streaming, TR-186 (RPE report), Stony Brook University, June 2005. (pdf)

Class 23: Content Distribution - ESM (Tue 4/4)

Discussion leader: Sachin Kulkarni
  • *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)

Class 24: Content Distribution - Gia (Thu 4/6)

Discussion leaders: Paul Cheong
  • *Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, Nick Lanham, Scott Shenker, Making Gnutella-like P2P Systems Scalable, Proc. ACM SIGCOMM, San Diego, CA, August 2003. (pdf)

Class 25: Virtual machines (Tue 4/11)

Discussion leader: Chutika Udomsinn
  • *Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, Andrew Warfiel, Xen and the Art of Virtualization, Proceedings of the 19th ACM Symposium on Operating Systems Principles, Lake George, NY, Oct, 2003. (pdf)

Class 26: VM Migration (Thu 4/13)

Discussion leader: Mike Merideth
  • *Christopher Clark, Keir Fraser, Steven Hand, Jacob Gorm Hanseny, Eric July, Christian Limpach, Ian Pratt, Andrew Warfield, "Live Migration of Virtual Machines", NSDI '05, (html)
  • Constantine P. Sapuntzakis, Ramesh Chandra, Ben Pfaff, Jim Chow, Monica S. Lam, and Mendel Rosenblum, Optimizing the Migration of Virtual Computers, 5th Symposium in Operating System Design and Implementation (OSDI 02), Boston, MA, Dec, 2002. (html)

Class 27: ISR (Tue 4/18)

Discussion leader: Dave O'Hallaron
  • *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)
  • Michael A. Kozuch, Casey J. Helfrich, David O'Hallaron, and Mahadev Satyanarayanan, Enterprise Client Management with Internet Suspend/Resume, Intel Technology Journal, vol 8, num 4, November 17, 2004. (pdf)

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

Class 29: No class - GP prep (Tue 4/25)

Class 30: No class - GP prep (Thu 4/27)

Class 31: No class - GP prep (Tue 5/2)

Class 32: GP poster session (Thu 5/4, Location HH 1112)

Dave O'Hallaron
Last modified: Tue Apr 18 12:33:30 EDT 2006