Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks

Details Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks

2006-11-25

arxiv.org/abs/cs/0611128v3

Computer Science

Networking and Internet Architecture

19 pages, 12 figures, submitted to ICDCS 2007 (International Conference on Distributed Computing Systems 2007), one minor corr

Scientific paper

In unstructured peer-to-peer (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 of N nodes can be as efficient as O(ln N), while scale-free (power-law) topologies offer even better search efficiencies like as good as O(lnln N) 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. A key limitation of scale-free topologies is the high load (i.e. high degree) on very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store large number of entries for construction of the overlay topology. So, to achieve fairness and practicality among all peers, 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 investigate construction of scale-free topologies with hard cutoffs (i.e. there are not any major hubs) and effect of these hard cutoffs on the search efficiency. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.

Affiliated with

Also associated with

No associations

Rating

Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-576692