A scalable content-addressable network

Authors:
Sylvia Ratnasamy

Dept. of Electrical Eng. & Comp. Sci., University of California at Berkeley, Berkeley, CA and ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA

Dept. of Electrical Eng. & Comp. Sci., University of California at Berkeley, Berkeley, CA and ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA
View Profile

,
Paul Francis

ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA

ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA
View Profile

,
Mark Handley

ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA

ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA
View Profile

,
Richard Karp

Dept. of Electrical Eng. & Comp. Sci., University of California at Berkeley, Berkeley, CA and ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA

Dept. of Electrical Eng. & Comp. Sci., University of California at Berkeley, Berkeley, CA and ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA
View Profile

,
Scott Shenker

ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA

ACIRI, AT&T Center for Internet Research at ICSI, Berkeley, CA
View Profile

SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communicationsAugust 2001Pages 161–172https://doi.org/10.1145/383059.383072

Published:27 August 2001Publication History

SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 161–172

ABSTRACT

Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation.

References

1.W. Bolosky, J. Douceur, D. Ely, and M. Theimer. Feasibility of a Serverless Distributed File System Deployed on an existing set of Desktop PCs. In Proceedings of SIGMETRICS 2000, Santa Clara, CA, June 2000.]] Google ScholarDigital Library
2.I. Clarke, O. Sandberg, B. Wiley, and T. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. ICSI Workshop on Design Issues in Anonymity and Unobservability, July 2000.]] Google ScholarDigital Library
3.S. Czerwinski, B. Zhao, T. Hodes, A. Joseph, and R. H. Katz. An Architecture for a Secure Service Discovery Service. In Proceedings of Fifth ACM Conf. on Mobile Computing and Networking (MOBICOM), Seattle, WA, 1999. ACM.]] Google ScholarDigital Library
4.P. Francis. Yoid: Extending the Internet Multicast Architecture. Unpublished paper, available at http://www.aciri.org/yoid/docs/index.html, Apr. 2000.]]Google Scholar
5.FreeNet. http://freenet.sourceforge.net.]]Google Scholar
6.Gnutella. http://gnutella.wego.com.]]Google Scholar
7.J. Guterman. Gnutella to the Rescue ? Not so Fast, Napster fiends. Link to article at http://gnutella.wego.com, Sept. 2000.]]Google Scholar
8.Infrasearch. http://www.infrasearch.com.]]Google Scholar
9.B. Karp and H. Kung. Greedy Perimeter Stateless Routing. In Proceedings of ACM Conf. on Mobile Computing and Networking (MOBICOM), Boston, MA, 2000. ACM.]] Google ScholarDigital Library
10.J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. Oceanstore: An Architecture for Global-scale Persistent Storage. In Proceedings of ASPLOS 2000, Cambridge, Massachusetts, Nov. 2000.]] Google ScholarDigital Library
11.S. Kumar, C. Alaettinoglu, and D. Estrin. SCOUT: Scalable Object Tracking through Unattended Techniques. In Proceedings of the Eight IEEE International Conference on Network Protocols, Osaka, Japan, Nov. 2000.]] Google ScholarDigital Library
12.J. Li, J. Jannotti, D. D. Couto, D. Karger, and R. Morris. A Scalable Location Service for Geographic Ad-hoc Routing. In Proceedings of ACM Conf. on Mobile Computing and Networking (MOBICOM), Boston, MA, 2000. ACM.]] Google ScholarDigital Library
13.A. D. R. Marc Waldman and L. F. Cranor. Publius: A Robust, Tamper-evident, Censorship-resistant, Web Publishing System. In Proceedings of the 9th USENIX Security Symposium, pages 59-72, August 2000.]] Google ScholarDigital Library
14.Napster. http://www.napster.com.]]Google Scholar
15.C. Plaxton, R. Rajaram, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1997.]] Google ScholarDigital Library
16.J. B. Postel. Internet Protocol Specification.ARPANET Working Group Requests for Comment, DDN Network Information Center, SRI International, Menlo Park, CA, Sept. 1981. RFC-791.]]Google Scholar
17.S. Ratnasamy, P. Francis, M. Handley, R. Karp, J. Padhye, and S. Shenker. Grass-roots Content Distribution: RAID meets the Web. Jan. 2001. unpublished document available at http://www.aciri.org/sylvia/.]]Google Scholar
18.S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A Scalable Content-Addressable Network. In ICSI Technical Report, Jan. 2001.]]Google ScholarDigital Library
19.Y. Rekhter and T. Li. A Border Gateway Protocol 4 BGP-4. ARPANET Working Group Requests for Comment, DDN Network Information Center, Mar. 1995. RFC-1771.]] Google ScholarDigital Library
20.I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings ACM Sigcomm 2001, San Diego, CA, Aug. 2001.]] Google ScholarDigital Library
21.M. Welsh, N. Borishov, J. Hill, R. von Behren, and A. Woo. Querying large collections of music for similarity. Technical report, University of California, Berkeley, CA, Nov. 1999.]]Google Scholar
22.E. Zegura, K. Calvert, and S. Bhattacharjee. How to Model an Internetwork. In Proceedings IEEE Infocom '96, San Francisco, CA, May 1996.]]Google ScholarCross Ref
23.Zeropaid.com. File sharing portal at http://www.zeropaid.com.]]Google Scholar

Index Terms

A scalable content-addressable network
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks
  1. Network architectures
  2. Network protocols

Recommendations

A scalable content-addressable network
Proceedings of the 2001 SIGCOMM conference

Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-...
Read More
A scalable content-addressable network
Read More
Dynamic load balancing in RCAN content addressable network
ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication

RCAN [1] is a novel multi-ring content addressable peer-to-peer system. RCAN was proposed in the aim of improving the routing performance of CAN [4] overlays while minimizing the maintenance overhead during nodes churn in large networks. The key idea of ...
Read More

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Published in
SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications
August 2001
298 pages
ISBN:1581134118
DOI:10.1145/383059
Chairmen:
Rene Cruz
Unvi. of California, San Diego
,
George Varghese
Unvi. of California, San Diego
ACM SIGCOMM Computer Communication Review Volume 31, Issue 4
Proceedings of the 2001 SIGCOMM conference
October 2001
275 pages
ISSN:0146-4833
DOI:10.1145/964723
Issue’s Table of Contents
Copyright © 2001 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 27 August 2001
Permissions
Request permissions about this article.
Request Permissions

Check for updates
Qualifiers
- Article
Conference

Acceptance Rates
SIGCOMM '01 Paper Acceptance Rate23of252submissions,9%Overall Acceptance Rate554of3,547submissions,16%
More
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 4,859
  Total Citations
  View Citations
- 11,423
  Total Downloads
- Downloads (Last 12 months)415
- Downloads (Last 6 weeks)53
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

A scalable content-addressable network

SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications

ABSTRACT

References

Cited By

Index Terms

Recommendations

A scalable content-addressable network

A scalable content-addressable network

Dynamic load balancing in RCAN content addressable network