Ad Hoc, self-supervising peer-to-peer search networks

ABSTRACT

Peer-to-peer search networks are a popular and widely deployed means of searching massively distributed digital information repositories. Unfortunately, as such networks grow, peers may become overloaded processing messages from other peers. This article examines how to reduce the load on nodes in P2P networks by allowing them to self-organize into a relatively efficient network, and then self-tune to make the network even more efficient. Two local operations used by a peer are introduced: connect(), in which the peer forms an ad hoc search or index link to another peer, and break(), in which the peer breaks a link that is producing too much load. By replacing fixed rules with dynamic local decision-making, such “self-supervising” networks can better adjust to network conditions. Different ways to implement connect() and break() are described, and the network structures that form under different configurations are examined. Simulation results indicate that the ad hoc networks formed using the described techniques are more efficient than popular supernode topologies for several important scenarios. Results for the fault tolerance and search latency of such ad hoc networks are also presented.

REFERENCES

• 1: Özalp Babaoglu , Hein Meling , Alberto Montresor, Anthill: A Framework for the Development of Agent-Based Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.15, July 02-05, 2002
• 2: Mayank Bawa , Roberto J. Bayardo, Jr. , Sridhar Rajagopalan , Eugene J. Shekita, Make it fresh, make it quick: searching a network of personal webservers, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775234]
• 3: Bernstein, P., Giunchiglia, F., Kementsietsidis, A., Mylopoulos, J., Serafini, L., and Zaihrayeu, I. 2002. Data management for peer-to-peer computing: A vision. In Proceedings of the WebDB Workshop.
• 4: Bhattacharjee, B. 2003. Efficient peer-to-peer searches using result-caching. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS).
• 5: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: Brian F. Cooper , Hector Garcia-Molina, Peer-to-peer data trading to preserve information, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.133-170, April 2002 [doi>10.1145/506309.506310]
• 7: Cooper, B. F. and Garcia-Molina, H. 2003a. SIL: Modeling and measuring scalable peer-to-peer search networks. In Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing.
• 8: Cooper, B. F. and Garcia-Molina, H. 2003b. SIL: Modeling and measuring scalable peer-to-peer search networks. Technical report, available at http://www.cc.gatech.edu/cooperb/pubs/searchnetsext.pdf.
• 9: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 10: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 11: Roger Dingledine , Michael J. Freedman , David Molnar, The free haven project: distributed anonymous storage service, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.67-95, January 2001, Berkeley, California, United States
• 12: Gnutella. 2003. Gnutella. Web site: http://gnutella.wego.com.
• 13: Gribble, S., Halevy, A., Ives, Z., Rodrig, M., and Suciu, D. 2001. What can databases do for peer-to-peer. In Proceedings of the WebDB Workshop.
• 14: Alon Y. Halevy , Zachary G. Ives , Peter Mork , Igor Tatarinov, Piazza: data management infrastructure for semantic web applications, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775231]
• 15: Huebsch, R., Hellerstein, J. M., Lanham, N., Loo, B. T., and Shenker, S. 2003. Querying the Internet with PIER. In Proceedings of the International Conference on Very Large Databases (VLDB).
• 16: Vana Kalogeraki , Dimitrios Gunopulos , D. Zeinalipour-Yazti, A local search mechanism for peer-to-peer networks, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584842]
• 17: Kazaa. 2003. Kazaa. Web site: http://www.kazaa.com.
• 18: Anastasios Kementsietsidis , Marcelo Arenas , Renée J. Miller, Mapping data in peer-to-peer systems: semantics and algorithmic issues, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872798]
• 19: Khambatti, M., Ryu, K., and Dasgupta, P. 2003. Structuring peer-to-peer networks using interest-based communities. In Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing.
• 20: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 21: Loeser, A., Naumann, F., Siberski, W., Nejdl, W., and Thaden, U. 2003. Semantic overlay clusters within peer-to-peer networks. In Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing.
• 22: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 23: Qin Lv , Sylvia Ratnasamy , Scott Shenker, Can Heterogeneity Make Gnutella Scalable?, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.94-103, March 07-08, 2002
• 24: Wolfgang Nejdl , Martin Wolpers , Wolf Siberski , Christoph Schmitz , Mario Schlosser , Ingo Brunkhorst , Alexander Löser, Super-peer-based routing and clustering strategies for RDF-based peer-to-peer networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775229]
• 25: G. Pandurangan, Building Low-Diameter P2P Networks, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.492, October 14-17, 2001
• 26: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 27: Matei Ripeanu , Ian T. Foster, Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.85-93, March 07-08, 2002
• 28: Saroiu, S., Gummadi, K., and Gribble, S. 2002. A measurement study of peer-to-peer file sharing systems. In Proceedings of the Multimedia Conferencing and Networking.
• 29: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 30: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 31: Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002
• 32: Yang, B. and Garcia-Molina, H. 2003. Designing a super-peer network. In Proceedings of the International Conference on Data Engineering (ICDE).
• 33: Beverly Yang , Patrick Vinograd , Hector Garcia-Molina, Evaluating GUESS and Non-Forwarding Peer-to-Peer Search, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.209-218, March 24-26, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases; Distributed applications

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness); Information networks

General Terms:
Design, Performance, Reliability

Keywords:
Peer-to-peer systems, information search and discovery