Evaluating unstructured peer-to-peer lookup overlays

ABSTRACT

Unstructured peer-to-peer lookup systems incur small constant overhead per single join or leave operation, and can easily support keyword searches. Hence, they are suitable for dynamic failure-prone environments. In this paper, we define metrics for evaluating unstructured overlays for peer-to-peer lookup systems. These metrics capture the search dependability and efficiency, and the granularity at which one can control the tradeoff between the two, as well as fairness. According to these metrics, we evaluate different graphs and overlays, including a Gnutella graph, a power law random graph, normal random graphs, a 3-regular random graph, and a 3-Araneola overlay. Our study shows that, according to our metrics, a 3-Araneola overlay achieves the best results, and hence it is an excellent solution for flooding-based peer-to-peer lookup system.

REFERENCES

• 1: E. Adar and B. A. Huberman. Free riding on gnutella. First Monday, Sept. 2000.
• 2: B. Bollobas. Random graphs.
• 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: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 5: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: C. Law and K. Siu. Distributed construction of random expander networks. In IEEE Infocom, April 2003.
• 7: 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]
• 8: Roie Melamed , Idit Keidar, Araneola: A Scalable Reliable Multicast System for Dynamic Environments, Proceedings of the Network Computing and Applications, Third IEEE International Symposium on (NCA'04), p.5-14, August 30-September 01, 2004
• 9: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369 ]
• 10: N. Wormald. Models of random regular graphs. Surveys in Combinatorics, 276:239--298, 1999.

INDEX TERMS

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

General Terms:
Measurement

Keywords:
dependability, efficiency, evaluation, graphs, lookup systems, metrics, unstructured peer-to-peer overlays