You are here

FAU Collections » FAU Research Repository » FAU Theses and Dissertations

Efficient and Effective Searching m Unstructured FileSharing Peer-to-Peer Networks

Download pdf | Full Screen View

Date Issued:
2006
Summary:
Peer-to-peer (P2P) networking has been receiving increasing attention from the research community recently. How to conduct efficient and effective searching in such networks has been a challenging research topic. This dissertation focuses on unstructured file-sharing peer-to-peer networks. Three novel searching schemes are proposed, implemented, and evaluated. In the first scheme named ISRL (Intelligent Search by Reinforcement Learning), we propose to systematically learn the best route to desired files through reinforcement learning when topology adaptation is impossible or infeasible. To discover the best path to desired files, ISRL not only explores new paths by forwarding queries to randomly chosen neighbors, but also exploits the paths that have been discovered for reducing the cumulative query cost. Three models of ISRL are put forwarded: a basic version for finding one desired file, MP-ISRL (MP stands for Multiple-Path ISRL) for finding at least k files, and C-ISRL (C refers to Clustering) for reducing maintenance overhead through clustering when there are many queries. ISRL outperforms existing searching approaches in unstructured peer-to-peer networks by achieving similar query quality with lower cumulative query cost. The experimental results confirm the performance improvement of ISRL. The second approach, HS-SDBF (Hint-based Searching by Scope Decay Bloom Filter), addresses the issue of effective and efficient hint propagation. We design a new data structure called SDBF (Scope Decay Bloom Filter) to represent and advertise probabilistic hints. Compared to existing proactive schemes, HSSDBF can answer many more queries successfully at a lower amortized cost considering both the query traffic and hint propagation traffic. Both the analytic and the experimental results support the performance improvement of our protocol. The third algorithm, hybrid search, seeks to combine the benefits of both forwarding and non-forwarding searching schemes. In this approach, a querying source directly probes its own extended neighbors and forwards a query to a subset of its extended neighbors and guides these neighbors to probe their own extended neighbors on its behalf. The hybrid search is able to adapt query execution to the popularity of desired files without generating too much state maintenance overhead because of the 1-hop forwarding inherent in the approach. It achieves a higher query efficiency than the forwarding scheme and a better success rate than the non-forwarding approach. To the best of our knowledge, this work is the first attempt to integrate forwarding and non-forwarding schemes. Simulation results demonstrate the effectiveness of the hybrid search.
Title: Efficient and Effective Searching m Unstructured FileSharing Peer-to-Peer Networks.
48 views
19 downloads
Name(s): Li, Xiuqi
Wu, Jie, Thesis advisor
Florida Atlantic University, Degree grantor
College of Engineering and Computer Science
Department of Computer and Electrical Engineering and Computer Science
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Date Created: 2006
Date Issued: 2006
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, Fla.
Physical Form: application/pdf
Extent: 156 p.
Language(s): English
Summary: Peer-to-peer (P2P) networking has been receiving increasing attention from the research community recently. How to conduct efficient and effective searching in such networks has been a challenging research topic. This dissertation focuses on unstructured file-sharing peer-to-peer networks. Three novel searching schemes are proposed, implemented, and evaluated. In the first scheme named ISRL (Intelligent Search by Reinforcement Learning), we propose to systematically learn the best route to desired files through reinforcement learning when topology adaptation is impossible or infeasible. To discover the best path to desired files, ISRL not only explores new paths by forwarding queries to randomly chosen neighbors, but also exploits the paths that have been discovered for reducing the cumulative query cost. Three models of ISRL are put forwarded: a basic version for finding one desired file, MP-ISRL (MP stands for Multiple-Path ISRL) for finding at least k files, and C-ISRL (C refers to Clustering) for reducing maintenance overhead through clustering when there are many queries. ISRL outperforms existing searching approaches in unstructured peer-to-peer networks by achieving similar query quality with lower cumulative query cost. The experimental results confirm the performance improvement of ISRL. The second approach, HS-SDBF (Hint-based Searching by Scope Decay Bloom Filter), addresses the issue of effective and efficient hint propagation. We design a new data structure called SDBF (Scope Decay Bloom Filter) to represent and advertise probabilistic hints. Compared to existing proactive schemes, HSSDBF can answer many more queries successfully at a lower amortized cost considering both the query traffic and hint propagation traffic. Both the analytic and the experimental results support the performance improvement of our protocol. The third algorithm, hybrid search, seeks to combine the benefits of both forwarding and non-forwarding searching schemes. In this approach, a querying source directly probes its own extended neighbors and forwards a query to a subset of its extended neighbors and guides these neighbors to probe their own extended neighbors on its behalf. The hybrid search is able to adapt query execution to the popularity of desired files without generating too much state maintenance overhead because of the 1-hop forwarding inherent in the approach. It achieves a higher query efficiency than the forwarding scheme and a better success rate than the non-forwarding approach. To the best of our knowledge, this work is the first attempt to integrate forwarding and non-forwarding schemes. Simulation results demonstrate the effectiveness of the hybrid search.
Identifier: FA00012572 (IID)
Degree granted: Dissertation (Ph.D.)--Florida Atlantic University, 2006.
Collection: FAU Electronic Theses and Dissertations Collection
Note(s): College of Engineering and Computer Science
Subject(s): Peer-to-peer architecture (Computer networks)
Computer security
Database searching
Internetworking (Telecommunication)
Heterogeneous computing
Held by: Florida Atlantic University Libraries
Sublocation: Digital Library
Persistent Link to This Record: http://purl.flvc.org/fau/fd/FA00012572
Use and Reproduction: Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU
Is Part of Series: Florida Atlantic University Digital Library Collections.