No Access

HASH-BASED OVERLAY PARTITIONING IN UNSTRUCTURED PEER-TO-PEER SYSTEMS

Foundation for Research and Technology-Hellas, Institute of Computer Science, N. Plastira 100, Vassilika Vouton, GR-70013 Heraklion, Crete, Greece

Search for more papers by this author

PARASKEVI FRAGOPOULOU

Foundation for Research and Technology-Hellas, Institute of Computer Science, N. Plastira 100, Vassilika Vouton, GR-70013 Heraklion, Crete, Greece

With the Department of Applied Informatics and Multimedia, Technological Educational Institute of Crete, Greece.

Search for more papers by this author

EVANGELOS P. MARKATOS

Foundation for Research and Technology-Hellas, Institute of Computer Science, N. Plastira 100, Vassilika Vouton, GR-70013 Heraklion, Crete, Greece

Search for more papers by this author

MARIOS D. DIKAIAKOS

Department of Computer Science, University of Cyprus, 1678 Nicosia, Cyprus

Search for more papers by this author

, and

ALEXANDROS LABRINIDIS

Department of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260, USA

Search for more papers by this author

https://doi.org/10.1142/S0129626409000067Cited by:0 (Source: Crossref)

Abstract

Unstructured peer-to-peer (P2P) networks suffer from the increased volume of traffic produced by flooding. Methods such as random walks or dynamic querying managed to limit the traffic at the cost of reduced network coverage. In this paper, we propose a partitioning method of the unstructured overlay network into a relative small number of distinct subnetworks. The partitioning is driven by the categorization of keywords based on a uniform hash function. The method proposed in this paper is easy to implement and results in significant benefit for the blind flood method. Each search is restricted to a certain partition of the initial overlay network and as a result it is much more targeted. Last but not least, the search accuracy is not sacrificed to the least since all related content is searched. The benefit of the proposed method is demonstrated with extensive simulation results, which show that the overhead for the implementation and maintenance of this system is minimal compared to the resulted benefit in traffic reduction.

This research work was carried out under the FP6 NoE CoreGRID funded by the EC (IST-2002-004265).

Keywords:

References

Gnutella 0.6 protocol specification. http://rfc-gnutella.sourceforge.net/developer/stable/index.html . Google Scholar
Limewire Inc. http://www.limewire.com . Google Scholar
B. H. Bloom, Communications of the ACM 13(7), 422 (1970), DOI: 10.1145/362686.362692. Crossref, Web of Science, Google Scholar
Y. Chawatheet al., Making gnutella-like P2P systems scalable, Proc. ACM SIGCOMM 2003 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communication (2003) pp. 407–418. Google Scholar
V. Cholvi , P. Felber and E. Biersack , Efficient search in unstructured peer-to-peer networks , Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures ( 2004 ) . Google Scholar
A. Crespo and H. Garcia-Molina , Routing indices for peer-to-peer systems , Int. Conf. on Distributed Computing Systems (ICDCS'02) ( 2002 ) . Google Scholar
A. Crespo and H. Garcia Molina , Semantic overlay networks for P2P Systems , Int. Conf. on Agents and Peer-to-Peer Computing (AP2PC 2004) ( 2004 ) . Google Scholar
A. Fisk. Gnutella Ultrapeer Query Routing, v. 0.1. Lime Wire Inc. 2003 . Google Scholar
C. Gkantsidis , M. Mihail and A. Saberi , Hybrid search schemes for unstructured peer-to-peer networks , IEEE INFOCOM 2005 ( 2005 ) . Google Scholar
Q. Lv et al. , Search and replication in unstructured peer-to-peer networks , Int. Conf. on Supercomputing (SC 2002) ( 2002 ) . Google Scholar
C. Papadakis et al. , A feedback-based approach to reduce duplicate messages in unstructured peer-to-peer networks , Proc. of the CoreGRID Integration Workshop ( 2005 ) . Google Scholar
A. Ratnasamyet al., A scalable content-addressable network, ACM SIGCOMM (2001) pp. 161–172. Google Scholar
R. Rejaie , S. Zhao and D. Stutzbach , Characterizing files in the modern Gnutella network: A measurement study , Proc. SPIE/ACM Multimedia Computing and Networking ( 2006 ) . Google Scholar
A. Rowstron and P. Druschel , Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems , Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001) ( 2001 ) . Google Scholar
K. Sripanidkulchai , B. Maggs and H. Zhang , Efficient content location using interest based locality in peer-to-peer Systems , IEEE INFOCOM 2003 ( 2003 ) . Google Scholar
I. Stoica et al. , Chord: A scalable peer-to-peer lookup service for Internet applications , SIGCOMM'01 ( 2001 ) . Google Scholar
D. Stutzbach and R. Rejaie , Characterizing the two-tier gnutella topology , Proc. of the ACM SIGMETRICS, Poster Session ( 2005 ) . Google Scholar
P. Trunfioet al., Future Generation Computer Systems 23, 864 (2007), DOI: 10.1016/j.future.2006.12.003. Crossref, Web of Science, Google Scholar
D. Tsoumakos and N. Roussopoulos , A Comparison of peer-to-peer search methods , Int. Workshop on the Web and Databases (WebDB 2003) ( 2003 ) . Google Scholar
B. Yang and H. Garcia-Molina , Improving search in peer-to-peer networks , Proc. of the 22nd International Conference on Distributed Computing Systems (ICDCS02) ( 2002 ) . Google Scholar
B. Yang and H. Garcia-Molina, Designing a super-peer network, Proc. Int. Conference on Data Engineering (ICDE 2003) (2003) pp. 49–60. Google Scholar
B. Y. Zhaoet al., IEEE Journal on Selected Areas in Communications 22(1), (2004), DOI: 10.1109/JSAC.2003.818784. Google Scholar