HASH-BASED OVERLAY PARTITIONING IN UNSTRUCTURED PEER-TO-PEER SYSTEMS
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).
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
- Communications of the ACM 13(7), 422 (1970), DOI: 10.1145/362686.362692. Crossref, ISI, Google Scholar
Y. Chawathe , 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 , Search and replication in unstructured peer-to-peer networks , Int. Conf. on Supercomputing (SC 2002) ( 2002 ) . Google Scholar -
C. Papadakis , A feedback-based approach to reduce duplicate messages in unstructured peer-to-peer networks , Proc. of the CoreGRID Integration Workshop ( 2005 ) . Google Scholar A. Ratnasamy , 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 , 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 - Future Generation Computer Systems 23, 864 (2007), DOI: 10.1016/j.future.2006.12.003. Crossref, ISI, 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- IEEE Journal on Selected Areas in Communications 22(1), (2004), DOI: 10.1109/JSAC.2003.818784. Google Scholar


