Networked Systems Architecture

Overview

The objective of this course is to cover basic principles that underlie the design of modern networked systems with an emphasis on the basic ideas of the underlying architectural design and algorithmic elements. The course covers the foundations of TCP/IP networking, peer-to-peer networks, data centre systems, and some aspects of online services.

The course requires no specific prerequisites.

The work for the course will consist of studying material presented through lectures, a series of laboratory exercises complementing the lectures, and a seminar that consists of studying a research paper. The laboratory exercises will provide hands on experience with network administration tools and using state of the art computing cluster systems.

Course Outline

(1) TCP/IP Network Foundations

• Routing at the data link layer, internal IP routing, external IP routing
• All shortest paths using Bellman-Ford and Dijkstra
• Transport control protocol: TCP and UDP

(2) Peer-to-Peer Networks

• Structured and unstructured overlay networks, key look-up service, distributed hash table
• Decentralized search in unstructured networks
• File dissemination strategies

• Survey Papers
• H. Balakrishnan, M.F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Looking up data in P2P systems. Communications of the ACM 46:43-48, February 2003.
• E.-K. Lua, J. Crowcroft, M. Pias, R. Sharma and S. Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Communications Surveys and Tutorials, 7(2005).
• Unstructured Approaches
• I. Clarke, O. Sandberg, B. Wiley, T. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. International Workshop on Design Issues in Anonymity and Unobservability, 2000.
• A. Goel, H. Zhang, and R. Govindan. Using the Small-World Model to Improve Freenet Performance. IEEE Infocom, 2002.
• Structured Approaches
• C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. ACM SPAA 1997.
• S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker. A Scalable Content-Addressable Network. ACM SIGCOMM, 2001
• A. Rowstron, P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001).
• I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. ACM SIGCOMM, 2001.
• B. Y. Zhao, J. D. Kubiatowicz, A. D. Joseph, Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing. UC Berkeley Computer Science Division, Report No. UCB/CSD 01/1141, April 2001.
• P. Maymounkov and D. Mazieres, Kadmelia: A Peer-to-Peer Information System Based on the XOR Metric, IPTPS, 2001.
• S. Ratnasamy, S. Shenker and I. Stoica. Routing Algorithms for DHTs: Some Open Questions. IPTPS, 2002.
• D. Malkhi, M. Naor, D. Ratajczak. Viceroy: A Scalable and Dynamic Emulation of the Butterfly. ACM PODC, 2002.
• G. S. Manku, M. Bawa, P. Raghavan. Symphony: Distributed hashing in a small world. Proc. 4th USENIX Symposium on Internet Technologies and Systems, 2003.
• G. Manku, M. Naor, and U. Wieder. Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks. STOC, 2004.
• P2P data transfer
• L. Massoulie and M. Vojnovic. Coupon Replication Systems. ACM Sigmetrics 2005.
• C. Gkantsidis and P. Rodriguez. Network Coding for Large Scale Content Distribution. ACM Infocom 2005.

(3) Data Centres

• Computing as a utility, distributed computing clusters, interconnect topologies
• Parallel processing paradigms - Mapreduce, Dryad, Dryad/LINQ
• Scheduling of jobs in data centres
• Algorithms for processing of massive amounts of data, e.g. frequency counters, hash and range partitioning

• Background material
• M. Armburst, A. Fox, R. Griffith, A. D. Joseph, R. H. Katz, A. Konwinski, G. Lee, D. A. Patterson, A. Rabkin, I. Stoica, M. Zaharia, Above the Clouds: A Berkeley View of Cloud Computing, UCB Technical Report, 2009.
• M. Al-Fares, A. Loukissas and A. Vahdat, A Scalable, Commodity, Data Center Network Architecture, ACM Sigcomm, 2008.
• A. Greenberg, P. Lahiri, D. A. Matz, P. Patel and S. Sengupta, Towards a Next Generation Data Center Architecture: Scalability and Commoditization, PRESTO, 2008.
• C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang and S. Lu, DCell: A Scalable and Fault-Tolerant Network Structure for Data Centers, ACM Sigcomm 2008.
• C. E. Leiserson, Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing, IEEE Trans. on Computers, 1985.
• J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI 2004.
• M. Isard, M. Budiu, Y. Yu, A. Birrell and D. Fetterly, Dryad: Distributed Parallel Programs from Sequential Building Blocks, EuroSys 2007.
• 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, OSDI 2006.
• G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007.
• R. Chaiken, B. Jenkins, P.-A. Larson, B. Ramsey, D. Shakib, S. Weaver, and J. Zhou, SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets, VLDB 2008.
• Hadoop, Pig.
• D. Peng and F. Dabek, Large-scale Incremental Processing Using Distributed Transactions and Notifications, OSDI 2010.
• M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, A. Goldberg, Quincy: Fair Scheduling for Distributed Computing Clusters, SOSP 2009.
• M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, I. Stoica, Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling, Eurosys 2010.

(4) Online Services

• Ranking of web documents, eigenvector centrality
• Sponsored search auctions, generalized second price auction
• Standard auctions: first price, second price, truthfulness of second price auctions, revenue equivalence, optimal auction design

• Ranking of web documents
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Mining the link structure of the World Wide Web. IEEE Computer, August 1999.
• J. Kleinberg. Authoritative sources in a hyperlinked environment. SODA, 1998. Extended version in Journal of the ACM 46(1999).
• S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. WWW, 1998.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Mining the link structure of the World Wide Web. IEEE Computer, August 1999.
• A. Borodin, J. S. Rosenthal, G. O. Roberts, P. Tsaparas, Finding Authorities and Hubs From Link Structures on the World Wide Web. WWW, May 2001.
• A. Altman and M. Tennenholtz. Ranking Systems: The PageRank Axioms. ACM EC 2005.
• Online advertising
• V. Krishna, Auction Theory, Academic Press 2002.
• B. Edelman, M. Ostrovsky and M. Schwarz, Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords, NBER Working Paper No. 11765, 2005.
• H. R. Varian, Position auctions, Int'l Journal of Industrial Organization, Vol 25, 2007.

Course Schedule

Seminars

Grading

where L = grade of laboratory exercises (%), S = grade of the seminar (%), and F = grade of the final exam (written) (%)