CS590A: Topics in Overlay Networks

Fall 2003.
Ananth Grama.

As peer-to-peer networks become popular, the algorithmic basis for these overlay networks has also matured. From the inital days of Napster, these algorithms have improved significantly with respect to their scalability, robustness, and performance. At the same time, significant higher-level functionality has been built atop these overlays. This functionality includes storage systems, streaming media services, services networks, and secure and anonymous data storage and transfer. In this class, we will overview the algorithmic basis for these developments. Specific topics include, but are not limited to:

Networks, Routing, and Embeddings
Overlay Networks for the Internet --
- Constraints, Support, and Features
Software Infrastructure for Experiments
- PlanetLab
- P2PSim, etc.
Overlay Network Case Studies --
- Gnutella, Freenet,
- Chord, Tapestry, Pastry, CAN, etc.
Performance and Availability
- Locality
- Caching
- Fault Tolerance
Higher Level Functionality
- Storage Systems -- CFS, OceanStore, PAST, etc.
- Services Networks -- JXTA, Ninja, etc.
- Media Streaming Support
Security Aspects of Overlay Networks
Overlay Networks for Mobile Ad-Hoc Devices

The course will be based on research papers -- covering approximately 2-3 papers a week. Presentations will include those by the students as well as the instructor. Students will be expected to undertake a semester-long project in an area related to overlay networks. These may either be individual, or group projects. The projects are expected to culminate in a presentation and a brief report.

Reading List

Location and Placement in P2P Networks

Napster Guts.
The Gnutella Protocol
Gnutella 2
I. Clarke, O. Sandberg, B. Wiley and T. Hong, Freenet: A distributed anonymous information storage and retrieval system, in Designing Privacy Enhancing Technologies: International Workshop on Design Issues in Anonymity and Unobservability, LNCS 2009, ed. by H. Federrath. Springer: New York (2001).
K. Truelove, A. Chasin, Morpheus out of the Underworld
L. Gong, Sun's Project JXTA: A technology Overview
I. Stoica, R. Morris, D. Karger, M. Kaashoek, H. Balakrishnan, Chord: A scalable peer-to-peer lookup service for Internet applications, Proceedings of ACM Sigcomm, August 2001.
Ion Stoica et al, "Internet Indirection Infrastructure," Proceedings of SIGCOMM 2002.
Ratnasamy, Francis, Handley, Karp, Shneker, "A Scalable COntent-Addressable Network," Proceedings of ACM SIGCOMM, Augiste 2001.
B. Zhou, D. A. Joseph, J. Kubiatowicz, Tapestry: a fault tolerant wide area network infrastructure, SIGCOMM 2001.
M Harren et al, "Complex Queries in DHT-based Peer-to-Peer Networks," 2nd IPTPS Workshop.
The Coop Net Project

Media Streaming

Apostolopoulos, Tan and Wee, "Video Streaming: Concepts, Algorithms, and Systems," HP Technical Report, Sept. 2002
H. Deshpande, M. Bawa, H. Garcia-Molina, Streaming Live Media over a Peer-to-Peer Network.

Security, Anonymity, and Integrity

V. Scarlata, B.N. Levine, and C. Sheilds, Responder Anonymity and Anonymous Peer-to-Peer file sharing. ICNP 2001.
Biddle, England, Peinado, Willman, "The Darknet and the Future of Content Distribution," 2002 ACM Workshop on Digital Rights Management, 2002
Angelos Keromytis, Vishal Misra, and Dan Rubenstein. SOS: Secure Overlay Services Proceedings of ACM SIGCOMM '02, Pittsburgh, PA, August, 2002.

Quantitative Analysis

Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. "A Measurement Study of Peer-to-Peer File Sharing Systems," Proceedings of Multimedia Computing and Networking 2002 (MMCN'02), January 2002.
Jacky Chu, Kevin Labonte, and Brian Neil Levine, "Availability and Locality Measurements of Peer-to-Peer File Systems" Proc. ITCom: Scalability and Traffic Control in IP Networks II Conferences July 2002 Proceedings of SPIE Vol. #4868.
C. Kommareddy, N. Shankar and S. Bhattacharjee, Finding close friends on the Internet Proceedings of ICNP'01.
E. Adar, and B. Huberman, "Free Riding on Gnutella," First Monday, Vol. 5, No. 10, http://www.firstmonday.dk/issues/issue5_10/adar/
Lada A. Adamic, Amit R. Puniyani, Rajan M. Lukose, and Bernardo A. Huberman, Search in Power-Law Networks
A. Rowstron, A-M. Kermarrec, P. Druschel and M. Castro, "SCRIBE: The design of a large-scale vent notification infrastructure.

Wireless/ubicomp services

Wenrui Zhao, Mostafa Ammar, "Proactive Routing in Highly Partitioned Mobile Networks," Proceedings of the 2003 Conference on Future Trends of Distributed Computing\ Systems.
James Davis, Andy Fagg, and Brian Neil Levine, "Wearable Computers as Packet Transport Mechanisms in Highly Partitioned Ad-Hoc Networks", in Proc. International Symposium on Wearable Computers October 8, 2001.
A. Snoeren and H. Balakrishnan, An End-to-End Approach to Host Mobility , ACM Mobicom 2000.

Content distribution networks

A. Myers, P. Dinda and H. Zhang, Performance Characteristics of Mirror Servers on the Internet, Proceedings of IEEE INFOCOM'99.
P. Rodriguez, A. Kirpal, and E. W. Biersack, Parallel-Access for Mirror Sites in the Internet, Proceedings of IEEE INFOCOM'00.
E. Zegura, M. Ammar, Z. Fei and S. Bhattacharjee, Application-layer anycasting: a server selection architecture and use in a replicated web service, IEEE/ACM Transactions on Networking,
B. Krishnamurthy, C. Wills and Y. Zhang, On the use and performance of content distribution networks, Proceedings of ACM Sigcomm Internet Measurement Workshop, 2001.
Akamai.
S. Seshan, M. Stemm and R. Katz, SPAND Infocom'00
IDMaps, Infocom'99 paper
IDMaps, Transactions on Networking paper