Efficient lookup on unstructured topologies

ABSTRACT

We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT).We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.

REFERENCES

• 1: I. Abraham and D. Malkhi. Probabilistic quorums for dynamic systems. In International Symposium on Distributed Computing (DISC), pages 60--74, 2003.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 4: J. Chu, K. Labonte, and B. N. Levine. Availability and locality measurements of peer-to-peer file systems. In Proc. ITCom: Scalability and Traffic Control in IP Networks II Conferences, volume 4868, July 2002.
• 5: Ian Clarke , Scott G. Miller , Theodore W. Hong , Oskar Sandberg , Brandon Wiley, Protecting Free Expression Online with Freenet, IEEE Internet Computing, v.6 n.1, p.40-49, January 2002 [doi>10.1109/4236.978368]
• 6: P. Ganesan, Q. Sun, and H. Garcia-Molina. Yappers: A peer-to-peer lookup service over arbitrary topology. In 22nd Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), 2003.
• 7: C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In IEEE Infocom, 2004.
• 8: Gnutella http://www.gnutella.com.
• 9: S. Jiang, L. Guo, and X. Zhang. LightFlood: an efficient flooding scheme for file search in unstructured peer-to-peer systems. In International Conference on Parallel Processing, 2003.
• 10: 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]
• 11: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 12: Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384004]
• 13: Alessandro Panconesi , Aravind Srinivasan, Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds, SIAM Journal on Computing, v.26 n.2, p.350-368, April 1997 [doi>10.1137/S0097539793250767]
• 14: V. Ramasubramanian and E. G. Sirer. Beehive: Exploiting power law query distributions for O(1) lookup performance in peer to peer overlays. In Proceedings of NSDI, 2004.
• 15: 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
• 16: S. C. Rhea and J. Kubiatowicz. Probabilistic location and routing. In Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), Proceedings, volume 3, pages 1248--1257, New York, NY USA, June 23--27 2002. IEEE.
• 17: RipeanuGnutellaGraphs people.cs.uchicago.edu/~matei/GnutellaGraphs/
• 18: 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
• 19: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 20: Stefan Saroiu , Krishna P. Gummadi , Steven D. Gribble, Measuring and analyzing the characteristics of Napster and Gnutella hosts, Multimedia Systems, v.9 n.2, p.170-184, August 2003 [doi>10.1007/s00530-003-0088-1]
• 21: 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
• 22: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

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

General Terms:
Design, Performance, Theory

Keywords:
distributed algorithms, lookup protocols, peer-to-peer networks, random walks