22-03-2012, 04:45 PM
Search Algorithms for Unstructured Peer-to-Peer Networks
10.1.1.89.8828.pdf (Size: 180.3 KB / Downloads: 34)
INTRODUCTION
Peer-to-peer networks are widely used for file sharing
purposes. This type of usage tends to favour resilient, decentralized
architectures over centralized solutions. However
this comes at a penalty in ease of searching. At first, peerto-
peer systems addressed this shortcoming by incorporating
a flooding mechanism for resource discovery. A node in the
peer-to-peer network broadcasts a query message to its neighbours.
The neighbours in turn are responsible for reporting any
matches as well as forwarding the message to its neighbours,
if necessary. This mechanism has been proven effective in
practice for finding items which are prevalent across the
peer-to-peer network, but otherwise ineffective and resource
consuming.
Flooding.
Flooding is one of the simplest search strategies and
yet one of the most commonly used in peer-to-peer networks.
For instance, it is the search method employed by the Gnutella
network. The search proceeds as follows: the origin of the
search sends “discovery” messages to all its neighbours, which
in turn propagate the message to their own neighbours (except
the neighbour from which they have received the message) and
so on.
Flooding as described above is unrestricted in the sense that
there is no constraint on the number of messages generated
by the search request. A simple way to limit the range of
the flooding is to introduce the so-called time-to-live (TTL)
parameter. More superficially, the origin of the search sends
a discovery message to all its neighbours, along with the
parameter TTL. The recipients decrease TTL by one and
if TTL is still positive they propagate the message to their
own neighbourhoods (except the neighbour from which they
have received the message), and so fourth. In this way, it is
guaranteed that the search is restricted within a ball of radius
TTL from the origin of the search.
Simulation of Random Walks.
Random walks have emerged
in the area of peer-to-peer networks as alternatives to flooding.
The idea is that instead of forwarding a request to all the
neighbours, the recipient sends it to a random neighbour. The
appealing property of the random walk method is the small
message complexity, which means the algorithm scales well
with the size of the network. In addition, random walks have
been studied extensively from a theoretical point of view.
Naturally, we are interested in the time (or, equivalently, on
the number of hops) the random walk needs to locate the host
sought. An efficient random walk will have the property that
this time is small.
Local flooding with k independent random walks.
In this paper we propose and study a new hybrid algorithm, as
a compromise between flooding and random walks. The idea
is to first perform a (local) flooding starting from the origin
of the search; the flooding continues until exactly k new outer
nodes have been discovered, for some predefined value of k.
In the case where one of these nodes has the file, the search
is successful and the origin is notified. Otherwise, each of the
k nodes initiates an independent random walk.