Reading List for CS 347

Reading List for CS 347: Large-Scale Networked Systems - Spring 2002

Discussion 1: Internet Architecture and Design Principles

[SRC84] J. Saltzer, D. Reed, and D. Clark, End-to-end Arguments in System Design. ACM Transactions on Computer Systems, Vol. 2, No. 4, pp. 195-206, 1984.
[BC01] D. Clark and M. Blumenthal, Rethinking the design of the Internet: The end to end arguments vs. the brave new world, Workshop on Policy Implications of End-to-End. December 1, 2001.

History:

[CK74] V. Cerf and R. Kahn, A Protocol for Packet Network Interconnection IEEE Transactions on Communications, COM-22, pp. 637-641 , 1974.
[Cla88] D. Clark, Design Philosophy of the DARPA Internet Protocols, In Proc. of ACM SIGCOMM '88.

Discussion 2: Flat Pricing vs. Prioritized Traffic

[BS98] L. Breslau and S. Shenker, Best-Effort versus Reservations: A Simple Comparative Analysis, SIGCOMM98
[O00] Andrew Odlyzko, Should flat-rate Internet pricing continue? Computer Networks, 2000

For more depth:

The current state and likely evolution of the Internet, A. M. Odlyzko. Proc. Globecom'99
and more by Odlyzko...
An Architecture for Differentiated ServicesRFC 2475

Discussion 3: Internet Measurements

[BBBC01] Paul Barford, Azer Bestavros, John Byers, and Mark Crovella, On the Marginal Utility of Network Topology Measurements. (PDF). ACM SIGCOMM Internet Measurement Workshop 2001.
[ZDPS01] Y. Zhang, N. Duffield, V. Paxson, S. Shenker, On the Constancy of Internet Path Properties, ACM SIGCOMM Internet Measurement Workshop, November 2001.

Discussion 4: Availability in Wide-Area

[LAJ99] C. Labovitz, A. Ahuja, F. Jahanian, Experimental Study of Internet Stability and Wide-Area Backbone Failures . FTCS99.
[CDGN01] B. Chandra, M. Dahlin, L. Gao, A. Nayate, End-to-end WAN Service Availability. USITS 2001.

Discussion 5: Structure of Real Networks

[FFF99] Michalis Faloutsos, Petros Faloutsos, Christos Faloutsos, On Power-Law Relationships of the Internet Topology. (PDF) ACM SIGCOMM'99.
[BKMR00] Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener. 2000 Graph structure in the web Comput. Netw. 33 309

More details:

Réka Albert and Albert-László Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics 74, 47 (2002).
Albert-László Barabási, Réka Albert, Emergence of scaling in random networks, Science 286 509-512 (1999)
If you want to participate in a small-world experiment (a remake of Milgram's experiment from the '60s), go here.

Discussion 6: Exploiting the Structure of Real Networks

[ALPH01] Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani and Bernardo A. Huberman, Search in power-law networks, Phys. Rev. E, 64 46135 (2001)
[K99] J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. Also appears as Cornell Computer Science Technical Report 99-1776 (October 1999). (Much) Shorter version: J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.
[W98] Toby Walsh, Search in a Small World (1998)
[A99] Lada Adamic, The Small World Wide Web, in Proceedings of ECDL'99, LNCS 1696, Springer, pp. 443-452.

Discussion 7: Caching in Internet Services

[BJSM01] H. Balakrishnan, J. Jung, E. Sit, and R. Morris, DNS Performance and the Effectiveness of Caching. (abstract , PDF) . In the Proceedings of the ACM SIGCOMM Internet Measurement Workshop '01 , San Francisco, California, November 2001.
[KSBB99] David R. Karger, Alex Sherman, Andy Berkheimer, Bill Bogstad, Rizwan Dhanidina, Ken Iwamoto, Brian Kim, Luke Matkins, Yoav Yerushalmi. " Web Caching with Consistent Hashing". WWW8 / Computer Networks 31(11-16): 1203-1213 (1999)

More on web caching:

[BCFPS99] Lee Breslau, Pei Cao, Li Fan, Graham Phillips and Scott Shenker, Web Caching and Zipf-like Distributions: Evidence and Implications. INFOCOM'99.

Discussion 8: Peer-to-Peer Solutions (1)

Proc. ACM SIGCOMM Conf., San Diego, CA, September 2001.
[SGG02] Stefan Saroiu, P. Krishna Gummadi, Steven D. Gribble: A Measurement Study of Peer-to-Peer File Sharing Systems. Proceedings of Multimedia Computing and Networking (MMCN) 2002, San Jose, CA, USA, January 2002.
[SMKK01] Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, Hari Balakrishnan, Chord: A Peer-to-Peer Lookup Service for Internet Applications.

More background on:

Gnutella:

Gnutella Protocol

Peer-to-Peer Architecture Case Study: Gnutella Network . Matei Ripeanu. University of Chicago Technical Report TR-2001-26 , 24 July, 2001

Distributed Hash Tables:

Anthony Rowstron and Peter Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. ; Rawstron, Druschel. PAST. 18th SOSP

Ben Zhao, John Kubiatowicz, Anthony Joseph. Tapestry: An Infrastructure for Wide-area Fault-tolerant Location and Routing.

[RFHK01] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, A Scalable Content-Addressable Network. SIGCOMM 2001.

