|
Unstructurd Peer-to-Peer Networks
Summary: Peer-to-peer networks (P2P) are the most recent replacement for the traditional client-server architectures in many applications from file sharing to database and from messaging to media streaming. In unstructured P2P networks, the overlay topology (or connectivity graph) among peers is a crucial component in addition to the peer/data organization and search. Topological characteristics have profound impact on the efficiency of search on such unstructured P2P networks as well as other networks. It has been well-known that search on small-world
topologies can be as efficient as O(lnN), while scale-free (power-law) topologies offer even better search efficiencies like O(ln lnN) for a range of degree distribution exponents. However, generation and maintenance of such scale-free topologies are hard to realize in a distributed and potentially uncooperative environments as in the P2P networks. Another key limitation of scale-free topologies is the high load (i.e. high degree) on very few number of hub nodes. To achieve fairness and practicality among all peers, peers do not accept to maintain high degrees/loads as they may not want to store large number of entries for construction of the overlay topology. So, in a typical unstructured P2P network, hard cutoffs on the number of entries are imposed by the individual peers, which limits scale-freeness of the overall topology. Thus, efficiency of the flooding search reduces as the size of the hard cutoff does. We investigated construction of scale-free topologies with hard cutoffs (i.e. there are not any major hubs) and the effect of these hard cutoffs on the search efficiency. We observed that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases. As an extension to these
models we are currently working on different join/leave scenarios relevant to peer-to-peer networks.
Publications:
|
