Unstructured p2p systems
From P2P Wiki
Contents |
Introduction
An unstructured P2P network is formed when the overlay links are established arbitrarily. Such networks can be easily constructed as a new peer that wants to join the network can copy existing links of another node and then form its own links over time. In an unstructured P2P network, if a peer wants to find a desired piece of data in the network, the query has to be flooded through the network to find as many peers as possible that share the data. The main disadvantage with such networks is that the queries may not always be resolved. Popular content is likely to be available at several peers and any peer searching for it is likely to find the same thing, but if a peer is looking for rare data shared by only a few other peers, then it is highly unlikely that search will be successful. Since there is no correlation between a peer and the content managed by it, there is no guarantee that flooding will find a peer that has the desired data. Flooding also causes a high amount of signalling traffic in the network and hence such networks typically have very poor search efficiency. Most of the popular P2P networks such as Gnutella and FastTrack are unstructured.
Resource Allocation
In these systems, peers have the same capability and responsibility. Communication between peers is symmetric: there is no central directory index server where the files metadata is stored. This metadata is stored locally among all peers. Examples of such systems include Gnutella, Freenet , or MojoNation. A wide variety of techniques for resource location were spawn in this period in time. Some of the most popular are:
- Flooding: The query is sent to the node‘s neighbours, and spread from neighbour to neighbour through a maximum number of hops. This technique is explained in greater detail below.
- Epidemic algorithms: Epidemic algorithms follow the paradigm of nature by applying simple rules to spread information by just having a local view of the environment. These algorithms are easy to implement and guarantee message propagation in heterogeneous environments that are not always coherent.
Each epidemic algorithm contains a population consisting of a set of interactive, communicating units. These units use a ruleset that defines how to spread specific information that might be of interest to other units. This ruleset is considerably affected by the design of the algorithm and can be freely chosen. The only requirement is that at a specific time t a unit must have one of the following states regarding specific information:
- Susceptible: the unit does not know anything about the specific information but it can get it.
- Infective: the unit knows the specific information and uses the ruleset to spread it.
- Removed (Recovered): the unit knows the specific information but does not spread it.
- Random Walk: Random walk is a well-known technique which forwards a query message to a randomly chosen neighbor at each step until the object is found. This message is called a walker. When standard random walk is used (with one walker), it reduces message overhead significantly, by an order of magnitude compared to flooding across the network topologies.
However, this efficiency increases user-perceived delay in successful searches by an order of magnitude. To decrease the delay, the number of walkers is increased. That is, instead of just sending out one query message, a requesting node sends k query messages, and each query message takes its own random walk. The expectation is that k walkers after T steps should reach roughly the same number of nodes as one walker after kT steps.
See also
Papers
Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, "Search and Replication in Unstructured Peer-to-Peer Networks," in International Conference on Supercomputing. New York, USA: ACM Press, 2002, pp. 84-95.
