P2P Searching Algorithms
Gnutella:: BFS
· A node sends query to all its neighbors and each neighbor searches itself and forwards the message to all its own neighbors
· If (once) query is satisfied, response sent back to the original requester
· Can cause a lot of traffic
· Query Flooding
· Each file has a unique ID and location
· Information stored on peer host under searchable keys
· Depth-first search—each node forwards the query to a single neighbor
· If query not satisfied, forwards query to another neighbor
· Central server has info about users and files
· Node sends query to a subset of its neighbors and waits either for a minimum number of results or for a maximum amount of time
· Node keeps info on its neighbors from past queries for better searching in the future
· Node also keeps info on the speed and connection time of its neighbor
o Can know which neighbor has highest/lowest number of results
o Neighbors that forwards many/few messages
· Each node maintains index of data of all nodes w/in a certain amount of distance from itself….a “radius”
· When receives a query, a node can process it on behalf of itself or for every node within its radius….fewer nodes to be searched
· Data structure that allows node to select “best” neighbors to send query to
· Ranks neighbors in order of their abilities to handle a query
o “Ability” can mean number of documents it has or number of documents in nearby nodes
o Or return rate
· Each node keeps local index of its own documents for efficient seaching
· Find data using log(N) messages
· Distributed Hash Table (Dhash)
· Giventhe ID of a piece of data, returns the ID of the node whose identifier most closely follows the data’s ID in a circular identifier space
· Given a key, maps the key onto a node
Waterhouse, Steve. JXTA Search: Distributed Search for Distributed Networks. http://search.jxta.org/JXTAsearch.pdf
Li, Jun. Peer-To-Peer
Networks
Ambastha, Beak, et al.
A Cache-Based Resource Location Approach for Unstructured P2P Network
Architectures