Discussion 9: Peer-to-Peer Solutions (2)

[RFHK01] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, A Scalable Content-Addressable Network. SIGCOMM 2001.
[RHKS02] Sylvia Ratnasamy, Mark Handley, Richard Karp, Scott Shenker, Topologically-Aware Overlay Construction and Server Selection. Infocom 2002.

More:

Electronic Proceedings for the 1st International Workshop on Peer-to-Peer Systems (IPTPS '02)

Discussion 10: Overlay Networks

[ABKM01] David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris, Resilient Overlay Networks. Proc. SOSP 2001 , Banff, Canada, October 2001.
[CDHR] M. Castro, P. Druschel, Y. C. Hu, A. Rowstron, "Exploiting network proximity in peer-to-peer overlay networks", submitted for publication. [ pdf.zip | ps.zip | pdf | ps ]

Discussion 11: Sensornets

[EGHK99] Deborah Estrin, Ramesh Govindan, John Heidemann and Satish Kumar Next Century Challenges: Scalable Coordination in Sensor Networks , In Proceedings of the Fifth Annual International Conference on Mobile Computing and Networks (MobiCOM '99), August 1999, Seattle, Washington.
[HSWH00] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, Kristofer Pister, System Architecture Directions for Networked Sensors, ASPLOS 2000.

Discussion 12: Presentations of:

1. "Building Low-Diameter P2P Networks" by Pandurangan, Raghavan and Upfal. http://www.cs.brown.edu/people/eli/papers/focs01.pdf (Rahul)
2. "Spatial Gossip and Resource Location Problems" by Kemper, Kleinberg, and Demers, STOC 2001:
http://www.cs.cornell.edu/home/kleinber/stoc01-gossip.ps (Janos)
3. "Probabilistic Location and Routing" by Rhea and Kubiatowicz: http://www.ieee-infocom.org/2002/papers/336.pdf (Matei)

Discussion 13: Wireless Networks:

[DPMM01] Samir R. Das, Charles E. Perkins, Elizabeth M. Royer and Mahesh K. Marina. "Performance Comparison of Two On-demand Routing Protocols for Ad hoc Networks." IEEE Personal Communications Magazine special issue on Ad hoc Networking, February 2001, p. 16-28.
[GKWC02] Deepak Ganesan, Bhaskar Krishnamachari, Alec Woo, David Culler, Deborah Estrin and Stephen Wicker, An Empirical Study of Epidemic Algorithms in Large Scale Multihop Wireless Networks, Submitted for review. UCLA Computer Science Technical Report UCLA/CSD-TR 02-0013.

Background:

Elizabeth M. Royer and Charles E. Perkins. "An Implementation Study of the AODV Routing Protocol." Proceedings of the IEEE Wireless Communications and Networking Conference, Chicago, IL, September 2000.
David B. Johnson, David A. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing (ed. T. Imielinski and H. Korth), Kluwer Academic Publishers, Dordrecht, The Netherlands, (1996). http://citeseer.nj.nec.com/johnson96dynamic.html

Discussion 14: Fault Tolerance:

[G99] Felix C. Gärtner, Fundamentals of Fault-Tolerant Distributed Computing in Asynchronous Environments (1999), ACM Computing Surveys,
[C01] Christian Cachin, Distributing Trust on the Internet (2001), In Proceedings of the International Conference on Dependable Systems and Networks (DSN2001) , Goteborg, Sweden, June 2001. IEEE."

Baground

Flaviu Cristian, Understanding Fault-Tolerant Distributed Systems (1993), Communications of the ACM

Discussion 15: Security:

[SA99] Frank Stajano and Ross Anderson, The Cocaine Auction Protocol: On the Power of Anonymous Broadcast, (1999), Information Hiding, p.434-447
[SM02] Emil Sit and Robert Morris, Security Considerations for P2P Distributed Hash Tables , IPTPS 2002.

Extra Material

Modeling the Internet Topology

[YJBxx] Modeling the Internet's Large-Scale Topology, by Soon-Hyung Yook , Hawoong Jeong , and Albert-Laszlo Barabasi
[TGSW01] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, W. Willinger, Network Topologies, Power Laws, and Hierarchy, Technical Report 01-746, Computer Science Department, University of Southern California.

More on Content Distribution Networks:

[C00] Jeff Camp, "The Internet Evolution-Content Networking", Morgan Stanley Report, October 27, 2000 (Also in HTML).
[JCDK00] Kirk L. Johnson, John F. Carr, Mark S. Day and M. Frans Kaashoek. "The Measured Performance of Content Distribution Networks", Proceedings of International Web Caching and Content Delivery Workshop, June 2000.
[FCAB98] L. Fan, P. Cao, J. Almeida, A. Broder, Summary Cache: A Scalable Wide-Area Cache Sharing Protocol, In Proc. SIGCOMM '98, pp. 254-265, Vancouver, Canada, September 1998.
[Cla00] I. Clarke, O. Sandberg, B. Wiley, and T. Hong, Freenet: A Distributed Anonymous Information Storage and Retrieval System, Proc. ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, July 2000.

More P2P Systems

An Adaptive Peer-to-Peer Network for Distributed Caching of OLAP Results, Panos Kalnis, Wee Siong Ng, Beng Chin Ooi, Dimitris Papadias, Kian Lee Tan, ACM Sigmod 2002.